Numerik-Grundlagen: Gleitkommazahlen, Rundungs­fehler und Kondition

In der Mathematik gibt es unendlich viele reelle Zahlen. Ein Computer hat nur endlich viel Speicher und rechnet deshalb mit Gleitkommazahlen, die nur ein winziger Ausschnitt der reellen Zahlen sind. Jede Rechnung rundet, und jede Rundung macht einen kleinen Fehler. Die Numerik fragt, wie diese Fehler wachsen, wann ein Ergebnis trotzdem verlässlich ist und wie man Verfahren so baut, dass sich Fehler nicht aufschaukeln. Das beginnt mit zwei Fragen: Wie genau kann man überhaupt rechnen, und wie empfindlich ist die gestellte Aufgabe selbst?

Diese Seite führt in die Grundbegriffe ein: Zahlendarstellung, Rundungsfehler, Auslöschung und Kondition. Sie ist die Grundlage für die weiteren Seiten zur Numerik: Newton-Verfahren, Numerische Lineare Algebra und Interpolation und Quadratur. Die Beispiele sind in Standard-Gleitkommaarithmetik (doppelte Genauigkeit) nachgerechnet.

Gleitkommazahlen

Eine Gleitkommazahl hat die Form $x=\pm m·2^e$ mit einer Mantisse $m$ und einem Exponenten $e$. Wie bei der wissenschaftlichen Schreibweise $\mathrm{2,998}·{10}^8$ „gleitet“ das Komma mit dem Exponenten. Bei der doppelten Genauigkeit (binary64, Standard IEEE 754) gehören zu jeder Zahl 64 Bit: 1 Bit Vorzeichen, 11 Bit Exponent und 52 Bit Mantisse. Weil die Mantisse normalisiert mit führender Eins beginnt, die nicht gespeichert wird („hidden bit“), hat sie effektiv 53 Bit. Das entspricht etwa 15 bis 16 Dezimalstellen. Die größte Zahl ist etwa $\mathrm{1,8}·{10}^{308}$, die kleinste positive normalisierte etwa $\mathrm{2,2}·{10}^{-308}$.

Wichtig ist der relative Abstand der Zahlen: Zwischen $2^e$ und $2^{e+1}$ liegen genau $2^{52}$ Zahlen im gleichen Abstand $2^{e-52}$, der relative Abstand schwankt zwischen $2^{-53}$ und $2^{-52}$. Wird eine reelle Zahl $x$ zur nächsten Gleitkommazahl $\mathrm{fl}(x)$ gerundet, ist der Fehler höchstens ein halber Abstand, also

Die Zahl $u$ heißt Rundungseinheit, die doppelte Zahl $2^{-52}$ Maschinenepsilon: der Abstand von 1 zur nächsten größeren Gleitkommazahl.

Für die Grundrechenarten gilt das Standardmodell: Das gerundete Ergebnis ist das exakte Ergebnis mit einem kleinen relativen Fehler, $\mathrm{fl}(a\circ b)=(a\circ b)(1+\delta )$ mit $\left|\delta \right|\le u$ für $\circ \in \{+,-,·,/\}$. Daraus folgen Rechenregeln, die in der reellen Mathematik gelten, im Rechner aber nicht: Das Assoziativgesetz ist verletzt, $(a+b)+c\ne a+(b+c)$. Die Summe großer und kleiner Zahlen zeigt Absorption: Wegen $2^{53}=9007199254740992\approx 9·{10}^{15}$ ist für Zahlen über $2^{53}$ der Abstand benachbarter Gleitkommazahlen mindestens 2. Deshalb liefert $({10}^{16}+1)-{10}^{16}$ im Rechner den Wert 0 statt 1, das Plus eins geht verloren.

Fehler und Fehlerfortpflanzung

Ist $\tilde{x}$ eine Näherung für $x$, heißt $|\tilde{x}-x|$ der absolute Fehler und $\frac{|\tilde{x}-x|}{\left|x\right|}$ der relative Fehler. Das relative Maß ist meist das richtige, denn ein Fehler von einem Millimeter ist bei einem Haus winzig, bei einer Schraube nicht.

Für einfache Rechnungen addieren sich die Fehler nach festen Regeln. Bei Summen und Differenzen addieren sich im ungünstigsten Fall die absoluten Fehler. Bei Produkten und Quotienten addieren sich näherungsweise die relativen Fehler: Ist $x$ auf 1 Prozent und $y$ auf 2 Prozent genau, so ist $xy$ auf etwa 3 Prozent genau. Bei Potenzen $x^n$ wird der relative Fehler mit $n$ multipliziert. Die allgemeine Regel liefert die Ableitung: $\Delta f\approx f^{\prime }(x)\Delta x$.

Auslöschung

Die gefährlichste Operation ist die Subtraktion zweier fast gleicher Zahlen. Die führenden Stellen heben sich auf, übrig bleiben die hinteren, in denen die Rundungsfehler stecken.

Beweis. Es ist $(\tilde{a}-\tilde{b})-(a-b)=a{\epsilon }_a-b{\epsilon }_b$, und der Betrag ist höchstens $(|a|+|b|)\epsilon$. Division durch $|a-b|$ liefert die Behauptung.

Je näher $a$ und $b$ beieinander liegen, desto größer ist der Faktor $\frac{\left|a\right|+\left|b\right|}{|a-b|}$. Man sagt, die Subtraktion ist dort schlecht konditioniert.

