Lektion 4.5

Newton-Verfahren und iterative Nullstellenbestimmung

35 min Lesezeit

Nach dieser Lektion kannst du

  • erklären, warum man viele Gleichungen nur näherungsweise lösen kann und was ein iteratives Verfahren ist

  • die Newton-Formel aus der Tangentengleichung herleiten

  • Newton-Schritte von Hand und mit einer Tabelle ausführen und ein sinnvolles Abbruchkriterium wählen

  • erkennen, wann das Verfahren versagt: waagerechte Tangente, Zyklus, Sprung zu einer anderen Nullstelle

Gleichungen ohne Lösungsformel. Für ax2+bx+c=0ax^2 + bx + c = 0 gibt es die Mitternachtsformel. Schon bei x3+x−1=0x^3 + x - 1 = 0 wird es mühsam, und für eine so harmlos aussehende Gleichung wie cos⁡x=x\cos x = x gibt es überhaupt keine Formel, die die Lösung exakt angibt. Trotzdem braucht man solche Lösungen ständig: in der Physik, in der Technik, in jedem Taschenrechner, der eine Wurzel zieht.

Der Ausweg ist ein iteratives Verfahren (von lateinisch *iterare*, wiederholen). Man beginnt mit einer groben Schätzung und verbessert sie mit einer festen Rechenvorschrift. Das Ergebnis eines Schritts ist der Startwert des nächsten. Die Intervallhalbierung aus der Lektion über Stetigkeit ist so ein Verfahren: Sie halbiert bei jedem Schritt die Unsicherheit. Für sechs richtige Nachkommastellen braucht sie etwa zwanzig Schritte. Isaac Newton hatte eine bessere Idee, und sie beruht auf der Ableitung.

Die Idee: Kurve durch Gerade ersetzen. Die Nullstelle einer Kurve zu finden ist schwer. Die Nullstelle einer Geraden zu finden ist leicht. In der Nähe eines Punktes sieht ein differenzierbarer Graph aber fast aus wie seine Tangente. Also ersetzt man den Graphen durch die Tangente und nimmt deren Nullstelle als neue Schätzung. Weil die Tangente den Graphen nur in der Nähe gut beschreibt, trifft man die Nullstelle nicht genau, kommt ihr aber meist viel näher. Dann wiederholt man das Ganze vom neuen Punkt aus.

Vermute zuerst

Gesucht ist 2\sqrt{2}, also die positive Nullstelle von f(x)=x2−2f(x) = x^2 - 2. Man startet bei x0=3x_0 = 3 und wendet die Tangenten-Idee immer wieder an. Wie viele Schritte braucht man ungefähr, bis sechs Nachkommastellen von 2=1,414213…\sqrt{2} = 1{,}414213\ldots stimmen?

Newton-Verfahren für f(x)=x2−2f(x) = x^2 - 2

Jede Tangente schneidet die Achse etwas rechts der Nullstelle, weil der Graph nach oben gekrümmt ist. Der Abstand schrumpft aber mit jedem Schritt drastisch.

Probier es aus

Schritt für Schritt

Die Newton-Formel herleiten

Wir haben eine Näherung xnx_n und wollen die nächste, xn+1x_{n+1}, ausrechnen. Dazu brauchen wir nur die Tangentengleichung aus der Lektion über die Ableitung.

  1. Tangente an den Graphen von ff im Punkt (xn∣f(xn))(x_n \mid f(x_n)):

    t(x)=f(xn)+f′(xn)⋅(x−xn)t(x) = f(x_n) + f'(x_n) \cdot (x - x_n)
Schritt 1 von 4
Definition

Newton-Verfahren

Gegeben ist eine differenzierbare Funktion ff und ein Startwert x0x_0 in der Nähe einer Nullstelle. Man berechnet nacheinander

x1=x0−f(x0)f′(x0),x2=x1−f(x1)f′(x1),…x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}, \quad x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}, \quad \ldots

und hört auf, wenn sich zwei aufeinanderfolgende Näherungen um weniger als eine vorher gewählte Genauigkeit unterscheiden, zum Beispiel ∣xn+1−xn∣<10−6|x_{n+1} - x_n| < 10^{-6}. Diese Bedingung heißt Abbruchkriterium.

