Newtonsches Näherungsverfahren
Mit dem Newtonschen Näherungsverfahren (benannt nach Isaac Newton, auch Newton-Raphsonsche Methode) lassen sich Näherungswerte der Gleichung f(x)=0, d.h. Näherungen der Nullstellen dieser Funktion finden. Dazu konstruiert man sich die Fixpunktgleichung wie folgt (keine vollständige Herleitung eher eine Veranschaulichung):
Man erhält dann folgende Iterationsgleichung:
Table of contents |
2 Konvergenz 3 Geometrische Deutung 4 Das Verfahren im Mehrdimensionalen 5 Abbruchkriterien 6 Anwendungen 7 Weblinks |
Es muss anfänglich ein Näherungswert x0 bekannt sein. Die Funktion f(x) muss in jedem Punkt der Ausgangsmenge differenzierbar sein. Das heißt für f(x) muss dort die Ableitung f'(x) existieren. Weiterhin muss gelten, dass f'(x) stetig invertierbar ist. Das heißt die Funktion von x0 darf bis zur anzunähernden Nullstelle keine Extrema oder Sattelpunkte besitzen, da dort die Ableitung f'(x) gegen 0 ginge.
Diese Voraussetzung:
Sei differenzierbar mit
ist zum Beispiel erfüllt, wenn f streng monoton steigend.
Das Newton Verfahren ist ein so genanntes lokal konvergentes Verfahren. Konvergenz zu einer Nullstelle ist also nur garantiert, wenn der Startwert hinreichend nah an der Nullstelle liegt. Ist der Startwert zu weit weg, kann alles passieren: das Verfahren divergiert, es konvergiert trotzdem oder, falls die Funktion mehrere Nullstellen hat, ist es auch möglich, dass das Verfahren eine andere als die gewünschte Nullstelle findet.
Bei geeigneter Wahl des Startwertes x0 kann das Newtonsche Verfahren quadratisch, also mit der Konvergenzordnung 2, konvergieren.
Das Newton-Verfahren kann auch benutzt werden, um Nullstellen von mehrdimensionalen Funktionen zu bestimmen. Ausgangspunkt der Iteration ist wieder die obige Fixpunktgleichung:
die das Newton-Verfahren inspiriert:
wobei f'(x) die Jacobi-Matrix, also die Matrix der partiellen Ableitungen von f(x), ist. Da die Berechnung der Inversen einer Matrix sehr aufwändig ist, wird auf die Aufstellung von verzichtet und statt dessen folgender Weg gewählt:
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.
Mögliche Abbruchkriterien bezüglich einer Restgröße (zum Beispiel Rechner-Arithmetik) sind:
In beiden Fällen kann es vorkommen, dass das Abbruchkriterium zu einem "schlechten" Zeitpunkt erfüllt ist.
Ein Spezialfall des Newtonschen Näherungsverfahrens ist das Babylonische Wurzelziehen, auch bekannt als Heronverfahren:
Wendet man die Iterationsformel auf die Funktion
Anfangsbedingungen
Konvergenz
Geometrische Deutung
lässt sich geometrisch als die Nullstelle der Tangente durch den Punkt P(; f()) deuten:
Bemerkungen
Um alle Nullstellen zu finden, muss man das Newtonverfahren mehrmals mit verschiedenen Startwerten durchführen.
Satz von Kantorovich.
Das Newtonverfahren ist also zur Lösung von fast beliebigen nichtlinearen Gleichungen geeignet.Das Verfahren im Mehrdimensionalen
Abbruchkriterien
Anwendungen
Berechnung der Quadratwurzel
an, dann erhält man die für die Lösung das Näherungsverfahren
Diese Verfahren konvergiert für jeden beliebigen Anfangswert x0.