Newton-Verfahren Rechner (Newton-Raphson für Nullstellen)

Newton-Raphson-Rechner für Nullstellen: quadratische Konvergenz x_{n+1} = x_n - f(x_n)/f'(x_n), Polynome, trigonometrische Funktionen, sqrt(a)-Berechnung.

Berechnungsparameter
War dieser Rechner nützlich?

Newton-Raphson-Verfahren

Das Newton-Verfahren (oder Newton-Raphson) ist ein iterativer Algorithmus zum Finden reeller Nullstellen von Gleichungen f(x) = 0. Die Iterationsformel lautet x_{n+1} = x_n - f(x_n)/f'(x_n). Es ist einer der wichtigsten Algorithmen der numerischen Analysis.

Geometrische Idee

Bei einem Anfangswert x_n zeichnet man die Tangente an den Graphen von f im Punkt (x_n, f(x_n)). Der Schnitt dieser Tangente mit der x-Achse ergibt die nächste Iterierte x_{n+1}. Wenn f linear ist, genügt eine Iteration. Wenn f quadratisch nahe der Nullstelle ist, vervierfacht sich der Fehler bei jedem Schritt (quadratische Konvergenz).

Iterationsformel

x_{n+1} = x_n - f(x_n) / f'(x_n). Erfordert: (1) Ableitung f'(x), (2) f'(x*) != 0 an der Nullstelle (einfache Nullstelle). Wenn f'(x*) = 0 (mehrfache Nullstelle), nur lineare Konvergenz.

Quadratische Konvergenz

Wenn x* einfache Nullstelle von f und f'' stetig ist, existiert eine Umgebung von x* in der Newton quadratisch konvergiert: |x_{n+1} - x*| <= C |x_n - x*|^2 mit C = |f''(x*)/(2 f'(x*))|. Praktisch: Anzahl der korrekten Stellen verdoppelt sich bei jeder Iteration.

Beispiel: Berechnung von sqrt(a)

Für f(x) = x^2 - a erhält man x_{n+1} = (x_n + a/x_n) / 2 (Heron-Formel, 100 n. Chr.). Berechnung von sqrt(2) ab x0 = 1.5: 1.5 -> 1.41666 -> 1.41421568 -> 1.41421356... (4 Iterationen, 16 exakte Stellen).

Versagensfälle

  • Ableitung Null: wenn f'(x_n) = 0, Formel explodiert.
  • Anfangspunkt weit weg: Divergenz oder Sprung zu anderer Nullstelle.
  • Funktionen mit Spitzen oder Unstetigkeiten.
  • Zyklen: x_n+1 = -x_n (ständige Oszillation).
  • Chaotisches Becken bei komplexen Polynomen (Newton-Fraktale).

Vergleich mit anderen Verfahren

  • Bisektion: lineare Konvergenz, immer garantiert wenn f Vorzeichen wechselt.
  • Sekante: Ordnung phi ~ 1.618, ohne Ableitung.
  • Halley: Ordnung 3 (kubisch), erfordert f''(x).
  • Brent: adaptive Kombination aus Bisektion + Interpolation.

Newton in höheren Dimensionen

Für F: R^n -> R^n: x_{n+1} = x_n - J(x_n)^(-1) F(x_n) mit J Jacobi-Matrix. Quadratische Konvergenz wenn J an Lösung invertierbar. Verwendet in Optimierung, computergestützter Geometrie, Physik.

Newton-Fraktale

Für komplexe Polynome p(z) = 0 mit mehreren Nullstellen bildet das Einzugsgebiet jeder Nullstelle ein Fraktal in der komplexen Ebene. Klassisches Beispiel z^3-1: drei Becken mit 120-Grad-Symmetrie. Beckenränder sind Julia-Mengen. Spektakuläre Visualisierung mit Färbung nach Nullstelle.

Geschichte

Isaac Newton entwickelte die Methode 1669 für Polynome. Joseph Raphson definierte sie 1690 in allgemeiner Form um. Thomas Simpson verallgemeinerte sie 1740 auf nichtlineare Systeme. Vincent und Cauchy untersuchten die Konvergenz rigoros.

Das Konvergenzgebiet und die Wahl von x0

Die quadratische Konvergenz des Newton-Verfahrens ist eine lokale Eigenschaft: sie gilt nur, wenn der Startpunkt x0 nahe genug an einer einfachen Nullstelle liegt. Die Menge der Startpunkte, die zu einer gegebenen Nullstelle konvergieren, heisst ihr Einzugsgebiet, und fur Funktionen mit mehreren Nullstellen konnen diese Gebiete extrem komplexe Rander haben, die beruhmten Newton-Fraktale. Eine schlechte Wahl von x0 kann zur Konvergenz gegen eine andere als die gewunschte Nullstelle, zur Divergenz oder zu einem Zyklus fuhren.

Der Satz von Newton-Kantorowitsch liefert strenge hinreichende Bedingungen, die die Konvergenz garantieren: hat die Funktion in einer Umgebung von x0 eine beschrankte zweite Ableitung, verschwindet die erste Ableitung nicht und ist der erste Schritt klein genug, so konvergiert die Iteration gegen eine Nullstelle und der Fehler nimmt quadratisch ab. In der Praxis kombiniert man oft eine robuste Anfangsphase (etwa die Bisektion), um sich der Nullstelle zu nahern, gefolgt von Newton zur schnellen Verfeinerung des Ergebnisses.

Robuste Varianten: gedampftes Newton, hybrid und Halley

Um die Grenzen des reinen Verfahrens zu uberwinden, gibt es zahlreiche Varianten. Das gedampfte Newton fuhrt einen Schrittfaktor lambda in (0,1] ein, x_{n+1} = x_n - lambda f/f', verkleinert, bis der Betrag der Funktion abnimmt: dies globalisiert das Verfahren und vermeidet Divergenz, wenn x0 weit von der Nullstelle entfernt ist. Hybride Verfahren wie der Brent-Algorithmus wechseln zwischen Newton oder der Sekante und der Bisektion und sichern so sowohl globale Robustheit als auch lokale Geschwindigkeit.

Wird noch schnellere Konvergenz benotigt, verwendet das Halley-Verfahren auch die zweite Ableitung, x_{n+1} = x_n - 2 f f' / (2 f'^2 - f f''), und erreicht kubische Konvergenz (der Fehler geht wie die dritte Potenz des vorherigen). In hoheren Dimensionen wird Newton zum vektoriellen Newton-Raphson-Verfahren, bei dem man statt der Division durch die Ableitung ein lineares System mit der Jacobi-Matrix lost, das Herzstuck eines Grossteils der modernen numerischen Optimierung.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Was ist das Newton-Raphson-Verfahren?

