Algoritmo de Gauss-Legendre

Cálculo rápidamente convergente de π

El algoritmo de Gauss-Legendre es un algoritmo para calcular los dígitos de π . Se destaca por ser rápidamente convergente, con sólo 25 iteraciones produciendo 45 millones de dígitos correctos de  π . Sin embargo, tiene algunos inconvenientes (por ejemplo, consume mucha memoria del ordenador ) y, por eso, durante muchos años, todos los cálculos récord han utilizado otros métodos, casi siempre el algoritmo de Chudnovsky . Para más detalles, consulte Cronología del cálculo de π .

El método se basa en el trabajo individual de Carl Friedrich Gauss (1777–1855) y Adrien-Marie Legendre (1752–1833) combinado con algoritmos modernos de multiplicación y raíces cuadradas . Reemplaza repetidamente dos números por su media aritmética y geométrica , con el fin de aproximar su media aritmético-geométrica .

La versión que se presenta a continuación también se conoce como algoritmo de Gauss-Euler , Brent-Salamin (o Salamin-Brent ) ; ^[1] fue descubierto de forma independiente en 1975 por Richard Brent y Eugene Salamin . Se utilizó para calcular los primeros 206.158.430.000 dígitos decimales de π del 18 al 20 de septiembre de 1999, y los resultados se comprobaron con el algoritmo de Borwein .

Algoritmo

1. Configuración del valor inicial:
   $${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.}$$
2. Repita las siguientes instrucciones hasta que la diferencia de y esté dentro de la precisión deseada: ${\displaystyle a_{n}}$ ${\displaystyle b_{n}}$
   $${\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}}}$$
3. Entonces π se aproxima como:
   $${\displaystyle \pi \approx {\frac {(a_{n+1}+b_{n+1})^{2}}{4t_{n+1}}}.}$$

Las primeras tres iteraciones dan (aproximaciones dadas hasta el primer dígito incorrecto inclusive):

${\displaystyle 3.140\dots }$

${\displaystyle 3.14159264\dots }$

${\displaystyle 3.1415926535897932382\dots }$

El algoritmo tiene convergencia cuadrática , lo que esencialmente significa que el número de dígitos correctos se duplica con cada iteración del algoritmo.

Antecedentes matemáticos

Límites de la media aritmético-geométrica

La media aritmético-geométrica de dos números, a ₀ y b ₀ , se encuentra calculando el límite de las secuencias.

${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\[6pt]b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}}}$

los cuales ambos convergen al mismo límite.
Si y entonces el límite es ¿dónde está la integral elíptica completa de primer tipo? ${\displaystyle a_{0}=1}$ ${\displaystyle b_{0}=\cos \varphi }$ ${\textstyle {\pi \over 2K(\sin \varphi )}}$ ${\displaystyle K(k)}$

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

Si , entonces ${\displaystyle c_{0}=\sin \varphi }$ ${\displaystyle c_{i+1}=a_{i}-a_{i+1}}$

${\displaystyle \sum _{i=0}^{\infty }2^{i-1}c_{i}^{2}=1-{E(\sin \varphi ) \over K(\sin \varphi )}}$

¿ Dónde está la integral elíptica completa de segundo tipo ? ${\displaystyle E(k)}$

${\displaystyle E(k)=\int _{0}^{\pi /2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\;d\theta }$

y

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

Gauss conocía estos dos resultados. ^{[2] [3] [4]}

La identidad de Legendre.

Legendre demostró la siguiente identidad:

${\displaystyle K(\cos \theta )E(\sin \theta )+K(\sin \theta )E(\cos \theta )-K(\cos \theta )K(\sin \theta )={\pi \over 2},{\text{ for all }}\theta .}$^[2]

Prueba elemental con cálculo integral.

Se puede demostrar que el algoritmo de Gauss-Legendre da resultados que convergen a π utilizando únicamente cálculo integral. Esto se hace aquí ^[5] y aquí. ^[6]

Ver también

• Aproximaciones numéricas de π

Referencias

1. Brent, Richard , Algoritmos antiguos y nuevos para pi , Cartas al editor, Avisos de AMS 60(1), p. 7
2. Brent, Richard (1975), Traub, JF (ed.), "Métodos de búsqueda de ceros de precisión múltiple y la complejidad de la evaluación de funciones elementales", Analytic Computational Complexity , Nueva York: Academic Press, págs. Archivado desde el original el 23 de julio de 2008 , consultado el 8 de septiembre de 2007.
3. Salamin, Eugene , Cálculo de pi , memorando 74-19 de la ISS del laboratorio Charles Stark Draper, 30 de enero de 1974, Cambridge, Massachusetts
4. Salamin, Eugene (1976), "Cálculo de pi utilizando la media aritmética-geométrica", Matemáticas de la Computación , vol. 30, núm. 135, págs. 565–570, doi :10.2307/2005327, ISSN  0025-5718, JSTOR  2005327
5. Lord, Nick (1992), "Cálculos recientes de π: el algoritmo de Gauss-Salamin", The Mathematical Gazette , 76 (476): 231–242, doi :10.2307/3619132, JSTOR  3619132, S2CID  125865215
6. Milla, Lorenz (2019), Prueba sencilla de tres algoritmos π recursivos , arXiv : 1907.04110