Global convergence of Newton's method

Question

Let $f=x^2 - a$, with $a>0$, and consider the Newton's method applied to the equation $f=0$.

Show that it is globally convergent to the unique root $\alpha$

---

To have global convergence for a fix point iteration $x_{k+1} = \phi(x_k)$, I need to show there exists a constant $L<1$ s.t. $$|\phi(x_1) - \phi(x_2)| \leq L |x_1 - x_2| \quad (\star) $$ for every $x_1, x_2 \in [0, a]$

Here $\phi(x) = x - \frac{x^2 - a}{2x}$, therefore

$$|\frac{x_1}{2} - \frac{x_2}{2} - \frac{a}{2x_2} + \frac{a}{2x_1}| = |\frac{1}{2}\bigl( x_2 - x_1 \bigr) - \frac{a}{2} \bigl( \frac{1}{x_1} - \frac{1}{x_2}\bigr)|$$

Now, since $x_2 > x_1$, I would like to bound the last term with $\frac{1}{2}|x_2 - x_1|$, which is $(\star)$ with $L=\frac{1}{2}$, but this inequality is not true.

How can I solve it?

Answer 1

Consider $\Phi$ as a function from $D:=(0,\infty)$ into itself, take any $x_0\in D$ and put $x_{n+1}:=\Phi(x_n)$. Note that $\Phi(x)=\frac12(x+\frac{a}{x})$. Using the simplest case of the inequality between the arithmetic and the geometric mean implies that $\Phi(x)\geq \sqrt{x\frac{a}{x}}=\sqrt{a}$. Moreover $\Phi(x)\leq x$ if $x\geq \sqrt{a}$ since $\Phi(x)-x =\frac12(\frac{a}{x}-x)\leq 0$. Therefore the sequence $(x_n)_{n\geq 1}$ is decreasing (and bounded from below by $\sqrt{a}$). This implies its convergence to some $\xi \geq \sqrt{a}$ such that $\xi=\Phi(\xi)$. Thus $\xi=\sqrt{a}$.

Answer 2

Hint:

(WLOG, $a=1$, because with $y=\sqrt ax$, the equation is $y^2=1$.)

Instead we can show that

$$\left|\phi(x)-1\right|<L|x-1|$$ that is $$\left|\frac{x^2+1}{2x}-1\right|<L|x-1|$$

or after simplification$$\left|\frac{x-1}{2x}\right|<L.$$

This is only true for $x\ge1$.