Newtons Verfahren: Nullstellen schnell finden mit iterativer Annäherung

Manche Gleichungen lassen sich nicht sauber algebraisch lösen.

Du kannst faktorisieren und substituieren, so viel du willst – einige Gleichungen haben keine geschlossene Form. Für Polynome ab Grad fünf gibt es zum Beispiel keine allgemeine algebraische Lösung. Funktionen, die Exponentialfunktionen mit Polynomen mischen, wie e^x = 3x, gehören in dieselbe Kategorie. In solchen Fällen brauchst du einen anderen Ansatz.

Newtons Verfahren ist genau dieser Ansatz. Es findet Nullstellen numerisch, indem es immer bessere Schätzwerte bildet – jeder Schritt wird von der Tangente der Funktion an der aktuellen Stelle geleitet.

In diesem Artikel zeige ich dir die Formel hinter Newtons Verfahren, erkläre Schritt für Schritt, wie es funktioniert, wann es konvergiert und wann nicht – mit konkreten Beispielen, die die Theorie greifbar machen.

Du suchst nach weiteren Mathe-Themen, die du als Data Scientist kennen solltest? Lies unseren Blogbeitrag Geometric Series: Formula, Convergence, and Examples und sieh, wie sie in Finanzen, Physik und Informatik angewendet werden.

Was ist Newtons Verfahren?

Newtons Verfahren ist eine iterative Technik zur Bestimmung der Nullstellen einer Funktion. Nullstellen sind die Eingabewerte, für die die Funktion gleich null ist.

Du startest mit einem Anfangswert. Anschließend nutzt das Verfahren die Geometrie der Funktion an diesem Punkt, um einen besseren Wert zu finden. Diesen Prozess wiederholst du, und jede Iteration bringt dich näher an die tatsächliche Nullstelle.

Das ist die ganze Idee. Du brauchst nur eine clevere, wiederholbare Aktualisierungsregel, die auf die Lösung zuläuft.

Die Formel von Newtons Verfahren

Der Kern von Newtons Verfahren ist eine einzige Aktualisierungsregel, die du wiederholt anwendest, bis du nah genug an der Nullstelle bist.

Hier ist die Formel:

Formel von Newtons Verfahren

Jede Iteration nimmt deine aktuelle Schätzung x_n und liefert eine bessere, x_{n+1}. Du aktualisierst weiter, bis das Ergebnis nahe genug an null liegt.

Die Formel hat drei Bestandteile:

• x_n – deine aktuelle Schätzung der Nullstelle

• f(x_n) – der Funktionswert an dieser Stelle

• f'(x_n) – die Ableitung der Funktion an dieser Stelle, also die Steigung der Tangente

Ist f(x_n) groß, bist du weit von der Nullstelle entfernt. Ist f'(x_n) steil, ändert sich die Funktion schnell – du kannst einen größeren Schritt machen. Das Verhältnis f(x_n) / f'(x_n) sagt dir genau, wie weit du gehen solltest – und du ziehst es von deiner aktuellen Schätzung ab, um näher zu kommen.

Ist f'(x_n) null oder nahe null, funktioniert die Formel nicht wirklich. Du würdest durch null teilen, wodurch keine nächste Schätzung berechnet werden kann. Mehr dazu im Abschnitt zu den Einschränkungen.

So funktioniert Newtons Verfahren

Newtons Verfahren folgt in jeder Iteration denselben vier Schritten.

1. Wähle einen Anfangswert: Nimm einen Startwert x_0 in der Nähe der Nullstelle. Er muss nicht exakt sein – nur so nah, dass sich die Funktion dort vorhersagbar verhält. Was „nah genug“ bedeutet, erkläre ich im Abschnitt zur Konvergenz.

2. Berechne den Funktionswert: Werte f(x_0) aus. Das zeigt dir, wie weit die Funktion an deiner aktuellen Schätzung von null entfernt ist. Wenn f(x_0) = 0 gilt, bist du fertig – du hast die Nullstelle gefunden.

3. Berechne die Ableitung: Werte f'(x_0) aus. Das liefert dir die Steigung der Funktion in x_0, also die Steigung der Tangente an diesem Punkt.

4. Aktualisiere die Schätzung: Wende die Aktualisierungsregel gemäß der Formel aus dem vorherigen Abschnitt an.

Und das war’s!

Der neue Wert x_1 ist der Schnittpunkt der Tangente mit der x-Achse. Geometrisch zeichnest du eine Gerade, die die Kurve in x_0 berührt, und folgst ihr bis zur x-Achse. Dieser Schnittpunkt ist deine nächste, bessere Schätzung.

