Dies ist eine maschinelle Übersetzung; das englische Original ist die maßgebliche Fassung. Original lesen
Das Newton-Verfahren kann seinen Fehler in jedem Schritt verdoppeln – und das Ergebnis war 0,01 entfernt
Man beginnt 0,01 von der Lösung entfernt. Zwanzig Schritte später steht man bei −5.242,88 – und jeder Schritt war korrekt berechnet.
Zu lösen ist x³ − x − 2 = 0. Es gibt keine handliche Formel, die zu merken sich lohnte; man tut also, was jede numerische Software tut: Man schätzt einen Startwert und lässt ihn anschließend durch das Newton-Verfahren korrigieren.
Beginnt man bei 1,5, erhält man nach drei Iterationen 1,52138; der Funktionswert liegt dort bei 5,89387 × 10⁻⁷, also weniger als ein Millionstel von null entfernt. Drei Schritte. Jeder Schritt verdoppelt näherungsweise die Zahl der korrekten Stellen – genau deshalb steckt dieses Verfahren im Taschenrechner, im CAD-Programm und im Solver der Tabellenkalkulation.
Nun verlangt man von ihm etwas Einfacheres: Zu lösen ist ∛x = 0.
Die Antwort ist bekannt: Sie lautet null, und es ist die einzige. Man beginnt bei 0,01 – bereits auf ein Hundertstel nah dran – und beobachtet:
0,01 → −0,02 → 0,04 → −0,08 → 0,16 → −0,32 → 0,64 → −1,28 → 2,56 → …
Nach zwanzig Iterationen liegt der Näherungswert bei −5242,88. Das Residuum, das bei 0,215 begann, beträgt nun 17,37. Das Verfahren geriet weder ins Stocken noch ist es umhergeirrt; es hat sich mit vollkommener mathematischer Folgerichtigkeit von der Lösung entfernt, indem es in jedem einzelnen Schritt den Fehler verdoppelt und das Vorzeichen umgekehrt hat.
Nichts ist schiefgegangen
Die Versuchung liegt nahe, nach einem Programmierfehler zu suchen. Es gibt keinen, und die Rechnung lohnt sich, 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, also
f(x)/f′(x) = x1/3 ÷ ⅓x−2/3 = 3x
und der nächste Näherungswert lautet x − 3x = −2x. Nicht näherungsweise, sondern exakt. Jede Iteration multipliziert den Näherungswert mit −2, von jedem beliebigen Ausgangspunkt aus, für immer. Daher stammt der Wert −5242,88: Er entspricht 0,01 × (−2)19, und die gesamte geometrische Folge lässt sich in der Iterationstabelle im Newton's Method Explorer unter der Voreinstellung diverge ablesen.
Die Kubikwurzel verletzt schlichtweg die Annahme, auf der das Verfahren beruht. Das Newton-Verfahren ersetzt die Kurve durch ihre Tangente und springt dorthin, wo diese Gerade die Nullachse schneidet. In der Nähe einer Nullstelle ist das eine hervorragende Näherung: Es ist das lineare Glied der Taylor-Entwicklung, und die vernachlässigten Terme schrumpfen quadratisch – genau deshalb verdoppelt sich die Zahl der korrekten Stellen. Doch ∛x besitzt bei null eine senkrechte Tangente. Ihre Ableitung wird dort nicht bloß klein, sondern unendlich, und die Kurve ist bei keiner Vergrößerung lokal geradlinig. Tangenten nahe null verlaufen fast senkrecht nach oben, und der Schnittpunkt mit der Achse landet dennoch bei −2x: doppelt so weit von der Nullstelle entfernt wie der Ausgangspunkt, auf der gegenüberliegenden Seite.
Man betrachte die beiden nebeneinanderstehenden Spalten in der Tabelle: f(x) wächst, während f′(x) gegen 0,001 schrumpft. Die Schrittweite ist ihr Quotient und wächst somit gleich doppelt.
Das zweite Scheitern ist gravierender, weil es wie ein Erfolg aussieht
Eine Divergenz kündigt sich zumindest an.
Man betrachte f(x) = x³ − x mit den Nullstellen −1, 0 und +1. Startet man bei 0,57, konvergiert das Verfahren sauber: dreizehn Iterationen, Residuum 2,3 × 10⁻¹¹ – und die ausgegebene Nullstelle ist −1.
Man betrachte die Lage von 0,57: Der Wert ist 0,43 von +1 und 1,57 von −1 entfernt. Zudem liegt er nur 0,57 von der Nullstelle bei null entfernt. Das Newton-Verfahren liefert die am weitesten entfernte Nullstelle zurück, nachdem es an zwei näher gelegenen Nullstellen geradewegs vorbeigelaufen ist, und meldet vollen Erfolg mit elf korrekten Nachkommastellen.
Startet man nun stattdessen bei 0,58: Fünfzehn Iterationen, und das Ergebnis lautet +1.
Eine Änderung des Startwerts um ein Hundertstel, und der Löser landet am entgegengesetzten Ende der Funktion. Zwischen diesen beiden Startpunkten liegt 1/√3 ≈ 0,5774, wo die Ableitung von x³ − x gleich null ist. Die Tangente verläuft dort waagerecht und schneidet die Achse nirgends in der Nähe; nähert man sich diesem Punkt von der einen oder anderen Seite, fällt der erste Schritt gewaltig aus – in jeweils entgegengesetzte Richtungen. Jede flache Stelle einer Kurve wirkt wie eine Abschussrampe, und der Bereich, in den man geschleudert wird, hat nichts mit räumlicher Nähe zu tun.
Diese Eigenschaft macht die Frage „Welche Nullstelle werde ich erhalten?“ im Allgemeinen unbeantwortbar. Bei Polynomen über den komplexen Zahlen nennt man die Mengen der Startwerte, die zu einer bestimmten Nullstelle führen, Einzugsgebiete, und ihre Ränder sind fraktal: Beliebig nahe an einem Punkt, der zu einer Nullstelle konvergiert, liegt ein Punkt, der zu einer anderen konvergiert. Hubbard, Schleicher und Sutherland zeigten 2001, dass man dennoch eine endliche Menge von Startwerten konstruieren kann, die garantiert jede Nullstelle eines gegebenen Polynoms findet. Ein beachtliches Resultat – und ein Maß dafür, wie viel Arbeit hinter der scheinbar einfachen Anweisung „Verwende einfach das Newton-Verfahren“ im Stillen verborgen liegt.
Was dies für die praktische Anwendung bedeutet
Daraus ergeben sich drei praktische Konsequenzen, und die ersten beiden sind hier unmittelbar ersichtlich.
Erstens: Ein kleines Residuum ist keine Garantie. Im obigen Durchlauf mit der Voreinstellung diverge beträgt das Residuum 17,37 und steigt weiter an; dieser Fall fällt also auf. Doch beim Durchlauf mit 0,57 liegt das Residuum bei 2 × 10⁻¹¹, und das Ergebnis ist eine vollkommen einwandfreie Nullstelle – nur eben nicht diejenige, die gesucht war. Konvergenzkriterien können bestätigen, dass man eine Lösung gefunden hat. Nichts an dem Verfahren kann garantieren, dass es die gesuchte Lösung ist.
Zweitens: Begrenzungen der Iterationszahl sind von tragender Bedeutung. Der Explorer stoppt standardmäßig bei zwanzig Schritten, was der einzige Grund dafür ist, dass der divergente Durchlauf ein Ende findet statt eines Überlaufs. Produktiv eingesetzte Löser tun dasselbe, und die Zahl ist keineswegs willkürlich gewählt: Eine funktionierende Newton-Iteration auf einer gutartigen Funktion erreicht die Maschinengenauigkeit in fünf bis zehn Schritten. Alles, was nach zwanzig Schritten noch rechnet, konvergiert nicht langsam – es konvergiert überhaupt nicht.
Drittens: Die Abhilfe bei einem ungeeigneten Startwert ist meist kein besserer Algorithmus, sondern eine Intervallschachtelung. Eine Bisektion kann nicht divergieren – wechselt die Funktion über einem Intervall das Vorzeichen, kann das Verfahren dieses Intervall nicht verlassen – und sie kann nicht die falsche Nullstelle wählen, da sich im Intervall nur eine einzige befindet. Sie ist lediglich langsam: Sie gewinnt pro Schritt nur ein Bit hinzu, anstatt die Stellenanzahl zu verdoppeln. Die meisten praktischen Löser nutzen daher ein Hybridverfahren: Bisektion, bis der Näherungswert nachweislich nahe genug liegt, und anschließend drei abschließende Schritte mit dem Newton-Verfahren. Man erhält die Geschwindigkeit dort, wo die Voraussetzungen erfüllt sind, und die Absicherung dort, wo sie es nicht sind.
Es gibt noch eine historische Fußnote zum Namen. Newtons eigenes Verfahren aus der Zeit um 1669 verwendete keine Ableitungen und war für Polynome als Folge von Substitutionen formuliert; Raphson vereinfachte es im Jahr 1690; die heute gelehrte Form mit f′ und einer beliebigen differenzierbaren Funktion f stammt von Simpson aus dem Jahr 1740. Ypma zeichnete diese gesamte Entwicklungslinie 1995 nach. Was bei der Kubikwurzel so lehrreich versagt, ist eine Überarbeitung eines Rezepts aus dem 17. Jahrhundert durch das 18. Jahrhundert – und gehört seither zum festen Bestandteil der Numerik. Genau deshalb sollte man präzise wissen, wo seine Grenzen liegen.