Es ist ein iteratives Verfahren zur Bestimmung der Nullstellen einer Gleichung f(x)=0. Ausgehend von einer Schatzung x0 berechnet es sukzessive Naherungen mit der Formel x_{n+1} = x_n - f(x_n)/f'(x_n) entlang der Tangente an die Kurve. Es konvergiert sehr schnell, wenn x0 nahe einer einfachen Nullstelle liegt.

Was ist quadratische Konvergenz?

Sie bedeutet, dass sich die Zahl der korrekten Ziffern bei jeder Iteration etwa verdoppelt: der Fehler im Schritt n+1 ist proportional zum Quadrat des Fehlers im Schritt n. Diese aussergewohnliche Geschwindigkeit nahe einfacher Nullstellen ist der grosse Vorteil von Newton gegenuber linearen Verfahren wie der Bisektion.

Wann versagt das Newton-Verfahren?

Es versagt, wenn die Ableitung f'(x) verschwindet (Division durch null), wenn x0 zu weit von der Nullstelle entfernt ist (Divergenz), wenn die Iteration in einen Zyklus gerat oder nahe mehrfacher Nullstellen, wo es die quadratische Konvergenz verliert und nur noch linear ist. Dann verwendet man robustere Verfahren.

Wie wahlt man den Startpunkt x0?

Idealerweise nahe der gesuchten Nullstelle, innerhalb ihres Einzugsgebiets. Eine grafische Analyse oder eine anfangliche Bisektionsphase helfen, ein gutes x0 zu finden. Der Satz von Newton-Kantorowitsch liefert hinreichende Bedingungen, um die Konvergenz ab x0 zu garantieren.

Wie berechnet es eine Quadratwurzel?

Wendet man Newton auf f(x)=x^2-a an, erhalt man die Heron-Formel x_{n+1} = (x_n + a/x_n)/2, schon den alten Babyloniern bekannt. Sie konvergiert quadratisch fur jedes x0 > 0: zum Beispiel erreicht sqrt(2) 14 korrekte Ziffern in etwa 4-5 Iterationen ausgehend von 1,5.

Was sind Newton-Fraktale?

Es sind Bilder, die entstehen, wenn man jeden Punkt der Ebene danach farbt, welche Nullstelle das Newton-Verfahren von dort aus erreicht. Fur Funktionen mit mehreren Nullstellen haben die Grenzen zwischen den Einzugsgebieten eine fraktale, auf jeder Skala selbstahnliche Struktur von grosser visueller Schonheit.

Welchen Vorteil hat es gegenuber der Bisektion?

Die Bisektion konvergiert linear (etwa eine Ziffer alle 3-4 Iterationen), ist aber stets garantiert, wenn die Nullstelle eingeschlossen ist. Newton konvergiert quadratisch, viel schneller, ist aber nicht global garantiert. Oft kombiniert man beide: Bisektion zum Annahern, Newton zum Verfeinern.

Gibt es schnellere Verfahren als Newton?

Ja: das Halley-Verfahren nutzt auch die zweite Ableitung und konvergiert kubisch (verdreifacht die Ziffern bei jedem Schritt). Es gibt Verfahren noch hoherer Ordnung, doch sie erfordern mehr Ableitungen und Rechnung pro Iteration und lohnen sich daher nicht immer gegenuber der Einfachheit von Newton.

Kommentare (0)

Noch keine Kommentare. Sei der Erste!