Newtonverfahren

Das Newtonsche Näherungsverfahren, auch Newton-Raphsonsche Methode, (benannt nach Sir Isaac Newton 1669 und Joseph Raphson 1690) ist in der Mathematik das Standardverfahren zur numerischen Lösung von nichtlinearen Gleichungen und Gleichungssystemen. Im Falle einer Gleichung mit einer Variablen lassen sich zu einer gegebenen stetig differenzierbaren Funktion $f:\mathbb {R} \to \mathbb {R}$ Näherungswerte zu Lösungen der Gleichung $f(x)=0$, d.h. Näherungen der Nullstellen dieser Funktion finden. Die grundlegende Idee dieses Verfahrens ist, die Funktion in einem Ausgangspunkt zu linearisieren, d.h. ihre Tangente zu bestimmen, und die Nullstelle der Tangente als verbesserte Näherung der Nullstelle der Funktion zu verwenden. Die erhaltene Näherung kann wieder Ausgangspunkt für einen weiteren Verbesserungsschritt dienen. Diese Iteration wird so oft wiederholt, bis die Änderung in der Näherungslösung eine festgesetzte Schranke unterschreitet. Das unendlich oft fortgesetzte Iterations-Verfahren konvergiert im günstigsten Fall mit quadratischer Konvergenzordnung, die Zahl der korrekten Dezimalstellen verdoppelt sich dann in jedem Schritt.

Newton-Verfahren für reelle Funktionen einer Veränderlichen

Historisches über das Newtonverfahren

Isaac Newton verfasste im Zeitraum 1664-1671 die Arbeit „Methodus fluxionum et serierum infinitarum“ (latein für: Von der Methode der Fluxionen und unendlichen Folgen). Darin erklärt er einen neuen Algorithmus zum Lösen einer polynomialen Gleichung am Beispiel $y^{3}-2y-5=0$. Dazu kann man leicht den Punkt $y=2$ als erste Näherung raten. Newton machte den Ansatz $y=2+p$ mit einem als "klein" angenommenen $p$ und setzte diesen in die Gleichung ein:

Nach den binomischen Formeln gilt

$y^{3}=(2+p)^{3}=8+12p+6p^{2}+p^{3}\$, $\ 2y=4+2p$

$\Rightarrow \ 0=y^{3}-2y-5=-1+10p+6p^{2}+p^{3}$.

Da $p$ "klein" sein soll, können die Terme höherer Ordnung gegen den linearen und konstanten vernachlässigt werden, womit $10p-1=0$ bzw. $p=0,1$ übrig bleibt. Wir können nun dieses Vorgehen wiederholen und $p=0,1+q$ ansetzen, in die zweite Gleichung einsetzen, höhere Terme weglassen und $q=-0,061/11,23=-0,0054\dots$ erhalten.

Joseph Raphson beschrieb 1690 in der Arbeit „Analysis Aequationum universalis“ diesen Rechenprozess formal und illustrierte den Formalismus an der allgemeinen Gleichung 3. Grades, wobei er die nachfolgende Iterationsvorschrift fand. (Nach Quelle [1].)

Konstruktion am Graphen

Anschaulich gelangt man wie folgt zu diesem Verfahren: Sei $f:\mathbb {R} \to \mathbb {R}$ eine stetig differenzierbare reelle Funktion, von der wir eine Stelle $x_{n}$ im Definitionsbereich mit „kleinem“ Funktionswert kennen. Wir wollen einen Punkt $x_{n+1}$ nahe $x_{n}$ finden, der eine verbesserte Näherung der Nullstelle darstellt. Dazu linearisieren wir die Funktion $f$ an der Stelle $x_{n}$, d.h. wir ersetzen sie durch ihre Tangente im Punkt $P(x_{n}\,;\,f(x_{n}))$ mit Anstieg $f^{\prime }(x_{n})$.

Die Tangente ist durch die Funktion $t(x_{n}+h):=f(x_{n})+f^{\prime }(x_{n})h$ gegeben, setzen wir $h=x-x_{n}$ ein, so erhalten wir

$t(x):=f(x_{n})+f^{\prime }(x_{n})(x-x_{n})$.

Wir wählen als $x_{n+1}$ die einzige Nullstelle dieser linearen Funktion,

$0=t(x_{n+1})=f(x_{n})+f^{\prime }(x_{n})(x_{n+1}-x_{n})\quad \Rightarrow \quad x_{n+1}=x_{n}-f(x_{n})/f'(x_{n})$.

Wenden wir diese Konstruktion mehrfach an, so erhalten wir aus einer ersten Stelle $x_{0}$ eine unendliche Folge von Stellen $(x_{n})_{n\in \mathbb {N} }$, die durch die Rekursionsvorschrift

$x_{n+1}:=N_{f}(x_{n}):=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

