algoritmo de Gauss-Legendre - Gauss–Legendre algorithm

O algoritmo de Gauss-Legendre é um algoritmo para calcular os dígitos de π . É notável por ser rapidamente convergente, com apenas 25 iterações produzindo 45 milhões de dígitos correcção de π. No entanto, a desvantagem é que é a memória do computador -intensive e, portanto, às vezes fórmulas Machin-como são usadas.

O método baseia-se no trabalho individual de Carl Friedrich Gauss (1777-1855) e Adrien-Marie Legendre (1752-1833) combinado com algoritmos modernos para a multiplicação e raízes quadradas . Ele substitui repetidamente dois números por sua aritmética e média geométrica , de forma a aproximar a sua média aritmética-geométrica .

A versão apresentada abaixo também é conhecido como o Gauss-Euler, Brent algoritmo-Salamin (ou Salamin-Brent) ; descobriu-se, independentemente, em 1975, por Richard Brent e Eugene Salamin . Ele foi usado para calcular os 206,158,430,000 primeiros dígitos decimais de π em 18 de Setembro a 20 de 1999, e os resultados foram verificados com o algoritmo de Borwein .

Algoritmo

Definição inicial valor:
${\ Displaystyle a_ {0} = 1 \ qquad b_ {0} = {\ frac {1} {\ sqrt {2}}} \ qquad t_ {0} = {\ frac {1} {4}} \ qquad p_ {0} = 1. \!}$
Repita as seguintes instruções até que a diferença de e está dentro da precisão desejada: ${\ Displaystyle a_ {n} \!}$ ${\ Displaystyle b_ {n} \!}$
${\ Displaystyle {\ {começar alinhados} 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}. \ final {alinhados}}}$
π é então aproximado como:
${\ Displaystyle \ pi \ aprox {\ frac {(a_ {n + 1} + b_ {n + 1}) ^ {2}} {4t_ {n + 1}}}. \!}$

Os primeiros três iterações dar (aproximações dadas até e incluindo o primeiro dígito incorrecto):

{\ Displaystyle 3.140 \ dots \!}

{\ Displaystyle 3.14159264 \ dots \!}

{\ Displaystyle 3,1415926535897932382 \ dots \!}

O algoritmo tem convergência quadrática , o que essencialmente significa que o número de dígitos corretos dobra a cada iteração do algoritmo.

fundo matemático

Limites da média aritmética-geométrica

A média aritmética-geométrica de dois números, um ₀ e b ₀ , encontra-se através do cálculo do limite das sequências

{\ Displaystyle {\ {começar alinhados} a_ {n + 1} = {& \ frac {a_ {n} + b_ {n}} {2}}, \\ b_ {n + 1} = {& \ sqrt { a_ {n} b_ {n}}}, \ final {alinhados}}}

que tanto convergem para o mesmo limite.
Se e , em seguida, o limite é onde é a integral elíptica completa de primeira espécie ${\ Displaystyle a_ {0} = 1 \!}$ ${\ Displaystyle b_ {0} = \ cos \ varphi \!}$ ${\ Displaystyle {\ pi \ over 2K (\ sin \ varphi)} \!}$ ${\ Displaystyle K (k) \!}$

{\ Displaystyle K (k) = \ int _ {0} ^ {\ pi / 2} {\ frac {d \ teta} {\ sqrt {1-k ^ {2} \ sin ^ {2} \ teta}} }. \!}

Se , . então ${\ Displaystyle c_ {0} = \ sin \ varphi \!}$ ${\ Displaystyle c_ {i + 1} = a_ {i} -a_ {i + 1} \!}$

{\ Displaystyle \ soma _ {i = 0} ^ {\ infty} 2 ^ {i-1} C_ {i} ^ {2} = {1- E (\ sin \ varphi) \ sobre K (\ sin \ varphi )} \!}

onde é o integral elíptica completa do segundo tipo : ${\ Displaystyle E (k) \!}$

{\ Displaystyle E (k) = \ int _ {0} ^ {\ pi / 2} {\ sqrt {1-k ^ {2} \ sin ^ {2} \ teta}} \, d \ teta. \! }

Gauss conhecia ambos os resultados.

A identidade de Legendre

Por e tal que Legendre provou a identidade: ${\ Displaystyle \ varphi \!}$ ${\ Displaystyle \ theta \!}$ ${\ Displaystyle \ varphi + \ theta = {1 \ over 2} \ pi \!}$

{\ Displaystyle K (\ sin \ varphi) E (\ sin \ teta) + K (\ teta pecado \) E (\ sin \ varphi) -K (\ sin \ varphi) K (\ sin \ theta) = {1 \ over 2} \ pi. \!}

método de Gauss-Euler

Os valores podem ser substituídos na identidade de Legendre e as aproximações de K, E pode ser encontrado em termos das sequências para a média geométrica aritmética com e . ${\ Displaystyle \ varphi = \ theta = {\ pi \ over 4} \!}$ ${\ Displaystyle a_ {0} = 1 \!}$ ${\ Displaystyle b_ {0} = \ sin {\ pi \ over 4} = {\ frac {1} {\ sqrt {2}}} \!}$

Languages

In other projects