Newtonverfahren

Grundidee und Iteration

Das Newtonverfahren, auch Newton-Raphson-Verfahren, ist ein häufig verwendeter Approximationsalgorithmus zur numerischen Lösung nichtlinearer Gleichungen und Gleichungssysteme. Bei einer stetig differenzierbaren Funktion f: R -> R sucht man Näherungen für Lösungen von f(x)=0, also für Nullstellen. Die Grundidee ist, die Funktion an einem aktuellen Näherungswert zu linearisieren: Man ersetzt sie dort durch ihre Tangente und nimmt die Nullstelle dieser Tangente als nächste, meist bessere Näherung.

Ausgehend von einem Startwert x_0 wird wiederholt gerechnet:

x_{n+1}=x_n - f(x_n)/f'(x_n).

Diese Vorschrift heißt Newtoniteration, die zugehörige Funktion N_f(x)=x-f(x)/f'(x) Newtonoperator. Wenn die Folge gegen einen Grenzwert xi konvergiert, dann gilt xi=N_f(xi), also f(xi)=0. Das Verfahren ist damit eine spezielle Fixpunktiteration. Praktisch wichtig ist die Wahl eines geeigneten Startwerts x_0: Liegt er günstig, konvergiert das Verfahren sehr schnell; liegt er ungünstig, kann es scheitern oder zu einer anderen Nullstelle führen.

Geometrische Herleitung und Startwerte

Geometrisch betrachtet wählt man zu einem Punkt P(x_n; f(x_n)) auf dem Graphen die Tangente mit Steigung f'(x_n). Die Tangente hat die Form

t(x)=f(x_n)+f'(x_n)(x-x_n).

Ihre Nullstelle wird als neuer Näherungswert x_{n+1} benutzt. Aus 0=t(x_{n+1}) folgt genau die Iterationsformel x_{n+1}=x_n-f(x_n)/f'(x_n).

Viele nichtlineare Gleichungen besitzen mehrere Lösungen. Ein Polynom n-ten Grades kann bis zu n Nullstellen haben. Will man in einem Bereich D alle Nullstellen finden, muss zu jeder Nullstelle ein passender Startwert gefunden werden, für den die Newtoniteration dorthin konvergiert. Dazu kann man zum Beispiel vorher mit Bisektion kleine isolierende Intervalle zu den einzelnen Nullstellen bestimmen.

Konvergenz und mögliche Fehler

Das Newtonverfahren ist lokal konvergent. Das bedeutet: Konvergenz zu einer Nullstelle ist nur garantiert, wenn der Startwert schon ausreichend nahe an dieser Nullstelle liegt. Ist der Startwert zu weit entfernt, kann die Folge divergieren, zwischen Werten oszillieren oder gegen eine andere Nullstelle konvergieren.

Wenn das Verfahren bei einer einfachen Nullstelle konvergiert, also an einer Nullstelle a mit f'(a) != 0, dann ist die Konvergenz im günstigen Fall quadratisch, mit Konvergenzordnung 2. Anschaulich heißt das: Die Anzahl gültiger Stellen verdoppelt sich ungefähr in jedem Schritt. Im Artikel wird dies über die Abschätzung

|N_f(x)-a| <= (M_2/(2m_1)) |x-a|^2

beschrieben, wobei m_1 eine untere Schranke für |f'(x)| und M_2 eine obere Schranke für |f''(x)| in einem Intervall um a ist. Mit K=M_2/(2m_1) folgt unter passenden Voraussetzungen K|x_n-a| <= (K|x_0-a|)^{2^n}.

Bei mehrfachen Nullstellen wird das gewöhnliche Newtonverfahren langsamer. Hat f bei a eine k-fache Nullstelle, f(x)=(x-a)^k g(x) mit g(a) != 0, dann kann der Fehler ohne Änderung nur ungefähr mit einem Faktor 1-1/k kleiner werden. Für k=2 wird der Abstand zur Nullstelle etwa halbiert, für k=3 beträgt der Faktor etwa 0,67. Mit der modifizierten Formel

x_neu = x - k f(x)/f'(x)

kann man wieder quadratische Konvergenz erreichen.

Nicht-Konvergenz und Abbruch

Das Verfahren kann auch nicht konvergieren. Für f(x)=x^3-2x+2 mit f'(x)=3x^2-2 entsteht bei den Startwerten 0 und 1 ein Zyklus: N(0)=1 und N(1)=0. Die Folge wechselt also periodisch zwischen 0 und 1. Dieser Zyklus ist stabil, weil auch Startwerte aus gewissen Umgebungen gegen diesen Zyklus laufen.

Ein Beispiel für Divergenz liefert f(x)=sin(x) mit f'(x)=cos(x) und N(x)=x-tan(x). Es gibt einen Startwert x_0=arctan(-2pi)=-1,412965136506737759... mit x_n=x_0+2pi n. Die Werte entfernen sich also immer weiter. Dieses Verhalten ist nicht stabil: Schon leichte Änderungen des Anfangswertes können eine andere Entwicklung erzeugen.

