Kapitel 0 – Einleitung

Folien: 📄 Numa00.pdf · Skript Grieb, Kap. 1

Organisation

Prof. Dr. Georg Umlauf, Institut für Optische Systeme, Büro E 407. Sprechzeit: „jederzeit, wenn die Tür offen ist“.

Was	Wann / Wo
Vorlesung	Montag 11:30–13:00, F 023
Theoretische Übungen	kapitelweise als PDF online, siehe Übersicht
Programmierübung	ein Thema aus vier, siehe Übersicht
Prüfung	mündlich, Einzeltermin in der Prüfungszeit, Terminplanung nach der Anmeldung im Dezember

Skript: H. Grieb (FH Esslingen) im Moodle, liegt hier als 📄 NumaSkript.pdf. Viel Stoff kommt per Tafelanschrieb.

Literatur (Folien 7–9): Dahmen/Reusken, Numerik für Ingenieure und Naturwissenschaftler; Press et al., Numerical Recipes in C++; Stoer/Bulirsch, Numerische Mathematik 1.

Inhalt: §0 Einleitung · §1 Rundungsfehler · §2 Nichtlineare Gleichungen · §3 Lineare Gleichungssysteme · §4 Überbestimmte LGS · §5 Interpolation · §6 Approximation.

Was ist numerische Mathematik? (Folie §0/13)

Ein Problem aus der Praxis wird erst zu einem naturwissenschaftlichen Modell, dann zu einem mathematischen Modell. Für das mathematische Modell fragt die Algebra/Analysis: Gibt es eine Lösung? Ist sie eindeutig? Kann man sie exakt hinschreiben? Die Numerik fragt dagegen:

• Welcher Algorithmus, direkt oder iterativ?
• Wie gut passt der Algorithmus zum Problem (Konsistenz), wie empfindlich ist das Problem (Kondition), wie robust der Algorithmus (Stabilität)?
• Welcher Fehler bleibt am Ende, und wie schnell ist das Ganze (Effizienz)?

Das Ergebnis wird dann in der Praxis überprüft und das Modell gegebenenfalls angepasst. Der Kreis schließt sich.

Forderungen an ein numerisches Verfahren (Folien §0/14–15)

Ein Verfahren muss als Algorithmus darstellbar sein:

• benutzt nur elementare Rechenoperationen,
• liefert aus den Eingabedaten nach endlich vielen Schritten die Ergebnisdaten,
• ist logisch und arithmetisch korrekt, z.B. keine Division durch Null,
• liefert Fehlerschranken, damit man das Ergebnis garantieren oder bewerten kann.

Man unterscheidet

Art	Idee	Beispiele
direkt	endliche Formel, liefert (bis auf Rundung) das exakte Ergebnis	Gauß-Elimination, Mitternachtsformel
iterativ	wiederholt denselben Schritt, die Genauigkeit wird schrittweise besser	Newton-Verfahren, Backpropagation

Bei der Analyse eines Verfahrens interessieren: Anzahl der Rechenoperationen (Laufzeit), Speicherbedarf, Parallelisierbarkeit (GPGPU), Stabilität gegenüber Eingabefehlern, Fehlerschranken und bei Iterationen die Approximationsgüte.

Grieb ergänzt (S. 5): Ein Algorithmus soll keine rechnerabhängigen Daten verwenden, und sein Fehler soll mit wachsender Ziffernlänge des Rechners gegen 0 gehen.

Fehlerarten (Folie §0/16)

Fehler	Ursache	Wer ist zuständig?
Eingabefehler	Messungenauigkeit, Erhebungsfehler, Abtastrate, Konvertierung in Maschinenzahlen	Problem der Daten, hat aber Einfluss auf die Numerik
Rundungsfehler	nur endlich viele Stellen (Quantisierung)	zentrale Aufgabe der Numerik
Abbruchfehler	Rechnung muss nach endlich vielen Schritten enden	zentrale Aufgabe der Numerik
Diskretisierungsfehler	stetige Funktion durch endlich viele Werte ersetzt (Schrittweite), z.B. Differenzenquotient statt Ableitung	zentrale Aufgabe der Numerik
Menschlicher Irrtum, Fehlfunktion		außerhalb der Numerik

