查看“︁高斯-勒让德算法”︁的源代码

{{NoteTA
|G1=IT
}}

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

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

下文的版本也被称为'''高斯-欧拉，布伦特-萨拉明（或萨拉明-布伦特）算法'''<ref>[[理查德·布伦特|Brent, Richard]], ''Old and New Algorithms for pi'', Letters to the Editor, Notices of the AMS 60(1), p. 7</ref>；它于1975年被[[理查德·布伦特]]和[[尤金·萨拉明]]独立发现。日本筑波大学于2009年8月17日宣布利用此算法计算出&pi;小数点后2,576,980,370,000位数字，计算结果用[[波温算法]]检验。<ref name="tsukuba">[{{Cite web |url=http://www.tsukuba.ac.jp/public/press/090817.pdf |script-title=ja:円周率計算桁数世界記録樹立について |access-date=2009-11-29 |archive-date=2020-09-25 |archive-url=https://web.archive.org/web/20200925075505/http://www.tsukuba.ac.jp/public/press/090817.pdf |dead-url=no }} {{lang|ja|円周率計算桁数世界記録樹立について}}]</ref>

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

== 算法 ==
# 设置初始值：<br /><math>a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1.\!</math>
# 反复执行以下步骤直到<math>a_n\!</math>与<math>b_n\!</math>之间的误差到达所需精度：<br /><math> \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}
</math>
# 则&pi;的近似值为：<br /><math>\pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.\!</math>

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

:<math>3.140\dots\!</math>
:<math>3.14159264\dots\!</math>
:<math>3.1415926535897932382\dots\!</math>

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

== 数学背景 ==

=== 算术-几何平均数的极限 ===

a<sub>0</sub>和b<sub>0</sub>两个数的[[算术-几何平均数]]，是通过计算它们的序列极限得到的：

:<math>\begin{align} a_{n+1} & = \frac{a_n+b_n}{2}, \\
                     b_{n+1} & = \sqrt{a_n b_n},
       \end{align}
</math>

两者汇聚于同一极限。<br />
若<math>a_0=1\!</math>且<math>b_0=\cos\varphi\!</math>，则极限为<math>{\pi \over 2K(\sin\varphi)}\!</math>，其中<math>K(k)\!</math>为[[椭圆积分#第一类完全椭圆积分|第一类完全椭圆积分]]：

:<math>K(k) = \int_0^{\pi \over 2} \frac{d\theta}{\sqrt{1-k^2 \sin^2\theta}}.\!</math>

若<math>c_0 = \sin\varphi\!</math>，<math>c_{i+1} = a_i - a_{i+1}\!</math>，则

:<math>\sum_{i=0}^\infty 2^{i-1} c_i^2 = 1 - {E(\sin\varphi)\over K(\sin\varphi)}\!</math>

其中<math>E(k)\!</math>为[[椭圆积分#第二类完全椭圆积分|第二类完全椭圆积分]]：

:<math>E(k) = \int_0^{\pi \over 2}\sqrt {1-k^2 \sin^2\theta}\, d\theta.\!</math>

高斯知道以上这两个结果。<ref name="brent">{{Citation
 | last=Brent
 | first=Richard
 | author-link=理查德·布伦特
 | publication-date=
 | date=
 | year=1975
 | title=Multiple-precision zero-finding methods and the complexity of elementary function evaluation
 | periodical=Analytic Computational Complexity
 | series=
 | publication-place=New York
 | place=
 | publisher=Academic Press
 | editor-last=Traub
 | editor-first=J F
 | volume=
 | issue=
 | pages=151–176
 | url=http://wwwmaths.anu.edu.au/~brent/pub/pub028.html
 | issn=
 | doi=
 | oclc=
 | accessdate=8 September 2007
 | archive-date=2008-07-23
 | archive-url=https://web.archive.org/web/20080723170157/http://wwwmaths.anu.edu.au/~brent/pub/pub028.html
 | dead-url=no
 }}</ref>
<ref name="salamin1">[[尤金·萨拉明|Salamin, Eugene]], ''Computation of pi'', Charles Stark Draper Laboratory ISS memo 74–19, 30 January, 1974, Cambridge, Massachusetts</ref>
<ref name="salamin2">{{Citation
 | last=Salamin
 | first=Eugene
 | author-link=尤金·萨拉明
 | publication-date=
 | date=1976
 | year=1976
 | title=Computation of pi Using Arithmetic-Geometric Mean
 | periodical=Mathematics of Computation
 | series=
 | publication-place=
 | place=
 | publisher=
 | editor-last=
 | editor-first=
 | volume=30
 | issue=135
 | pages=565–570
 | url=
 | issn=0025--5718
 | doi=
 | oclc=
 | accessdate=
}}</ref>

=== 勒让德恒等式 ===
对于满足<math>\varphi+\theta={1 \over 2}\pi\!</math>的<math>\varphi\!</math>与<math>\theta\!</math>，勒让德证明了以下恒等式：
:<math>K(\sin \varphi) E(\sin \theta ) + K(\sin \theta ) E(\sin \varphi) - K(\sin \varphi) K(\sin \theta) = {1 \over 2}\pi\!.</math><ref name="brent" />

=== 高斯-欧拉法 ===

<math>\varphi=\theta={\pi\over 4}\!</math>的值可以代入勒让德恒等式，且K、E的近似值可通过<math>a_0=1\!</math>与<math>b_0=\sin{\pi \over 4}=\frac{1}{\sqrt{2}}\!</math>的算术-几何平均数的序列项得到。<ref>Adlaj, Semjon, ''An eloquent formula for the perimeter of an ellipse'', Notices of the AMS 59(8), p. 1096</ref>

== 参考文献 ==
{{reflist}}

{{DEFAULTSORT:高斯-勒让德算法}}
[[Category:圆周率算法]]