高斯-勒让德算法

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

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

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

知名的电脑性能测试程序Super PI也使用此算法。

算法

1. 设置初始值：
   $a_0=1b_0=\frac{1}{\sqrt{2}}{t}_0=\frac{1}{4}{p}_0=1.$
2. 反复执行以下步骤直到$a_n$与$b_n$之间的误差到达所需精度：
   $\begin{array}{cc}{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{array}$
3. 则π的近似值为：
   $\pi \approx \frac{(a_{n+1}+b_{n+1}{)}^2}{4t_{n+1}}.$

下面给出前三个迭代结果（近似值精确到第一个错误的位数）：

$3.140\dots$

$3.14159264\dots$

$3.1415926535897932382\dots$

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

数学背景

算术-几何平均数的极限

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

$\begin{array}{cc}{a}_{n+1}& =\frac{a_n+b_n}{2},\\ b_{n+1}& =\sqrt{a_n{b}_n},\end{array}$

两者汇聚于同一极限。
若$a_0=1$且$b_0=\cos \phi$，则极限为$\frac{\pi }{2K(\sin \phi )}$，其中$K(k)$为第一类完全椭圆积分：

$K(k)=\underset{0}{\overset{\frac{\pi }{2}}{\int }}\frac{d\theta }{\sqrt{1-k^2{\sin }^2\theta }}.$

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

$\sum _{i=0}^{\mathrm{\infty }}{2}^{i-1}{c}_i^2=1-\frac{E(\sin \phi )}{K(\sin \phi )}$

其中$E(k)$为第二类完全椭圆积分：

$E(k)=\underset{0}{\overset{\frac{\pi }{2}}{\int }}\sqrt{1-k^2{\sin }^2\theta }d\theta .$

高斯知道以上这两个结果。

勒让德恒等式

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

$K(\sin \phi )E(\sin \theta )+K(\sin \theta )E(\sin \phi )-K(\sin \phi )K(\sin \theta )=\frac{1}{2}\pi .$

高斯-欧拉法

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