Newton-Verfahren
Das Newton-Verfahren, das nach Sir Isaac Newton benannt ist, 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 Funktion $f: \R \rightarrow \R$ zu bestimmen.
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
der 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 man sie durch die Tangente im Punkt $(x_0, f(x_0))$ ersetzt. Anschließend kann der verbesserter Näherungswert $x_1$ bestimmt werden, indem man den Schnittpunkt der Tangente mit der $x$-Achse bestimmt. 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 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
Wendet man die Rekursionsformel zur Nullstellenberechnung auf die Funktion
an, so erhält man eine Näherungslösung für den Wert $\sqrt{a}$:
Dieses Verfahren konvergiert für jedes $a \geq 0$ und für jeden beliebigen Anfangswert $x_0 \neq 0$.
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
Wendet man die Rekursionsformel zur Nullstellenberechnung auf die Funktion
an, so erhält man eine Näherungslösung für den Wert $\sqrt[3]{a}$:
Dieses Verfahren konvergiert für jedes $a$ und für jeden beliebigen Anfangswert $x_0 \neq 0$, falls $a$ und $x_0$ dasselbe Vorzeichen besitzen. Für negative Werte von $a$ empfiehlt sich zudem die Umrechnung $\sqrt[3]{a} = -\sqrt[3]{-a}$.
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: