Algoritmo de Gauss-Legendre

El algoritmo Gauss-Legendre es un algoritmo para calcular los dígitos de π. Se destaca por ser rápidamente convergente, con solo 25 iteraciones que producen 45 millones de dígitos correctos de π. Sin embargo, tiene algunos inconvenientes (por ejemplo, consume mucha memoria de la computadora) y, por lo tanto, todos los cálculos récord durante muchos años han utilizado otros métodos, casi siempre el algoritmo Chudnovsky. Para obtener más información, 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 para multiplicación y raíces cuadradas. Reemplaza repetidamente dos números por su media aritmética y geométrica, para aproximar su media aritmético-geométrica.

La versión que se presenta a continuación también se conoce como algoritmo Gauss–Euler, Brent–Salamin (o Salamin–Brent) ; 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 verificaron con Borwein& #39;s algoritmo.

Algoritmo

1. Valor inicial:
   $${displaystyle a_{0}=1qquad {fnMicroc}}qquad {fnK}fnK} P_{0}=1.$$

   
2. Repita las siguientes instrucciones hasta la diferencia ${displaystyle a_{n}$ y ${displaystyle B_{n}$ está dentro de la precisión deseada:
   $${displaystyle {begin{aligned}a_{n+1} {a_{n}+b_{n} {2}}\\b_{n+1} {sqrt={sqrt} {a_{n}b_{n}}},\\\t_{n+1} {=t_{n}(a_{n}-a_{n+1})} {2},\\\\p_{n+1} {n}}}}\\\\\\cH00}}}}}\\\\\\\\\\\\\\\\\\\p_\\\\\cH00\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\cH00cH00cH00cH00cH00cH00cH00cH00cH00$$

   
3. π es entonces aproximado como:
   $${displaystyle pi approx {frac {(a_{n+1}+b_{n+1}}{2}}{4t_{n+1}}}} {fn+1}} {fn0}} {fn0}}} {fn0}}}}}$$

   

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

${displaystyle 3.140dots}$

${displaystyle 3.14159264dots}$

${displaystyle 3.1415926535897932382}$

El algoritmo tiene convergencia cuadrática, lo que esencialmente significa que la cantidad 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ética-geométrica de dos números, a₀ y b₀, se encuentra calculando el límite de las sucesiones

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

que ambos convergen al mismo límite.
Si ${displaystyle A_{0}=1}$ y ${displaystyle b_{0}=cos varphi }$ entonces el límite es ${textstyle {pi over 2K(sin varphi)}$ Donde ${displaystyle K(k)}$ es la integral elíptica completa del primer tipo

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

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

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

Donde ${displaystyle E(k)}$ es la integral elíptica completa del segundo tipo:

${displaystyle E(k)=int ¿Qué? {1-k^{2}Theta};dtheta$ y ${displaystyle K(k)=int _{0}{pi /2}{frac {dtheta ♫{sqrt {1-k^{2}sin ^{2}theta }}}$

Gauss conocía estos dos resultados.

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.}}$

Prueba elemental con cálculo integral

Se puede probar que el algoritmo de Gauss-Legendre da resultados que convergen a π usando solo cálculo integral. Esto se hace aquí y aquí.