Numerik im Überblick: Verfahren, Fehler und Konvergenz

Die meisten Probleme, die in Technik und Naturwissenschaft auftreten, haben keine Formel als Lösung: Die Gleichung $\cos x=x$ lässt sich nicht nach $x$ auflösen, das Integral ${\int }_0^1{e}^{-x^2}\text{d}x$ hat keine Stammfunktion aus bekannten Funktionen, ein Gleichungssystem mit einer Million Unbekannten lässt sich nicht von Hand lösen. Die Numerik (numerische Mathematik) liefert dafür Verfahren, die Näherungen berechnen und dabei den Fehler abschätzen. Auf dieser Seite bekommst du die Landkarte: Welches Verfahren gehört zu welchem Problem, wie schnell konvergiert es, und wie vergleichst du Verfahren miteinander?

Woher kommen Fehler?

Es gibt vier Quellen, die sich überlagern. Modellfehler entstehen, wenn die Gleichung die Wirklichkeit nur vereinfacht beschreibt. Datenfehler stecken in Messwerten. Verfahrensfehler entstehen, weil ein Verfahren nach endlich vielen Schritten abbricht oder eine Funktion durch ein Polynom ersetzt. Rundungsfehler entstehen, weil der Computer Zahlen nur mit endlich vielen Stellen speichert: Bei doppelter Genauigkeit sind es etwa $16$ Dezimalstellen. Die Seite Numerik-Grundlagen erklärt, wie sich die Fehler fortpflanzen und warum die Subtraktion fast gleicher Zahlen gefährlich ist (Auslöschung). Wie empfindlich ein Problem auf kleine Änderungen reagiert, misst die Konditionszahl. Ein gut konditioniertes Problem lässt sich mit einem stabilen Verfahren zuverlässig lösen, ein schlecht konditioniertes nicht, egal wie genau man rechnet.

Die Landkarte der Verfahren

Konvergenzordnung: wie schnell nähert sich ein Verfahren?

Ein Iterationsverfahren erzeugt eine Folge $x_0,x_1,x_2,\dots$ mit dem Fehler $e_k=|x_k-x^{\ast }|$. Gilt $e_{k+1}\approx C{e}_k^p$, dann hat das Verfahren die Konvergenzordnung $p$. Bei $p=1$ und $C<1$ spricht man von linearer Konvergenz: Der Fehler schrumpft pro Schritt um den festen Faktor $C$. Bei $p=2$ (quadratisch) verdoppelt sich die Zahl der richtigen Stellen in jedem Schritt. Bei Verfahren mit Schrittweite $h$ gibt man die Ordnung als $O(h^p)$ an: Halbiert man $h$, schrumpft der Fehler um den Faktor $2^p$.

Beispiel 1: die Gleichung $\cos x=x$

Gesucht ist die Nullstelle von $f(x)=\cos x-x$ im Intervall $[0,1]$. Sie liegt bei $x^{\ast }=\mathrm{0,7390851332}\dots$. Drei Verfahren sollen sie auf ${10}^{-6}$ genau bestimmen.

• Bisektion: Das Intervall wird in jedem Schritt halbiert, der Fehler also pro Schritt um den Faktor $\frac{1}{2}$. Bis die halbe Intervallbreite unter ${10}^{-6}$ liegt, braucht man $19$ Schritte. Die Zahl der Schritte ist vorhersagbar, das Verfahren funktioniert immer, wenn $f$ stetig ist und das Vorzeichen wechselt, aber es ist langsam.
• Fixpunktiteration: Die Gleichung $\cos x=x$ ist schon in Fixpunktform. Aus $x_{k+1}=\cos x_k$ mit $x_0=1$ folgt der Fehlerfaktor $|\sin x^{\ast }|\approx \mathrm{0,673}$ pro Schritt, und es werden $32$ Schritte gebraucht. Das Verfahren konvergiert nach dem Banachschen Fixpunktsatz, weil der Kosinus das Intervall $[0,1]$ in sich abbildet und dort $\left|{(\cos x)}^{\prime }\right|\le \sin 1\approx \mathrm{0,84}<1$ gilt, siehe Banachscher Fixpunktsatz.
• Newton-Verfahren: $x_{k+1}=x_k-\frac{\cos x_k-x_k}{-\sin x_k-1}$ mit $x_0=1$. Nach nur $3$ Schritten ist der Fehler $\mathrm{1,7}·{10}^{-10}$.

Der Fehler wird quadriert und mit einer Konstanten multipliziert: ${(\mathrm{2,8}·{10}^{-5})}^2\approx \mathrm{7,8}·{10}^{-10}$, und tatsächlich ist $e_3\approx \mathrm{0,22}·e_2^2$, denn die Konstante ist $C=\left|\frac{f^{″}(x^{\ast })}{2f^{\prime }(x^{\ast })}\right|\approx \mathrm{0,22}$. Die Fehlerfolge ${10}^{-1},{10}^{-2},{10}^{-5},{10}^{-10}$ zeigt das Verdoppeln der Stellen. Dafür braucht jeder Newton-Schritt die Ableitung, und das Verfahren kann bei schlechtem Startwert versagen (Newton-Verfahren).

