Direkt zum Inhalt

Lexikon der Mathematik: Newtonverfahren

eine der wichtigsten Methoden zur numerischen Approximation von Nullstellen einer Funktion und – damit verbunden – zur Approximation lokaler Extremalpunkte von Optimierungsproblemen.

Die Einsatzbereiche des Newtonverfahrens sind so vielfältig, daß hier nur ein kleiner Eindruck vermittelt werden kann. Die Methode ist sowohl theoretisch als auch praktisch von unschätzbarer Bedeutung.

Die elementarste Form der Newtonmethode ist ihre Anwendung auf die Bestimmung einer Nullstelle einer stetig differenzierbaren Funktion f : [a, b] → ℝ. Das Verfahren versucht, iterativ von einem Startpunkt x0 ∈ (a, b) aus eine Folge {xk, k ∈ ℕ} zu konstruieren, die gegen eine Nullstelle von f in (a, b) konvergiert. Dabei berechnet sich die neue Iterierte xk+1 aus der alten xk gemäß \begin{eqnarray}{x}_{k+1}:={x}_{k}-\displaystyle\frac{f({x}_{k})}{f^{\prime} ({x}_{k})}.\end{eqnarray}Hierbei ist vorausgesetzt, daß die Ableitung f′(xk) nicht verschwindet. Die geometrische Idee hinter dieser Iteration ist es, in xk die Tangente an den Graphen von f zu legen und diese mit der x–Achse zu schneiden. Der Schnittpunkt ist dann gerade xk+1. Damit führt das Newtonverfahren eine Linearisierung des Problems aus: In jedem Schritt wird anstelle einer (möglicherweise) nichtlinearen Gleichung f(x) = 0 das entsprechende lineare System \begin{eqnarray}f({x}_{k})+{f}{^{\prime} }({x}_{k})\cdot (x-{x}_{k})=0\end{eqnarray} zu xk gelöst.

Abbildung 1 zum Lexikonartikel Newtonverfahren
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Newtonverfahren: Die Tangentengleichung an f(x) in f(xk) ist f′(xk) · x + f(xk) − f′(xk) · xk; Schnittpunkt mit der x-Achse ist xk+1 = xkf′(xk)−1 · f(xk). Die Abbildung zeigt zwei Newtonschritte von x0 aus.

Wie man unschwer sieht, läßt sich das Newtonverfahren ebenfalls als Eulersches Polygonzugverfahren zur näherungsweisen Lösung der Differentialgleichung \begin{eqnarray}\displaystyle\frac{dx(t)}{dt}=-\displaystyle\frac{1}{2}\cdot \displaystyle\frac{d}{dx}{f}^{2}(x(t))\end{eqnarray} mit Schrittweite h = 1 auffassen. Andere Schrittweiten liefern die Iterationsvorschrift \begin{eqnarray}{x}_{k+1}={x}_{k}+{h}_{k}\cdot f{({x}_{k})}^{-1}\cdot f({x}_{k})\end{eqnarray} und werden ebenso verwendet.

Schon im obigen eindimensionalen Fall zeigen sich zentrale Fragestellungen in Zusammenhang mit dem Newtonverfahren, wie etwa: Für welche Startwerte x0 konvergiert die Methode gegen eine Nullstelle von f; gegen welche Nullstelle konvergiert das Verfahren (falls überhaupt), wenn mehrere Nullstellen vorhanden sind; wie schnell konvergiert das Newtonverfahren? Die nächste Abbildung zeigt ein einfaches Beispiel, in dem keine Konvergenz vorliegt.

Am Beispiel sieht man, daß die Tangente an f dort, wo die Ableitung fast verschwindet, eine weit von der Nullstelle entfernte nächste Newtoniterierte liefert. Die geometrische Idee hinter diesem Beispiel führt zu folgendem recht einfach beweisbaren Konvergenzkriterium.

Abbildung 2 zum Lexikonartikel Newtonverfahren
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Divergenz des Newtonverfahrens

Sei f : [a, b] → ℝ eine dreimal stetig differenzierbare Funktion, die in \(\bar{x}\in (a,b)\)eine Nullstelle habe. Gelte ferner f′(x) = 0 in einer Umgebung U von \(\bar{x}\)(d. h. insbesondere, daß \(\bar{x}\)eine einfache Nullstelle ist). Dann konvergiert das Newtonverfahren für f für jeden Startpunkt x0U gegen die Nullstelle \(\bar{x}\). Die Konvergenzgeschwindigkeit ist quadratisch, d. h., es gibt eine Konstante C > 0, so daß\begin{eqnarray}|\bar{x}-{x}_{k+1}|\le C{|\bar{x}-{x}_{k}|}^{2},\,\,k\in {\mathbb{N}},\end{eqnarray}gilt.

Letzteres bedeutet, daß sich die Anzahl der korrekten Stellen mit jedem Iterationsschritt nahezu verdoppelt (in Abwesenheit von Rundungsfehlern). Genauer kann man sogar zeigen, daß \begin{eqnarray}\mathop{\mathrm{lim}}\limits_{k\to \infty }\displaystyle\frac{|{x}_{k+1}-\bar{x}|}{{({x}_{k}-\bar{x})}^{2}}=\displaystyle\frac{1}{2}\left|\displaystyle\frac{{f}{^{\prime\prime} }(\bar{x})}{{f}{^{\prime} }(\bar{x})}\right|.\end{eqnarray}