Die Zahlen x0,x1,x2,…x_0, x_1, x_2, \ldots bilden eine Folge von Näherungen. Wenn sie sich einer Zahl x∗x^* beliebig nähern, sagt man, die Folge konvergiert gegen x∗x^*. Ist ff stetig differenzierbar und f′(x∗)≠0f'(x^*) \neq 0, dann ist dieser Grenzwert eine Nullstelle von ff.

Schritt für Schritt

Ein Rechenbeispiel von Hand: x3+x−1=0x^3 + x - 1 = 0

In der Lektion über Stetigkeit haben wir mit dem Zwischenwertsatz gezeigt, dass f(x)=x3+x−1f(x) = x^3 + x - 1 zwischen 00 und 11 eine Nullstelle hat. Jetzt bestimmen wir sie. Startwert x0=1x_0 = 1.

  1. Ableitung bilden:

    f′(x)=3x2+1f'(x) = 3x^2 + 1
Schritt 1 von 5
Kurz geprüft

Führe für f(x)=x2−5f(x) = x^2 - 5 mit dem Startwert x0=2x_0 = 2 einen Newton-Schritt aus. Wie groß ist x1x_1?

Kurz geprüft

Vereinfache die Newton-Iteration für f(x)=x2−5f(x) = x^2 - 5. Schreib xn+1x_{n+1} als Term in xnx_n (tippe dafür einfach xx).

Potenzen mit ^, Wurzel als sqrt(x), Brüche mit / und Klammern.

Satz

Quadratische Konvergenz beim Wurzelziehen

Für f(x)=x2−af(x) = x^2 - a mit a>0a > 0 und jeden Startwert xn>0x_n > 0 gilt für den Fehler der nächsten Näherung

xn+1−a=(xn−a)22xnx_{n+1} - \sqrt{a} = \frac{(x_n - \sqrt{a})^2}{2x_n}
Beispiel

Eine Gleichung ohne Formel: cos⁡x=x\cos x = x

Gesucht ist die Stelle, an der der Kosinus seinem Argument gleich ist (xx im Bogenmaß). Wir bringen alles auf eine Seite: f(x)=cos⁡x−xf(x) = \cos x - x mit f′(x)=−sin⁡x−1f'(x) = -\sin x - 1.

xn+1=xn−cos⁡xn−xn−sin⁡xn−1=xn+cos⁡xn−xnsin⁡xn+1x_{n+1} = x_n - \frac{\cos x_n - x_n}{-\sin x_n - 1} = x_n + \frac{\cos x_n - x_n}{\sin x_n + 1}

Mit x0=1x_0 = 1: x1≈0,750364x_1 \approx 0{,}750364, x2≈0,739113x_2 \approx 0{,}739113, x3≈0,739085x_3 \approx 0{,}739085, x4≈0,739085x_4 \approx 0{,}739085. Nach drei Schritten stehen sechs Stellen fest: x∗≈0,739085x^* \approx 0{,}739085. Für diese Zahl gibt es keinen geschlossenen Ausdruck. Das Newton-Verfahren ist hier der einzige Weg zu einem Zahlenwert.

Newton-Verfahren für f(x)=cos⁡x−xf(x) = \cos x - x

Probier es aus

Wenn es schiefgeht. Das Newton-Verfahren ist schnell, aber nicht unfehlbar. Es kann auf drei Arten scheitern:

  • Waagerechte Tangente. Ist f′(xn)=0f'(x_n) = 0, schneidet die Tangente die Achse nicht. Liegt xnx_n nur in der Nähe eines Hoch- oder Tiefpunkts, ist die Tangente fast waagerecht, und xn+1x_{n+1} landet sehr weit weg.
  • Zyklus. Die Näherungen springen immer zwischen denselben Werten hin und her und kommen nie an.
  • Falsche Nullstelle. Hat ff mehrere Nullstellen, kann das Verfahren bei einer anderen ankommen, als man erwartet hat.

Der folgende Versuch zeigt ein berühmtes Beispiel für einen Zyklus.

Ein Zyklus bei f(x)=x3−2x+2f(x) = x^3 - 2x + 2

Von 00 führt die Tangente nach 11, von 11 zurück nach 00. Die echte Nullstelle liegt bei etwa −1,769-1{,}769. Ein Startwert in ihrer Nähe löst das Problem.

Probier es aus

Häufige Fehler

Das Vorzeichen in der Formel

