高斯-勒让德算法

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

下文的版本也被称为布伦特-萨拉明(或萨拉明-布伦特)算法;它于1975年被理查德·布伦特尤金·萨拉明独立发现。日本筑波大学于2009年8月17日宣布利用此算法计算出π小数点后2,576,980,370,000位数字,计算结果用波温算法检验。[1]知名的电脑性能测试程序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\!

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

数学背景[编辑]

算术-几何平均数的极限[编辑]

a0和b0两个数值的算术-几何平均数,是通过计算它们的序列极限得到的:

\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.\!

高斯知道以上这些结果。[2] [3] [4]

勒让德恒等式[编辑]

对于满足\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\![2]

高斯-勒让德方法[编辑]

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

参考文献[编辑]

  1. ^ 円周率計算桁数世界記録樹立について
  2. ^ 2.0 2.1 2.2 Brent, RichardTraub, 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] 
  3. ^ Salamin, Eugene. Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January, 1974, Cambridge, Massachusetts
  4. ^ Salamin, Eugene, Computation of pi Using Arithmetic-Geometric Mean, Mathematics of Computation. 1976, 30 (135): 565–570, ISSN 0025--5718