Newtonverfahren

Das Newtonverfahren nähert eine Nullstelle von f, also eine Zahl r mit $f(r) = 0$, durch Wiederholung eines Schritts an. Am aktuellen Näherungswert $x_n$ betrachtet man die Tangente im Punkt $(x_n, f(x_n))$ mit der Gleichung $L(x) = f(x_n) + f'(x_n)(x - x_n)$. Nahe $x_n$ liegt sie dicht an der Kurve; ihr Schnittpunkt mit der x-Achse ist daher ein besserer Näherungswert für den Schnittpunkt der Kurve. Lösen von $L(x) = 0$ liefert den nächsten Näherungswert. Im Diagramm führt jeder Schritt entlang der blassen gestrichelten Linie von $x_n$ zur Kurve und dann entlang der Tangente zur Achse.

Der Fehler sei $e_n = x_n - r$. Ist r eine einfache Nullstelle ($f'(r) \ne 0$) und hat f eine stetige zweite Ableitung, liefert die Taylorentwicklung des Schritts $e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$, sobald $x_n$ nahe bei r liegt. Das Quadrieren des Fehlers verdoppelt ungefähr die Zahl korrekter Ziffern. Für x² − 2 ab x₀ = 1 sind die Fehler 0.086, 0.0025, 2.1 × 10⁻⁶ und 1.6 × 10⁻¹²; in der Anzeige nähert sich $e_n/e_{n-1}^2$ dem Wert $1/(2\sqrt2) \approx 0.354$. Weit von der Nullstelle gilt diese Garantie nicht. Wenn $f''(r) = 0$, fällt der quadratische Term weg und es geht noch schneller: Für arctan x beträgt der nächste Fehler etwa $-\tfrac23 e_n^3$, wird also bei jedem Schritt kubiert.

Der Schritt setzt $f'(x_n) \ne 0$ voraus. Eine waagerechte Tangente trifft die Achse nie, eine fast waagerechte erst weit entfernt: Bei x² − 2 ab 0.1 landet der erste Schritt bei 10.05. Das Verfahren kann auch scheitern, ohne davonzulaufen. Bei x³ − 2x + 2 trifft die Tangente bei 0 auf 1 und die bei 1 wieder auf 0. Startwerte nahe 0 werden zu diesem Zyklus hingezogen: Die Folge bleibt beschränkt, hat aber keinen Grenzwert. Für arctan x gibt es die Grenze α ≈ 1.3917, die Zahl mit $2\alpha = (1 + \alpha^2)\arctan\alpha$. Startwerte mit |x₀| < α konvergieren; außerhalb davon landet jeder Schritt weiter außen auf der anderen Seite. Alle Startwerte färbt die x-Achse nach dem jeweiligen Ziel ein. Bei x³ − 2x + 2 landet etwa ein Fünftel von [−3, 3] im Zyklus, darunter schmale Bänder, die sich nahe den Stellen mit waagerechter Tangente $\pm\sqrt{2/3}$ häufen. Mit komplexen Startwerten werden diese Bänder zum Newtonfraktal.

An einer mehrfachen Nullstelle gilt auch $f'(r) = 0$; die quadratische Fehlerabnahme geht verloren. Für $(x - 1)^2$ lautet der Schritt exakt $x_{n+1} = (x_n + 1)/2$, sodass sich der Fehler jedes Mal halbiert. Dies ist lineare Konvergenz: etwa 3.3 Schritte je zusätzlicher Dezimalstelle. Nahe einer Nullstelle der Vielfachheit m strebt das Verhältnis $e_{n+1}/e_n$ gegen $(m - 1)/m$.