Newton-Verfahren
Viele Gleichungen lassen sich nicht exakt lösen – zum Beispiel $x^3 - 3x + 1 = 0$ oder $e^x = 3x$. Das Newton-Verfahren findet Nullstellen trotzdem: Es ersetzt den Graphen immer wieder durch eine Tangente und nähert sich der Nullstelle so in wenigen Schritten sehr genau an.
Die Idee
Du startest mit einem Wert $x_0$ in der Nähe der Nullstelle. Im Punkt $(x_0 \mid f(x_0))$ legst Du die Tangente an den Graphen. Die Tangente ist eine Gerade – ihre Nullstelle kannst Du leicht ausrechnen. Diese Nullstelle ist der neue, bessere Näherungswert $x_1$. Dann wiederholst Du das Ganze mit $x_1$, $x_2$ und so weiter.
Die Tangente in $x_n$ ist $t(x) = f'(x_n) \cdot (x - x_n) + f(x_n)$. Aus $t(x) = 0$ folgt:
Beispiel: $\sqrt{2}$ berechnen
$\sqrt{2}$ ist die positive Nullstelle von $f(x) = x^2 - 2$. Mit $f'(x) = 2x$ lautet die Vorschrift $x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n}$. Start: $x_0 = 1$.
| n | $x_n$ | $f(x_n)$ | $f'(x_n)$ | $x_{n+1}$ |
|---|---|---|---|---|
| 0 | 1 | −1 | 2 | 1,5 |
| 1 | 1,5 | 0,25 | 3 | 1,416667 |
| 2 | 1,416667 | 0,006944 | 2,833333 | 1,414216 |
| 3 | 1,414216 | 0,000006 | 2,828431 | 1,414214 |
Schon nach drei Schritten stimmen sechs Nachkommastellen: $\sqrt{2} \approx 1{,}414214$. Die Zahl der richtigen Stellen verdoppelt sich ungefähr mit jedem Schritt.
Wann hört man auf?
Üblich sind zwei Abbruchkriterien: Entweder ändern sich die Näherungswerte in den gewünschten Nachkommastellen nicht mehr (zum Beispiel $|x_{n+1} - x_n| < 0{,}0001$), oder die Aufgabe gibt eine feste Zahl von Schritten vor („Berechne $x_3$“). Runde erst am Ende – rechne mit allen Stellen des Taschenrechners weiter.
Wann versagt das Newton-Verfahren?
Achtung
- Waagerechte Tangente: Ist $f'(x_n) = 0$, schneidet die Tangente die x-Achse nicht – Du müsstest durch 0 teilen. Beispiel: $f(x) = x^2 - 4x + 1$ mit Start $x_0 = 2$.
- Schlechter Startwert: Liegt $x_0$ nahe an einem Hoch- oder Tiefpunkt, ist die Tangente sehr flach, und der nächste Wert landet weit weg – vielleicht bei einer ganz anderen Nullstelle.
- Pendeln: Bei manchen Funktionen springen die Werte zwischen zwei Zahlen hin und her, zum Beispiel bei $f(x) = x^3 - 2x + 2$ mit $x_0 = 0$ (dann ist $x_1 = 1$, $x_2 = 0$, …).
- Keine Nullstelle: Hat $f$ gar keine Nullstelle (etwa $x^2 + 1$), springen die Werte planlos umher.
Darum lohnt sich vorher ein Blick auf den Graphen oder eine Wertetabelle: Wo wechselt $f$ das Vorzeichen? Dort liegt ein guter Startwert.
Im Vergleich: Intervallhalbierung (Bisektion)
Die Intervallhalbierung braucht keine Ableitung, nur einen Vorzeichenwechsel: Ist $f(a) < 0 < f(b)$ (oder umgekehrt), liegt bei einer stetigen Funktion dazwischen eine Nullstelle. Du berechnest $f$ in der Mitte $m = \frac{a + b}{2}$ und behältst die Hälfte, in der das Vorzeichen wechselt.
| Newton-Verfahren | Intervallhalbierung | |
|---|---|---|
| braucht | Startwert und Ableitung | Intervall mit Vorzeichenwechsel |
| Tempo | sehr schnell (Stellen verdoppeln sich) | langsam (pro Schritt halbe Intervalllänge, also etwa 3,3 Schritte pro Dezimalstelle) |
| Sicherheit | kann versagen (siehe oben) | findet bei stetigen Funktionen immer eine Nullstelle |
| Fehler | nicht direkt ablesbar | höchstens die halbe Intervalllänge |
Wie viele Halbierungen für eine gewünschte Genauigkeit nötig sind und wie das Verfahren Schritt für Schritt abläuft, zeigt die Seite Bisektionsverfahren. Eine weitere Idee ohne Ableitung ist die Fixpunktiteration.
Regula falsi: Sekante statt Mitte
Die Regula falsi (lateinisch etwa „Regel des falschen Ansatzes“) arbeitet wie die Intervallhalbierung mit einem Intervall $[a; b]$, an dessen Rändern $f$ verschiedene Vorzeichen hat. Statt der Mitte nimmt sie aber die Nullstelle der Sekante durch die Punkte $(a \mid f(a))$ und $(b \mid f(b))$. Liegt die Nullstelle näher an einem Rand, landet die Sekante auch dort – das spart oft Schritte.
Danach behältst Du wie bei der Halbierung das Teilintervall, in dem das Vorzeichen wechselt: Hat $f(x)$ dasselbe Vorzeichen wie $f(a)$, ersetzt $x$ die Grenze $a$, sonst die Grenze $b$.
Beispiel: $f(x) = x^3 - 2x - 5$ im Intervall $[2; 3]$
$f(2) = -1$ und $f(3) = 16$ – es gibt einen Vorzeichenwechsel. Erster Schritt: $x = 2 - (-1) \cdot \frac{3 - 2}{16 - (-1)} = 2 + \frac{1}{17} \approx 2{,}058824$.
| Schritt | $a$ | $b$ | $x$ | $f(x)$ |
|---|---|---|---|---|
| 1 | 2 | 3 | 2,058824 | −0,390800 |
| 2 | 2,058824 | 3 | 2,081264 | −0,147204 |
| 3 | 2,081264 | 3 | 2,089639 | −0,054677 |
| 4 | 2,089639 | 3 | 2,092740 | −0,020203 |
Die Nullstelle ist $x^* \approx 2{,}094551$. Auffällig: Die rechte Grenze $b = 3$ bleibt die ganze Zeit stehen, und $x$ nähert sich nur von links. Das passiert, wenn der Graph im Intervall gekrümmt ist – die Regula falsi ist dann zuverlässig, aber nur mäßig schnell.
Sekantenverfahren
Das Sekantenverfahren benutzt dieselbe Formel, nimmt aber immer die beiden letzten Werte – egal, ob dazwischen ein Vorzeichenwechsel liegt. Aus zwei Startwerten $x_0$ und $x_1$ entsteht so die Folge
Man kann es auch als Newton-Verfahren ohne Ableitung sehen: Statt der Tangentensteigung $f'(x_k)$ steht die Steigung der Sekante durch die letzten beiden Punkte.
Beispiel: wieder $f(x) = x^3 - 2x - 5$, Start mit $x_0 = 2$ und $x_1 = 3$
| $k$ | $x_k$ | $f(x_k)$ |
|---|---|---|
| 0 | 2 | −1 |
| 1 | 3 | 16 |
| 2 | 2,058824 | −0,390800 |
| 3 | 2,081264 | −0,147204 |
| 4 | 2,094824 | 0,003044 |
| 5 | 2,094549 | −0,000023 |
| 6 | 2,094551 | ≈ 0 |
Die ersten beiden neuen Werte stimmen mit der Regula falsi überein. Ab $x_4$ rechnet das Sekantenverfahren mit den beiden neuesten Punkten weiter statt mit der festen Grenze $3$ – und ist nach wenigen Schritten auf sechs Nachkommastellen genau.
Achtung
Weil das Sekantenverfahren keinen Vorzeichenwechsel festhält, kann es wie das Newton-Verfahren davonlaufen oder abbrechen – zum Beispiel, wenn $f(x_k) = f(x_{k-1})$ ist und die Sekante waagerecht verläuft.
Welches Verfahren ist am schnellsten?
Wie schnell ein Verfahren ist, beschreibt die Konvergenzordnung $p$. Ist $e_k = |x_k - x^*|$ der Fehler im $k$-ten Schritt, so gilt nahe der Nullstelle ungefähr $e_{k+1} \approx C \cdot e_k^{\,p}$. Bei $p = 1$ (linear) schrumpft der Fehler in jedem Schritt um einen festen Faktor, bei $p = 2$ (quadratisch) verdoppelt sich ungefähr die Zahl der richtigen Stellen.
| Verfahren | braucht | Konvergenzordnung | findet sicher eine Nullstelle? |
|---|---|---|---|
| Intervallhalbierung | Vorzeichenwechsel | linear, Fehler etwa ½ pro Schritt | ja (bei stetigem $f$) |
| Regula falsi | Vorzeichenwechsel | meist linear – oft schneller, manchmal langsamer als die Halbierung | ja (bei stetigem $f$) |
| Sekantenverfahren | zwei Startwerte | überlinear, $p \approx 1{,}618$ | nein |
| Newton-Verfahren | Startwert und $f'$ | quadratisch, $p = 2$ (bei einfacher Nullstelle) | nein |
Für $x^3 - 2x - 5$ in $[2; 3]$ brauchen die Verfahren bis zu einem Fehler unter $10^{-10}$: Halbierung 32 Schritte, Regula falsi 21, Sekantenverfahren 6 und Newton-Verfahren (Start in der Mitte) 4. Dafür muss Newton in jedem Schritt zusätzlich die Ableitung ausrechnen. Probiere es im Rechner unten mit „Verfahren vergleichen“ aus – die Tabelle und die Grafik zeigen, wie der Fehler bei jedem Verfahren schrumpft.
Tipp aus der Praxis
Gute Programme kombinieren beides: Mit Halbierung oder Regula falsi wird die Nullstelle sicher eingegrenzt, dann übernimmt ein schnelles Verfahren wie Newton oder die Sekante die letzten Stellen.
Numerisch integrieren: die Trapezregel
Auch Integrale lassen sich nicht immer exakt berechnen – für $\int_0^1 e^{-x^2}\,\mathrm{d}x$ gibt es keine Stammfunktion aus bekannten Funktionen. Die Trapezregel teilt $[a; b]$ in $n$ gleich breite Streifen der Breite $h = \frac{b - a}{n}$ und ersetzt den Graphen über jedem Streifen durch eine Strecke. Die Trapezflächen zusammen ergeben
Beispiel
$\int_0^2 x^2\,\mathrm{d}x$ mit $n = 4$: $h = 0{,}5$, Funktionswerte $0;\ 0{,}25;\ 1;\ 2{,}25;\ 4$.
$T_4 = 0{,}5 \cdot \left(0 + 0{,}25 + 1 + 2{,}25 + 2\right) = 2{,}75$. Exakt ist $\frac{8}{3} \approx 2{,}667$ – der Fehler beträgt etwa 0,083. Bei Linkskurven liegt die Trapezsumme immer etwas zu hoch.
Viel genauer ist die Simpsonregel, die Parabeln statt Strecken verwendet – sie und den Vergleich mit der Mittelpunktregel findest Du bei der numerischen Integration.
Rechner: Newton, Halbierung, Regula falsi, Sekante und Trapezregel
Übungsaufgaben
Stufe 1: Newton: Vorschrift und ein Schritt
-
Aufgabe 1
\(\sqrt{20} \text{ mit } f(x) = x^{2} - 20,\) \(x_0 = 4:\ x_1\)\(x_1 =\)\(x_1 = 4 - \frac{-4}{8} = \frac{9}{2} \approx 4{,}5\)
-
Aufgabe 2
\(f(x) = -x^{2} + x,\ x_0 = -2:\ x_1\)\(x_1 =\)\(x_1 = -2 - \frac{f(-2)}{f'(-2)}\) \(= -2 - \frac{-6}{5}\) \(= -\frac{4}{5}\)
-
Aufgabe 3
\(f(x) = -x^{3} + 3x^{2} + 4x + 1,\) \(x_0 = -1:\ x_1\)\(x_1 =\)\(x_1 = -1 - \frac{f(-1)}{f'(-1)}\) \(= -1 - \frac{1}{-5}\) \(= -\frac{4}{5}\)
-
Aufgabe 4
\(\sqrt{11} \text{ mit } f(x) = x^{2} - 11,\) \(x_0 = 3:\ x_1\)\(x_1 =\)\(x_1 = 3 - \frac{-2}{6} = \frac{10}{3} \approx 3{,}3333\)
-
Aufgabe 5
\(f(x) = x^{3} - 2x - 5,\ x_0 = 2:\ x_1\)\(x_1 =\)\(x_1 = 2 - \frac{f(2)}{f'(2)}\) \(= 2 - \frac{-1}{10}\) \(= \frac{21}{10}\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Newton-Verfahren und numerische Verfahren
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 11–13.
Regula falsi und Sekantenverfahren üben
Rechne mit dem Taschenrechner und runde erst das Ergebnis auf vier Nachkommastellen. Brüche darfst Du auch exakt eingeben, zum Beispiel 35/17.
Stufe 3: zwei Schritte, Fehlerabschätzung
-
Aufgabe 1
\(f(x) = x^{3} - 11,\quad [2;\,3]\)\(x_2 \approx\)\(x_2 \approx 2{,}2052\) \((\)Intervall danach \([2{,}205;\,3])\)
-
Aufgabe 2
Halbierung: Startintervall der Länge \(2,\) Länge kleiner als \(10^{-3}\)\(n =\)\(n = 11\quad(2^{11} > 2 \cdot 10^{3})\)
-
Aufgabe 3
\(f(x) = x^{3} - 25,\quad [2;\,3]\)\(x_2 \approx\)\(x_2 \approx 2{,}9233\) \((\)Intervall danach \([2{,}923;\,3])\)
-
Aufgabe 4
Halbierung: Startintervall der Länge \(4,\) Länge kleiner als \(10^{-6}\)\(n =\)\(n = 22\quad(2^{22} > 4 \cdot 10^{6})\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Regula falsi und Sekantenverfahren
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 11–13.
Exakte Lösungswege für Nullstellen (pq-Formel, Substitution, Polynomdivision …) findest Du unter Nullstellen berechnen. Wie die Tangente aufgestellt wird, zeigt der Tangenten-Rechner, exakte Integrale berechnet der Integralrechner. Funktionswerte von Polynomen rechnest Du mit dem Horner-Schema besonders schnell – praktisch für die Wertetabellen der Näherungsverfahren.
Weiterlesen: Newtonverfahren, Bisektion, Regula falsi, Sekantenverfahren, Trapezregel bei Wikipedia