Dies ist eine maschinelle Übersetzung; das englische Original ist maßgeblich. Original lesen
Das Newton-Verfahren kann seinen Fehler in jedem Schritt verdoppeln – und die Lösung war nur 0,01 entfernt
Beginnen Sie 0,01 von der Lösung entfernt. Zwanzig Schritte später befinden Sie sich bei −5.242,88, und jeder Schritt wurde korrekt berechnet.
Lösen Sie x³ − x − 2 = 0. Da es dafür keine einprägsame Formel gibt, macht man das, was jede Numerik-Software tut: Man rät und lässt das Newton-Verfahren diesen Schätzwert korrigieren.
Man beginnt bei 1,5. Drei Iterationen später erhält man 1,52138, und der dort ausgewertete Funktionswert beträgt 5,89387 × 10⁻⁷ — weniger als ein Millionstel von null entfernt. Drei Schritte. Jeder Schritt verdoppelt ungefähr die Anzahl korrekter Nachkommastellen; deshalb steckt dieses Verfahren in Ihrem Taschenrechner, Ihrer CAD-Software und dem Solver Ihrer Tabellenkalkulation.
Nun verlangen Sie von ihm etwas Einfacheres. Lösen Sie ∛x = 0.
Sie kennen die Antwort. Sie lautet null, und sie ist die einzige. Starten Sie bei 0,01 — bereits bis auf ein Hundertstel nah dran — und beobachten Sie:
0,01 → −0,02 → 0,04 → −0,08 → 0,16 → −0,32 → 0,64 → −1,28 → 2,56 → …
Nach zwanzig Iterationen beträgt der Schätzwert −5242,88. Das Residuum, das bei 0,215 begann, liegt nun bei 17,37. Das Verfahren ist weder stecken geblieben noch abgekommen; es hat sich mit perfekter logischer Konsequenz von der Lösung entfernt, indem es in jedem einzelnen Schritt den Fehler verdoppelt und das Vorzeichen umgekehrt hat.
Nichts ist schiefgegangen
Die Versuchung ist groß, nach einem Fehler im Programm zu suchen. Es gibt keinen, und es lohnt sich, die Rechnung durchzugehen, weil sie so kurz ist.
Der Newton-Schritt lautet x − f(x)/f′(x). Für f(x) = x1/3 ist die Ableitung (1/3)x−2/3, folglich
f(x)/f′(x) = x1/3 ÷ ⅓x−2/3 = 3x
und der nächste Schätzwert lautet x − 3x = −2x. Nicht näherungsweise: exakt. Jede Iteration multipliziert den Schätzwert mit −2, von jedem beliebigen Startpunkt aus, für immer. Daher stammt −5242,88 — es ist 0,01 × (−2)19, und man kann die gesamte geometrische Folge in der Iterationstabelle im Newton's Method Explorer unter der Voreinstellung diverge ablesen.
Die Kubikwurzel hat die Voraussetzung verletzt, auf der das Verfahren beruht. Das Newton-Verfahren ersetzt die Kurve durch ihre Tangente und springt an die Stelle, an der diese Gerade die Nullstelle schneidet. In der Nähe einer Nullstelle ist das eine hervorragende Näherung — es ist das erste Glied der Taylor-Entwicklung, und die vernachlässigten Terme schrumpfen quadratisch, was genau der Grund für die Verdopplung der Stellen ist. Aber ∛x besitzt bei null eine senkrechte Tangente. Seine Ableitung wird dort nicht etwa klein, sondern unendlich, und die Kurve ist bei keiner Vergrößerung lokal gerade. Tangenten nahe null verlaufen fast senkrecht nach oben, sodass ihr Schnittpunkt mit der Achse fast dreimal so weit entfernt liegt wie der Startpunkt.
Beobachten Sie die beiden nebeneinanderliegenden Spalten in der Tabelle: f(x) wächst, während f′(x) gegen 0,001 schrumpft. Der Schritt ist ihr Quotient, sodass er gleich doppelt wächst.
Der zweite Fehlschlag ist schlimmer, weil er wie ein Erfolg aussieht
Divergenz kündigt sich zumindest an. Hier ist der Fall, der das nicht tut.
Betrachten wir f(x) = x³ − x mit den Nullstellen −1, 0 und +1. Man startet bei 0,57. Das Verfahren konvergiert sauber, dreizehn Iterationen, Residuum 2,3 × 10⁻¹¹ — und die gelieferte Nullstelle ist −1.
Schauen wir uns an, wo 0,57 liegt. Es ist 0,43 von +1 und 1,57 von −1 entfernt. Zudem liegt es nur 0,57 von der Nullstelle bei null entfernt. Das Newton-Verfahren liefert die am weitesten entfernte Lösung zurück, nachdem es glatt an zwei näheren Nullstellen vorbeigeflogen ist, und meldet vollen Erfolg mit elf korrekten Nachkommastellen.
Startet man stattdessen bei 0,58: Fünfzehn Iterationen, und das Ergebnis ist +1.
Eine Änderung des Startwerts um ein Hundertstel, und der Solver landet am entgegengesetzten Ende der Funktion. Zwischen diesen beiden Startwerten liegt 1/√3 ≈ 0,5774, wo die Ableitung von x³ − x gleich null ist. Die Tangente ist dort waagerecht und schneidet die Achse weit entfernt; nähert man sich diesem Punkt von einer der beiden Seiten, ist der erste Schritt enorm und führt in entgegengesetzte Richtungen. Jede flache Stelle auf einer Kurve wirkt wie eine Abschussrampe, und der Bereich, in den man katapultiert wird, hat nichts mit räumlicher Nähe zu tun.
Diese Eigenschaft führt dazu, dass die Frage „Welche Nullstelle werde ich erhalten?“ im Allgemeinen unbeantwortbar ist. Für Polynome über den komplexen Zahlen nennt man die Mengen der Startwerte, die zu einer bestimmten Nullstelle führen, Einzugsgebiete, und ihre Grenzen sind fraktal: Beliebig nahe an einem Punkt, der zu einer Nullstelle konvergiert, liegt ein Punkt, der zu einer anderen konvergiert. Hubbard, Schleicher und Sutherland haben 2001 gezeigt, dass man dennoch eine endliche Menge von Startpunkten konstruieren kann, die garantiert jede Nullstelle eines gegebenen Polynoms findet — ein bedeutendes Ergebnis und ein Maß dafür, wie viel Arbeit hinter dem schlichten Satz „Verwenden Sie einfach das Newton-Verfahren“ verborgen liegt.
Was das für die praktische Anwendung bedeutet
Daraus ergeben sich drei praktische Konsequenzen, die alle drei auf dieser Seite sichtbar werden.
Erstens: Ein kleines Residuum ist keine Garantie. In dem Durchlauf unter diverge oben beträgt das Residuum 17,37 und steigt weiter, sodass dieser Fall erkannt wird. Aber beim Startwert 0,57 liegt das Residuum bei 2 × 10⁻¹¹ und das Ergebnis ist eine völlig korrekte Nullstelle — nur eben nicht diejenige, die man gesucht hat. Konvergenztests können zeigen, dass man eine Lösung gefunden hat. Nichts im Verfahren kann einem sagen, ob es die Lösung ist.
Zweitens: Obergrenzen für die Iterationszahl sind essenziell. Der Explorer stoppt standardmäßig nach zwanzig Schritten; das ist der einzige Grund, warum der divergierende Durchlauf ein Ende nimmt, anstatt einen Überlauf zu erzeugen. Solver in der Praxis handhaben das genauso, und die Zahl ist keineswegs willkürlich: Eine funktionierende Newton-Iteration bei einer gutartigen Funktion erreicht in fünf bis zehn Schritten Maschinengenauigkeit. Was nach zwanzig Schritten immer noch läuft, konvergiert also nicht langsam — es konvergiert gar nicht.
Drittens: Die Abhilfe für einen schlechten Startwert ist meist kein besserer Algorithmus, sondern eine Intervallschachtelung. Das Bisektionsverfahren kann nicht divergieren — wenn die Funktion über einem Intervall das Vorzeichen wechselt, kann die Mittelpunktsregel dieses Intervall nicht verlassen — und es kann nicht die falsche Nullstelle wählen, weil sich nur eine einzige im Intervall befindet. Es ist lediglich langsam und gewinnt einen Bit pro Schritt, statt die Stellen zu verdoppeln. Die meisten praktischen Solver nutzen daher ein Hybridverfahren: Bisektion, bis der Schätzwert nachweislich nah genug liegt, und anschließend bringt Newton das Ergebnis in drei Schritten zu Ende. Man erhält die Geschwindigkeit dort, wo die Voraussetzungen gelten, und die Garantie dort, wo sie es nicht tun.
Zur Benennung gibt es noch eine Anmerkung. Newtons eigenes Verfahren aus der Zeit um 1669 verwendete keine Ableitungen und wurde für Polynome als Folge von Substitutionen formuliert; Raphson vereinfachte es 1690; die heute gelehrte Form mit f′ und einer beliebigen differenzierbaren Funktion f stammt von Simpson aus dem Jahr 1740. Ypma hat diese Entwicklungsgeschichte 1995 lückenlos zurückverfolgt. Das Verfahren, das an der Kubikwurzel so lehrreich scheitert, ist eine Überarbeitung eines Rezepts aus dem siebzehnten Jahrhundert durch Mathematik des neunzehnten Jahrhunderts, und es gehört seitdem zum festen Werkzeugkasten der Numerik — weshalb man genau wissen sollte, wo seine Grenzen liegen.