13.4 Das Newton-Verfahren
13.4 Das Newton-Verfahren
Viele Gleichungen lassen sich nicht exakt lösen und man ist für praktische Zwecke darauf angewiesen, die Lösungen näherungsweise so genau und effektiv wie möglich zu bestimmen.
Wir werden im Verlauf der Vorlesung gelegentlich über solche Verfahren sprechen, zum Beispiel zur Lösung von Differentialgleichungen oder zur näherungsweisen Berechung von Integralen.
Das erste Näherungsverfahren, mit dem wir uns beschäftigen wollen, geht auf Isaac Newton zurück und dient der Bestimmung von Nullstellen einer differenzierbaren Funktion. In vielen Varianten spielt dieses Verfahren auch heute noch eine extrem wichtige Rolle in der Numerik.
Es handelt sich um ein sogenanntes Iterationsverfahren. Man beginnt mit einem (meist geratenen) Näherungswert \(x_0\) für die gesuchte Lösung der Gleichung
\(f(x) = 0\)
und berechnet daraus eine weitere, hoffentlich bessere Näherung \(x_1\). Aus dieser Zahl \(x_1\) berechnet man auf dieselbe Weise weitere Näherungen \(x_2, x_3,\dots\) und hofft, dass sich diese Werte der Lösung immer mehr annähern.
Für reelle Funktionen \(f\colon \mathbb {R} \to \mathbb {R}\) lässt sich das Verfahren geometrisch sehr einleuchtend motivieren. Ausgehend von einem Startwert \(x_0\) wird eine Folge von Näherungen \(x_1, x_2, x_3,\ldots \) rekursiv konstruiert. Dabei erhält man \(x_{n+1}\) aus \(x_ n\), indem man die Funktion \(f\) durch ihre Tangente im Punkt \((x_ n,f( x_ n))\) ersetzt und die Nullstelle der Funktion
\(\tilde{f}(x)=f( x_n)+(x-x_n)f’(x_n)\)
berechnet.
Diese liefert dann die nächste Näherung \(x_{n+1}\).
Sei \(f\colon\mathbb{R}\to\mathbb{R}\) stetig differenzierbar. Dann bezeichnet man als Newton-Verfahren zum Startwert \(x_0\) die Rekursionsvorschrift
\( x_{n+1} = x_n - \displaystyle\frac{f( x_n)}{f'(x_n)}.\)
Man berechnet so viele Glieder dieser rekursiven Folge, bis man eine ausreichende Genauigkeit erreicht hat.
Die Geometrie des Newton-Verfahrens kann man in dem folgenden Applet erkennen.
Applet: Das Newton-Verfahren geometrisch
Führen Sie mit dem Schieberegler bis zu fünf Schritte des Newton-Verfahrens durch und beobachten Sie das Verhalten der Iterierten \(x_1, x_2, x_3, x_4\) und \(x_5\).
Experimentieren Sie auch mit verschiedenen Startwerten.
J.H., erstellt mit GeoGebra
Beispiel:
Die Gleichung \(\sin( x)= x-1\) besitzt nach dem Zwischenwertsatz mindestens eine Lösung im Intervall \([0,\pi ]\), denn betrachtet man die Funktion \(f( x):=\sin( x) -x +1\), so ist \(f(0)=1>0\) und \(f(\pi )= 0-\pi +1<0\). Die Funktion \(f\) besitzt also eine Nullstelle zwischen \(0\) und \(\pi \). Um diese näherungsweise zu berechnen kann man das Newton-Verfahren verwenden, beispielsweise mit Startwert \(x_0=2\).
Die Iterationsvorschrift
\(x_{n+1}=x_n-\displaystyle\frac{\sin( x_n)-x_n+1}{\cos( x_n)-1}\)
führt auf
\(\begin{array}{rcl}x_1&=&1-\displaystyle\frac{\sin(1)}{\cos(1)-1}\approx2,8304877\\x_2&\approx&2,04955524\\x_3&\approx&1,93865612\\x_4&\approx&1,9345689621\\x_5&\approx&1,934563210763\end{array}\)
Die Folge scheint also zu konvergieren. Außerdem scheint der Grenzwert tatsächlich eine Nullstelle zu sein, denn
\(\sin(1,934563210763)-1,934563210763+1=-1,545\cdot10^{-11}.\)
Es stellt sich nun die Frage, ob dieses Verfahren immer so gut funktioniert. Leider gibt es dazu eine positive und eine negative Antwort. Zunächst die negative: Man kann sich anhand der geometrischen Konstruktion Funktionen \(f\) und Startwerte \(x_0\) überlegen, bei denen die Folge der Newton-Iterierten keinesfalls konvergiert. Die gute Nachricht: Wenn man den Startwert bereits
Sei \([a,b]\subset \mathbb {R}\) und \(f:[a,b]\to \mathbb {R}\) zweimal stetig differenzierbar und sei \(f’(x)\neq 0\) für alle \(x\in [a,b]\). Sei weiter \(f(a)\cdot f(b)<0\), so dass \(f\) nach dem Zwischenwertsatz eine Nullstelle \(x_{\ast }\) im Intervall \((a,b)\) besitzt.
Dann existiert ein \(\delta >0\), so dass das Newton-Verfahren für jeden Startwert \(x_0\in (x_{\ast }-\delta , x_{\ast }+\delta )\) gegen \(x_{\ast }\) konvergiert.
Die Konvergenz ist quadratisch, d.h. es gibt eine Konstante \(c>0\), so dass für den (absoluten) Fehler die Ungleichung
\(|x_{n+1}-x_{\ast}|\;\leq \;c\,|x_n-x_{\ast}|^2\)
gilt.
Beweis: Wegen der Stetigkeit von \(f’\) und da \(f’(x_{\ast })\neq 0\) ist, gibt es ein \(\varepsilon >0\) und ein \(\delta >0\), so dass für \(|x-x_{\ast }|<\delta \) gilt: \(|f’(x)|>\varepsilon \). Unter Anwendung des Mittelwertsatzes ist \(\begin{array}{rcl}|x_{n+1}-x_{\ast}|&=&\left|x_n-x_{\ast}-\displaystyle\frac{f(x_n)}{f’(x_n)}\right|\\ &=&\left|x_n-x_{\ast}-\displaystyle\frac{f(x_n)-f(x_{\ast})}{f’(x_n)}\right|\\ &=&\left|x_n-x_{\ast}-(x_n-x_{\ast})\displaystyle\frac{f’(\eta)}{f’(x_n)}\right|\\ &=&|x_n-x_{\ast}|\cdot\left|1-\displaystyle\frac{f’(\eta)}{f’(x_n)}\right|\end{array}\) für eine Zwischenstelle \(\eta \) zwischen \(x_ n\) und \(x_{\ast }\). Ebenfalls mit dem Mittelwertsatz erhält man die Gleichung \(1-\displaystyle\frac{f’(\eta)}{f’(x_n)}=\displaystyle\frac{f’(x_n)-f’(\eta)}{f’(x_n)}=(x_n-\eta)\displaystyle\frac{f”(\tau)}{f’(x_n)}\) mit einer weiteren Zwischenstelle \(\tau \) zwischen \(\eta \) und \(x_{\ast }\). Insgesamt gilt also \(|x_{n+1}-x_{\ast}|=|x_n-x_{\ast}|\cdot\left|1-\displaystyle\frac{f’(\eta)}{f’(x_n)}\right|=|x_n-x_{\ast}|\cdot|x_n-\eta|\cdot\displaystyle\frac{|f”(\tau)|}{|f’(x_n)|}\leq|x_n-x_{\ast}|^2\cdot\displaystyle\frac{|f”(\tau)|}{|f’(x_n)|}\) Nach dem Satz vom Maximum nimmt die stetige Funktion \(|f”|\) ihr Maximum auf dem Intervall \([a,b]\) an, es gibt also eine Zahl \(M>0\), so dass \(|f”(x)|\leq M\) für alle \(x\in [a,b]\). Dann gilt also \(|x_{n+1}-x_{\ast}|\leq |x_n-x_{\ast}|^2 \displaystyle\frac{M}{\varepsilon}.\) Wir verkleinern (falls nötig) \(\delta \) noch etwas, so dass \(\delta \displaystyle\frac {M}{\varepsilon }<\displaystyle\frac {1}{2}\) ist. Dann ist \(|x_{n+1}-x_{\ast}|\leq\delta\displaystyle\frac{M}{\varepsilon}|x_n-x_{\ast}|<\displaystyle\frac{1}{2}|x_n-x_{\ast}|\) und der Abstand der Iterierten zum Fixpunkt wird immer kleiner. Auf diese Weise ist sichergestellt, dass das Newton-Verfahren auf jeden Fall gegen \(x_{\ast }\) konvergiert. Am Ende des Kapitels haben Sie wieder die Wahl: