Newton-Verfahren-Simulation

Über dieses Experiment

Die meisten Gleichungen lassen sich nicht mit einer Formel lösen, und doch berechnet ein Taschenrechner √2 oder die Nullstelle von cos x = x augenblicklich. Ein Grund dafür ist das Newton-Verfahren: Ausgehend von einem Schätzwert folgt man der Tangente bis zur x-Achse und nimmt deren Schnittpunkt als nächsten Schätzwert. In der Nähe einer einfachen Nullstelle verdoppelt sich die Anzahl der korrekten Stellen ungefähr bei jedem Schritt. Beobachte, wie es funktioniert, und dann, wie es scheitert: doppelte Nullstellen, waagerechte Tangenten, Zyklen, Divergenz und die fraktalen Einzugsgebiete, die es in der komplexen Ebene zeichnet.

Lernziele

Leite die Newton-Iteration aus der Gleichung der Tangente her
Erkenne die quadratische Konvergenz in einer Fehlerwerttabelle
Erkläre, warum die Konvergenz an einer mehrfachen Nullstelle linear wird
Gib Beispiele an, bei denen das Newton-Verfahren versagt: horizontale Tangenten, Zyklen und Divergenz
Beschreibe die Einzugsgebiete und erkläre, warum ihre Grenzen in der komplexen Ebene fraktal sind

Anleitung

1Betrachte x² − 2 mit x₀ = 3, führe das Verfahren Schritt für Schritt durch und beobachte die Ziffernspalte. Wie schnell wächst ungefähr die Anzahl der korrekten Ziffern?
2Zeige, dass sich für f(x) = x² − a die Iteration zu x_{n+1} = (x_n + a/x_n)/2 vereinfacht, dem babylonischen Verfahren.
3Wähle (x − 1)²(x + 2) und starte bei 2.5. Vergleiche die Fehler von einem Schritt zum nächsten mit dem Fall einer einfachen Nullstelle. Wie lautet der Quotient?
4Wähle x³ − 2x + 2 und starte genau bei 0. Was passiert? Starte nun bei 0.1 oder −0.5.
5Wähle arctan x. Bestimme mit zwei Dezimalstellen den größten Startwert, für den das Verfahren noch konvergiert.
6Wechsle mit z³ − 1 zur komplexen Ebene. Stelle dir vor, du zoomst in eine Grenze zwischen zwei Farben hinein: Warum gibt es dort immer Punkte der dritten Farbe?

Das Modell

y = f (x_{n}) + f^{'} (x_{n}) (x - x_{n}) = 0 \Rightarrow x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}

Der nächste Näherungswert ist der Schnittpunkt der Tangente mit der x-Achse

e_{n + 1} \approx \frac{f ^{''} ( r )}{2 f ^{'} ( r )} e_{n}^{2}

Quadratische Konvergenz in der Nähe einer einfachen Nullstelle r

e_{n + 1} \approx \frac{m - 1}{m} e_{n}

Lineare Konvergenz in der Nähe einer Nullstelle der Vielfachheit m

p \approx \frac{ln ( e _{n + 1} / e _{n} )}{ln ( e _{n} / e _{n - 1} )}

Geschätzte Konvergenzordnung anhand von drei Fehlerwerten

Annahmen

Die Berechnungen erfolgen mit doppelter Genauigkeit, also etwa 16 signifikanten Stellen. Daher nimmt der Fehler ab etwa 10^−16 nicht weiter ab.
Der Fehler ist der Abstand zur nächstgelegenen exakten Nullstelle, die für jede dargestellte Funktion bekannt ist.
Das Verfahren wird beendet, wenn die Tangente waagerecht ist, wenn |x| größer als 10^6 wird oder nach 40 Schritten.
In der komplexen Ebene wird ein Startpunkt entsprechend der Nullstelle eingefärbt, die er innerhalb von 50 Schritten erreicht; je mehr Schritte er benötigt, desto dunkler die Farbe. Punkte, die ihr Ziel nie erreichen, werden fast schwarz dargestellt.

Im Unterricht ausprobieren

Q1Führe von x₀ = 2 aus zwei Newton-Schritte aus, um die Kubikwurzel von 10 näherungsweise zu bestimmen.
Q2Warum muss f′(x) in der Nähe der Nullstelle ungleich null sein, damit das Newton-Verfahren gut funktioniert?
Q3Bestimme die Newton-Iteration für f(x) = 1/x − a. Warum ist sie für Computer nützlich, die nicht dividieren können?
Q4Zeige für f(x) = x^(1/3), dass x_{n+1} = −2x_n gilt. Was bedeutet das für jeden Startwert?
Q5Vergleiche das Newton-Verfahren mit dem Bisektionsverfahren: Welches benötigt weniger Schritte, um 10 korrekte Ziffern zu erreichen, und bei welchem ist der Erfolg garantiert?

Häufig gestellte Fragen

Warum heißt es Newton-Raphson-Verfahren?

Isaac Newton beschrieb 1669 eine Version für Polynome, bei der das Polynom in jedem Schritt neu geschrieben wurde. Joseph Raphson veröffentlichte 1690 die einfachere iterative Form, und Thomas Simpson gab 1740 die allgemeine Version der Infinitesimalrechnung an.

Wie vermeiden praktische Lösungsverfahren die hier gezeigten Fehlschläge?

Sie kombinieren das Newton-Verfahren mit einem sicheren Verfahren wie der Bisektion (wie beim Brent-Verfahren), verkürzen den Schritt, wenn dadurch der Funktionswert steigen würde (gedämpftes Newton-Verfahren oder Liniensuche), oder beginnen mit einer guten Schätzung, die auf andere Weise ermittelt wurde.

Wo wird das Newton-Verfahren eingesetzt?

Bei der Berechnung von Quadratwurzeln und Kehrwerten in Hardware, beim Lösen nichtlinearer Gleichungen in den Ingenieur- und Naturwissenschaften, bei der impliziten Zeitintegration von Differentialgleichungen und bei der Optimierung, wo das Newton-Verfahren auf den Gradienten angewendet wird, um Minima zu finden.