Man rechnet xn+1=xn+f(xn)f′(xn)x_{n+1} = x_n + \frac{f(x_n)}{f'(x_n)}.

Richtig ist

Es heißt minus. Anschaulich: Ist f(xn)>0f(x_n) > 0 und steigt ff (also f′(xn)>0f'(x_n) > 0), dann liegt die Nullstelle links von xnx_n, man muss also nach links gehen. Mit Plus würde man sich von der Nullstelle entfernen.

Häufige Fehler

Die Ableitung an der falschen Stelle

Man berechnet f′f' einmal am Startwert und verwendet diesen Wert in allen Schritten weiter.

Richtig ist

In jedem Schritt braucht man die Tangente am aktuellen Punkt, also f(xn)f(x_n) und f′(xn)f'(x_n) neu. Eine Tabelle mit den Spalten nn, xnx_n, f(xn)f(x_n), f′(xn)f'(x_n) hilft, nichts zu vergessen.

Häufige Fehler

Aufhören, sobald f(xn)f(x_n) klein ist

Man bricht ab, weil f(xn)=0,001f(x_n) = 0{,}001 ist, und hält xnx_n für genau.

Richtig ist

Ein kleiner Funktionswert heißt nicht, dass xnx_n nahe an der Nullstelle liegt. Bei einem sehr flachen Graphen kann man noch weit weg sein. Deshalb prüft man besser, ob sich zwei Näherungen nur noch wenig unterscheiden, und gibt nur so viele Stellen an, wie sich nicht mehr ändern.

Zusammenfassung

  • Iterative Verfahren verbessern eine Näherung Schritt für Schritt. Sie lösen Gleichungen, für die es keine Formel gibt.

  • Newton-Idee: Den Graphen durch die Tangente ersetzen und deren Nullstelle als nächste Näherung nehmen.

  • Newton-Iteration: xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, nur für f′(xn)≠0f'(x_n) \neq 0.

  • In der Nähe einer Nullstelle verdoppelt sich die Zahl der richtigen Stellen pro Schritt ungefähr (quadratische Konvergenz).

  • Abbruch, wenn ∣xn+1−xn∣|x_{n+1} - x_n| kleiner als die gewünschte Genauigkeit ist.

  • Das Verfahren kann versagen: bei waagerechten Tangenten, durch Zyklen oder indem es zu einer anderen Nullstelle läuft. Ein guter Startwert aus einem Vorzeichenwechsel hilft.

Übungen

Aufgabe 1Numerisch

Berechne für f(x)=x2−3f(x) = x^2 - 3 mit x0=2x_0 = 2 die erste Newton-Näherung x1x_1.

Aufgabe 2Numerisch

Für f(x)=x3−10f(x) = x^3 - 10 und x0=2x_0 = 2: Berechne x1x_1 auf drei Nachkommastellen.

Aufgabe 3Term eingeben

Stelle die vereinfachte Newton-Iteration für f(x)=x2−7f(x) = x^2 - 7 auf. Schreib xn+1x_{n+1} als Term in xnx_n (tippe xx für xnx_n).

Potenzen mit ^, Wurzel als sqrt(x), Brüche mit / und Klammern.

Aufgabe 4Multiple Choice

Für f(x)=x3−3x+1f(x) = x^3 - 3x + 1 wählt man den Startwert x0=1x_0 = 1. Was passiert im ersten Schritt?

Aufgabe 5Numerisch

Die Gleichung ex=3e^x = 3 soll mit Newton gelöst werden: f(x)=ex−3f(x) = e^x - 3, f′(x)=exf'(x) = e^x, Startwert x0=1x_0 = 1. Berechne x1x_1 auf drei Nachkommastellen (e≈2,71828e \approx 2{,}71828).

Aufgabe 6Multiple Choice

Nach der Fehlerformel xn+1−a=(xn−a)22xnx_{n+1} - \sqrt{a} = \frac{(x_n - \sqrt{a})^2}{2x_n}: Wie groß ist ungefähr der Fehler von xn+1x_{n+1}, wenn xnx_n beim Berechnen von 4=2\sqrt{4} = 2 um 0,010{,}01 zu groß ist?

Aufgabe 7Freitext

Erkläre anhand einer Skizze, warum das Newton-Verfahren für f(x)=x2−2f(x) = x^2 - 2 mit einem Startwert x0>0x_0 > 0 nahe bei 00 (zum Beispiel x0=0,1x_0 = 0{,}1) zunächst sehr weit nach rechts springt. Berechne x1x_1 und begründe, warum das Verfahren trotzdem bei 2\sqrt{2} ankommt.