Dann wiederholst du das Ganze. Setze x_1 in die Schritte 2 bis 4 ein, um x_2 zu erhalten, dann x_3 und so weiter. Jede Iteration zeichnet an der neuen Stelle eine Tangente und findet ihren Schnittpunkt mit der x-Achse.

Der Prozess endet, wenn f(x_n) hinreichend nahe bei null ist – typischerweise, wenn es unter einen kleinen, vorab definierten Schwellenwert fällt.

Geometrische Interpretation von Newtons Verfahren

Stell dir eine Kurve im Koordinatensystem vor – das ist deine Funktion f(x). Die Nullstelle ist dort, wo die Kurve die x-Achse schneidet. Du weißt noch nicht, wo das ist, also startest du mit einer Schätzung x_0 auf der x-Achse.

In jedem Schritt markierst du den Punkt (x_0, f(x_0)) auf der Kurve und zeichnest die Tangente an dieser Stelle – eine Gerade, die die Kurve dort berührt und ihrer Steigung folgt. Diese Tangente ist nicht horizontal. Sie ist geneigt und schneidet, wenn du ihr folgst, die x-Achse. Dieser Schnittpunkt ist deine nächste Schätzung, x_1.

Dann wiederholst du das. In x_1 zeichnest du eine neue Tangente und bestimmst ihren Schnittpunkt mit der x-Achse. Das ergibt x_2. Jede Tangente ist eine lokale lineare Approximation der Kurve, und jeder Schnittpunkt landet näher an der tatsächlichen Nullstelle.

Das Diagramm unten zeigt zwei Iterationen von Newtons Verfahren angewendet auf f(x) = x^2 - 2, gestartet bei x_0 = 2.5:

Geometrische Interpretation

Das funktioniert, weil die Tangente die beste Geradenapproximation einer Kurve an einem gegebenen Punkt ist. Je näher du an der Nullstelle bist, desto stärker ähnelt die Tangente der Kurve selbst – und desto genauer wird dein nächster Schritt.

In der Praxis nähern sich die Schätzwerte der Nullstelle nicht nur langsam an. Sie springen schnell dorthin, oft verdoppelt sich mit jeder Iteration die Anzahl korrekter Dezimalstellen.

Schritt-für-Schritt-Beispiel für Newtons Verfahren

Wenden wir Newtons Verfahren auf f(x) = x^2 - 2 an. Die Nullstelle dieser Funktion ist x = sqrt(2) ≈ 1.4142 – wir berechnen also die Quadratwurzel von 2.

Die Ableitung ist f'(x) = 2x, daher wird die Aktualisierungsregel zu:

Beispiel (Aktualisierungsregel)

Starten wir mit einer Anfangsschätzung von x_0 = 2.5.

Iteration 1:

Beispiel (Iteration 1)

Iteration 2:

Beispiel (Iteration 2)

Iteration 3:

Beispiel (Iteration 3)

Nach nur drei Iterationen sind wir bereits auf vier Dezimalstellen genau. Der Fehler ist von 1.086 bei x_0 auf 0.0001 bei x_3 gefallen – und sinkt mit jedem Schritt weiter.

So sehen diese Schätz- und Fehlerwerte visuell aus:

Visuelle Übersicht über Schätzung und Fehler

Das linke Panel zeigt, wie jede Schätzung sqrt(2) ≈ 1.4142 näher kommt, während das rechte Panel den Fehler auf einer logarithmischen Skala kleiner werden lässt – jede Iteration erhöht die Genauigkeit grob quadratisch gegenüber der vorherigen.

Konvergenz von Newtons Verfahren

Newtons Verfahren kann schnell konvergieren – aber nur unter den richtigen Bedingungen.

Wenn dein Anfangswert nahe an der Nullstelle liegt und die Funktion in dieser Region glatt ist, zeigt das Verfahren quadratische Konvergenz. Das ist der Fachbegriff für das, was du im Beispiel gesehen hast: Jede Iteration quadriert den Fehler ungefähr. Aus zwei korrekten Dezimalstellen werden vier, aus vier acht usw.

Dafür müssen zwei Bedingungen erfüllt sein:

• Eine gute Anfangsschätzung: Je näher x_0 an der tatsächlichen Nullstelle liegt, desto schneller konvergiert das Verfahren. Startest du zu weit weg, kann dich die Tangente an diesem Punkt in die falsche Richtung schicken.
• Eine gutmütige Funktion: Die Funktion sollte in der Nähe der Nullstelle glatt und differenzierbar sein. Scharfe Knicke oder flache Bereiche können die Tangentenapproximation stören.