Beispiel Abbruchfehler (Grieb S. 6): Die harmonische Reihe $\sum_{k\ge1} 1/k$ divergiert, liefert auf jedem Rechner aber einen endlichen (falschen) Wert. Ab irgendeinem $k$ ist $1/k$ kleiner als die Rundungsgenauigkeit der Teilsumme und ändert nichts mehr.

Formalisierung: die vier Fragen (Folien §0/17–31)

Ein mathematisches Modell ist eine Abbildung $\mathcal F:\mathcal X\to\mathcal Y$ mit Eingabe $x\in\mathcal X$ („gegeben“) und Ausgabe $y=\mathcal F(x)\in\mathcal Y$ („gesucht“).

Aber: Die Eingabe ist nur gestört als $\tilde x$ bekannt, und $\mathcal F$ lässt sich oft nicht exakt, nicht effizient oder nicht geschlossen berechnen. Man benutzt deshalb ein numerisches Verfahren $\tilde{\mathcal F}$ und berechnet

$\tilde{\mathcal F}(\tilde x)\quad\text{statt}\quad\mathcal F(x).$

Zum Verständnis betrachtet man zusätzlich die beiden „Zwischenwerte“ $\mathcal F(\tilde x)$ und $\tilde{\mathcal F}(x)$. Damit bilden die vier Werte ein Quadrat:

      gewünscht  F(x)  ──── Konsistenz ────  F̃(x)
                  │                            │
              Kondition                    Stabilität
                  │                            │
                 F(x̃)                        F̃(x̃)  tatsächlich berechnet

Die Diagonale von $\mathcal F(x)$ nach $\tilde{\mathcal F}(\tilde x)$ ist die Konvergenz.

1. Kondition – Eigenschaft des Problems (Folie §0/27)

Wie empfindlich reagiert das mathematische Modell $\mathcal F$ auf Fehler in der Eingabe? Man betrachtet $\|\mathcal F(\tilde x)-\mathcal F(x)\|$.

Die relative Kondition (Konditionszahl) $\kappa$ ist die kleinste Konstante $\kappa\ge 0$ mit

$\frac{\|\mathcal F(x)-\mathcal F(\tilde x)\|_{\mathcal Y}}{\|\mathcal F(x)\|_{\mathcal Y}}\;\le\;\kappa\cdot\frac{\|x-\tilde x\|_{\mathcal X}}{\|x\|_{\mathcal X}}.$

• gut konditioniert: $\kappa\le 1$, Fehler werden gedämpft,
• schlecht konditioniert: $\kappa\gg 1$, Fehler werden verstärkt.

Das ist ein unvermeidbarer Problemfehler. Kein Algorithmus kann ihn beseitigen, nur eine Änderung des Modells.

Beispiele (Grieb S. 7):

• $P=x\cdot y$ ist gut konditioniert: $(x+h)(y+h)-xy=(x+y)h+h^2$ bleibt in der Größenordnung von $h$.
• $x-y$ für $x\approx y$ ist schlecht konditioniert (Auslöschung, siehe 1.2).
• $x^2+4x+4=(x+2)^2=0$ hat die doppelte Lösung $-2$. Ändert man die $4$ um $|\Delta c|\approx10^{-7}$ zu $3.9999999$, liegen die Lösungen bei $-1.9996837$ und $-2.0003126$, also $|\Delta x|\approx 3\cdot10^{-4}=3000\cdot|\Delta c|$. Warum genau $\sqrt{10^{-7}}$ herauskommt, steht in 2.2 Kondition des Nullstellenproblems.

2. Konsistenz – Verfahren passt zum Problem (Folie §0/28)

Wie gut löst das Verfahren $\tilde{\mathcal F}$ das Modell $\mathcal F$ bei exakter Eingabe? Man betrachtet $\|\tilde{\mathcal F}(x)-\mathcal F(x)\|$.

Konsistenzordnung $p\in\mathbb N$ (für $\mathcal F\in C^0$):

