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
- Valor inicial:
- Repita las siguientes instrucciones hasta la diferencia y está dentro de la precisión deseada:
- π es entonces aproximado como:
Las primeras tres iteraciones dan (aproximaciones dadas hasta el primer dígito incorrecto incluido):
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, a0 y b0, se encuentra calculando el límite de las sucesiones
que ambos convergen al mismo límite.
Si y entonces el límite es Donde es la integral elíptica completa del primer tipo
Si , , entonces
Donde es la integral elíptica completa del segundo tipo:
- y
Gauss conocía estos dos resultados.
Identidad de Legendre
Legendre demostró la siguiente identidad:
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í.
Contenido relacionado
André-Marie Ampère
Magma (álgebra)
Teorema de inversión de Lagrange