1
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jul 11 '14 at 15:44
  • $\begingroup$ @Christian Blatter So, the idea in general doesn't work $\endgroup$
    – OBDA
    Jul 11 '14 at 15:53
1
$\begingroup$

The idea is alright, but more care should have been applied.

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – OBDA
    Jul 11 '14 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.