Gauss–Legendre algorithm: Difference between revisions

Revision as of 16:10, 7 July 2019

Revision as of 16:26, 7 July 2019

Line 7:

== Algorithm ==

1. Initial value setting:

:<math>a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1.\!</math>

2. Repeat the following instructions until the difference of <math>a_n\!</math> and <math>b_n\!</math> is within the desired accuracy:

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

b_{n+1} & = \sqrt{a_n b_n}, \\

Line 16:

</math>

3. {{pi}} is then approximated as:

:<math>\pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.\!</math>

The first three iterations give (approximations given up to and including the first incorrect digit):

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

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

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

The algorithm has [[quadratic convergence]], which essentially means that the number of correct digits doubles with each [[iteration]] of the algorithm.

Line 38:

which both converge to the same limit.<br />

If <math>a_0=1\!</math> and <math>b_0=\cos\varphi\!</math> then the limit is <math display="inline">{\pi \over 2K(\sin\varphi)}\!</math> where <math>K(k)\!</math> is the [[Elliptic integral#Complete elliptic integral of the first kind|complete elliptic integral of the first kind]]

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

If <math>c_0 = \sin\varphi\!</math>, <math>c_{i+1} = a_i - a_{i+1}\!</math>, then

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

where <math>E(k)\!</math> is the [[Elliptic integral#Complete elliptic integral of the second kind|complete elliptic integral of the second kind]]:

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

Gauss knew of both of these results.<ref name="brent">{{Citation

Line 100:

=== Legendre’s identity ===

For <math>\varphi\!</math> and <math>\theta\!</math> such that <math display="inline">\varphi+\theta={1 \over 2}\pi\!</math> Legendre proved the identity:

:<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" />

=== Gauss–Euler method ===

The values <math display="inline">\varphi=\theta={\pi\over 4}\!</math> can be substituted into Legendre’s identity and the approximations to K, E can be found by terms in the sequences for the arithmetic geometric mean with <math>a_0=1\!</math> and <math display="inline">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>

== See also ==