Als Abbruchkriterien werden häufig Restgrößen verwendet, etwa ||f(x_n)|| < epsilon_1 oder ||x_{n+1}-x_n|| < epsilon_2, wobei epsilon_1, epsilon_2 positive reelle Zahlen sind und die geforderte Qualität der Näherung festlegen. In beiden Fällen kann das Kriterium aber zu einem ungünstigen Zeitpunkt erfüllt sein, sodass die gefundene „Nullstelle“ schlecht sein kann.

Wichtige Anwendungen und Beispiele

Ein klassisches Beispiel ist die Berechnung von Wurzeln. Für die Quadratwurzel von a verwendet man die Funktion f(x)=x^2-a. Da f'(x)=2x gilt, ergibt sich das Heronverfahren

x_{n+1}=1/2 (x_n + a/x_n).

Dieses Verfahren konvergiert für jedes a >= 0 und jeden Anfangswert x_0 != 0. Für die Kubikwurzel von a nimmt man f(x)=x^3-a und f'(x)=3x^2. Daraus folgt

x_{n+1}=1/3 (2x_n + a/x_n^2).

Für negative Radikanden empfiehlt sich die Umrechnung mit cbrt(x)=-cbrt(-x). Das Verfahren konvergiert für a und x_0 != 0, wenn a und x_0 dasselbe Vorzeichen haben. Allgemein erhält man für die N-te Wurzel aus f(x)=x^N-a die Formel

x_{n+1}=x_n(1-N^{-1}) + a/(N x_n^{N-1}).

Das Newtonverfahren kann außerdem Extremwerte finden, indem man Nullstellen der ersten Ableitung sucht. Für f: R -> R lautet der Schritt dann x_{n+1}=x_n-f'(x_n)/f''(x_n). Auch Schnittpunkte zweier Funktionen f(x) und g(x) lassen sich bestimmen, indem man die Gleichung f(x)-g(x)=0 löst.

Ein konkretes Beispiel ist die positive Lösung von cos(x)=x^3. Man setzt f(x)=cos(x)-x^3 und f'(x)=-sin(x)-3x^2. Da cos(x)<=1 und x^3>1 für x>1 gilt, liegt die Nullstelle zwischen 0 und 1. Mit Startwert x_0=0,5 ergeben sich die Näherungen x_1≈1,11214163710, x_2≈0,909672693736, x_3≈0,867263818209, x_4≈0,865477135298, x_5≈0,865474033111, x_6≈0,865474033101 und x_7≈0,865474033102. Damit sind die ersten zwölf Ziffern der Nullstelle bekannt.

Mehrdimensionale und komplexe Varianten

Das Newtonverfahren lässt sich auf mehrdimensionale Funktionen f: R^n -> R^n übertragen. Statt einer gewöhnlichen Ableitung verwendet man die Jacobimatrix J(x), also die Matrix der partiellen Ableitungen. Aus der Taylorentwicklung f(x+h)=f(x)+J(x)h+O(||h||^2) ergibt sich die Iteration

x_{n+1}=x_n-(J(x_n))^{-1} f(x_n).

Da das Berechnen einer inversen Matrix aufwendig und numerisch ungünstig ist, löst man in der Praxis das lineare Gleichungssystem

J(x_n) Delta x_n = -f(x_n)

und setzt anschließend x_{n+1}=x_n+Delta x_n. Ist die Jacobimatrix in der Nullstelle invertierbar und in einer Umgebung der Nullstelle lipschitzstetig, so konvergiert das Verfahren lokal quadratisch.

Für komplexe Zahlen z wird entsprechend z_1=z_0-f(z_0)/f'(z_0) verwendet, wobei f holomorph ist. Schreibt man f(z)=u(x,y)+iv(x,y), gelten die Cauchy-Riemann’schen Differentialgleichungen u_x=v_y und v_x=-u_y. Die komplexe Iteration kann in Real- und Imaginärteil zerlegt werden und hängt geometrisch mit der Minimierung von |f(z)| zusammen.

Varianten versuchen vor allem, den Aufwand für Ableitungen zu verringern. Beim vereinfachten Newtonverfahren wird die Ableitung nicht in jedem Schritt neu berechnet; dadurch sinken die Kosten, aber die Konvergenz ist nicht mehr quadratisch, kann jedoch superlinear bleiben. Beim inexakten Newtonverfahren wird die Ableitung angenähert, zum Beispiel durch finite Differenzen; je schlechter diese Approximation ist, desto schlechter wird typischerweise die Konvergenz. Für nichtlineare partielle Differentialgleichungen gibt es Newton-Krylow-Verfahren, bei denen Krylow-Unterraum-Verfahren die linearen Gleichungssysteme lösen und matrixfreie Varianten über finite Differenzen möglich sind.