Spickzettel

Zum schnellen Nachschlagen in der Vorlesung. Alles Wichtige auf einer Seite, mit Links zur ausführlichen Erklärung. Stand: bis 2.3 Newton-Verfahren.

Schneller finden

/ oder Strg+K öffnet die Suche überall auf der Seite. Tippfehler sind egal („auslöschng“, „konvergensordnung“).

Die vier Fragen (Kapitel 0)

Begriff	Eigenschaft von	Frage	Merkhilfe
Kondition	Problem	Wie stark wirken Eingabefehler auf das exakte Ergebnis?	$\kappa=\left\lvert\frac{x f'(x)}{f(x)}\right\rvert$
Konsistenz	Verfahren	Löst das Verfahren (ohne Rundung) das richtige Problem?	Verfahrensfehler $\to0$
Stabilität	Algorithmus	Verstärkt die Rechnung Rundungsfehler?	Auslöschung vermeiden
Konvergenz	alles zusammen	Kommt am Rechner das Richtige heraus?	konsistent + stabil ⇒ konvergent

Rundungsfehler (Kapitel 1)

Was	Formel / Wert
Maschinenzahlen	$\pm E^b\sum_{i=1}^N a_iE^{-i}$, $a_1\neq0$, $b_{\min}\le b\le b_{\max}$
IEEE double	1 + 11 + 52 Bit, $10^{-308}<\lvert x\rvert<10^{308}$, $\approx16$ Stellen
Maschinengenauigkeit	$\text{eps}=2^{-53}\approx1.1\cdot10^{-16}$
Rechenmodell	$\operatorname{rd}(x)=x(1+\tau)$, $\lvert\tau\rvert\le\text{eps}$
absoluter / relativer Fehler	$\Delta x=\tilde x-x$, $\varepsilon_x=\Delta x/x$
totales Differential	$\Delta z\approx\sum_i\frac{\partial f}{\partial x_i}\Delta x_i$, $\varepsilon_z\approx\sum_i\frac{x_i}{f}\frac{\partial f}{\partial x_i}\varepsilon_{x_i}$
Addition	$\varepsilon_{x+y}=\frac{x}{x+y}\varepsilon_x+\frac{y}{x+y}\varepsilon_y$
Multiplikation / Division	$\varepsilon_{xy}\approx\varepsilon_x+\varepsilon_y$, $\varepsilon_{x/y}\approx\varepsilon_x-\varepsilon_y$
$\ln$, $\sqrt{\phantom{x}}$, $\sin$	$\varepsilon_x/\ln x$, $\;\frac12\varepsilon_x$, $\;x\cot x\,\varepsilon_x$
mit Rundung des Ergebnisses	zusätzlich $+\tau_z$, $\lvert\tau_z\rvert\le\text{eps}$

Stabil oder nicht?

stabil	instabil
$\cdot$, $\div$, $\sqrt{\phantom{x}}$	Subtraktion fast gleicher Zahlen (Auslöschung)
$+$ bei gleichen Vorzeichen	$\ln x$ für $x\approx1$, $\sin x$ für $x\approx k\pi$
Rekursion mit Fehlerfaktor $<1$	Rekursion mit Fehlerfaktor $>1$ (Übung 1)

Stabil umformen: $\sqrt{a+h}-\sqrt a=\dfrac{h}{\sqrt{a+h}+\sqrt a}$, $\;1-\sqrt{1-u^2}=\dfrac{u^2}{1+\sqrt{1-u^2}}$, $\;1-\cos x=2\sin^2\frac x2$.

Nichtlineare Gleichungen (Kapitel 2)

Was	Formel
Kondition, $m$-fache Nullstelle	$\lvert\tilde x^*-x^*\rvert\lesssim\left(\frac{\varepsilon\,m!}{\lvert f^{(m)}(x^*)\rvert}\right)^{1/m}$
… einfach ($m=1$)	$\varepsilon/\lvert f'(x^*)\rvert$, gut konditioniert
… mehrfach	$\sim\varepsilon^{1/m}$, z.B. $\varepsilon=10^{-16}$, $m=4$: $10^{-4}$
Newton	$x_{i+1}=x_i-\dfrac{f(x_i)}{f'(x_i)}$ (Minus!)
Tangente in $x_i$	$y=f(x_i)+f'(x_i)(x-x_i)$
Konvergenzsatz	$f\in C^2[a,b]$, B1 $f(a)f(b)<0$, B2 $f'\neq0$, B3 $f''$ ohne Vorzeichenwechsel, B4 Newton-Schritt von $a$, $b$ bleibt in $[a,b]$
Konstanten	$m=\min\lvert f'\rvert$, $M=\max\lvert f''\rvert$, $K=\frac{M}{2m}$
a posteriori	$\lvert x^*-x_n\rvert\le K\lvert x_n-x_{n-1}\rvert^2$
a priori	$\lvert x^*-x_n\rvert\le\frac1K\big((b-a)K\big)^{2^n}$
Konvergenzordnung $p$	$\lvert x_{n+1}-x^*\rvert\le C\lvert x_n-x^*\rvert^p$
Newton, einfache NST	$p=2$ (Stellen verdoppeln sich)
Newton, $m$-fache NST	$p=1$, Faktor $\frac{m-1}{m}$
Abbruch	$\lvert x_{n+1}-x_n\rvert<\varepsilon$ oder $\lvert f(x_n)\rvert<\varepsilon$, plus $n_{\max}$

Probleme bei Newton: $f'(x_i)=0$ (waagrechte Tangente) · Sprung zu anderer Nullstelle · Zyklus $x_{n+2}=x_n$ (Wendepunkt, z.B. $\tanh$) · mehrfache Nullstelle (nur linear).

Beispiele mit Ergebnis

Beispiel	Startwert	Ergebnis
Zins $Kx^{m+1}-(r+K)x^m+r$, $K=50000$, $r=1200$, $m=48$	$1.01$	$x^*=1.0059298$, $p\approx7.12\,\%$ ($x=1$ ist Scheinlösung)
$x-\cos x$	$0.7$	$0.739085133215$
$x-e^{-x}$ auf $[0,1]$	beliebig in $[0,1]$	$0.567143290410$, $K=\frac{e}{2(e+1)}\approx0.366$
Kettenlinie $\cosh z=1+0.1z$	$0.2$	$z^*=0.1993390461$, $a=10/z^*\approx50.17$ m
$\frac\pi2-x-\cos x$ (dreifach)	$1.5$	linear, Stillstand bei Fehler $\approx7\cdot10^{-6}$