definiert ist. Diese Vorschrift wird auch als Newton-Iteration bezeichnet, die Funktion $N_{f}$ als Newton-Operator. Die Newton-Iteration ist ein spezieller Fall einer Fixpunktiteration, falls die Folge gegen $\xi =\lim _{n\to \infty }x_{n}\,$ konvergiert, so gilt $\xi =N_{f}(\xi )=\xi -f(\xi )/f'(\xi )$ und daher $f(\xi )=0$.

Die Kunst der Anwendung des Newtonverfahrens besteht darin, geeignete Startwerte $x_{0}$ zu finden. Je mehr über die Funktion $f$ bekannt ist, desto kleiner läßt sich die notwendige Menge von Startwerten gestalten.

Viele nichtlineare Gleichungen haben mehrere Lösungen, so hat ein Polynom $n$-ten Grades bis zu $n$ Nullstellen. Will man alle Nullstellen in einem bestimmten Bereich $D\subseteq \mathbb {R}$ ermitteln, so muss zu jeder Nullstelle ein passender Startwert in $D$ gefunden werden, für den die Newton-Iteration konvergiert. Dazu könnte man z.B. per Bisektion genügend kleine isolierende Intervalle zu jeder Nullstelle bestimmen.

Erstes Beispiel

Die Quadratwurzel einer Zahl $a>0$ sind die Nullstellen der Funktion $f(x)=1-a/x^{2}$. Diese Funktion hat die Ableitung $f^{\prime }(x)=2a/x^{3}$, die Newton-Iteration erfolgt also nach der Vorschrift

$x_{n+1}:=N_{f}(x_{n})=x_{n}-{\frac {1-a/x_{n}^{2}}{2a/x_{n}^{3}}}=x_{n}-{\frac {x_{n}^{3}}{2a}}+{\frac {x_{n}}{2}}$$={\frac {x_{n}}{2}}\left(3-{\frac {x_{n}^{2}}{a}}\right)$

Der Vorteil dieser Vorschrift gegenüber dem Wurzelziehen nach Heron (siehe unten) ist, dass es divisionsfrei ist, sobald einmal der Kehrwert von $a$ bestimmt wurde. Als Startwert wurde in der Tabelle $x_{0}:=(1+a)/2$ gewählt. Die Iterierten wurden an der ersten ungenauen Stelle abgeschnitten. Es ist zu erkennen, dass nach wenigen Schritten die Anzahl gültiger Stellen schnell wächst.

n	$x_{n}$ bei $a=2$	$x_{n}$ bei $a=3$	$x_{n}$ bei $a=5$
0	$1{,}5$	$2$	$3$
1	$1{,}40$	$1{,}6$	$1{,}8$
2	$1{,}4141$	$1{,}72$	$2{,}1$
3	$1{,}41421355$	$1{,}73203$	$2{,}22$
4	$1{,}41421356237309502$	$1{,}7320508074$	$2{,}23601$
5	$1{,}414213562373095048801688724209697$	$1{,}73205080756887729351$	$2{,}236067975$
6	$1{,}414213562373095048801688724209698$	$1{,}7320508075688772935274463415058723669426$	$2{,}236067977499789692$
7	$1{,}414213562373095048801688724209698$	$1{,}7320508075688772935274463415058723669428$	$2{,}23606797749978969640917366873127622$
8	$1{,}414213562373095048801688724209698$	$1{,}7320508075688772935274463415058723669428$	$2{,}23606797749978969640917366873127623$

Betrachten wir die Differenz $x_{n+1}-{\sqrt {a}}$ zum Grenzwert im $(n+1)$-ten Schritt, so kann mittels der binomischen Formeln die Differenz im $n$-ten Schritt zweimal abgespalten werden:

$x_{n+1}-{\sqrt {a}}={\frac {3}{2}}x_{n}-{\frac {x_{n}^{3}}{2a}}-{\frac {3}{2}}{\sqrt {a}}+{\frac {{\sqrt {a}}^{3}}{2a}}=(x_{n}-{\sqrt {a}})\cdot \left({\frac {3}{2}}-{\frac {x_{n}^{2}+x_{n}{\sqrt {a}}+a}{2a}}\right)$

$=(x_{n}-{\sqrt {a}})\cdot {\frac {a-x_{n}^{2}+a-x_{n}{\sqrt {a}}}{2a}}=-(x_{n}-{\sqrt {a}})^{2}\cdot (x_{n}+2{\sqrt {a}})$

Nach der Ungleichung vom arithmetischen und geometrischen Mittel gilt $0<{\sqrt {a}}\leq {\frac {1+a}{2}}$, so dass der zweite Faktor sinnvoll durch $3/2(1+a)$ beschränkt werden kann. Ist die Differenz im $n$-ten Schritt eine kleine Zahl, so ist die Differenz im $(n+1)$-ten Schritt proportional zum Quadrat davon, also wesentlich kleiner. So entsteht durch Quadrieren eines Fehlers $10^{-m}$ eine Fehlerabschätzung proportional zu $10^{-2m}$. Deshalb spricht man davon, dass sich die Anzahl der gültigen Stellen in jedem Schritt der Newton-Iteration in etwa verdoppelt.

