2.3 Newton-Verfahren

Auch Newton-Raphson-Verfahren. Folien: 📄 Folie 3–7, Zusammenfassung 📄 Folie 11

Aufgabe (Tafel): Finde eine Lösung $x^*$ zu einer Gleichung $f(x)=0$.

Bemerkung (Tafel): Für eine Gleichung $f_1(x)=f_2(x)$ löse die Gleichung $f_1(x)-f_2(x)=0$.

Prinzip (Tafel)

1. a) Wähle einen Startwert $x_0$. b) Approximiere $f$ im Punkt $P_0=(x_0,y_0)$ mit $y_0=f(x_0)$ durch die Tangente $t_0$. c) Berechne den Schnittpunkt $(x_1,0)$ von $t_0$ mit der $x$-Achse. d) Ist $x_0$ geeignet gewählt, ist $x_1$ eine bessere Näherung an $x^*$.
2. Wiederhole 1) mit $x_1$ als Startwert.
3. Terminiere die Iteration geeignet.

⇒ Die so konstruierte Folge $(x_i)$ konvergiert unter geeigneten Voraussetzungen gegen die gesuchte Lösung $x^*$.

Die Idee: Eine Gerade kann man trivial nach $x$ auflösen. Also ersetzt man $f$ lokal durch die beste Gerade, die Tangente, und nimmt deren Nullstelle.

Iterationsvorschrift (Tafel)

Tangentengleichung von $f$ in $P_i=(x_i,y_i)=(x_i,f(x_i))$. Ansatz $y=f'(x_i)\,x+c$, durch $P_i$: $c=y_i-x_i f'(x_i)$.

$$y=x\,f'(x_i)+\underbrace{y_i}_{=f(x_i)}-x_i\,f'(x_i)=f(x_i)+f'(x_i)(x-x_i).$$

Schnittpunkt mit der $x$-Achse ($y=0$):

$$0=f(x_i)+f'(x_i)(x-x_i)\quad\Longleftrightarrow\quad x=x_i-\frac{f(x_i)}{f'(x_i)}\qquad(f'(x_i)\neq0).$$

⇒ Verbesserung der Näherung:

$$\boxed{\;x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)},\qquad i=0,1,2,\dots\ \text{(bis Stop)}\;}$$

Korrektur zum Aufschrieb

Im Heft steht beim Umstellen $x=x_i+\frac{f(x_i)}{f'(x_i)}$ (mit Plus). Aus $0=f(x_i)+f'(x_i)(x-x_i)$ folgt $x-x_i=-\frac{f(x_i)}{f'(x_i)}$, also Minus. So steht es auch auf 📄 Folie 11. Kontrolle an einem Beispiel: $f(x)=x-1$, $x_0=3$. Minus liefert $x_1=3-2/1=1$ ✔, Plus liefert $5$ ✘.

Ablauf (Folie 5, Skript)

📄 Folie 5

Schritt	Was tun	Beispiel Zins
A) Intervall	$[a,b]$ wählen, in dem genau eine Nullstelle liegt (Vorzeichenwechsel, Skizze)	$x>1$, Scheinlösung $x=1$ ausschließen
B) Startwert	$x_0\in[a,b]$, möglichst nah an $x^*$; Konvergenzsatz prüfen	$x_0=1.01$
C) Iteration	$x_{i+1}=x_i-f(x_i)/f'(x_i)$	Formel mit $f'(x)=(m+1)Kx^m-m(r+K)x^{m-1}$
D) Abbruch	z.B. $\lvert x_{n+1}-x_n\rvert<\varepsilon$ oder $\lvert f(x_n)\rvert<\varepsilon$ oder $n>n_{\max}$	$p=1200(x_n-1)$

Abbruchkriterien richtig wählen

• $|x_{n+1}-x_n|<\varepsilon$: misst den Schritt. Bei quadratischer Konvergenz ist der Fehler von $x_{n+1}$ dann sogar $\approx K\varepsilon^2$ (a-posteriori-Schranke). Bei großen $x$ besser relativ: $|x_{n+1}-x_n|<\varepsilon\,|x_{n+1}|$.
• $|f(x_n)|<\varepsilon$: allein trügerisch, wenn $f$ sehr flach ist (kleines $f$, aber großer Abstand zu $x^*$, vgl. Kondition).
• Immer zusätzlich eine maximale Iterationszahl, sonst endlose Schleife bei Divergenz oder Zyklus. (Ergänzung)

