# Show that Newton method converges for every choice of $x_0$

Let $f\in\mathcal C^{2}(\mathbb R)$ with $f'(x)>0$ and $f''(x)<0$. If $f(x^*)=0$, show that the Newton method converges to $x^*$ for every choice of $x_0$

Wlog, choose a start point $x_0$, s.t. $f(x_0)>0$, then;

$\displaystyle x_1=x_0-\frac{f(x_0)}{f'(x_0)}<x_0$

Since, $f''(x)<0$, which means that $f$ is concave and this implies;

$\displaystyle f(x_1)\le f(x_0)+f'(x_1)(x_1-x_0)=f(x_0)+f'(x_1)\frac{-f(x_0)}{f'(x_0)}<0$ (because $f'(x_1)>f'(x_0)$)

Moreover

$\displaystyle x_2=x_1-\frac{f(x_1)}{f'(x_1)}>x_1$ and

$\displaystyle f(x_2)\le f(x_1)+f'(x_1)(x_2-x_1)=f(x_1)+f'(x_1)\frac{-f(x_1)}{f'(x_1)}=0$

So the sequence $\{x_n\}_{n\ge 2}$ is monotone increasing and bounded above by $0$ ($\forall n\ge 2:f(x_n)\le 0$). Therefore it converges.

Is my proof correct ?

• This cannot be correct: The point $x=0$ (appearing as upper bound of the $x_n$) is by no means distinguished in the setup. The latter is fully translation invariant. Jul 11 '14 at 15:44
• @Christian Blatter So, the idea in general doesn't work
– OBDA
Jul 11 '14 at 15:53

The first WLOG is unjustified: The cases $f(x_0)>0$ and $f(x_0)<0$ are totally different. But nevertheless we may assume $f(x_0)>0$ to begin with and see what happens.
Then, using $f''(x)<0$ we obtain $$f(x_1)<f(x_0)+f'(x_0)(x_1-x_0)=0\ .$$ Correctly you then have $x_2>x_1$, and the next equation together with strict convexity shows that $f(x_2)<0$. Now comes the decisive mistake: This implies that $x_2<x_*$ and not $x_2<0$.
From what we have now we can say that starting with $n=2$ the $x_n$ form an increasing sequence bounded above by $x_*$. The rest should be clear.
• Thanks a lot. But if $f(x_0)<0$ then the whole sequence $\{x_n\}_{n\ge 0}$ (no excluded points) is increasing and bounded, that's why I choose first $f(x_0)>0$, because it includes the other case.