Mündliche Prüfung – Fragen & Tipps

Format: mündlich, Einzeltermin in der Prüfungszeit, ohne Hilfsmittel. Dazu kommt die Programmieraufgabe (ein Thema aus vier). Die Prüfung knüpft vermutlich daran an.

Stand

Abgedeckt sind die Kapitel 0–2.3 (bis Newton-Verfahren). Varianten des Newton-Verfahrens und alles ab Kapitel 3 (LGS, Interpolation, Approximation) kommen dazu, sobald sie dran waren. Die Fragen sind selbst zusammengestellt aus Folien, Tafel und Übungen, nicht von Prof. Umlauf.

Hints für die Prüfung

1. Die vier Begriffe sauber trennen. Kondition gehört zum Problem, Stabilität zum Algorithmus, Konsistenz zum Verfahren, Konvergenz zum Ganzen. Wer das durcheinanderwirft, fällt sofort auf. Zu jedem Begriff ein Beispiel parat haben.
2. Immer eine Skizze. Newton-Verfahren = Tangente zeichnen. Kondition einer doppelten Nullstelle = Parabel um $\varepsilon$ verschieben. Auslöschung = zwei fast gleiche Zahlen untereinander schreiben.
3. Formeln herleiten können, nicht nur hinschreiben. Newton-Vorschrift aus der Tangente, $\varepsilon^{1/m}$ aus Taylor, Fehlerfortpflanzung aus dem totalen Differential. Das sind jeweils drei Zeilen.
4. Zahlen im Kopf haben: $\text{eps}\approx10^{-16}$, 16 Stellen, $m$-fache Nullstelle ⇒ $16/m$ Stellen, Newton verdoppelt die Stellen pro Schritt.
5. Die Programmieraufgabe ist Prüfungsstoff. Wer gedämpftes Newton implementiert hat, sollte Abbruchkriterien, Sonderfälle ($f'=0$, Zyklen) und Testfunktionen erklären können.

Kapitel 0 – Einleitung

Was ist der Unterschied zwischen direkten und iterativen Verfahren?

Direkt: liefert die Lösung nach endlich vielen Schritten exakt (bis auf Rundung), z.B. Gauß-Elimination, $p$-$q$-Formel. Iterativ: erzeugt eine Folge $x_0,x_1,\dots\to x^*$ und wird nach endlich vielen Schritten abgebrochen, z.B. Newton. Iterative Verfahren haben also zusätzlich einen Abbruchfehler. Mehr

Welche Fehlerarten gibt es?

Modellfehler (das mathematische Modell vereinfacht die Wirklichkeit), Datenfehler (Messungen, Eingaben), Verfahrensfehler (Diskretisierung, Abbruch einer Iteration), Rundungsfehler (endliche Maschinenzahlen). Die Numerik kümmert sich vor allem um die letzten beiden und darum, wie sich Datenfehler auswirken (Kondition). Mehr

Was ist Kondition? Geben Sie ein schlecht konditioniertes Problem an.

Kondition misst, wie stark sich Fehler in den Eingabedaten auf das exakte Ergebnis auswirken, unabhängig vom Algorithmus. Relative Konditionszahl für $f:\mathbb R\to\mathbb R$: $\kappa=\left|\frac{x\,f'(x)}{f(x)}\right|$. Schlecht konditioniert: Subtraktion fast gleicher Zahlen ($x-y$ mit $x\approx y$), mehrfache Nullstellen ($\varepsilon^{1/m}$). Gut konditioniert: Multiplikation ($\kappa=1$). Mehr

Was ist der Unterschied zwischen Kondition und Stabilität?

Kondition ist eine Eigenschaft des Problems: Wie empfindlich reagiert die exakte Lösung auf Eingabestörungen? Dagegen kann man nichts tun. Stabilität ist eine Eigenschaft des Algorithmus: Verstärkt er die Rundungsfehler mehr als unvermeidlich? Ein und dasselbe gut konditionierte Problem kann man stabil oder instabil ausrechnen, z.B. $\sqrt{a+h}-\sqrt a$ (instabil) vs. $\frac{h}{\sqrt{a+h}+\sqrt a}$ (stabil). Mehr

Wann konvergiert ein Verfahren am Rechner?

Faustregel: konsistent + stabil ⇒ konvergent. Beweisidee mit der Dreiecksungleichung: Abstand berechnet–exakt ≤ Abstand berechnet–exakt gerechnetes Verfahren (Stabilität) + Abstand Verfahren–Problem (Konsistenz). Mehr

Kapitel 1 – Rundungsfehler

Wie sind Maschinenzahlen aufgebaut? Was ist eps?

$\pm E^b\sum_{i=1}^Na_iE^{-i}$ mit Basis $E$, $N$ Mantissenstellen, $a_1\neq0$ (normalisiert), Exponent $b_{\min}\le b\le b_{\max}$. IEEE double: $E=2$, 1 Bit Vorzeichen, 11 Bit Exponent, 52 Bit Mantisse, Bereich $10^{-308}$ bis $10^{308}$. $\text{eps}=2^{-53}\approx1.1\cdot10^{-16}$ ist der maximale relative Rundungsfehler: $\operatorname{rd}(x)=x(1+\tau)$, $|\tau|\le\text{eps}$. Also etwa 16 gültige Dezimalstellen. Mehr

Warum gilt das Assoziativgesetz am Rechner nicht? Beispiel?

Weil $\mathbb M$ unter $+$ nicht abgeschlossen ist und nach jeder Operation gerundet wird. Beispiel mit 16 Stellen: $(10^{20}+17)-10^{20}=0$, aber $(10^{20}-10^{20})+17=17$. Die 17 wird neben $10^{20}$ „verschluckt“. Folie §1/3 liefert je nach Reihenfolge $0$, $120$, $137$ oder $-10$. Mehr

Leiten Sie die Fehlerfortpflanzung für die Addition her. Wann ist sie gefährlich?

$\Delta z=\Delta x+\Delta y$, also $\varepsilon_z=\frac{x}{x+y}\varepsilon_x+\frac{y}{x+y}\varepsilon_y$. Bei gleichen Vorzeichen sind die Faktoren in $(0,1)$ ⇒ $|\varepsilon_z|\le\max(|\varepsilon_x|,|\varepsilon_y|)$, stabil. Bei verschiedenen Vorzeichen und $|x|\approx|y|$ werden die Faktoren $\frac{|x|}{||x|-|y||}$ riesig ⇒ Auslöschung. Beispiel $0.98765444-0.98765333$: aus 8 werden 3 gültige Stellen. Mehr

Wie pflanzen sich Fehler bei einer allgemeinen Funktion fort?

Taylor erster Ordnung (totales Differential): $\Delta z\approx\sum_i\frac{\partial f}{\partial x_i}\Delta x_i$. Relativ: $\varepsilon_z\approx\sum_i\frac{x_i}{f}\frac{\partial f}{\partial x_i}\varepsilon_{x_i}$. Beispiele: $xy$: $\varepsilon_x+\varepsilon_y$ (stabil). $\ln x$: $\varepsilon_x/\ln x$ (kritisch bei $x\approx1$). $\sqrt x$: $\frac12\varepsilon_x$. Mit Rundung des Ergebnisses kommt noch $+\tau_z$, $|\tau_z|\le\text{eps}$, dazu. Mehr

Was erzeugt bei der Auslöschung eigentlich den Fehler?

Nicht die Subtraktion selbst. Die ist bei fast gleichen Zahlen sogar exakt. Sie macht den schon vorhandenen absoluten Fehler von $x$ und $y$ relativ groß, weil das Ergebnis viel kleiner ist als die Eingaben. Die führenden Stellen heben sich weg, übrig bleiben die unsicheren.

Übung 1: Warum ist die Archimedes-Rekursion instabil und wie repariert man sie?

$s_{2n}=n\sqrt{2(1-\sqrt{1-(s_n/n)^2})}$. Für großes $n$ ist $\sqrt{1-(s_n/n)^2}\approx1$, die Differenz $1-\sqrt{\cdots}$ ist Auslöschung. In float wird sie ab $n\approx200$ ungenau und am Ende exakt 0. Reparatur durch Erweitern: $1-\sqrt{1-u^2}=\frac{u^2}{1+\sqrt{1-u^2}}$, also $s_{2n}=s_n\sqrt{\frac{2}{1+\sqrt{1-(s_n/n)^2}}}$. Keine Subtraktion mehr. Mehr

Übung 1: Warum ist die Rekursion y(n+1) = (1 − (n+1) y(n))/2 vorwärts unbrauchbar, rückwärts aber gut?

Vorwärts: $\Delta y_{n+1}=-\frac{n+1}2\Delta y_n$, also $|\Delta y_n|=\frac{n!}{2^n}|\Delta y_0|$. Der Fehler wächst faktoriell, bei $n=25$ ist das Ergebnis Unsinn. Rückwärts: $y_n=\frac{1-2y_{n+1}}{n+1}$, Fehler wird pro Schritt durch $\frac{n+1}2$ geteilt. Selbst der grobe Start $y_{k+1}=0$ liefert dann $y_0$ auf volle Genauigkeit. Mehr

Kapitel 2 – Nichtlineare Gleichungen

Wie kommt man beim Zins-Beispiel auf ein Polynom? Was ist mit x = 1?

Mit $x=1+\frac{p}{1200}$ ist nach $m$ Monaten $0=(\cdots(Kx-r)x-\cdots)x-r=Kx^m-r\sum_{i=0}^{m-1}x^i$. Geometrische Summe einsetzen und mit $(x-1)$ multiplizieren: $Kx^{m+1}-(r+K)x^m+r=0$. $x=1$ löst das immer, ist aber eine Scheinlösung durch das Multiplizieren mit $(x-1)$. Grad $m+1\ge5$ ⇒ keine Lösungsformel ⇒ Newton. Mehr

Wie gut ist das Nullstellenproblem konditioniert? Herleitung?

$f\in C^m$, $x^*$ $m$-fach, $|\tilde f-f|\le\varepsilon$, $\tilde f(\tilde x^*)=0$. Dann $|f(\tilde x^*)|\le\varepsilon$, und Taylor um $x^*$ gibt $f(\tilde x^*)=\frac{f^{(m)}(\xi)}{m!}(\tilde x^*-x^*)^m$. Also $|\tilde x^*-x^*|\lesssim\left(\frac{\varepsilon\,m!}{|f^{(m)}(x^*)|}\right)^{1/m}$. Einfach: $\varepsilon/|f'(x^*)|$, gut. Mehrfach: $\sim\varepsilon^{1/m}$, schlecht, z.B. $10^{-16}$ und $m=4$ gibt $10^{-4}$. Mehr

Warum betrachtet man hier den absoluten und nicht den relativen Fehler?

Weil $f(x^*)=0$ ist. Ein relativer Fehler im Funktionswert würde durch $0$ teilen. Für die Lage $x^*$ selbst ginge relativ zwar, aber $x^*=0$ ist auch möglich.

Leiten Sie das Newton-Verfahren her.

Tangente in $(x_i,f(x_i))$: $y=f(x_i)+f'(x_i)(x-x_i)$. Nullsetzen: $x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$, falls $f'(x_i)\neq0$. Idee: $f$ lokal durch die beste lineare Näherung ersetzen und deren Nullstelle nehmen. Skizze zeichnen! Mehr

Unter welchen Voraussetzungen konvergiert Newton? Was sagt der Satz?

$f\in C^2[a,b]$ mit B1 $f(a)f(b)<0$ (Nullstelle existiert), B2 $f'\neq0$ (eindeutig, keine Division durch 0), B3 $f''$ ohne Vorzeichenwechsel (kein Wendepunkt, monotone Konvergenz), B4 Newton-Schritte von $a$ und $b$ bleiben in $[a,b]$. Dann konvergiert Newton für jeden Startwert aus $[a,b]$, und mit $K=\frac{M}{2m}$ gilt $|x^*-x_n|\le K|x_n-x_{n-1}|^2$. Mehr

Prüfen Sie die Voraussetzungen für f(x) = x − e^(−x) auf [0, 1].

B1: $f(0)=-1$, $f(1)=1-\frac1e>0$. B2: $f'=1+e^{-x}>0$. B3: $f''=-e^{-x}<0$. B4: $x_1|_{x_0=0}=\frac12$, $x_1|_{x_0=1}=\frac2{1+e}\approx0.54$. $m=1+\frac1e$, $M=1$, also $|x^*-x_n|\le\frac{e}{2(e+1)}|x_n-x_{n-1}|^2\approx0.37|x_n-x_{n-1}|^2$. Mehr

Was ist der Unterschied zwischen a-priori- und a-posteriori-Fehlerabschätzung?

A priori: vor der Rechnung, nur aus $a,b,K$: $|x^*-x_n|\le\frac1K((b-a)K)^{2^n}$. Sagt, wie viele Schritte man höchstens braucht, ist aber grob und nur für $(b-a)K<1$ brauchbar. A posteriori: nach der Rechnung, aus den Iterierten: $|x^*-x_n|\le K|x_n-x_{n-1}|^2$. Scharf und direkt als Abbruchkriterium nutzbar. Mehr

Was ist die Konvergenzordnung? Welche hat Newton und warum?

Ordnung $p$: $|x_{n+1}-x^*|\le C|x_n-x^*|^p$. Newton hat bei einfacher Nullstelle $p=2$: Taylor um $x_n$ in $x^*$ gibt $x^*-x_{n+1}=-\frac{f''(\xi)}{2f'(x_n)}(x^*-x_n)^2$. Praktisch: Die Zahl der gültigen Stellen verdoppelt sich pro Schritt. Bei $m$-facher Nullstelle nur $p=1$ mit Faktor $\frac{m-1}m$. Mehr

Was kann beim Newton-Verfahren schiefgehen?

1. $f'(x_i)=0$: waagrechte Tangente, Division durch 0 bzw. riesiger Sprung. 2. Konvergenz gegen eine andere Nullstelle (Zins: Scheinlösung $x=1$). 3. Zyklus $x_{n+2}=x_n$ bei Wendepunkt, z.B. $\tanh x$ mit $x_0\approx1.0887$, oder Divergenz. 4. Mehrfache Nullstelle: nur linear, und die Genauigkeit ist durch $\varepsilon^{1/m}$ begrenzt. Abhilfe: guter Startwert, Konvergenzsatz prüfen, Dämpfung (kommt später), maximale Iterationszahl. Mehr

Welche Abbruchkriterien gibt es, und welche Schwächen haben sie?

$|x_{n+1}-x_n|<\varepsilon$ (Schrittweite; bei quadratischer Konvergenz ist der Fehler dann sogar $\approx K\varepsilon^2$), $|f(x_n)|<\varepsilon$ (Residuum; trügt bei flachem $f$, also schlechter Kondition), und immer zusätzlich $n\le n_{\max}$ gegen Endlosschleifen bei Divergenz oder Zyklus. Bei großen $|x|$ die Schrittweite relativ messen.

Übung 2, Aufgabe 4: Warum konvergiert Newton für f = g so langsam?

Bei $x^*=\frac23$ stimmen $f$ und $g$ in Wert, erster und zweiter Ableitung überein ($1$, $-\frac12$, $\frac14$), erst die dritte unterscheidet sich. $F=f-g$ hat dort eine dreifache Nullstelle ⇒ Newton linear mit Faktor $\frac23$, und die Kondition begrenzt die Genauigkeit auf $\approx10^{-5}$. Mehr