Newtonverfahren

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):

$x-({f'(x)})^{-1}\cdot f(x)=x-\underbrace {({f'(x)})^{-1}\cdot 0} _{=0}=x$ $\Leftrightarrow x=x-{\frac {f(x)}{f'(x)}}:=F(x)\qquad \mathrm {Fixpunktgleichung}$

Man erhält dann folgende Iterationsgleichung:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}:=F(x_{n})\qquad \mathrm {Iterationsgleichung}$

Anfangsbedingungen

Es muss anfänglich ein Näherungswert x₀ 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 x₀ darf bis zur anzunähernden Nullstelle keine Extrema oder Sattelpunkte besitzen, da dort die Ableitung f'(x) gegen 0 ginge.

Diese Voraussetzung:

Sei $f:\mathbb {R} \rightarrow \mathbb {R}$ differenzierbar mit $f'(x)\neq 0\quad \forall \quad x\in [x_{1},x_{2}]\qquad (x_{1}\neq x_{2})$

ist zum Beispiel erfüllt, wenn f streng monoton steigend.

Konvergenz

Das Newton Verfahren ist ein sogenanntes 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 x₀ kann das Newtonsche Verfahren quadratisch, also mit der Konvergenzordnung 2, konvergieren.

Geometrische Deutung

$x_{n+1}$ lässt sich geometrisch als die Nullstelle der Tangente durch den Punkt P($x_{n}$; f($x_{n}$)) deuten:

Bemerkungen

• Schon bei Polynomen gibt es schon oft mehr als eine Nullstelle von f
  

Um alle Nullstellen zu finden, muss man das Newtonverfahren mehrmals mit verschiedenen Startwerten durchführen.

• Der Konvergenzbeweis basiert auf einer Taylor-Entwicklung, ist im mehrdimensionalen Fall allerdings technisch schwierig. Für den Fall wurde er zuerst von Leonid Kantorovich geführt.

Satz von Kantorovich.

• Jede Gleichung lässt sich in eine Nullstellenform bringen.

Das Newtonverfahren ist also zur Lösung von fast beliebigen nichtlinearen Gleichungen geeignet.

Das Verfahren im Mehrdimensionalen

Das Newton-Verfahren kann auch benutzt werden, um Nullstellen von mehrdimensionalen Funktionen $f(x):R^{n}\rightarrow R^{n}$ zu bestimmen. Ausgangspunkt der Iteration ist wieder die obige Fixpunktgleichung:

$x=x-f'(x)^{-1}f(x):=F(x)$

die das Newton-Verfahren inspiriert:

$x_{n+1}=x_{n}-f'(x_{n})^{-1}f(x_{n}),$

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 $f'(x)^{-1}$ verzichtet und statt dessen folgender Weg gewählt:

$f'(x_{n})\Delta x=-f(x_{n}),\qquad 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.

Abbruchkriterien

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

$\vert f(x_{n})\vert \approx 0\qquad \mathrm {oder} \qquad \vert x_{n+1}-x_{n}\vert \approx 0$

In beiden Fällen kann es vorkommen, dass das Abbruchkriterium zu einem "schlechten" Zeitpunkt erfüllt ist.

Anwendungen

Berechnung der Quadratwurzel

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

Wendet man die Iterationsformel auf die Funktion

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

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

$x_{n+1}:={1 \over 2}(x_{n}+{a \over x_{n}})$
Diese Verfahren konvergiert für jeden beliebigen Anfangswert x₀.

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$

Weblinks

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