Beispiele

Beispiel 1: Zins

Siehe 2.1: ab $x_0=1.01$ in 5 Schritten $p\approx7.1158\,\%$.

Beispiel 2: $x=\cos x$

Siehe 2.1: ab $x_0=0.7$ nach 3 Schritten $x^*\approx0.739085133215$.

Beispiel 3: $e^{-x}=x$ (Folie 6–7)

📄 Folie 6

$f(x)=x-e^{-x},\qquad x_{n+1}=x_n-\frac{x_n-e^{-x_n}}{1+e^{-x_n}}.$

A) Intervall: $a=0$, $b=1$. Dort ist $f\in C^2[0,1]$.

B) Voraussetzungen des Konvergenzsatzes prüfen:

	Bedingung	Nachweis
B1	Vorzeichenwechsel	$f(0)=-1<0$, $f(1)=1-\frac1e>0$ ⇒ Nullstelle in $[0,1]$
B2	$f'\neq0$	$f'(x)=1+e^{-x}>0$ ⇒ $f$ streng monoton wachsend, Nullstelle eindeutig
B3	$f''$ ohne Vorzeichenwechsel	$f''(x)=-e^{-x}<0$ ⇒ $f$ ist konkav (↷) auf $[0,1]$
B4	Newton-Schritt von den Rändern bleibt im Intervall	$x_1\vert_{x_0=0}=\frac12$, $x_1\vert_{x_0=1}=\frac{2}{1+e}\approx0.538<1$ ⇒ Startwerte ok

Folgerungen (Folie 7):

a) Die Folge $x_0,x_1,x_2,\dots$ konvergiert für jeden Startwert aus $[0,1]$ gegen die Nullstelle.

b) Fehlerabschätzung mit

$$m=\min_{[0,1]}|f'(x)|=\min_{[0,1]}(1+e^{-x})=1+\frac1e=\frac{e+1}{e},\qquad M=\max_{[0,1]}|f''(x)|=\max_{[0,1]}e^{-x}=1,$$ $$\Rightarrow\quad|x^*-x_n|\le\frac{M}{2m}|x_n-x_{n-1}|^2=\frac{e}{2(e+1)}|x_n-x_{n-1}|^2\approx0.3655\,|x_n-x_{n-1}|^2.$$

Zahlen (selbst nachgerechnet, $x^*=0.567143290409784$):

$n$	$x_n$ (ab $x_0=0$)	Schranke $0.3655\,\lvert x_n-x_{n-1}\rvert^2$	wahrer Fehler
1	0.500000000000	$9.1\cdot10^{-2}$	$6.7\cdot10^{-2}$
2	0.566311003197	$1.6\cdot10^{-3}$	$8.3\cdot10^{-4}$
3	0.567143165035	$2.5\cdot10^{-7}$	$1.3\cdot10^{-7}$
4	0.567143290410	$5.7\cdot10^{-15}$	$2.9\cdot10^{-15}$

Die Schranke ist immer gültig und dabei nur etwa um Faktor 2 zu pessimistisch.

Konvergenzsatz

Satz (Konvergenz des Newton-Verfahrens, Skript/Folie 6)

Sei $f\in C^2[a,b]$ mit

• (B1) $f(a)\cdot f(b)<0$,
• (B2) $f'(x)\neq0$ für alle $x\in[a,b]$,
• (B3) $f''(x)\ge0$ für alle $x\in[a,b]$ oder $f''(x)\le0$ für alle $x\in[a,b]$,
• (B4) $a-\dfrac{f(a)}{f'(a)}\in[a,b]$ und $b-\dfrac{f(b)}{f'(b)}\in[a,b]$.

Dann gilt:

1. $f$ hat genau eine Nullstelle $x^*\in[a,b]$, und das Newton-Verfahren konvergiert für jeden Startwert $x_0\in[a,b]$ gegen $x^*$.
2. Mit $m:=\min_{[a,b]}|f'|>0$, $M:=\max_{[a,b]}|f''|$ und $K:=\dfrac{M}{2m}$ gelten die Fehlerabschätzungen unten.

Warum die Bedingungen?