Konvergenzbetrachtungen

Das Newton-Verfahren ist ein so genanntes lokal konvergentes Verfahren. Konvergenz der in der Newton-Iteration erzeugten Folge zu einer Nullstelle ist also nur garantiert, wenn der Startwert, d.h. das 0-te Glied der Folge, schon „ausreichend nahe“ an der Nullstelle liegt. Ist der Startwert zu weit weg, kann alles passieren:

• Die Folge divergiert, die Folgenglieder entfernen sich über alle Grenzen.
• Die Folge divergiert, bleibt aber beschränkt. Sie kann z.B. periodisch werden, d.h. endlich viele Punkte wechseln sich in immer derselben Reihenfolge ab. Man sagt auch, dass die Folge oszilliert.
• Die Folge konvergiert trotz der Distanz zur Nullstelle, kann jedoch, falls die Funktion mehrere Nullstellen hat, gegen eine andere als die gewünschte Nullstelle (falls man weiß, welche man will) konvergieren.

Newton-Fraktal für p(z)=z³-1

Bei geeigneter Wahl des Startwertes $x_{0}$ kann das Newtonsche Verfahren allerdings quadratisch, also mit der Konvergenzordnung 2, konvergieren. Die Menge der Startpunkte, für die das Newton-Verfahren gegen eine bestimmte Nullstelle konvergiert, bildet den Einzugsbereich dieser Nullstelle. Färbt man für eine Polynomfunktion, mit reellen oder komplexen Koeffizienten, die Einzugsbereiche verschiedener Nullstellen in der komplexen Ebene verschieden ein, so ergibt sich ein Newton-Fraktal. In diesem ist zu erkennen, dass die Einzugsbereiche Bassins, d.h. Kreisscheiben um die Nullstellen enthalten, aus welchen heraus die Newton-Iteration stabil gegen die Nullstelle im Zentrum konvergiert. Aber es ist auch zu erkennen, dass die Ränder der Einzugsbereiche „ausgefranst“ sind, sie haben sogar eine fraktale Struktur. Geringe Abweichungen im Startpunkt können also zu verschiedenen Nullstellen führen.

Beispiele für Nicht-Konvergenz

1. Oszillierendes Verhalten ergibt sich für das Polynom $f(x):=x^{3}-2x+2$ (siehe Quelle [2]) mit $f'(x)=3x^{2}-2$. Der Punkt $x=0$ mit $f(0)=2$ und $f'(0)=-2$ wird durch den Newton-Operator auf den Punkt $N(0)=0-2/(-2)=1$ abgebildet, der Punkt $x=1$ wiederum, mit $f(1)=1$ und $f'(1)=1$, wird auf $N(1)=1-1/1=0$ abgebildet, so dass die Newton-Iteration mit einem dieser Punkte als Startwert eine periodische Folge ergibt, diese beiden Punkte wechseln sich zyklisch ab. Des Weiteren ist dieser Zyklus stabil, er bildet einen Attraktor der Newton-Iteration. Das bedeutet, es gibt eine kleine Umgebung beider Punkte, so dass Startpunkte in dieser Umgebung gegen den Zyklus konvergieren und somit je einen der Punkte 0 und 1 als Grenzwert der Teilfolge mit geradem Index und der mit ungeradem Index haben.
2. Divergenz bzw. beliebig weites Entfernen vom Startpunkt ergibt sich für $f(x)=\sin(x)$ mit $f'=\cos(x)$ und $N(x)=x-\tan(x)$. Es gibt eine Stelle $x_{0}\in \lbrack -\pi /2,0\rbrack$ mit $\tan(x_{0})=-2\pi$. Man überzeugt sich, dass dann $x_{n}=x_{0}+2\pi n$ gilt. Dieses Verhalten ist nicht stabil, denn bei leichter Variation des Anfangswertes, wie sie zum Beispiel durch die numerische Berechnung entsteht, entfernt sich die Newton-Iteration immer weiter von der idealen divergierenden Folge. Selbst bei schließlicher Konvergenz wird die gefundene Nullstelle sehr weit vom Startwert entfernt sein.

Lokale quadratische Konvergenz

Sei $f$ eine zweimal stetig differenzierbare reelle Funktion und $\xi$ eine Nullstelle von $f$, in welcher die Ableitung keine Nullstelle hat. Das bedeutet, dass der Graph der Funktion transversal, d.h. nicht-berührend, die x-Achse schneidet. Dann kann die Wirkung des Newton-Operators in der Nähe von $\xi$ angenähert werden durch

