Gauss–Legendre algorithm: Difference between revisions

Revision as of 11:48, 19 August 2013

Revision as of 18:45, 14 October 2013

Line 13:

2. Repeat the following instructions until the difference of <math>a_n\!</math> and <math>b_n\!</math> is within the desired accuracy:

:<math> \begin{align} 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{align}

Line 22:

3. π is then approximated as:

<math>\pi \approx \frac{a_n^2(a_{n+b_n1}+b_{n+1})^2}{1-t_4t_{n+1}}.\!</math>

The first three iterations give (approximations given up to and including the first incorrect digit):

Line 31:

The algorithm has second-order convergent nature, which essentially means that the number of correct digits doubles with each step of the algorithm.

ADDENDUM:

The algorithm given above does not produce pi.

Instead use in step 2:

<math> \begin{align} 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{align}

</math>

3. π is then approximated as:

<math>\pi \approx \frac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}.\!</math>

== Mathematical background ==