2.2 Kondition des Nullstellenproblems

📄 Folie 2

Frage: $f$ ist am Rechner nie exakt bekannt. Rundung, Messfehler (z.B. die Rate $r$ im Zins-Beispiel) oder eine ungenaue Auswertung liefern stattdessen ein gestörtes $\tilde f$. Wie weit liegt die Nullstelle $\tilde x^*$ von $\tilde f$ von der wahren Nullstelle $x^*$ weg?

Das ist eine Frage an das Problem, nicht an ein Verfahren (siehe Kondition in Kapitel 0). Kein Verfahren kann $x^*$ genauer finden, als die Kondition erlaubt.

Voraussetzungen (Folie 2, Tafel)

Eingabe	$f\in C^m$, $x^*$ ist $m$-fache Nullstelle: $f(x^*)=f'(x^*)=\dots=f^{(m-1)}(x^*)=0$, $f^{(m)}(x^*)\neq0$
Störung	$\big\lvert\tilde f(x)-f(x)\big\rvert\le\varepsilon$ für alle $x$
Gesucht	Schranke für $\lvert\tilde x^*-x^*\rvert$, wobei $\tilde f(\tilde x^*)=0$

Man arbeitet hier mit dem absoluten Fehler: Wegen $f(x^*)=0$ ist ein relativer Fehler im Bild von $f$ nicht sinnvoll (Division durch 0).

Herleitung (Tafel)

Schritt 1. $\tilde x^*$ ist Nullstelle von $\tilde f$. Also ist $f$ dort höchstens $\varepsilon$ groß:

$|f(\tilde x^*)|=|f(\tilde x^*)-\underbrace{\tilde f(\tilde x^*)}_{=0}|\le\varepsilon.$

Schritt 2. Taylor-Entwicklung von $f$ um $x^*$ mit Lagrange-Restglied. Die ersten $m$ Terme verschwinden, weil $x^*$ $m$-fache Nullstelle ist:

$$f(\tilde x^*)=\underbrace{f(x^*)}_{0}+\underbrace{f'(x^*)}_{0}(\tilde x^*-x^*)+\dots+\frac{f^{(m)}(\xi)}{m!}(\tilde x^*-x^*)^m,\qquad\xi\text{ zwischen }x^*\text{ und }\tilde x^*.$$

Schritt 3. Einsetzen in Schritt 1 und nach $|\tilde x^*-x^*|$ auflösen:

$$\frac{|f^{(m)}(\xi)|}{m!}\,|\tilde x^*-x^*|^m\le\varepsilon \quad\Longrightarrow\quad \boxed{\;|\tilde x^*-x^*|\le\left(\frac{\varepsilon\cdot m!}{|f^{(m)}(\xi)|}\right)^{1/m}\approx\left(\frac{\varepsilon\cdot m!}{|f^{(m)}(x^*)|}\right)^{1/m}\;}$$

(Für $\tilde x^*$ nahe $x^*$ ist $f^{(m)}(\xi)\approx f^{(m)}(x^*)$.)

Folgerungen

Einfache Nullstelle ($m=1$)

$|\tilde x^*-x^*|\lesssim\frac{\varepsilon}{|f'(x^*)|}.$

Der Fehler ist proportional zu $\varepsilon$, die Konditionszahl ist $1/|f'(x^*)|$. Gut konditioniert, solange $f$ die $x$-Achse nicht zu flach schneidet. Anschaulich: Verschiebt man den Graphen um $\varepsilon$ nach oben/unten, wandert der Schnittpunkt um $\varepsilon/\text{Steigung}$.

Mehrfache Nullstelle ($m>1$)

$|\tilde x^*-x^*|\sim\sqrt[m]{\varepsilon}\;\gg\;\varepsilon.$

Tafel: Für $m>1$ ist $\sqrt[m]\varepsilon$ viel größer als $\varepsilon$ ⇒ das Problem ist schlecht konditioniert. Zahlenbeispiel aus dem Aufschrieb:

$\varepsilon=10^{-16},\;m=4\quad\Rightarrow\quad\sqrt[4]{10^{-16}}=10^{-4}.$

Von 16 Stellen Genauigkeit in $f$ bleiben nur 4 Stellen in der Nullstelle. Allgemein bleiben etwa $16/m$ Stellen übrig.

Datenfehler ε = 10⁻¹⁶

Vielfachheit m	Fehler der Nullstelle ≈ ε1/m	gültige Dezimalstellen
1	1.0e-16	≈ 16
2	1.0e-8	≈ 8
3	4.6e-6	≈ 5
4	1.0e-4	≈ 4
5	6.3e-4	≈ 3
6	2.2e-3	≈ 2

Beispiel f(x) = (x − 1)^m, gestört zu f(x) − ε: Die Nullstelle wandert von 1 nach 1 + ε^1/m.

Anschaulich

Bei einer mehrfachen Nullstelle berührt $f$ die Achse nur (oder schneidet sie sehr flach, z.B. $(x-1)^3$). Ein kleines Anheben des Graphen um $\varepsilon$ verschiebt den Schnittpunkt dann weit. Bei $m=2$ (Berührpunkt) kann die Nullstelle sogar ganz verschwinden oder sich in zwei aufspalten.

Konsequenz für Newton

Das ist keine Schwäche eines Verfahrens, sondern eine Grenze des Problems. Im Newton-Abschnitt sieht man das konkret: Für $f(x)=\frac\pi2-x-\cos x$ (dreifache Nullstelle bei $\pi/2$) bleibt Newton in double bei einem Fehler von $\approx7\cdot10^{-6}$ stehen. Die Formel mit $m=3$, $|f'''(\pi/2)|=1$, $m!=6$ und $\varepsilon\approx\text{eps}$ sagt $(6\,\text{eps})^{1/3}\approx9\cdot10^{-6}$ voraus. Das ist genau die Größenordnung.