Der häufigste Fehlermodus ist eine Ableitung nahe null. 

Wenn f'(x_n) nahe null ist, teilst du in der Aktualisierungsregel durch eine sehr kleine Zahl – die nächste Schätzung wird weit von der Nullstelle weggeschleudert. Im schlimmsten Fall ist f'(x_n) = 0 und die Rechnung bricht ab, weil du nicht durch null teilen kannst.

Ein schlechter Startpunkt kann außerdem zu Oszillation oder Divergenz führen. Statt sich der Nullstelle anzunähern, springen die Schätzungen hin und her oder entfernen sich mit jeder Iteration weiter.

Newtons Verfahren belohnt eine gute Vorbereitung. Eine sinnvolle Anfangsschätzung und eine glatte Funktion genügen, damit es konvergiert – und zwar schnell.

Vorteile von Newtons Verfahren

Wenn die Bedingungen passen, ist Newtons Verfahren kaum zu schlagen.

Der größte Vorteil ist die quadratische Konvergenz. Die meisten numerischen Methoden nähern sich der Nullstelle linear an, d. h. jede Iteration reduziert den Fehler um einen festen Betrag. Newtons Verfahren quadriert den Fehler hingegen – dadurch erreicht es mit sehr wenigen Iterationen hohe Genauigkeit.

Es ist außerdem universell einsetzbar. Du kannst es auf eine breite Palette von Funktionen anwenden – polynomisch, trigonometrisch, exponentiell – ohne etwas zu ändern. Darum taucht es in so vielen Bereichen auf, von Ingenieurssimulationen bis hin zum Training von Machine-Learning-Modellen.

Einschränkungen von Newtons Verfahren

Für diese Geschwindigkeit verlangt Newtons Verfahren auch einiges. Hier sind ein paar Einschränkungen, die du im Blick behalten solltest:

• Es erfordert eine Ableitung: Du brauchst einen analytischen Ausdruck für f'(x), bevor du überhaupt eine Iteration durchführen kannst. Ist die Ableitung schwer zu berechnen (oder existiert nicht), brauchst du einen anderen Ansatz.

• Es ist sensibel gegenüber dem Startwert: Startest du zu weit von der Nullstelle entfernt, kann dich das Verfahren in die falsche Richtung schicken.

• Es konvergiert nicht immer: Hat die Funktion flache Bereiche oder starke Krümmungen, funktioniert die Tangentenapproximation schlicht nicht.

• Es kann divergieren oder oszillieren: Im ungünstigen Fall konvergieren die Schätzungen nicht, entfernen sich weiter von der Nullstelle oder springen unendlich hin und her.

Bevor du also zu Newtons Verfahren greifst, stelle sicher, dass du deine Funktion verstehst.

Newtons Verfahren vs. andere Nullstellenverfahren

Newtons Verfahren ist nicht der einzige Weg zu Nullstellen – und nicht immer der richtige für dich.

Oft kommen zwei weitere Methoden ins Spiel: das Bisektionsverfahren und das Sekantenverfahren. Kurz erklärt:

Bisektionsverfahren

Das Bisektionsverfahren ist das einfachste der drei. Du startest mit einem Intervall [a, b], in dem die Funktion ihr Vorzeichen wechselt – also muss darin eine Nullstelle liegen. Dann halbierst du das Intervall wiederholt und behältst die Hälfte, in der der Vorzeichenwechsel weiterhin vorliegt.

Das funktioniert, ist aber langsam. Der Fehler halbiert sich pro Iteration, also lineare Konvergenz. Dafür klappt es garantiert, solange die Funktion stetig ist und dein Startintervall eine Nullstelle einschließt. Ableitungen sind nicht nötig.

Sekantenverfahren

Das Sekantenverfahren ist eng mit Newtons Verfahren verwandt. Anstatt die Ableitung analytisch zu berechnen, nähert es sie mit zwei vorherigen Schätzungen an:

Formel des Sekantenverfahrens

Das ist sinnvoll, wenn die Ableitung schwer zu bestimmen ist. Du zahlst mit geringerer Geschwindigkeit – das Sekantenverfahren ist schneller als Bisektion, aber langsamer als Newton.

Anwendungen von Newtons Verfahren

Newtons Verfahren ist in Wissenschaft, Technik und Machine Learning allgegenwärtig. So genau wird es eingesetzt:

Numerisches Lösen von Gleichungen

Die direkteste Anwendung: Hat eine Funktion keine geschlossene Lösung, findet Newtons Verfahren die Nullstelle. Das kommt in der wissenschaftlichen Datenverarbeitung ständig vor – etwa beim Finden von Gleichgewichtspunkten in chemischen Reaktionen oder beim Lösen transzendenter Gleichungen in der Signalverarbeitung.