• B1 garantiert eine Nullstelle (Zwischenwertsatz).
• B2 macht sie eindeutig (strenge Monotonie) und verhindert Division durch 0.
• B3 verhindert, dass $f$ einen Wendepunkt hat. Ohne Wendepunkt liegen alle Iterierten ab $x_1$ auf derselben Seite von $x^*$ und laufen monoton darauf zu. (Mit Wendepunkt kann Newton hin- und herspringen.)
• B4 sorgt dafür, dass selbst der erste Schritt vom ungünstigsten Startwert (Rand) nicht aus $[a,b]$ herausspringt.

Fehlerabschätzung

$$\boxed{\;\text{a posteriori:}\quad|x^*-x_n|\le K\,|x_n-x_{n-1}|^2\;}$$ $$\boxed{\;\text{a priori:}\quad|x^*-x_n|\le\frac1K\big(K\,|x_0-x^*|\big)^{2^n}\le\frac1K\big((b-a)\,K\big)^{2^n}\;}$$

• A posteriori = nach der Rechnung, mit den berechneten $x_n$. Scharf und praktisch: Die Schranke dient direkt als Abbruchkriterium.
• A priori = vor der Rechnung. Sagt, wie viele Schritte man höchstens braucht. Nur aussagekräftig, wenn $(b-a)K<1$, sonst ggf. das Intervall verkleinern.

Beispiel 3 a priori: $(b-a)K=0.3655$. Für $n=4$: $\frac1K\cdot0.3655^{16}\approx2.8\cdot10^{-7}$. Die a-posteriori-Schranke ($5.7\cdot10^{-15}$) ist viel schärfer.

Ergänzung: Herleitung der Abschätzungen

Quadratische Konvergenz. Taylor von $f$ um $x_n$, ausgewertet in $x^*$:

$0=f(x^*)=f(x_n)+f'(x_n)(x^*-x_n)+\tfrac12f''(\xi)(x^*-x_n)^2.$

Durch $f'(x_n)$ teilen und $x_{n+1}=x_n-f(x_n)/f'(x_n)$ einsetzen:

