Newton iteration converges monotonically

199 Views Asked by At

Suppose f is a real function of one variable, f(x)=0 has a solution x*. $f'$ is Lipschitz continuous,$f'(x*)$ is nonsingular. Let $x_0$ is sufficiently close to x* and $f(x_0).f''(x_0)>0$,then the Newton iteration converges monotonically to x*.

Note: Newton iteration reads $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$.. This question is from book "Iterative methods for Linear and Nonlinear Equations " by C.T.Kelly 5.7.13

1

There are 1 best solutions below

0
On

See http://www.numdam.org/article/NAM_1869_2_8__17_0.pdf

"Sur la méthode d'approximation de Newton", Nouvelles annales de mathématiques: journal des candidats aux écoles polytechnique et normale, serie 2, vol 8 (1869), pp.17-27

Let $x^*=x_0+h$ and $f(x^*)=0$, \begin{equation} f(x_0+h) = 0 = f(x_0) + hf'(x_0) + h^2 f''(x_0 + \theta h)/2 \end{equation} and \begin{equation} h = - \frac{f(x_0)}{f'(x_0)} - \frac{h^2 f''(x_0 + \theta h)/2}{f'(x_0)} = h_0 - \frac{h^2 f''(x_0 + \theta h)/2}{f'(x_0)} \end{equation} where \begin{equation} h_0 = - \frac{f(x_0)}{f'(x_0)} \end{equation}

Now, we need to compare $x_0$, $x_0 + h_0$ and $x_0 + h$. They correspond to the initial point, to the approximation after 1 step of the iteration, and the exact final root solution, respectively. If $x_0+h-x_0-h_0 = h-h_0$ has the same sign as $x_0+h_0-x_0=h_0$ we get closer to the solution. Clearly, $h-h_0$ will have the same sign as $h_0$ if $f(x_0)$ has the same sign as $f''(x_0 + \theta h)$, i.e., if $f(x_0)$ has the same sign as $f''(x_0)$.