$x_{n+1}=N_{f}(x_{n})\approx \xi +{\frac {1}{2}}\cdot {\frac {f''(\xi )}{f'(\xi )}}\cdot (x_{n}-\xi )^{2}$.

Eine mathematisch exaktere Formulierung dieses Sachverhaltes besagt, dass es eine Konstante $K\approx |f''(\xi )/f'(\xi )|$ und ein Intervall $I=(\xi -1/K,\xi +1/K)$ gibt, so dass innerhalb dieses Intervalls gilt

$|N_{f}(x)-\xi |\leq K/2\cdot |x-\xi |^{2}$ für alle $x\in I$.

Ist also $K/2|x_{0}-\xi |<1$, so konvergiert die Folge $(x_{n})$ der Newton-Iteration gegen $\xi$, denn die Folge $(d_{n})$ mit $d_{n}:=K/2\cdot |x_{n}-\xi |$ erfüllt $0<d_{n+1}\leq d_{n}{}^{2}$, nach vollständiger Induktion also $0<d_{n}\leq d_{0}{}^{2^{n}}$, was für $0<d_{0}<1$ eine Nullfolge ist.

Ist die Differenz $|x_{0}-\xi |\ll 1$ eine sehr kleine Zahl, so kann auch die Näherungsformel verwendet werden, es gilt dann

$x_{n}=\xi +\left({\frac {f^{''}(\xi )}{2f^{'}(\xi )}}\right)^{2^{n}-1}\cdot (x_{0}-\xi )^{2^{n}}$.

Je nach Vorzeichen der ersten beiden Ableitungen konvergiert die Folge der Newton-Iteration also von links oder rechts.

Die aus diesen Abschätzungen folgende Konvergenzgeschwindigkeit wird als quadratisch bezeichnet, die (logarithmische) Genauigkeit bzw. Anzahl gültiger Stellen verdoppelt sich in jedem Schritt. Die Abschätzung des Abstands $|x_{n}-\xi |$ zur Nullstelle wird oft linear in $|x_{0}-\xi |$ angegeben, so gilt z.B.

• für $|x_{0}-\xi |\leq {\frac {1}{K}}$ durch $2^{n}-1$-faches Einsetzen

$|x_{n}-\xi |\leq \left({\frac {1}{2}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |$,

wodurch sich die Anzahl der gültigen Stellen im Binärsystem abschätzen läßt, oder

• für $|x_{0}-\xi |\leq {\frac {1}{5K}}$ gilt

$|x_{n}-\xi |\leq \left({\frac {1}{10}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |$,

d.h. nahe genug an der Nullstelle ergibt sich die schon oben angesprochene Verdopplung der Dezimalstellen in jedem Schritt.

Bemerkungen

• Der globale Konvergenzbeweis basiert auf der Taylor-Entwicklung des Grades 2, ist im mehrdimensionalen Fall allerdings technisch schwierig. Für diesen Fall wurde er zuerst von Leonid Kantorowitsch geführt und ist als Satz von Kantorowitsch bekannt.
• Um einen geeigneten Startpunkt zu finden verwendet man gelegentlich andere ("gröbere") Verfahren. Beispielsweise kann man mit dem Gradientenverfahren eine ungefähre Löung ermitteln und diese dann mit dem Newton-Verfahren verfeinern.
• Bei unbekanntem Startpunkt kann man mittels einer Homotopie die Funktion $f$, von der man eine Nullstelle sucht, zu einer einfacheren Funktion $g$ deformieren, von der (mindestens) eine Nullstelle bekannt ist. Man durchläuft dann die Deformation rückwärts in Form einer endlichen Folge sich nur "wenig" unterscheidender Funktionen. Von der ersten Funktion $g$ kennt man eine Nullstelle. Als Startwert der Newton-Iteration zur gerade aktuellen Funktion der Folge verwendet man die Näherung einer Nullstelle der in der Folge vorhergehenden Funktion.

Als Beispiel mag die "Flutungshomotopie" dienen: mit einem willkürlichen $z$ bilden wir die Ausgangsfunktion $g(x)=f_{0}(x):=f(x)-f(z)$ mit bekannter Nullstelle $z$ . Wir haben den "Wasserspiegel" vom "Nullpegel" auf die Höhe $f(z)$ geflutet. Nun senken wir schrittweise den Wasserstand, $f_{n}(x):=f(x)-(f(z)-n\cdot h\cdot f(z))$, $h=1/N$, $n=1\dots N$. In jedem Schritt wird eine Näherung $\xi ^{(n)}$ einer Nullstelle bestimmt, wobei $x_{0}:=\xi ^{(n-1)}$ gesetzt wird. Es ist $f_{N}=f$ und somit $\xi ^{(N)}$ eine der gesuchten Näherungslösungen.

Abbruchkriterien

Mögliche Abbruchkriterien bezüglich einer Restgröße (zum Beispiel Rechner-Arithmetik) sind:

$\|f(x_{n})\|<\varepsilon _{1}\qquad \mathrm {oder} \qquad \|x_{n+1}-x_{n}\|<\varepsilon _{2}$

Wobei $\varepsilon _{1},\varepsilon _{2}\in \mathbb {R} ^{+}$ die Qualität der "Nullstelle" bestimmt. In beiden Fällen kann es vorkommen, dass das Abbruchkriterium zu einem "schlechten" Zeitpunkt erfüllt ist.

Weitere Anwendungsbeispiele

Berechnung der Quadratwurzel

Ein Spezialfall des Newtonschen Näherungsverfahrens ist das Babylonische Wurzelziehen, auch bekannt als Heronverfahren nach Heron von Alexandria:

Wendet man die Iterationsformel auf die Funktion

$f(x)=x^{2}-a=0$, $f'(x)=2x$

an, dann erhält man die für die Lösung ${\sqrt {a}}$ das Näherungsverfahren

$x_{n+1}:=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)$.

Dieses Verfahren konvergiert bei $a\geq 0$ für jeden beliebigen Anfangswert $x_{0}\neq 0$.

Schnittpunkt zweier Funktionen

Auf ähnliche Weise lässt sich auch der $x$ -Wert des Schnittpunktes zweier Funktionen $g(x)$ und $f(x)$ bestimmen:

Da man die beiden Funktionen zur Lösung des Problems gleichsetzt, lässt sich immer durch Umformung folgende Form, auf die das Newtonsche Näherungsverfahren angewendet werden kann, bestimmen:

$f(x)-g(x)=0$

Trigonometrische Funktion

Gesucht sei die positive Lösung eines Problems $x$ wobei $\cos(x)=x^{3}$. Das Problem kann umformuliert werden als $f(x)=\cos(x)-x^{3}$.

Wir haben nun $f'(x)=-\sin(x)-3x^{2}$. Da $\cos(x)\leq 1$ für alle $x$ gilt und $x^{3}>1$ für $x>1$, wissen wir, dass die Nullstelle zwischen 0 und 1 liegt. Wir starten die Iteration mit dem Wert $x_{0}=0,5$ .

${\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&{\frac {\cos(0{,}5)-0{,}5^{3}}{-\sin(0{,}5)-3\cdot 0{,}5^{2}}}&=&1{,}1121416371\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&&\vdots &=&0{,}909672693736\\x_{3}&&\vdots &&\vdots &=&0{,}867263818209\\x_{4}&&\vdots &&\vdots &=&0{,}865477135298\\x_{5}&&\vdots &&\vdots &=&0{,}865474033111\\x_{6}&&\vdots &&\vdots &=&0{,}865474033101\\x_{7}&&\vdots &&\vdots &=&0{,}865474033102\end{matrix}}$

Damit haben wir die ersten zwölf Ziffern der Nullstelle.

Das folgende Programm in JavaScript bestimmt diese Nullstelle. Um es auszuführen, kopieren Sie den Programmtext inklusive der Marken in eine neue Textdatei und speichern Sie sie mit dem Dateityp .html ab. Öffnen Sie dann die Datei mit einem Webbrowser.

 <script>
  
  function NewtonIterationFnct(x) {
     return  x - (Math.cos(x) - x*x*x) / (-Math.sin(x) - 3*x*x)     
  }  

  x = 0.5
  
  for (i=0; i<=99; i++) {
	document.write("Iteration " + i + ": ")
	document.write(x)
	document.write('<br>')
        xold = x
	x = NewtonIterationFnct(x) 
        if (x == xold) break 
  }

 </script>

Das Newton-Verfahren im Mehrdimensionalen

Das Newton-Verfahren kann auch benutzt werden, um Nullstellen von mehrdimensionalen Funktionen $f(x):\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ zu bestimmen. Ein konkreter Anwendungsfall ist die Kombination mit der Gaußschen Fehlerquadratmethode im Gauß-Newton-Verfahren. Für den allgemeinen Fall ist der Ausgangspunkt der Iteration die obige Fixpunktgleichung:

$x=N_{f}(x):=x-(Df(x))^{-1}f(x)\,$

die das Newton-Verfahren inspiriert:

$x_{n+1}:=N_{f}(x_{n})=x_{n}-(Df(x_{n}))^{-1}f(x_{n})\,,$

wobei $Df(x)=f'(x)={\frac {\partial f}{\partial x}}(x)$ die Jacobi-Matrix, also die Matrix der partiellen Ableitungen von $f(x)\,$, ist. $Df(x):={\frac {\partial (f_{1},\dots ,f_{n})}{\partial (x_{1},\dots ,x_{n})}}={\begin{pmatrix}{\frac {\partial f_{1}}{\partial x_{1}}}&{\frac {\partial f_{1}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{1}}{\partial x_{n}}}\\{\frac {\partial f_{2}}{\partial x_{1}}}&{\frac {\partial f_{2}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{2}}{\partial x_{n}}}\\\vdots &\vdots &\ddots &\vdots \\{\frac {\partial f_{n}}{\partial x_{1}}}&{\frac {\partial f_{n}}{\partial x_{2}}}&\ldots &{\frac {\partial f_{n}}{\partial x_{n}}}\end{pmatrix}}$

Da die Berechnung der Inversen einer Matrix sehr aufwändig ist, wird auf die Aufstellung von $(Df(x))^{-1}\,$ verzichtet und statt dessen folgender Weg gewählt: Man berechnet den Wert

$\Delta x:=-(Df(x_{n}))^{-1}f(x_{n})\;,$

indem man das lineare Gleichungssystem

$Df(x_{n})\;\Delta x=-f(x_{n})$

löst, und hat dann

$x_{n+1}=x_{n}+\Delta x_{n}\;.$

Statt die Inverse auszurechnen, wird also ein lineares Gleichungssystem gelöst. Häufig kann man hier Eigenschaften der Jacobi-Matrix ausnutzen, um schnell und effizient zu einer Lösung zu kommen. Die weiteren Eigenschaften des Newton-Verfahrens (lokale, quadratische Konvergenz) sind im mehrdimensionalen genau wie im eindimensionalen Fall.

Varianten des Newton-Verfahrens

Das größte Problem bei der Anwendung des Newton-Verfahrens liegt darin, dass man die erste Ableitung der Funktion benötigt. Die Berechnung dieser ist meist aufwändig und in vielen Anwendungen ist eine Funktion auch nicht explizit, sondern beispielsweise nur durch ein Computerprogramm gegeben (siehe auch Automatisches Differenzieren). Im eindimensionalen ist dann die Regula Falsi vorzuziehen, bei der die Sekante und nicht die Tangente benutzt wird. Im Mehrdimensionalen muss man andere Alternativen suchen. Hier ist das Problem auch dramatischer, da die Ableitung eine Matrix mit $n^{2}$ Einträgen ist, der Aufwand der Berechnung steigt also quadratisch mit der Dimension.

Das vereinfachte Newton-Verfahren

Statt die Ableitung in jedem Newton-Schritt auszurechnen, ist es auch möglich, sie nur in jedem $n$-ten Schritt zu berechnen. Dies senkt die Kosten für einen Iterationsschritt drastisch, der Preis ist ein Verlust an Konvergenzgeschwindigkeit. Die Konvergenz ist dann nicht mehr quadratisch, es kann aber weiterhin superlineare Konvergenz erreicht werden.

Inexakte Newton-Verfahren

Eine ähnliche Idee besteht darin, in jedem Schritt eine Approximation der Ableitung zu berechnen, beispielsweise über finite Differenzen. Eine quantitative Konvergenzaussage ist in diesem Fall schwierig, als Faustregel lässt sich jedoch sagen, dass die Konvergenz schlechter wird, je schlechter die Approximation der Ableitung ist.

Newton-Krylow-Verfahren

Für die numerische Lösung nichtlinearer partieller Differentialgleichungen bietet sich prinzipiell das Newton-Verfahren als Grundlöser an. Die entsprechende Jacobi-Matrix ist immer dünnbesetzt und so bieten sich Krylow-Unterraum-Verfahren zur Lösung der linearen Gleichungsysteme an. Man spricht dann von Newton-Krylow-Verfahren. Im Krylow-Verfahren selbst tritt die Jacobi-Matrix nur in Matrix-Vektorprodukten auf, welche als Richtungsableitungen interpretiert werden können. Approximiert man diese durch Finite Differenzen, so erhält man komplett matrixfreie Verfahren.

Beweise zur lokalen Konvergenz

Newton-Verfahren als Fixpunktiteration

Als zweite Motivation, neben der oben gezeigten graphischen, soll das Newton-Verfahren direkt als Fixpunktiteration abgeleitet werden. Aus dieser Ableitung ergibt sich auch recht leicht die Begründung der unten angegebenen Varianten.

Sei $f:\mathbb {R} \to \mathbb {R}$ eine stetig differenzierbare reelle Funktion, von der wir eine Nullstelle bestimmen möchten. Wir versuchen, die Voraussetzungen des Banachschen Fixpunktsatzes zu erfüllen. Dazu konstruieren wir aus $f(x)=0$ eine Fixpunktgleichung. Eine allgemeine Form dafür ist $x=N(x):=x+g(x)f(x)$, wobei $g$ eine zusätzliche, ebenfalls stetig differenzierbare Funktion ist. Jede Nullstelle $\xi$ von $f$, $f(\xi )=0$, ist Fixpunkt von $N$:

$N(\xi )=\xi +g(\xi )\cdot \underbrace {f(\xi )} _{=0}=\xi$.

Wir benötigen, nach den Voraussetzungen des Fixpunktsatzes, ein Intervall $I\subseteq \mathbb {R}$, welches die Nullstelle $\xi$ enthält, und dass die Abbildung $N$ auf diesem Intervall kontraktiv ist. Dazu ist es ausreichend, dass die Ableitung $N'(x)$ für $x\in I$ nur Werte im Intervall $\lbrack -q,\ q\rbrack$, $0<q<1$, annimmt, denn für $x,x+h\in I$ gilt

$|N(x+h)-N(x)|\leq \int _{0}^{1}|N'(x+th)h|\,dt\leq q\,|h|\int _{0}^{1}\,dt=q\,|h|$

bzw. mit ${\tilde {x}}:=x+h$

$|N({\tilde {x}})-N(x)|\leq q\,|{\tilde {x}}-x|$.

Insbesondere kann man fordern, dass der Wert der Ableitung $N'(\xi )$ von $N$ in $\xi$ einen möglichst kleinen Betrag habe. Die Ableitung von $N$ ist

$N'(x)=1+g'(x)\cdot f(x)+g(x)\cdot f'(x)\quad \Longrightarrow \quad N'(\xi )=1+g(\xi )f'(\xi )$,

wählt man also immer $g(x):=-f'(x)^{-1}$, und gibt es eine Umgebung von $\xi$, in der $f$ zweimal differenzierbar ist und $f'(x)$ nirgends Null wird, so ist $N'(\xi )=0$.

Wir gelangen somit wieder zur Fixpunktgleichung

$x=N_{f}(x):=x-{\frac {f(x)}{f'(x)}}$

mit dem Newton-Operator $N_{f}$, welche als Fixpunktiteration wieder die Newton-Iteration ergibt:

$x_{n+1}:=N_{f}(x_{n})=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

bei "geeigneter" Wahl eines Startpunktes $x_{0}$. Von dieser muß die Konvergenz gegen eine Nullstelle exakt nachgewiesen werden.

Lineare Konvergenz

Satz 1: Sei $f$ einmal stetig differenzierbar, $\xi$ eine Nullstelle von $f$. Sei $g$ ebenfalls einmal stetig differenzierbar mit $g(\xi )f'(\xi )\,\in \,(0,5;1,5)$. Dann gibt es eine Umgebung $I$ von $\xi$, so dass die Iteration $x_{n+1}:=N(x_{n}):=x_{n}-g(x_{n})f(x_{n})$ für jeden Startpunkt $x_{0}$ aus $I$ gegen $\xi$ konvergiert.

Bemerkungen:

1. $g(\xi )$ kann also von der Inversen der Ableitung abweichen.
2. Dieser Satz ist nicht-konstruktiv, d.h. er enthält keine Aussage darüber, wie dieses Intervall um die Nullstelle zu finden ist.
3. Vorausgesetzt, $x_{0}$ liegt nahe genug an der Nullstelle, kann konstant $g(x)=f'(x_{0})^{-1}$ gewählt werden.
4. Eine besonders große Schrittweite ergibt sich bei $g(x)=3/2f'(x)^{-1}$, eine besonders kleine bei $g(x)=1/2f'(x)^{-1}$. Die große Schrittweite erweist sich bei fast linearen Funktionen $f$ als günstig, eine eher kleine Schrittweite bei dicht beieinanderliegenden oder mehrfachen Nullstellen.

Beweis: Wegen der Stetigkeit von N'(x)=1-g'(x)f(x)-g(x)f'(x) und wegen |N'(ξ)|<0,5 laut Voraussetzung gibt es ein r>0, so dass -0.75 ≤ N'(x) ≤ 0.75 für alle Stellen x aus dem Intervall I:=[ξ-r,ξ+r] gilt. (q=0.75 als Beispiel eines q∈(0,5; 1) ) Wählen wir den Startwert x0∈I in diesem Intervall, so liegt auch jedes nachfolgende Glied der Folge in diesem Intervall. Denn mit xn∈I folgt aus den Fixpunkteigenschaften und dem Mittelwertsatz der Differentialrechnung: $x_{n+1}-\xi =N_{f}(x_{n})-N_{f}(\xi )=N'_{f}(x_{n}^{*})\cdot (x_{n}-\xi )$ mit einem Zwischenpunkt xn* zwischen xn und ξ, $\Longrightarrow |x_{n+1}-\xi |\leq {\frac {3}{4}}|x_{n}-\xi |\leq {\frac {3}{4}}r$. Wir lesen daraus nicht nur ab, dass auch xn+1∈I gilt, sondern sogar, dass die Differenzfolge (xn-ξ) eine Nullfolge mit geometrischer Majorante ist: $|x_{n}-\xi |\leq \left({\frac {3}{4}}\right)^{n}|x_{0}-\xi |$.

Diese Art der Konvergenzgeschwindigkeit nennt man linear (im Exponenten).

Ist $f$ zweimal stetig differenzierbar und $f'(\xi )\neq 0$, so ergibt sich die lokale Konvergenz des Newton-Verfahrens für die spezielle Wahl $g(x)=f'(x)^{-1}$. Dann kann allerdings auch eine bessere Abschätzung des Konvergenzverhaltens angegeben werden.

Quadratische Konvergenz

Satz 2: Sei $f$ zweimal stetig differenzierbar und $\xi$ eine Nullstelle von $f$. Dann gibt es eine Konstante $K>0$, so dass die Newton-Iteration mit Startpunkt im Intervall $I=(\xi -1/K,\xi +1/K)$ gegen $\xi$ konvergiert, genauer gilt $|x_{n}-\xi |\leq K/2|x_{n-1}-\xi |^{2}\leq (0,5)^{2^{n}-1}|x_{0}-\xi |$.

Näherungsweise gilt $x_{n+1}\approx \xi +{\frac {1}{2}}\cdot {\frac {f''(\xi )}{f'(\xi )}}\cdot (x_{n}-\xi )^{2}$ und damit $K\approx |f(\xi )/f'(\xi )|$.

Beweis: Die Ableitung N'f(x) bestimmt sich mit der Quotientenregel des Differenzierens zu: $N'_{f}(x)=1-{\frac {f'(x)f'(x)-f(x)f''(x)}{f'(x)^{2}}}={\frac {f(x)f''(x)}{f'(x)^{2}}}$. Ist die Funktion f "gutartig" oder das Intervall I "klein genug", so sind die Ableitungen f'(x) und f"(x) fast konstant auf I, der Funktionswert f(x) jedoch nahezu linear mit Nullstelle in ξ und Anstieg f'(ξ). Wir können also (wieder mit dem Mittelwertsatz) einen weiteren Faktor (x-ξ) aus f(x)=f(x)-f(ξ) abspalten: $N'_{f}(x)={\frac {f''(x)}{f'(x)^{2}}}\cdot (f(x)-f(\xi ))={\frac {f''(x)}{f'(x)^{2}}}f'(x^{*})\cdot (x-\xi )$ mit einem Zwischenpunkt x* zwischen x und ξ. Für x nahe ξ gilt damit näherungsweise $N'_{f}(x)\approx {\frac {f''(\xi )}{f'(\xi )}}\cdot (x-\xi )$, Integration von ξ bis x ergibt $N_{f}(x)=N_{f}(\xi )+\int _{\xi }^{x}N'_{f}(z)\,dz\approx \xi +{\frac {f''(\xi )}{2f'(\xi )}}\cdot (x-\xi )^{2}$. Dies entspricht der Behauptung über das näherungsweise Konvergenzverhalten. Je kleiner das Intervall I ist, desto besser wird durch diese Näherung die Konvergenz beschrieben.

Um zu einer exakten Abschätzung der Konvergenzgeschwindigkeit zu gelangen, können wir die zwei "komplizierten" Faktoren in N'f(x) gegen ihre Maxima über I abschätzen: $|N'_{f}(x)|\leq \max _{x\in I}{\frac {f''(x)}{f'(x)^{2}}}\cdot \max _{x^{*}\in I}|f'(x^{*})|\cdot |x-\xi |=K\cdot |x-\xi |$. Dabei wurde mit K die Konstante, die das Produkt der beiden Maxima ist, bezeichnet. Wir erhalten für die Rekursionsfolge der Newton-Iteration die folgenden Abschätzungen (dabei sei hn:=xn-ξ) $x_{n+1}-\xi =N_{f}(x_{n})-N_{f}(\xi )=\int _{0}^{1}N'_{f}(\xi +th_{n})h_{n}\,dt$, $\Longrightarrow |x_{n+1}-\xi |\leq \int _{0}^{1}K|(\xi +th_{n})-\xi |\cdot |h_{n}|\,dt=K|x_{n}-\xi |^{2}\int _{0}^{1}t\,dt={\frac {K}{2}}|x_{n}-\xi |^{2}$. Die rekursive Ungleichung $|h_{n+1}|\leq {\frac {K}{2}}|h_{n}|^{2}$ hat die Lösung $|h_{n}|=|x_{n}-\xi |\leq \left({\frac {K}{2}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |^{2^{n}}=\left({\frac {K|x_{0}-\xi |}{2}}\right)^{2^{n}-1}\cdot |x_{0}-\xi |$, wovon man sich mittels vollständiger Induktion überzeugt. Ist also K/2|x0-ξ|<1, so konvergiert die Folge (xn) mit quadratischer Konvergenzgeschwindigkeit gegen ξ.

Literatur

P. Deuflhard, A. Hohmann: Numerische Mathematik I. Eine algorithmisch orientierte Einführung. 3. überarbeitete und erweiterte Auflage. de Gruyter: Berlin, New York (2002) ISBN 3110171821

P. Deuflhard: "Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms". Series: Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin (2004), ISBN: 3-540-21099-7

J. M. Ortega, W. C. Rheinboldt: "Iterative Solution of Nonlinear Equations in Several Variables". Classics in Applied Mathematics, SIAM (2000), ISBN: 0-898-71461-3

Weblinks

• Facharbeit über das Newtonsche Näherungsverfahren und die Regula Falsi

• Newton-Verfahren interaktiv

• [1] Xavier Gourdon: Newton's method and high order iterations, fehlerfreie Darstellung in der Postscript-Datei.

• [2] J. H. Hubbard, D. Schleicher, S. Sutherland: How to Find All Roots of Complex Polynomials by Newton's Method Preprint (2000), Inventiones Mathematicae vol. 146 (2001)