$x^*-x_{n+1}=-\frac{f''(\xi)}{2f'(x_n)}(x^*-x_n)^2\quad\Rightarrow\quad|x^*-x_{n+1}|\le K\,|x^*-x_n|^2.$

Rekursiv eingesetzt: $K|x^*-x_n|\le(K|x^*-x_0|)^{2^n}$, das ist die a-priori-Schranke.

A posteriori. Taylor von $f$ um $x_{n-1}$, ausgewertet in $x_n$. Die ersten beiden Terme heben sich nach Konstruktion von $x_n$ genau auf:

$f(x_n)=\underbrace{f(x_{n-1})+f'(x_{n-1})(x_n-x_{n-1})}_{=0}+\tfrac12f''(\eta)(x_n-x_{n-1})^2.$

Mittelwertsatz: $|f(x_n)|=|f(x_n)-f(x^*)|\ge m\,|x_n-x^*|$. Zusammen: $m|x_n-x^*|\le\frac M2|x_n-x_{n-1}|^2$.

Konvergenzordnung

Ein Verfahren hat Konvergenzordnung $p\ge1$, wenn es ein $C>0$ gibt (für $p=1$: $C<1$) mit

$|x_{n+1}-x^*|\le C\,|x_n-x^*|^p\quad\text{für alle }n\text{ ab einem }n_0.$

$p$	Name	Verhalten
1	linear	pro Schritt kommt eine feste Anzahl Stellen dazu ($\approx-\log_{10}C$)
$1<p<2$	superlinear	z.B. Sekantenverfahren $p=\frac{1+\sqrt5}2\approx1.618$ (kommt später)
2	quadratisch	Anzahl gültiger Stellen verdoppelt sich pro Schritt
3	kubisch	verdreifacht sich (Halley, kommt später)

Newton hat Ordnung 2 bei einfachen Nullstellen und $f\in C^2$ (📄 Folie 11). Das zeigt die Herleitung oben mit $C=K$. Sichtbar in Beispiel 3: Fehler $6.7\cdot10^{-2}\to8.3\cdot10^{-4}\to1.3\cdot10^{-7}\to2.9\cdot10^{-15}$, der Exponent verdoppelt sich ungefähr.

Aber nur lokal

Quadratische Konvergenz gilt erst, wenn man nah genug an $x^*$ ist. Weiter weg kann Newton langsam sein, springen oder divergieren. Deshalb ist die Wahl von Intervall und Startwert (A, B) so wichtig, und deshalb gibt es das gedämpfte Newton-Verfahren (kommt später).

Probleme

1. Waagrechte Tangente

Ist $f'(x_i)=0$ (oder sehr klein), dann ist die Tangente waagrecht und schneidet die $x$-Achse nicht (oder sehr weit weg). Die Iteration bricht ab oder springt weit aus dem Intervall. Beispiel: $f(x)=x^2-1$ mit $x_0=0$.

2. Falsche Nullstelle

Liegt $x_0$ ungünstig, landet $x_1$ im Einzugsbereich einer anderen Nullstelle. Beispiel Zins: Für $x_0$ knapp über 1 konvergiert Newton zur Scheinlösung $x=1$.

3. Zyklen

Bei Wendepunkten (B3 verletzt) kann die Folge zwischen zwei Werten pendeln: $x_{n+2}=x_n$. Beispiel: $f(x)=\tanh x$ hat die einzige Nullstelle $0$. Für $x_0\approx1.08866$ ist $x_1=-x_0$, $x_2=x_0$, … (für $|x_0|$ noch größer divergiert die Folge sogar). In der Demo unten: Beispiel „tanh x“.

4. Mehrfache Nullstellen

Bei einer $m$-fachen Nullstelle ist $f'(x^*)=0$. Newton konvergiert dann nur noch linear mit Faktor $\frac{m-1}{m}$. Beispiel $f(x)=\frac\pi2-x-\cos x$, dreifache Nullstelle bei $\frac\pi2$, $x_0=1.5$:

$n$	1	2	3	5	10	15	20	25
Fehler	$4.7\cdot10^{-2}$	$3.2\cdot10^{-2}$	$2.1\cdot10^{-2}$	$9.3\cdot10^{-3}$	$1.2\cdot10^{-3}$	$1.6\cdot10^{-4}$	$2.2\cdot10^{-5}$	$7.2\cdot10^{-6}$

Der Fehler schrumpft pro Schritt um $\frac23$, und nach 26 Schritten steht die Iteration bei $7\cdot10^{-6}$, weil $f$ dort in double exakt $0$ wird. Genauer geht es wegen der Kondition ($\varepsilon^{1/3}$) auch nicht.

Ergänzung: warum Faktor $\frac{m-1}m$?

Für $f(x)=(x-x^*)^m$ ist $\frac{f}{f'}=\frac{x-x^*}{m}$, also $x_{n+1}-x^*=(x_n-x^*)\big(1-\frac1m\big)$. Abhilfe (kommt später, 📄 Folie 13–14): $x_{i+1}=x_i-m\,\frac{f(x_i)}{f'(x_i)}$, wenn $m$ bekannt ist, oder Newton auf $g=f/f'$ anwenden.

Interaktiv

Klick in den Plot setzt den Startwert $x_0$. Mit den Schritt-Knöpfen oder dem Schieberegler geht man Schritt für Schritt: erst Punkt und Tangente, dann ihr Schnittpunkt mit der $x$-Achse. Die Tabelle zeigt $x_i$, $f(x_i)$ und die Schrittweite.

f(x) = x − cos xf(x) = x − e^(−x)f(x) = Zins: Kx^(m+1) − (K+r)x^m + rf(x) = π/2 − x − cos xf(x) = tanh xf(x) = cosh x − 1 − x/10x₀ =oder ins Bild klicken, um x₀ zu setzen

Schritt 1/10: Startwert x₀ = 0.7.

langsamnormalschnellsehr schnell

Skript 2.2, Beispiel 1: einfache Nullstelle, quadratische Konvergenz.

i	xᵢ	f(xᵢ)	|xᵢ − xᵢ₋₁|
0	0.7	-6.48e-2

Zum Ausprobieren:

• x − cos x und x − e^(−x): quadratische Konvergenz, die Schrittweite quadriert sich ungefähr.
• Zins: $x_0=1$ eingeben, Newton bleibt auf der Scheinlösung. $x_0=1.002$ führt ebenfalls dorthin.
• π/2 − x − cos x: lineare Konvergenz und Stillstand bei $\approx7\cdot10^{-6}$.
• tanh x: $x_0=1.0886594924826534$ ergibt einen Zyklus, $x_0=1.2$ divergiert, $x_0=1$ konvergiert.
• cosh x − 1 − x/10: Übung 2, Aufgabe 3.

Übung 2

📄 Übungsblatt 2

Aufgabe 3: Kettenlinie

Ein Seil hängt zwischen zwei gleich hohen Masten, Spannweite $2\ell$, Durchhang $h$. Es gilt $a\cosh\frac{\ell}{a}=a+h$. Gegeben $h=1$ m, $\ell=10$ m, gesucht $a$.

Substitution $z=\frac{\ell}a=\frac{10}a$, also $a=\frac{10}z$:

$\frac{10}z\cosh z=\frac{10}z+1\quad\Big|\cdot\frac z{10}\quad\Longrightarrow\quad\cosh z=1+0.1\,z.$

Genau eine Lösung für $z>0$ (Skizze): $\cosh z$ startet bei $(0,1)$ mit Steigung $0$ und ist konvex. Die Gerade $1+0.1z$ startet am selben Punkt mit Steigung $0.1$. Also liegt die Gerade zuerst über $\cosh$, aber $\cosh$ wächst exponentiell und überholt sie genau einmal. ($z=0$ ist die triviale Lösung, die nicht zählt.)

Konvergenzsatz auf $[0.15,1]$ für $f(z)=\cosh z-1-0.1z$:

	Nachweis
B1	$f(0.15)\approx-0.00373<0$, $f(1)\approx0.443>0$
B2	$f'(z)=\sinh z-0.1$ ist wachsend, $f'(0.15)\approx0.0506>0$ ⇒ $f'>0$ auf $[0.15,1]$
B3	$f''(z)=\cosh z>0$
B4	Schritt von $0.15$: $0.2237\in[0.15,1]$. Schritt von $1$: $0.5879\in[0.15,1]$

$m=f'(0.15)\approx0.0506$, $M=\cosh1\approx1.543$, $K=\frac M{2m}\approx15.26$.

Newton ab $z_0=0.2$ (selbst nachgerechnet):

$n$	$z_n$	$\lvert z_n-z_{n-1}\rvert$	Schranke $K\lvert z_n-z_{n-1}\rvert^2$
1	0.19934124479551	$6.6\cdot10^{-4}$	$6.6\cdot10^{-6}$
2	0.19933904615910	$2.2\cdot10^{-6}$	$7.4\cdot10^{-11}$ ✔
3	0.19933904613461	$2.4\cdot10^{-11}$	$9.2\cdot10^{-21}$

Schon $z_2$ erfüllt $|z_n-z^*|<10^{-10}$. Damit $z^*\approx0.1993390461$ und

$a=\frac{10}{z^*}\approx50.166\ \text{m}.$

Aufgabe 4: Schnittpunkt $f=g$

$f(x)=\exp\Big(\frac13-\frac x2\Big),\qquad g(x)=x^4-\frac83x^3+\frac{67}{24}x^2-\frac{50}{27}x+\frac{257}{162}.$

Newton auf $F=f-g$ mit $x_0=1$:

$n$	1	2	5	10	20	28
$x_n$	0.91542	0.85201	0.74217	0.68189	0.66701	0.66668

Auffällig: Die Konvergenz ist nur linear, der Fehler schrumpft pro Schritt etwa um $\frac23$, und die Iteration steht bei $\approx0.66668$ still (Fehler $\approx2\cdot10^{-5}$).

Grund: Bei $x^*=\frac23$ stimmen $f$ und $g$ bis zur zweiten Ableitung überein: $f(\frac23)=g(\frac23)=1$, $f'=g'=-\frac12$, $f''=g''=\frac14$, aber $f'''=-\frac18\neq g'''=0$. Also ist $x^*=\frac23$ eine dreifache Nullstelle von $F$. Newton konvergiert linear mit Faktor $\frac{m-1}m=\frac23$ (Problem 4), und die Kondition begrenzt die Genauigkeit auf $\approx(6\,\text{eps}/\tfrac18)^{1/3}\approx2\cdot10^{-5}$.

a) Wie viele Schnittpunkte? In der Skizze sieht man nur einen Berührpunkt bei $x\approx\frac23$. Tatsächlich gibt es in $[0,2]$ zwei: die dreifache Nullstelle $\frac23$ und eine einfache bei $x\approx0.6458$ (selbst nachgerechnet). Dazwischen ist $F$ nur $\approx10^{-8}$ groß, das sieht man mit bloßem Auge nicht.

Ausblick

Noch nicht dran (kommt mit der nächsten Vorlesung, 📄 Folie 12 ff.): gedämpftes Newton-Verfahren, Newton für mehrfache Nullstellen, Quasi-Newton (Sekanten-, Muller-, Sidi-, Steffensen-Verfahren), höhere Ordnung (Halley), multivariates Newton.