高斯-勒让德算法

高斯-勒让德算法是一种用于计算π的算法。它的收敛速度是显著的，只需25次迭代即可产生π的4500万位正确数字。不过，内存密集是它的缺点，因此有时它不如梅钦类公式使用广泛。

该方法基于德國數學家卡尔·弗里德里希·高斯（Johann Karl Friedrich Gauß，1777–1855）和法國數學家阿德里安-马里·勒让德（Adrien-Marie Legendre，1752–1833）的个人成果与乘法和平方根运算的现代算法的结合。该算法反复替换两个数值的算术平均数和几何平均数，以接近它们的算术-几何平均数。

下文的版本也被称为布伦特-萨拉明（或萨拉明-布伦特）算法；它于1975年被理查德·布伦特和尤金·萨拉明独立发现。日本筑波大学于2009年8月17日宣布利用此算法计算出π小数点后2,576,980,370,000位数字，计算结果用波温算法检验。知名的電腦效能測試程式Super PI也使用此演算法。

算法

1. 设置初始值：

$a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1\!$

2. 反复执行以下步骤直到$a_n\!$与$b_n\!$之间的误差到达所需精度：

$\begin{align} a_{n+1} & = \frac{a_n + b_n}{2}, \\ b_{n+1} & = \sqrt{a_n b_n}, \\ t_{n+1} & = t_n - p_n(a_n - a_{n+1})^2, \\ p_{n+1} & = 2p_n. \end{align}$

3. 则π的近似值为：

$\pi \approx \frac{(a_n+b_n)^2}{4t_n}.\!$

下面给出前三个迭代结果：

$3.140\dots\!$

$3.14159264\dots\!$

$3.14159265358979\dots\!$

该算法具有二阶收敛性，本质上说就是算法每执行一步正确位数就会加倍。

数学背景

算术-几何平均数的极限

a₀和b₀两个数值的算术-几何平均数，是通过计算它们的序列极限得到的：

$\begin{align} a_{n+1} & = \frac{a_n+b_n}{2}, \\ b_{n+1} & = \sqrt{a_n b_n}, \end{align}$

两者汇聚于同一限额。若$a_0=1\!$且$b_0=\cos\varphi\!$则限额为${\pi \over 2K(\sin\varphi)}\!$且$K(k)\!$为第一类完全椭圆积分：

$K(k) = \int_0^{\pi/2} \frac{d\theta}{\sqrt{1-k^2 \sin^2\theta}}.\!$

若$c_0 = \sin\varphi\!$，$c_{i+1} = a_i - a_{i+1}\!$，则

$\sum_{i=0}^\infty 2^{i-1} c_i^2 = 1 - {E(\sin\varphi)\over K(\sin\varphi)}\!$

且$E(k)\!$为第二类完全椭圆积分：

$E(k) = \int_0^{\pi/2}\sqrt {1-k^2 \sin^2\theta}\, d\theta.\!$

高斯知道以上这些结果。

勒让德恒等式

对于满足$\varphi+\theta={1 \over 2}\pi\!$的$\varphi\!$与$\theta\!$，勒让德证明了以下恒等式：

$K(\sin \varphi) E(\sin \theta ) + K(\sin \theta ) E(\sin \varphi) - K(\sin \varphi) K(\sin \theta) = {1 \over 2}\pi\!$

高斯-勒让德方法

$\varphi=\theta={\pi\over 4}\!$的值可以代入到勒让德恒等式，且K，E的近似值可通过$a_0=1\!$与$b_0=\sin{\pi \over 4}=\frac{1}{\sqrt{2}}\!$的算术-几何平均数的序列项得到。