高斯-勒讓德算法是一種用於計算圓周率(π)的算法。它以迅速收斂著稱,只需25次迭代即可產生π的4500萬位正確數字。不過,它的缺點是內存密集,因此有時它不如梅欽類公式使用廣泛。
該方法基於德國數學家卡爾·弗里德里希·高斯(Johann Carl Friedrich Gauß,1777–1855)和法國數學家阿德里安-馬里·勒讓德(Adrien-Marie Legendre,1752–1833)的個人成果與乘法和平方根運算之現代算法的結合。該算法反覆替換兩個數值的算術平均數和幾何平均數,以接近它們的算術-幾何平均數。
下文的版本也被稱為高斯-歐拉,布倫特-薩拉明(或薩拉明-布倫特)算法[1];它於1975年被理查德·布倫特和尤金·薩拉明獨立發現。日本筑波大學於2009年8月17日宣布利用此算法計算出π小數點後2,576,980,370,000位數字,計算結果用波溫算法檢驗。[2]
知名的電腦性能測試程序Super PI也使用此算法。
- 設置初始值:
![{\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07cb5ca2a99df7d66078e7f2d626b9fd6e0ec839)
- 反覆執行以下步驟直到
與
之間的誤差到達所需精度:
![{\displaystyle {\begin{aligned}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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/000357c43f0f911092d9e5129dcc45227565bcf8)
- 則π的近似值為:
![{\displaystyle \pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70561e8aed278793d403e309309151199a765fd1)
下面給出前三個迭代結果(近似值精確到第一個錯誤的位數):
![{\displaystyle 3.140\dots \!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b2de5f6e3ff588af17155907f319e7c1442d008)
![{\displaystyle 3.14159264\dots \!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acf48428eaa67cf115b5954849eb5a0de03c219d)
![{\displaystyle 3.1415926535897932382\dots \!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78c347926fda7646e636b70900c2b929cfe67a34)
該算法具有二階收斂性,本質上說就是算法每執行一步正確位數就會加倍。
a0和b0兩個數的算術-幾何平均數,是通過計算它們的序列極限得到的:
![{\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c09684973d8142acb22390df16107926224ca7e6)
兩者匯聚於同一極限。
若
且
,則極限為
,其中
為第一類完全橢圓積分:
![{\displaystyle K(k)=\int _{0}^{\pi \over 2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3efbbfaf70a5241fdd95a2a3510a8c0b72aceac7)
若
,
,則
![{\displaystyle \sum _{i=0}^{\infty }2^{i-1}c_{i}^{2}=1-{E(\sin \varphi ) \over K(\sin \varphi )}\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99e43c6f58b5b486f7928726ed13dc90d379435f)
其中
為第二類完全橢圓積分:
![{\displaystyle E(k)=\int _{0}^{\pi \over 2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\,d\theta .\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0614cb1bae5e84dd22431254cee72985dc4ad187)
高斯知道以上這兩個結果。[3]
[4]
[5]
對於滿足
的
與
,勒讓德證明了以下恆等式:
[3]
的值可以代入勒讓德恆等式,且K、E的近似值可通過
與
的算術-幾何平均數的序列項得到。[6]
- ^ Brent, Richard, Old and New Algorithms for pi, Letters to the Editor, Notices of the AMS 60(1), p. 7
- ^ [円周率計算桁数世界記録樹立について (PDF). [2009-11-29]. (原始內容存檔 (PDF)於2020-09-25). 円周率計算桁数世界記録樹立について]
- ^ 3.0 3.1 Brent, Richard, Traub, J F , 編, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic Computational Complexity (New York: Academic Press), 1975: 151–176 [8 September 2007], (原始內容存檔於2008-07-23)
- ^ Salamin, Eugene, Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January, 1974, Cambridge, Massachusetts
- ^ Salamin, Eugene, Computation of pi Using Arithmetic-Geometric Mean, Mathematics of Computation 30 (135), 1976, 30 (135): 565–570, ISSN 0025-5718
- ^ Adlaj, Semjon, An eloquent formula for the perimeter of an ellipse, Notices of the AMS 59(8), p. 1096