Newton-Verfahren
Das Newton-Verfahren (auch Newton-Raphson-Verfahren) gehört zu den mathematischen Standardverfahren zur numerischen Lösung nichtlinearer Gleichungen und Gleichungssysteme. Es kann beispielsweise verwendet werden, um näherungsweise die Nullstellen einer gegebenen reellen Funktion $f: \R \rightarrow \R$ zu bestimmen.
Das Newton-Verfahren ist nach Sir Isaac Newton benannt.
Definition
Gegeben seien eine stetig differenzierbare Funktion $f: \R \rightarrow \R$, die erste Ableitung $f': \R \rightarrow \R$ dieser Funktion sowie eine Stelle $x_0 \in \R$, die in der Nähe
einer Nullstelle von $f$ liegt.
Mithilfe der Folge $ {(x_n)}_{n \in \N}$ mit
können schrittweise verbesserte Näherungslösungen der Nullstelle berechnet werden, falls die Folge $(x_n)$ konvergiert. Divergiert die Folge $(x_n)$, so muss ein anderer, besser geeigneter
Startwert verwendet werden.
Beschreibung des Newton-Verfahrens
Gegeben seien eine stetig differenzierbare Funktion $f: \R \rightarrow \R$, die erste Ableitung $f': \R \rightarrow \R$ dieser Funktion sowie eine Stelle $x_0 \in \R$, die in der Nähe
einer Nullstelle von $f$ liegt.
Um einen besseren Näherungswert der Nullstelle von $f$ zu erhalten, wird die Funktion an der Stelle $x_0$ zunächst linearisiert, indem sie durch die Tangente im Punkt $(x_0, f(x_0))$ ersetzt wird. Anschließend kann der verbesserter Näherungswert $x_1$ bestimmt werden, indem der Schnittpunkt der Tangente mit der $x$-Achse bestimmt wird. Nach demselben Schema können weitere verbesserte Näherungswerte $x_2, x_3, \ldots$ iterativ berechnet werden – das Berechnen des nächsten Näherungswerts wird hierbei als Newton-Iteration bezeichnet.
Die Werte $x_0, x_1, \ldots$ bilden hierbei eine Folge $ {(x_n)}_{n \in \N}$ mit den folgenden Eigenschaften:
- Falls die Folge $(x_n)$ konvergiert, so ist der Grenzwert $\lim\limits_{n \rightarrow \infty}{x_n}$ die gesuchte Nullstelle. In diesem Fall kann durch zusätzliche Iterationen eine beliebig genaue Näherungslösung für die Nullstelle gefunden werden.
- Falls die Folge $(x_n)$ divergiert, so ist der Startwert $x_0$ ungeeignet. In diesem Fall muss zur Bestimmung der Nullstelle ein
besserer
Startwert verwendet werden.
Herleitung der Rekursionsformel
Zur Berechnung des Näherungswerts $x_{n+1}$ wird die Funktion $f$ an der Stelle $x_n$ mithilfe der Tangente $T_n$ im Punkt $(x_n, f(x_n))$ linearisiert. Bei der Tangente $T_n$ handelt es sich um eine Gerade mit Anstieg $f'(x_n)$, d.h. es gilt
wobei $b$ eine unbestimmte Konstante ist. Die Tangente $T_n$ durchläuft insbesondere die beiden Punkte $(x_n, f(x_n))$ und $(x_{n+1}, 0)$. Es gilt
Aus der ersten Gleichung folgt direkt $b = f(x_n) - f'(x_n) \cdot x_n$. Einsetzen in die zweite Gleichung liefert:
Diese Gleichung kann nun nach $x_{n+1}$ aufgelöst werden:
Mithilfe dieser Rekursionsformel können die Näherungslösungen $x_1,x_2,\ldots$ direkt berechnet werden.
Beispiel
Mit dem Newton-Verfahren soll exemplarisch der Wert $\sqrt{2}$ berechnet werden. Hierzu wird zunächst die quadratische Funktion
aufgestellt, die die Nullstelle $\sqrt{2}$ besitzt. Als Rekursionsformel ergibt sich in diesem Fall
In der nachfolgenden Tabelle sind die ersten Iterationsschritte für verschiedene Startwerte aufgelistet. Es ist zu erkennen, dass bereits nach wenigen Schritten eine sehr gute Näherungslösung für $\sqrt{2}$ erreicht wird. Es ist außerdem zu erkennen, dass diese umso schneller erreicht wird, je näher der Startwert $x_0$ an der tatsächlichen Lösung liegt.
| $n$ | $x_0 = 2$ | $x_0 = 3$ | $x_0 = 5$ |
|---|---|---|---|
| $0$ | $2$ | $3$ | $5$ |
| $1$ | $1.5$ | $1.83333333333333\ldots$ | $2.7$ |
| $2$ | $1.41666666666666\ldots$ | $1.46212121212121\ldots$ | $1.72037037037037\ldots$ |
| $3$ | $1.41421568627450\ldots$ | $1.41499842989480\ldots$ | $1.44145536817765\ldots$ |
| $4$ | $1.41421356237468\ldots$ | $1.41421378004719\ldots$ | $1.41447098136777\ldots$ |
| $5$ | $1.41421356237309\ldots$ | $1.41421356237311\ldots$ | $1.41421358579688\ldots$ |
| $6$ | $1.41421356237309\ldots$ | $1.41421356237309\ldots$ | $1.41421356237309\ldots$ |
| $7$ | $1.41421356237309\ldots$ | $1.41421356237309\ldots$ | $1.41421356237309\ldots$ |
Anwendungsfälle
Berechnung der Quadratwurzel
Das Newton-Verfahren kann zur Berechnung der Quadratwurzel $\sqrt{a}$ verwendet werden, indem die Rekursionsformel auf die Funktion
angewendet wird, deren (positive) Nullstelle der gesuchte Wert $\sqrt{a}$ ist. Für die näherungsweise berechneten Nullstellen ergibt sich somit:
Dieses Verfahren konvergiert für jedes $a \geq 0$ und für jeden beliebigen Anfangswert $x_0 \gt 0$. (Hinweis: Wird ein Startwert $x_0 \lt 0$ verwendet, so konvergiert das Verfahren gegen die negative Nullstelle $-\sqrt{a}$).
Bei dieser speziellen Anwendung des Newton-Verfahrens handelt es sich um das Babylonische Wurzelziehen, das auch als das nach Heron von Alexandria benannte Heron-Verfahren bekannt ist.
Berechnung der Kubikwurzel
Das Newton-Verfahren kann zur Berechnung der Kubikwurzel $\sqrt[3]{a}$ verwendet werden, indem die Rekursionsformel auf die Funktion
angewendet wird, deren einzige Nullstelle der gesuchte Wert $\sqrt[3]{a}$ ist. Für die näherungsweise berechneten Nullstellen ergibt sich somit:
Dieses Verfahren konvergiert für jedes $a$ und für jeden beliebigen Anfangswert $x_0 \neq 0$. Für negative Werte von $a$ empfiehlt sich zudem die Umrechnung $\sqrt[3]{a} = -\sqrt[3]{-a}$.
Berechnung der n-ten Wurzel
Das Newton-Verfahren kann analog zu den vorherigen Fällen zur Berechnung der Wurzel $\sqrt[m]{a}$ beliebigen Grades verwendet werden, indem die Rekursionsformel auf die Funktion
angewendet wird, die garantiert die Nullstelle $\sqrt[m]{a}$ besitzt. Für die näherungsweise berechneten Nullstellen ergibt sich somit:
Bezüglich der Konvergenz des Verfahrens gelten analoge Hinweise wie bei den vorausgehenden Fällen:
- Für gerade Wurzelexponenten $m$ konvergiert das Verfahren für jedes $a \geq 0$ und für jeden beliebigen Anfangswert $x_0 \gt 0$ gegen die positive Lösung $\sqrt[m]{a}$. Für $x_0 \lt 0$ konvergiert das Verfahren gegen die negative Lösung.
- Für ungerade Wurzelexponenten $m$ konvergiert das Verfahren für jedes $a$ und für jeden beliebigen Anfangswert $x_0 \neq 0$. Besitzt der Startwert $x_0$ dasselbe Vorzeichen wie der Wert $a$, so konvergiert das Verfahren oftmals schneller.
Schnittpunkt zweier Funktionen
Das Newton-Verfahren kann zur Berechnung der $x$-Werte des Schnittpunkte zweier Funktionen $f(x)$ und $g(x)$ verwendet werden, indem die Nullstellen der Funktion $f(x)-g(x)$ berechnet werden: