Newton-Verfahren

Oberstufe

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

Voraussetzung: $f$ $differenzierbar$ $,$ $f'(x_n) \neq 0$

$x_n$: aktuelle Näherung für die Nullstelle
$x_{n+1}$: nächste, meist bessere Näherung
$f(x_n)$: Funktionswert an der Stelle xₙ
$f'(x_n)$: Ableitung (Tangentensteigung) an der Stelle xₙ

Das Newton-Verfahren nähert eine Nullstelle an, indem es immer zur Nullstelle der Tangente im aktuellen Punkt springt.

Erklärung

Das Newton-Verfahren berechnet Nullstellen näherungsweise, wenn man die Gleichung $f(x) = 0$ nicht exakt lösen kann. Man startet mit einem Startwert $x_0$ in der Nähe der Nullstelle. Dann legt man im Punkt $(x_n \mid f(x_n))$ die Tangente an den Graphen und nimmt deren Nullstelle als nächste Näherung $x_{n+1}$ . Das wiederholt man, bis sich die Werte in der gewünschten Genauigkeit nicht mehr ändern.

Die Formel ist die Nullstelle der Tangente $t(x) = f(x_n) + f'(x_n)(x - x_n)$ . Deshalb muss $f'(x_n) \neq 0$ sein, sonst verläuft die Tangente waagerecht und hat keine Nullstelle.

Liegt der Startwert nah genug an einer einfachen Nullstelle, konvergiert das Verfahren sehr schnell: Die Anzahl der richtigen Stellen verdoppelt sich ungefähr in jedem Schritt (quadratische Konvergenz). Bei schlechtem Startwert kann es aber zu einer anderen Nullstelle laufen, pendeln oder ganz versagen.

Beispiele

$\sqrt{2}$ als Nullstelle von $f(x) = x^2 - 2$ mit $f'(x) = 2x$ und $x_0 = 1$ :

\begin{aligned} x_1 &= 1 - \frac{1 - 2}{2} = 1{,}5 \\ x_2 &= 1{,}5 - \frac{2{,}25 - 2}{3} = \frac{17}{12} \approx 1{,}416667 \\ x_3 &= \frac{17}{12} - \frac{(17/12)^2 - 2}{2 \cdot 17/12} = \frac{577}{408} \approx 1{,}414216 \end{aligned}

Der genaue Wert ist $\sqrt{2} \approx 1{,}414214$ . Für $f(x) = x^2 - a$ vereinfacht sich der Schritt zu $x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right)$ , dem Heron-Verfahren.

Nullstelle von $f(x) = x^3 - x - 1$ mit $f'(x) = 3x^2 - 1$ und $x_0 = 1{,}5$ : Es ist $f(1{,}5) = 0{,}875$ und $f'(1{,}5) = 5{,}75$ , also

x_1 = 1{,}5 - \frac{0{,}875}{5{,}75} \approx 1{,}3478

Ein Fall, in dem das Verfahren versagt: $f(x) = x^3 - 2x + 2$ mit $x_0 = 0$ liefert $x_1 = 1$ und daraus wieder $x_2 = 0$ . Die Folge pendelt, obwohl $f$ bei etwa $-1{,}77$ eine Nullstelle hat.

Typische Fehler

Plus statt minus rechnen: $x_n + \frac{f(x_n)}{f'(x_n)}$ läuft von der Nullstelle weg.
$f$ und $f'$ im Bruch vertauschen.
Einen Startwert wählen, an dem $f'(x_0) = 0$ oder fast $0$ ist. Die Tangente ist dann (fast) waagerecht, $x_1$ liegt weit entfernt.
Aus wenigen Schritten auf Konvergenz schließen, ohne $f(x_n) \approx 0$ zu prüfen.

Newton-Verfahren