Algoritmo de Gauss-Legendre

Predefinição:Sem fontes O algoritmo de Gauss-Legendre é um algoritmo para calcular os dígitos de π. É notável por ser rapidamente convergente, com 25 iterações produz 45 milhões de dígitos corretos do π. Entretanto, o inconveniente é que usa muita memória e consequentemente não é usado em fórmulas como a Fórmula de Machin.

O método é baseado no trabalho individual de Carl Friedrich Gauss (1779-1815) e Adrien-Marie Legendre (1799-1855) combinado com os algoritmos modernos para multiplicação e raízes quadradas. Substitui repetidamente dois números pela sua média aritmética e pela sua média geométrica, a fim de aproximar a sua média aritmética-geométrica.

Algoritmo

1. Valores iniciais: $a_0=1b_0=\frac{1}{\sqrt{2}}{t}_0=\frac{1}{4}{p}_0=1.$

2. Repita as seguintes instruções até que a diferença de $a_n$ e $b_n$ esteja na precisão desejada:

$\begin{array}{cc}{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{array}$

3. π é então aproximado como:

$\pi \approx \frac{(a_{n+1}+b_{n+1}{)}^2}{4t_{n+1}}.$

As 3 primeiras iterações dão (aproximações incluindo o primeiro dígito duvidoso):

$3.140\dots$

$3.14159264\dots$

$3.1415926535897932382\dots$

O algoritmo tem uma natureza convergente de segunda ordem, o que significa que o número de dígitos corretos duplica a cada iteração do algoritmo.

Ligações externas

Algoritmo em Java e em C