Optimierung

Ein Minimum oder Maximum von f(x) zu finden, heißt, die Stellen zu finden, an denen f'(x) = 0 gilt. Das ist ein Nullstellenproblem – also lässt sich Newtons Verfahren anwenden. Du führst den Algorithmus einfach auf f'(x) aus und nutzt die zweite Ableitung f''(x) anstelle der ersten.

Diese Variante heißt Newtons Verfahren für die Optimierung und konvergiert auf glatten, gutmütigen Funktionen schneller als Gradientenabstieg.

Machine Learning

Beim Machine Learning bedeutet das Trainieren eines Modells das Minimieren einer Verlustfunktion. Newtons Verfahren und seine Varianten kommen hier mehrfach zum Einsatz.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) ist ein Quasi-Newton-Optimierer, der die zweite Ableitung approximiert, um sie nicht direkt berechnen zu müssen. Er ist Standard für logistische Regression und andere konvexe Probleme. Newtons Verfahren bildet außerdem die Grundlage für die Newton-Raphson-Updates in der statistischen Modellierung, etwa bei generalisierten linearen Modellen.

Physik und Ingenieurwesen

Newtons Verfahren ist in Simulation und Design allgegenwärtig. Ingenieurinnen und Ingenieure lösen damit nichtlineare Gleichungssysteme, die physikalische Systeme beschreiben – etwa Tragwerksberechnungen oder Strömungsdynamik. In all diesen Fällen läuft das Grundproblem darauf hinaus, die Stellen zu finden, an denen ein Gleichungssystem gleich null ist.

Häufige Fehler bei Newtons Verfahren

Die meisten Fehler bei Newtons Verfahren gehen auf dieselben vier Ursachen zurück. Hier sind sie:

• Zu weit weg von der Nullstelle starten: Eine schlechte Anfangsschätzung ist der häufigste Grund für Divergenz oder Oszillation. Wenn du keine gute Intuition für die Lage der Nullstelle hast, plote die Funktion zuerst. So siehst du, wo du starten solltest.

• Falsche Ableitung: Die Aktualisierungsregel hängt von f'(x) ab. Eine fehlerhafte Ableitung – durch Rechen- oder Programmierfehler – produziert von der ersten Iteration an falsche Schätzungen, und der Fehler wächst mit jeder weiteren.

• Nicht auf Division durch null prüfen. Wenn f'(x_n) null ist oder sich stark nähert, kann der Aktualisierungsschritt nicht funktionieren. Baue in deine Implementierung eine Absicherung ein: Fällt die Ableitung unter einen kleinen Schwellenwert, stoppe und melde den Fehler, statt ein unsinniges Ergebnis auszugeben.

• Zu früh stoppen. Wenn du die Iterationen beendest, bevor die Schätzung konvergiert ist, bleibt ein Ergebnis, das nahe aussieht, es aber nicht ist. Lege deine Abbruchbedingung auf den tatsächlichen Fehler – entweder |f(x_n)| oder |x_{n+1} - x_n| – und zwar unter einen bewusst gewählten Schwellenwert, nicht nur nach einer festen Zahl von Iterationen.

Fazit

Newtons Verfahren ist eines der nützlichsten Werkzeuge der numerischen Mathematik. Eine einzige Aktualisierungsregel, wiederholt angewendet, findet Nullstellen mit beliebiger Genauigkeit oft in wenigen Iterationen.

Für diese Geschwindigkeit gelten Bedingungen. Du brauchst eine gute Anfangsschätzung, eine nichtflache und nicht „zackige“ Funktion sowie eine von null verschiedene Ableitung, um schnelle Konvergenz zu erreichen. Verstehst du diese Bedingungen, weißt du, wann du zu Newtons Verfahren greifst – und wann du besser etwas anderes (wie Bisektion oder Sekantenverfahren) nutzt.

Am besten baust du dir dieses Gespür mit einfachen Beispielen auf. Starte mit f(x) = x^2 - 2, probiere unterschiedliche Startwerte aus und beobachte, was passiert. Gehe dann zu Funktionen mit mehreren Nullstellen oder flachen Bereichen über und sieh, wo das Verfahren an Grenzen stößt.

Wenn dir das Prinzip der Optimierung durch Iteration gefällt, solltest du den Gradientenabstieg kennen. Lies unser Gradient Descent in Machine Learning: A Deep Dive und erfahre, wie damit ML-Modelle optimiert werden.