$\|\tilde{\mathcal F}(x_h)-\mathcal F(x_h)\|_{\mathcal Y}\le O(h^p)\quad\text{für } h=\|x_h-x\|_{\mathcal X}\to 0.$

Eigenschaft des Zusammenspiels von Modell und Verfahren. Verbessern kann man sie durch Wahl eines anderen Verfahrens.

3. Stabilität – Eigenschaft des Algorithmus (Folie §0/29)

Wie robust ist das Verfahren $\tilde{\mathcal F}$ gegenüber Fehlern in der Eingabe und Rundungsfehlern in den Rechenschritten? Man betrachtet $\|\tilde{\mathcal F}(x)-\tilde{\mathcal F}(\tilde x)\|$.

$\tilde{\mathcal F}$ heißt (numerisch) stabil, wenn es ein $\sigma\in\mathbb R$ gibt mit

$\|\tilde{\mathcal F}(x)-\tilde{\mathcal F}(\tilde x)\|_{\mathcal Y}\le\kappa\cdot\sigma\cdot\|x-\tilde x\|_{\mathcal X}.$

Bei einem stabilen Verfahren übersteigt der angesammelte Rundungsfehler den durch die Kondition ohnehin unvermeidbaren Fehler nicht wesentlich. Verbessern kann man Stabilität durch Umformen des Algorithmus.

Stabil heißt nicht gut konditioniert

Ein gut konditioniertes Problem kann man mit einem instabilen Algorithmus kaputtrechnen. Grieb S. 7: $D_1=\sqrt{a+h}-\sqrt a$ ist für $|h|\ll a$ instabil (Auslöschung), das algebraisch gleiche $D_2=\dfrac{h}{\sqrt{a+h}+\sqrt a}$ ist stabil. Zum Ausprobieren: Demo in 1.2.

4. Konvergenz – der „Reality Check“ (Folie §0/30)

Wie gut löst das Verfahren bei gestörter Eingabe das eigentliche Problem? Man betrachtet $\|\tilde{\mathcal F}(\tilde x)-\mathcal F(x)\|$, also genau das, was am Ende interessiert.

Konvergenz folgt in der Regel aus Stabilität + Konsistenz (Dreiecksungleichung über den Umweg $\tilde{\mathcal F}(x)$):

$\|\tilde{\mathcal F}(\tilde x)-\mathcal F(x)\|\le\underbrace{\|\tilde{\mathcal F}(\tilde x)-\tilde{\mathcal F}(x)\|}_{\text{Stabilität}}+\underbrace{\|\tilde{\mathcal F}(x)-\mathcal F(x)\|}_{\text{Konsistenz}}\le\kappa\sigma\|\tilde x-x\|+c\,\|\tilde x-x\|^p.$

Ist das Problem gut konditioniert und geht $\|x-\tilde x\|\to 0$, dann geht auch der Gesamtfehler gegen 0.

5. Effizienz (Folie §0/32)

• Direkte Verfahren: Anzahl der relevanten Rechenoperationen im O-Kalkül.
• Iterative Verfahren: Konvergenzgeschwindigkeit (oft im O-Kalkül, siehe Konvergenzordnung) mal Aufwand pro Iterationsschritt.

Überblick (Folie §0/31)

Begriff	Vergleicht	Beurteilt	Verbessern durch
Existenz, Eindeutigkeit	–	Modell	Modell ändern
Kondition	$\mathcal F(x)$ ↔ $\mathcal F(\tilde x)$	Modell	Modell ändern
Konsistenz	$\mathcal F(x)$ ↔ $\tilde{\mathcal F}(x)$	Modell + Verfahren	anderes Verfahren
Stabilität	$\tilde{\mathcal F}(x)$ ↔ $\tilde{\mathcal F}(\tilde x)$	Verfahren	Algorithmus umformen
Konvergenz	$\mathcal F(x)$ ↔ $\tilde{\mathcal F}(\tilde x)$	alles zusammen	folgt aus Stabilität + Konsistenz
Effizienz	–	Verfahren	schnelleres Verfahren