Auslöschung (numerische Mathematik)

Was ist Auslöschung?

Auslöschung (englisch: cancellation) bezeichnet in der Numerik den Verlust an Genauigkeit, der auftritt, wenn man fast gleich große Gleitkommazahlen voneinander subtrahiert. Gleitkommazahlen sind die im Computer übliche Darstellung von Dezimalzahlen mit begrenzter Stellenzahl.

Das Problem: Stimmen die höherwertigen Stellen zweier Zahlen überein, heben sich diese gültigen Stellen bei der Subtraktion zu 0 auf. Die Differenz besteht dann im Wesentlichen nur noch aus den Rundungsfehlern, die in den niedrigwertigen Stellen stecken. Die Information, dass sich die ersten Stellen zu Null aufgehoben haben, geht dabei verloren.

Zahlenbeispiel zur Auslöschung

Subtrahiert man a = 2,345678 und b = 2,346789, ergibt sich b − a = 0,001111.

Stammen a und b aus vorherigen Berechnungen, sind die niedrigwertigen Stellen durch Rundungsfehler verfälscht. Angenommen, nur die ersten drei Ziffern sind korrekt: Verkürzt man beide Zahlen auf ihre korrekten Ziffern, ergibt sich 2,34 − 2,34 = 0 – im Ergebnis 0,001111 findet sich dann keine einzige korrekte Ziffer mehr.

Sind die ersten vier Ziffern korrekt, erhält man 2,346 − 2,345 = 0,001. Gegenüber dem Ergebnis 0,001111 bedeutet das einen absoluten Fehler von 0,001111 − 0,001000 = 0,000111, also einen relativen Fehler von ungefähr 10 %.

Faustregel

Subtrahiert man zwei p-stellige, fast gleich große Zahlen, die in den ersten k Stellen übereinstimmen, so gehen im Ergebnis von den eigentlich möglichen p Stellen genau k verloren. Es bleiben nur p − k Stellen ungleich Null.

Unterscheiden sich die Zahlen in den letzten p − k Stellen lediglich um Rundungsfehler, hat das Ergebnis keine Aussagekraft mehr. Es sollte dann nicht in weitere Berechnungen einfließen.

Beispiel: Archimedes und die Kreiszahl π

Archimedes von Syrakus zeigte, dass sich der Umfang eines Kreises zu seinem Durchmesser genauso verhält wie die Fläche des Kreises zum Quadrat des Radius. Er gab eine Anleitung, wie man sich diesem Verhältnis (der Kreiszahl π) mit einbeschriebenen oder umschreibenden Vielecken beliebig genau nähern kann – vermutlich eines der ältesten numerischen Verfahren. Bis zum 96-Eck galt: 3,1408450… = 3 + 10/71 < π < 3 + 10/70 = 3,1428571…

In moderner Form beginnt man mit direkt berechenbaren Seitenlängen s_n eines in den Einheitskreis einbeschriebenen Vielecks, etwa Zweieck s₂ = 2, Dreieck s₃ = √3, Viereck s₄ = √2 oder Sechseck s₆ = 1. Durch zweimalige Anwendung des Satzes von Pythagoras erhält man für die verdoppelte Eckenzahl: s_2n = √(2 − 2√(1 − s_n²/4)).

Berechnet man dies in C mit doppelter Genauigkeit nach IEEE 754 (ca. 15 Dezimalstellen), konvergieren die Flächen a_n und A_n anfangs gut gegen π. Ab etwa der Hälfte der Stellenzahl (beim 32768-Eck) macht sich jedoch Auslöschung bei der Subtraktion der fast gleich großen Zahlen 2 und 2√(1 − s_n²/4) bemerkbar. Das Ergebnis wird wieder ungenauer und am Ende völlig falsch (2 − 2,000…000xxx = 0); die Werte verfehlen π schließlich deutlich.

Vermeidung der Auslöschung durch Umformung

In vielen Fällen lässt sich Auslöschung vermeiden, indem man die betroffenen Subtraktionen vermeidet. Hier gelingt das mit der Umformung a² − b² = (a + b)(a − b), also a − b = (a² − b²)/(a + b), mit a = 2 und b = 2√(1 − s_n²/4).

Die Formel für die Seitenlänge lässt sich damit äquivalent umformen zu: s_2n = √( (1/2) · s_n² · 1/(1 + √(1 − s_n²/4)) ) – ganz ohne Subtraktion fast gleich großer Zahlen. Im Zähler hebt sich die Subtraktion auf (ein glücklicher Zufall).

Mit der umgeformten Formel verläuft die Rechnung wie erwünscht: Die Näherungen konvergieren stabil gegen π, und schon beim 268435456-Eck erreicht man die volle Genauigkeit von knapp 16 Dezimalstellen. Als Abbruchsignal dient die 0 in der Spalte 1 − ρ_n.

Auslöschung bei der numerischen Ableitung

Auch bei der numerischen Berechnung von Ableitungen durch Differenzenquotienten tritt Auslöschung auf, zum Beispiel bei der Näherung f′(x) ≈ (f(x+h) − f(x))/h.

Wählt man das h zu klein, werden die Funktionswerte f(x+h) und f(x) nahezu gleich. Ihre Subtraktion löscht dann gültige Stellen aus, und das Ergebnis verliert an Genauigkeit.