Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon: Annotation to

Newton's Method

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview
With Newton's method we can determine a zero $ x_\ast$ of a function $ f$ numerically. The sequence $ x_0,\,x_1\,\ldots$ of the approximations to $ x_\ast$ is obtained via linearization, i.e., $ x_{l+1}$ is the intersection of the tangent to $ f$ at $ \left( x_\ell,f(x_\ell) \right)$ with the $ x$-axis:

$\displaystyle x_{\ell+1} = x_\ell - f(x_\ell)/f^\prime(x_\ell)$

\includegraphics[width=0.6\linewidth]{Newton_Verfahren.eps}

For a simple zero $ x_\ast$ $ (f^\prime(x_\ast)\ne0)$, Newton's iteration converges quadratically, i.e.,

$\displaystyle \left\vert x_{l+1}-x_{\ast} \right\vert \leq c\; \left\vert x_{l}-x_{\ast} \right\vert^2 $

if the initial approximation $ x_0$ is sufficiently close to $ x_\ast$.

With linear Taylor approximation we obtain

$\displaystyle 0=f(x_\ast)=f(x_\ell)+f'(x_\ell)(x_\ast-x_\ell)+R $

with the remainder

$\displaystyle R=\frac{1}{2}\,f^{\prime\prime}(t_\ell)(x_\ast-x_\ell)^2\,, $

where $ t_\ell$ lies between $ x_\ast$ and $ x_\ell$. Substituting

$\displaystyle f(x_\ell)=f^\prime(x_\ell)(x_\ell-x_\ast)-R $

into the Newton recursion yields

$\displaystyle x_{\ell+1} = x_\ast + R/f^\prime(x_\ell)\,. $

If $ f^{'}(x_\ell) \neq 0$, it follows that

$\displaystyle \vert x_{\ell+1} - x_{\ast}\vert = c_\ell\vert x_\ell - x_{\ast}... ...\left\vert \frac{f^{\prime\prime}(t_\ell)}{f^{\prime}(x_\ell)} \right\vert\,. $

By continuity, the assumption $ f^{\prime}(x_{\ast}) \neq 0$ implies that $ c_\ell$ is bounded for all $ x_\ell$ in a neighborhood $ [x_{\ast} - \delta, x_{\ast} + \delta]$ of $ x_{\ast}$:

$\displaystyle c_\ell \leq c\,. $

This establishes quadratic convergence.
[Back]
  automatisch erstellt am 22.  6. 2016