Newton-Verfahren

Das Newton-Verfahren ist ein Rechenverfahren, mit dem du Lösungen einer Gleichung $f(x)=0$ näherungsweise findest. Eine solche Lösung heißt Nullstelle von f. Du brauchst es, wenn sich die Gleichung nicht auflösen lässt, zum Beispiel bei $x^3-2x-5=0$ oder bei $\cos x=x$.

Du startest mit einem geschätzten Wert und verbesserst ihn mit der Tangente der Funktion. Dieses wiederholte Verbessern heißt Iteration. Die Tangente ist eine Gerade, die den Graphen an einer Stelle berührt. Ihre Steigung ist die Ableitung $f\prime (x)$. Mit dem Ableitungsrechner kontrollierst du sie.

Die Idee mit der Tangente

Stell dir den Graphen von $f(x)=x^2-2$ vor. Seine Nullstelle $\sqrt{2}$ suchst du. Du rätst den Startwert $x_0=2$ und gehst auf der Kurve zum Punkt $P_0(2|f(2))$. Dort legst du die Tangente an. Die Kurve selbst ist krumm, die Tangente ist eine Gerade, und deren Nullstelle ist leicht zu finden. Sie liegt bei $x_1=\mathrm{1,5}$ und ist schon viel näher an $\sqrt{2}$ als $x_0$.

Mit $x_1$ wiederholst du alles: Punkt $P_1$ auf der Kurve, Tangente, Nullstelle der Tangente. So entsteht $x_2\approx \mathrm{1,4167}$. Die Werte $x_0,x_1,x_2,\dots$ rücken immer näher an die Nullstelle heran.

Die Formel

Die Tangente im Punkt $(x_n|f(x_n))$ hat die Steigung $f\prime (x_n)$. Ihre Gleichung ist

Für ihre Nullstelle setzt du $y=0$ und löst nach x auf. Aus $0=f(x_n)+f\prime (x_n)(x-x_n)$ folgt $x-x_n=-\frac{f(x_n)}{f\prime (x_n)}$. Diesen Wert nennst du $x_{n+1}$.

Das Minus passt zur Anschauung: Ist $f(x_n)$ positiv und die Kurve steigt, liegt die Nullstelle links von $x_n$, und du musst nach links gehen.

Beispiel: Die Wurzel aus 2

Du suchst $\sqrt{2}$ als Nullstelle von $f(x)=x^2-2$. Mit $f\prime (x)=2x$ lautet die Formel

Der neue Wert ist also der Mittelwert aus $x_n$ und $\frac{2}{x_n}$. Ist $x_n$ zu klein, ist $\frac{2}{x_n}$ zu groß, und der Mittelwert liegt dazwischen. Dieses Verfahren kennst du als Heron-Verfahren (siehe Wurzelziehen nach Heron). Es ist ein Sonderfall des Newton-Verfahrens.

Nach vier Schritten stimmen schon zwölf Nachkommastellen. Die Fehler schrumpfen sehr schnell: 0,086 wird zu 0,0025 und das zu 0,000002.

Newtons eigenes Beispiel

Isaac Newton führte das Verfahren um 1669 an der Gleichung $x^3-2x-5=0$ vor. Mit $f(x)=x^3-2x-5$ und $f\prime (x)=3x^2-2$ lautet die Formel

Als Startwert eignet sich $x_0=2$: Es ist $f(2)=-1$ und $f(3)=16$. Die Funktion wechselt zwischen 2 und 3 das Vorzeichen, also liegt dort eine Nullstelle.

Die Nullstelle ist $x\approx \mathrm{2,094551481542}$. Zur Probe: ${\mathrm{2,0945514815}}^3-2·\mathrm{2,0945514815}-5\approx 0$.

Warum so schnell? Quadratische Konvergenz

Schau auf die Spalte „Fehler“ der Tabelle: $\mathrm{9,5}·{10}^{-2}$, dann $\mathrm{5,4}·{10}^{-3}$, dann $\mathrm{1,7}·{10}^{-5}$, dann $\mathrm{1,6}·{10}^{-10}$. Die Zahl der richtigen Stellen verdoppelt sich ungefähr: 1, 2, 4, 9, 19. Das nennt man quadratische Konvergenz. Der neue Fehler ist etwa ein Vielfaches vom Quadrat des alten:

Dabei ist $e_n$ der Fehler im Schritt n und $x^{*}$ die gesuchte Nullstelle. Bei Newtons Beispiel ist $C\approx \mathrm{0,56}$: Es ist $\frac{\mathrm{1,66}·{10}^{-5}}{(\mathrm{5,45}·{10}^{-3}{)}^2}\approx \mathrm{0,56}$. Quadriert man eine kleine Zahl wie 0,005, wird sie winzig, und deshalb gewinnt jeder Schritt so viele Stellen.

Das gilt, wenn $f\prime (x^{*})\ne 0$ ist und der Startwert nah genug an der Nullstelle liegt. Bei einer doppelten Nullstelle wie $x^2=0$ ist die Konvergenz nur noch linear: Aus $f(x)=x^2$ folgt $x_{n+1}=\frac{x_n}{2}$, der Fehler wird in jedem Schritt nur halbiert.

Wann hörst du auf?

Die wahre Nullstelle kennst du nicht, also kannst du den Fehler nicht ausrechnen. Du brauchst ein Abbruchkriterium. Üblich ist:

• Der Abstand zweier Näherungen ist klein: $|x_{n+1}-x_n|<\epsilon$ mit einer Schranke $\epsilon$, zum Beispiel ${10}^{-6}$.
• Zusätzlich eine Höchstzahl an Schritten, damit die Rechnung bei Zyklen nicht ewig läuft.

Bei Newtons Beispiel sind die Schrittweiten $\mathrm{0,1}$, dann $\mathrm{5,4}·{10}^{-3}$, dann $\mathrm{1,7}·{10}^{-5}$ und dann $\mathrm{1,6}·{10}^{-10}$. Mit $\epsilon ={10}^{-6}$ hörst du nach dem vierten Schritt auf. Wegen der quadratischen Konvergenz ist $x_4$ dann sogar viel genauer als verlangt. Die Schrittweite ist nämlich ungefähr der Fehler des vorigen Wertes.

Vorsicht: Ein kleiner Funktionswert $|f(x_n)|$ allein beweist nicht, dass du nah an der Nullstelle bist, wenn die Kurve dort sehr flach verläuft.

Wann das Verfahren scheitert

Das Newton-Verfahren ist schnell, aber nicht narrensicher. Es gibt vier typische Probleme.

• Waagerechte Tangente: Ist $f\prime (x_n)=0$, gibt es keinen Schnittpunkt der Tangente mit der x-Achse, und die Formel verlangt eine Division durch null. Bei $f(x)=x^2-2$ funktioniert der Startwert 0 deshalb nicht. Auch ein sehr kleines $f\prime (x_n)$ wirft den nächsten Wert weit weg.
• Zyklus: Bei $f(x)=x^3-2x+2$ und dem Startwert 0 ergibt sich $x_1=1$ und danach wieder $x_2=0$. Das Verfahren pendelt für immer zwischen 0 und 1, die echte Nullstelle bei etwa $-\mathrm{1,77}$ findet es nie.
• Divergenz: Bei $f(x)=\sqrt[3]{x}$ mit der Nullstelle 0 gilt $x_{n+1}=-2x_n$. Aus dem Startwert 1 wird $-2$, dann $4$, dann $-8$. Die Werte laufen weg statt hin.
• Falsche Nullstelle: Hat f mehrere Nullstellen, landet das Verfahren bei einer, die vom Startwert abhängt, und nicht unbedingt bei der, die du suchst.

Vergleich mit der Intervallhalbierung

Ein zweites Verfahren, das du kennen solltest, ist die Intervallhalbierung (Bisektion). Du brauchst zwei Stellen $a$ und $b$ mit verschiedenem Vorzeichen von $f$. Dann liegt zwischen ihnen eine Nullstelle. Du berechnest die Mitte $m$ des Intervalls und behältst die Hälfte, an deren Rändern $f$ weiter das Vorzeichen wechselt. Jeder Schritt halbiert das Intervall.

Bei $x^3-2x-5$ auf $[2;3]$ ist die Länge nach n Schritten $2^{-n}$. Damit der Mittelpunkt garantiert höchstens ${10}^{-12}$ von der Nullstelle entfernt ist, braucht es 39 Halbierungen, denn $2^{-40}\approx \mathrm{9,1}·{10}^{-13}$. Das Newton-Verfahren schafft mehr als diese Genauigkeit in vier Schritten.

In der Praxis kombiniert man beide: Erst grenzt man die Nullstelle durch einige Halbierungen ein, dann verfeinert man mit dem Newton-Verfahren. Ist die Ableitung schwer zu berechnen, ersetzt man sie durch eine Sekantensteigung. Das heißt Sekantenverfahren und ist etwas langsamer.

Rechnen lässt sich das Verfahren auch mit dem Newton-Verfahren-Rechner, und der Gleichungslöser hilft bei Gleichungen, die sich exakt lösen lassen.

Typische Fehler

Übungen

Mehr Aufgaben findest du unter Newton-Verfahren: Aufgaben.

Geschichte: von Babylon bis Raphson

Die Grundidee ist viel älter als Newton. Schon die Babylonier benutzten es für Quadratwurzeln, und Heron von Alexandria beschrieb das Verfahren in seiner Metrika. Das ist der Sonderfall für Wurzeln, den du oben gerechnet hast.

Isaac Newton verallgemeinerte die Idee auf beliebige Polynome. Er schrieb sie 1669 in seiner Schrift De analysi auf, die erst 1711 gedruckt wurde. Seine Rechnung sah anders aus als unsere Formel: Er suchte nach jedem Schritt eine neue Gleichung für die Korrektur. Zum ersten Mal gedruckt wurde das Verfahren 1685 in der Algebra von John Wallis. Joseph Raphson veröffentlichte 1690 eine vereinfachte Fassung, bei der man die Korrektur direkt aus dem Polynom berechnet. Deshalb heißt es auch Newton-Raphson-Verfahren.

Die heutige Form mit der Ableitung $f\prime$ stammt von Thomas Simpson. Erst durch sie ließ sich das Verfahren auf beliebige differenzierbare Funktionen anwenden. Mehr zur Zeit, in der das alles entstand, steht unter Mathematik des 17. Jahrhunderts.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Newtonverfahren
• Wikipedia: Heron-Verfahren
• Wikipedia: Bisektion
• Wikipedia: Newtonfraktal
• Joseph Raphson: Analysis aequationum universalis, London 1690.
• MacTutor History of Mathematics: Isaac Newton (englisch)