Kondition eines Problems

Auslöschung ist ein Sonderfall eines allgemeinen Phänomens: Manche Aufgaben reagieren von Natur aus stark auf kleine Änderungen der Eingabe, egal wie geschickt man rechnet. Das misst die Konditionszahl.

Die Herleitung ist der Mittelwertsatz: $f\left(\tilde{x}\right)-f(x)\approx f^{\prime }(x)·x\epsilon$, geteilt durch $f(x)$. Die Konditionszahl ist also das Verhältnis der relativen Änderung der Ausgabe zur relativen Änderung der Eingabe.

Kondition und Stabilität unterscheiden. Die Kondition hängt nur von der Aufgabe ab. Ein gut konditioniertes Problem kann trotzdem durch einen schlechten Algorithmus verdorben werden: $\sqrt{x+1}-\sqrt{x}$ ist als Funktion von $x$ gut konditioniert ($\kappa \approx \frac{1}{2}$), aber die direkte Auswertung ist instabil, weil sie in zwei Schritte mit Auslöschung zerlegt. Die erweiterte Form ist stabil. Umgekehrt kann kein Algorithmus ein schlecht konditioniertes Problem verbessern.

Kondition einer Matrix

Beim Lösen von $Ax=b$ stört man die rechte Seite $b$ (Messfehler, Rundung). Wie stark ändert sich $x$?

Beweis. Aus $A(\tilde{x}-x)=\Delta b$ folgt $\tilde{x}-x=A^{-1}\Delta b$ und $\Vert \tilde{x}-x\Vert \le \Vert A^{-1}\Vert \Vert \Delta b\Vert$. Aus $b=Ax$ folgt $\Vert b\Vert \le \Vert A\Vert \Vert x\Vert$, also $\frac{1}{\Vert x\Vert }\le \frac{\Vert A\Vert }{\Vert b\Vert }$. Multipliziert man beide Ungleichungen, ergibt sich die Behauptung.

Es gilt immer $\kappa (A)\ge 1$. Die Zahl $\kappa (A)$ ist der Verstärkungsfaktor für relative Fehler im Worst Case. Als Faustregel verliert man beim Lösen etwa ${\log }_{}\kappa (A)$ Dezimalstellen an Genauigkeit.

Berüchtigt sind die Hilbert-Matrizen $H_n=(\frac{1}{i+j-1}{)}_{i,j=1}^n$, deren Kondition exponentiell mit $n$ wächst. Schon für $n=10$ ist $\kappa$ etwa ${10}^{13}$, in doppelter Genauigkeit bleiben von 16 Stellen nur drei übrig. Wie man Systeme trotzdem zuverlässig löst, zeigt die Seite Numerische Lineare Algebra.

Regeln für numerisches Rechnen

• Keine Gleichheitsvergleiche von Gleitkommazahlen, sondern Toleranzen.
• Auslöschung vermeiden: Terme umformen (Erweitern, Trigonometrische Identitäten, Vieta), bevor man subtrahiert.
• Summieren von klein nach groß, damit kleine Summanden nicht absorbiert werden, oder mit der Kahan-Summation, die den Rundungsfehler mitführt.
• Polynome mit dem Horner-Schema auswerten: weniger Rechenschritte und weniger Rundungsfehler.
• Matrizen nicht invertieren, um $Ax=b$ zu lösen, sondern zerlegen und Systeme lösen. Die Inverse ist teurer und ungenauer.
• Kondition prüfen: Ist $\kappa$ sehr groß, helfen weder mehr Rechnen noch ein anderer Algorithmus. Dann muss man die Aufgabe anders stellen oder genauer messen.

Typische Fehler

Übungen

Geschichte: vom Zweistromland zu IEEE 754

Gleitkommaschreibweisen sind alt: Schon im Zweistromland rechnete man um 1750 v. Chr. mit einer Art Gleitkomma, indem man nur die Ziffernfolge schrieb und die Größenordnung im Kopf behielt (siehe Sumerische und babylonische Mathematik). Konrad Zuse baute zwischen 1936 und 1938 den Rechner Z1, der mit binären Gleitkommazahlen rechnete. Fertig war er 1938. Danach hatte fast jeder Hersteller sein eigenes Format, und Programme gaben auf verschiedenen Rechnern verschiedene Ergebnisse. Erst der Standard IEEE 754 von 1985 legte Formate und Rundungsregeln einheitlich fest und wurde 2008 überarbeitet. Die Analyse der Rundungsfehler als eigene Wissenschaft begann in den 1940er-Jahren: John von Neumann und Goldstine untersuchten 1947 das Invertieren großer Matrizen, und Alan Turing beschrieb 1948 das Gaußsche Verfahren als LU-Zerlegung und führte die Konditionszahl einer Matrix ein.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Gleitkommazahl
• Wikipedia: Kondition
• Nicholas J. Higham: Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia.
• Peter Deuflhard, Andreas Hohmann: Numerische Mathematik 1, De Gruyter, Berlin.
• Josef Stoer, Roland Bulirsch: Numerische Mathematik 1, Springer, Berlin.
• United States General Accounting Office: Patriot Missile Defense: Software Problem Led to System Failure at Dhahran, Saudi Arabia, GAO/IMTEC-92-26, 1992.