# convergence of arithmetic-geometric mean

Define $x_{n}=a_{n}/g_{n}$. By the arithmetic-geometric inequality  , we have $x_{n}\geq 1$. By the defining recursions, we have

 $x_{n+1}={a_{n+1}\over g_{n+1}}={a_{n}+g_{n}\over 2\sqrt{a_{n}g_{n}}}={1\over 2% }\left(\sqrt{a_{n}\over g_{n}}+\sqrt{g_{n}\over a_{n}}\right)={1\over 2}\left(% \sqrt{x_{n}}+{1\over\sqrt{x_{n}}}\right)$

Since $x_{n}\geq 1$, we have $1/\sqrt{x_{n}}\leq 1$, and $\sqrt{x_{n}}\leq x_{n}$, hence

 $x_{n+1}-1={1\over 2}\left(\sqrt{x_{n}}+{1\over\sqrt{x_{n}}}-2\right)\leq{1% \over 2}({x_{n}}+1-2)\leq{1\over 2}(x_{n}-1).$

From this inequality

 $0\leq x_{n+1}-1\leq{1\over 2}(x_{n}-1),$

we may conclude that $x_{n}\to 1$ as $n\to\infty$, which , by the definition of $x_{n}$, is equivalent     to

 $\lim_{n\to\infty}g_{n}=\lim_{n\to\infty}a_{n}.$

Not only have we proven that the arithmetic-geometric mean converges, but we can infer a rate of convergence from our proof. Namely, we have that $0\leq x_{n}-1\leq(x_{0}-1)/2^{n}$. Hence, we see that the rate of convergence of $a_{n}$ and $g_{n}$ to the answer goes as $O(2^{-n})$.

By more carefully bounding the recursion for $x_{n}$ above, we may obtain better estimates of the rate of convergence. We will now derive an inequality. Suppose that $y\geq 0$.

 $\displaystyle 0$ $\displaystyle\leq y^{5}+y^{4}+4y^{3}+3y^{2}$ $\displaystyle y^{2}+4y+4$ $\displaystyle\leq y^{5}+y^{4}+4y^{3}+4y^{2}+4y+4$ $\displaystyle(y+2)^{2}$ $\displaystyle\leq(y+1)(y^{2}+2)^{2}$

Set $x=y+1$ (so we have $x\geq 1$).

 $\displaystyle(x+1)^{2}$ $\displaystyle\leq x((x-1)^{2}+2)^{2}$ $\displaystyle x$ $\displaystyle\leq{x^{2}((x-1)^{2}+2)^{2}\over(x+1)^{2}}$ $\displaystyle\sqrt{x}$ $\displaystyle\leq{x((x-1)^{2}+2)\over x+1}$ $\displaystyle{x+1\over x}\sqrt{x}$ $\displaystyle\leq(x-1)^{2}+2$ $\displaystyle{1\over 2}\left(\sqrt{x}+{1\over\sqrt{x}}\right)$ $\displaystyle\leq 1+{1\over 2}(x-1)^{2}$

Thus, because $x_{n+1}=(\sqrt{x_{n}}+1/\sqrt{x_{n}})/2$, we have

 $x_{n+1}-1\leq{1\over 2}(x_{n}-1)^{2}.$

From this equation, we may derive the bound

 $x_{n}-1\leq\frac{1}{2^{2^{n}-1}}(x_{0}-1)^{2^{n}}.$

This is a much better bound! It approaches zero far more rapidly than any exponential function    , so we have superlinear convergence.

Title convergence of arithmetic-geometric mean ConvergenceOfArithmeticgeometricMean 2013-03-22 17:09:46 2013-03-22 17:09:46 rspuzio (6075) rspuzio (6075) 13 rspuzio (6075) Theorem  msc 33E05 msc 26E60