Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon: Erläuterung zu

Newton-Verfahren

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 Übersicht
Mit dem Newton-Verfahren kann eine Nullstelle $ x_\ast$ einer Funktion $ f$ numerisch bestimmt werden. Dabei wird durch Linearisierung eine Folge $ x_0,\,x_1\,\ldots$ von Approximationen für $ x_\ast$ generiert. Die Näherung $ x_{\ell+1}$ ist der Schnittpunkt der Tangente im Punkt $ \left( x_\ell,f(x_\ell) \right)$ mit der $ x$-Achse:

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

\includegraphics[width=0.4\linewidth]{Newton_Verfahren}

Für eine einfache Nullstelle $ x_\ast$ ( $ f^\prime(x_\ast)\neq 0$) konvergiert die Newton-Iteration lokal quadratisch, d.h.

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

für Startpunkte $ x_0$ in einer hinreichend kleinen Umgebung von $ x_\ast$.

Durch lineare Taylor-Approximation erhält man

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

mit dem Restglied

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

für ein $ t_\ell$ zwischen $ x_\ast$ und $ x_\ell$. Setzt man

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

in die Iterationsvorschrift ein, so folgt

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

Für $ f^{'}(x_\ell) \neq 0$ gilt also

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

Gilt $ f^{'}(x_{\ast}) \neq 0$, so ist $ c_\ell$ aus Stetigkeitsgründen für $ x_\ell$ in einer Umgebung $ [x_{\ast} - \delta, x_{\ast} + \delta]$ von $ x_{\ast}$ beschränkt:

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

Damit folgt die quadratische Konvergenz.
[Zurück]
  automatisch erstellt am 17.  6. 2016