Während obiges Kriterium Ableitungen bis zur dritten Ordnung verwendet und diese über einer offenen Menge U Einschränkungen unterwirft, gibt es andere Kriterien, die höhere Differenzierbarkeitsordnungen von f verlangen, dafür aber nur Bedingungen an die Ableitungen in der aktuellen Newtoniterierten stellen. Ein solches Kriterium stellt etwa die α-Theorie von Smale bereit.

I. allg. ist die Frage nach Konvergenzbereichen von immenser Schwierigkeit und Gegenstand intensiver Forschung. Die Frage nach den sogenannten Einzugsbereichen verschiedener Nullstellen (d. h. den Mengen von Startwerten, für die das Newtonverfahren gegen die entsprechende Nullstelle konvergiert) beispielsweise führt in die Theorie der dynamischen Systeme.

Ein noch recht einfaches Kriterium für einen Spezialfall liefert folgender Satz:

Es sei f ein Polynom r-ten Grades, r > 1, d. h.\begin{eqnarray}f(x)=\displaystyle \sum _{k=0}^{r}{a}_{k}{x}^{k},\,\,x\in {\mathbb{R}},\end{eqnarray}welches nur reelle Nullstellen ξi mit\begin{eqnarray}{\xi }_{1}\ge {\xi }_{2}\ge \ldots \ge {\xi }_{r}\end{eqnarray}besitzt.

Dann liefert das Newtonverfahren für jeden Startwertx0 >ξ1eine gegen ξ1konvergente monoton fallende Folge. Diese Konvergenz ist im Fall r ≥ 2 streng monoton.

Durch Abdivision lassen sich in dem durch den Satz beschriebenen Fall sukzessive sämtliche Nullstellen von f iterativ bestimmen.

Ersetzt man den in obiger Formel auftretenden Differentialquotienten f′(xk) durch den Differenzenquotienten \begin{eqnarray}\displaystyle\frac{f({x}_{k})-f({x}_{k-1})}{{x}_{k}-{x}_{k-1}},\,\,k\in {\mathbb{N}},\end{eqnarray} so erhält man das sogenannte Sekantenverfahren. Dieses ist durch die Iterationsvorschrift der Regula falsi, \begin{eqnarray}{x}_{k+1}=\displaystyle\frac{{x}_{k-1}f({x}_{k})-{x}_{k}f({x}_{k-1})}{f({x}_{k})-f({x}_{k-1})},\,\,k\in {\mathbb{N}},\end{eqnarray} festgelegt. Der wesentliche Vorteil des Sekantenverfahrens ist es, daß man für dieses f′ nicht explizit kennen muß. Andererseits konvergiert es i. allg. nicht quadratisch, sondern es gilt lediglich \begin{eqnarray}|\bar{x}-{x}_{k+1}|\le C{|\bar{x}-{x}_{k}|}^{1.618},\,\,k\in {\mathbb{N}}.\end{eqnarray}

Eine geradlinige Verallgemeinerung des bisher gesagten ist für mehrdimensionale Abbildungen möglich. Ist f : ℝn → ℝn differenzierbar, so definiert man die Newtonabbildung Nf : ℝn → ℝn zu f durch \begin{eqnarray}{N}_{f}(x):=x-{(Df(x))}^{-1}\cdot f(x),\end{eqnarray} sofern die Jacobi-Matrix Df(x) invertierbar ist. Eine Folge von Newtoniterierten wird analog zur eindimensionalen Situation erzeugt, und dieselben Fragen sind von fundamentaler Bedeutung. Entsprechend läßt sich das Newtonverfahren auf allgemeineren Räumen definieren.

Es ist unmittelbar einsichtig, daß das Newtonverfahren auch eine wesentliche Rolle bei der Suche nach Extremalpunkten spielt; die Mehrzahl der bekannten notwendigen und hinreichenden Optimalitätskriterien differenzierbarer Probleme lassen sich in Form von Gleichungssystemen und damit letztlich als Nullstellenprobleme beschreiben. Zahlreiche Verfahren benutzen dabei Varianten der Methode von Newton, so z. B. das DFP-Verfahren, das BFGS-Verfahren, viele innere-Punkte-Methoden, das Lagrange-Newton-Verfahren, Homotopieverfahren etc.

Eine Verallgemeinerung für die Situation, wenn die Matrix Df(x) nicht invertierbar ist, liefern Verfahren, die dem obigen Zugang ähneln, aber statt Inversen Pseudo-Inverse verwenden.

[1] Hämmerlin, G.; Hoffmann K.-H.: Numerische Mathematik. Springer-Verlag Heidelberg/Berlin, 1991.
[2] Meinardus, G.; Merz G.: Praktische Mathematik I, II. BI-Wissenschaftsverlag Mannheim, 1979/1982.
[3] Stoer, J.: Einführung in die Numerische Mathematik I. Springer-Verlag Heidelberg/Berlin, 1972.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.