Global convergence of Newton's method for square roots

185 Views Asked by At

To find approximate $\sqrt a$ we can use Newton's method to approximately solve the equation $x^2 − a = 0$ for $x$, starting from some rational $x_0$.

Newton's method in general is only locally convergent, so we have to be careful with initialization.

Show that in this case, the method always converges to something if $x_0 \neq 0$.

2

There are 2 best solutions below

0
On

The iteration is $x_{n+1}=g(x_n)$ with $g(x):=\frac12\left(x+\frac{a}{x}\right)$. We'll prove a lemma: if $x_0>0$ then $\lim_{n\to\infty}x_n=\sqrt{a}$. Since $g$ is odd, the lemma also implies that if $x_0<0$ then $\lim_{n\to\infty}x_n=-\sqrt{a}$.

Since $g(x)-\sqrt{a}=\frac12\left(\sqrt{x}-\sqrt{\frac{a}{x}}\right)^2\ge0$, $x_n\ge\sqrt{a}$ for all $n\ge1$. Then $x_n\ge\frac{a}{x_n}$, and $g(x_n)\le x_n$. Thus the sequence is decreasing but bounded below by $\sqrt{a}$, which is therefore the desired limit.

In fact, it's a pretty quick convergence. Define $\epsilon_n:=x_n-\sqrt{a}$ so$$\epsilon_{n+1}=\frac12\left(\epsilon_n-\sqrt{a}+\frac{a}{\epsilon_n+\sqrt{a}}\right)=\frac{\epsilon_n^2}{2(\epsilon_n+\sqrt{a})}=\frac{\epsilon_n^2}{2x_n}\sim\frac{\epsilon_n^2}{2\sqrt{a}}.$$

0
On

The most convenient method to analyze this iteration is to explore the fraction $$ \theta_n=\frac{x_n-\sqrt{a}}{x_n+\sqrt{a}} $$ as you will then find that $$ \theta_{n+1}={\theta_n}^2\implies \theta_n={\theta_0}^{2^n}\\~\\ \implies x_n=\frac{1+{\theta_0}^{2^n}}{1-{\theta_0}^{2^n}}\sqrt{a} =\sqrt{a}+\frac{2\;{\theta_0}^{2^n}}{1-{\theta_0}^{2^n}}\sqrt{a} $$