Beispiel 2: das Integral ${\int }_0^1{e}^{-x^2}\text{d}x$

Der exakte Wert ist $\mathrm{0,7468241328}\dots$ (er gehört zur Fehlerfunktion). Die Tabelle zeigt den Fehler von Trapez- und Simpson-Regel bei $n$ Teilintervallen.

Bei jeder Verdopplung von $n$ schrumpft der Trapez-Fehler um den Faktor $4$ (Ordnung $h^2$) und der Simpson-Fehler um den Faktor $16$ (Ordnung $h^4$). Noch effizienter ist die Gauß-Quadratur mit Knoten, die nicht gleichmäßig liegen: Mit nur zwei Funktionsauswertungen erreicht die Gauß-Regel auf $[0,1]$ den Fehler $\mathrm{2,3}·{10}^{-4}$. Das ist so gut wie die Trapezregel mit $n=16$, die $17$ Auswertungen braucht. Mit drei Auswertungen sinkt der Fehler auf $\mathrm{9,5}·{10}^{-6}$. Die Verfahren und ihre Fehlerformeln stehen auf der Seite Interpolation und Quadratur.

Beispiel 3: die Differentialgleichung $y^{\prime }=y$ und die Ordnung eines Verfahrens

Das Anfangswertproblem $y^{\prime }=y$, $y(0)=1$ hat die Lösung $e^x$, der Wert bei $x=1$ ist also $e=\mathrm{2,7182818285}\dots$ Mit der Schrittweite $h=\frac{1}{n}$ ergibt ein Euler-Schritt den Faktor $1+h$, ein Heun-Schritt den Faktor $1+h+\frac{h^2}{2}$ und ein Schritt des klassischen Runge-Kutta-Verfahrens den Faktor $1+h+\frac{h^2}{2}+\frac{h^3}{6}+\frac{h^4}{24}$, denn jedes Verfahren stimmt mit der Taylorreihe von $e^h$ bis zu seiner Ordnung überein. Nach $n$ Schritten steht die $n$-te Potenz des Faktors da:

Bei zehnmal so vielen Schritten schrumpft der Fehler beim Euler-Verfahren um den Faktor $10$, beim Heun-Verfahren um den Faktor $100$ und beim Runge-Kutta-Verfahren um den Faktor $10000$. Das ist die Ordnung $p$ im Exponenten: Der Fehler verhält sich wie $h^p$. Ein Verfahren höherer Ordnung kostet pro Schritt mehr Funktionsauswertungen (Euler eine, Heun zwei, Runge-Kutta vier), gewinnt das aber bei hoher Genauigkeit um ein Vielfaches zurück: Runge-Kutta mit $100$ Schritten (400 Auswertungen) ist um viele Größenordnungen genauer als Euler mit $1000$ Schritten (1000 Auswertungen).

Wie wählst du ein Verfahren?

• Fehler schätzen: Rechne mit einer Schrittweite und mit der halben. Die Differenz der Ergebnisse schätzt den Fehler des genaueren Werts, bei Ordnung $p$ ist er etwa $\frac{1}{2^p-1}$ der Differenz.
• Aufwand beachten: Ein Verfahren mit höherer Ordnung kann pro Schritt mehr kosten. Zähle die Funktionsauswertungen, nicht die Schritte.
• Nicht invertieren: Ein Gleichungssystem $Ax=b$ löst man mit LR-Zerlegung, nicht durch Berechnen von $A^{-1}$ (siehe Numerische Lineare Algebra).
• Abbruchkriterium: Höre auf, wenn die Änderung zwischen zwei Schritten klein ist und der Fehler unter der gewünschten Schranke liegt, und setze eine Höchstzahl von Schritten.
• Auslöschung vermeiden: Forme Formeln um, bevor du fast gleiche Zahlen subtrahierst.

Übungen

Geschichte: von den Weinfässern zu den Supercomputern

Numerisches Rechnen ist so alt wie das Rechnen selbst: Die Babylonier nähern $\sqrt{2}$ mit einem Verfahren, das dem Newton-Verfahren entspricht. Die Fassregel für Weinfässer hat Johannes Kepler 1615 beschrieben, und Carl Friedrich Gauß stellte 1814 die Quadratur mit optimal gewählten Knoten vor. Leonhard Euler beschrieb das nach ihm benannte Verfahren für Differentialgleichungen in seinem Lehrbuch der Integralrechnung. Augustin-Louis Cauchy schlug 1847 das Gradientenverfahren vor. Mit den Computern, die ab der Mitte des 20. Jahrhunderts zur Verfügung standen, wurde die Numerik zum eigenen Fach: Heute rechnen Wettervorhersagen, Flugzeugentwürfe und Schaltungssimulationen im Kern mit den hier beschriebenen Verfahren.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Numerische Mathematik
• Wikipedia: Konvergenzordnung
• Peter Deuflhard, Andreas Hohmann: Numerische Mathematik 1, De Gruyter, Berlin.
• Josef Stoer, Roland Bulirsch: Numerische Mathematik 1, Springer, Berlin.