Auslöschung (numerische Mathematik)
Unter Auslöschung (engl. cancellation) versteht man in der Numerik den Verlust an Genauigkeit bei der Subtraktion fast gleich großer Gleitkommazahlen.[1]
Beispiele
BearbeitenZahlenbeispiel
BearbeitenWir subtrahieren die Zahlen und
voneinander und erhalten als Ergebnis
.
Stammen nun und
bereits aus vorherigen Berechnungen, so werden die niedrigwertigen Stellen durch Rundungsfehler beeinflusst sein. Stimmen nun aber die höherwertigen Stellen von
und
überein, so löschen sich die gültigen Stellen zu
aus, und die Differenz ergibt sich ausschließlich aus Rundungsfehlern.
Angenommen, bei und
seien die ersten drei Ziffern korrekt, und alle niedrigwertigeren Ziffern durch Rundungsfehler verfälscht. Verkürzen wir die Zahlen auf ihre korrekten Ziffern, so ergibt sich
,
während sich im Ergebnis der ersten, vermeintlich genauen Berechnung keine einzige korrekte Ziffer mehr findet.
Angenommen, in und
seien die ersten vier Ziffern noch korrekt, so ergibt sich
,
wohingegen wir uns oben mit einen absoluten Fehler von
und damit einen relativen Fehler von ungefähr 10 % eingehandelt haben.
Beispiel: Algorithmus des Archimedes zur Kreiszahlberechnung
Bearbeiten![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/PiArchimedes.png/220px-PiArchimedes.png)
Archimedes von Syrakus bewies, dass sich der Umfang eines Kreises zu seinem Durchmesser genauso verhält, wie die Fläche des Kreises zum Quadrat des Radius. Er nannte dieses (heute als Kreiszahl bezeichnete) Verhältnis noch nicht π, gab aber eine Anleitung, wie man sich mit Hilfe von ein- und umschriebenen Vielecken dem Verhältnis bis zu einer beliebig hohen Genauigkeit nähern kann, vermutlich eines der ältesten numerischen Verfahren der Geschichte. Und er führte die Berechnung bis zum 96-Eck mit dem folgenden Resultat durch:
Wie man dem Zahlenbeispiel entnehmen kann, hatte Archimedes keine Chance, beim 96-Eck die Auslöschung überhaupt nur wahrzunehmen.
In heutiger Sprache beginnt man mit direkt berechenbaren Seitenlängen von in einem Einheitskreis (
) einbeschriebenen Vielecken, z. B. dem Zweieck
, dem Dreieck
, dem Viereck
oder dem Sechseck
.
Dann ist für Vielecke mit doppelter Eckenzahl deren Seitenlänge mit der Hilfsstrecke
und zweimaliger Anwendung des Satzes von Pythagoras (
und
) leicht herleitbar:
Mit den vier Grundrechenarten und dem Wurzelziehen kann man also beginnend mit dem Zweieck die Seitenlänge und den Umfang eines einbeschriebenen Vielecks und damit indirekt eine Näherung für berechnen. In der Praxis ist das Ergebnis jedoch enttäuschend. Die folgende Tabelle zeigt beginnend mit n=2 den Abstand
der Seitenmitte S zum Kreisrand, die Seitenlängen
des eingeschriebenen und
des umschriebenen n-Ecks und deren Flächen
und
, die beim Einheitskreis gegen
konvergieren sollten. Die Rechnung wurde in C mit doppelter Genauigkeit nach IEEE 754 und somit ca. 15 Dezimalstellen durchgeführt. Die Zahlenwerte sind aber auch mit jedem Taschenrechner, der Quadratwurzeln beherrscht, nachvollziehbar:
![]()
![]()
![]()
![]()
![]()
2 1.000e+00 2.00e+00 Inf 0.00000000000000 Inf4 2.929e-01 1.41e+00 2.00e+00 2.00000000000000 4.000000000000008 7.612e-02 7.65e-01 8.28e-01 2.82842712474619 3.3137084989847616 1.921e-02 3.90e-01 3.98e-01 3.06146745892072 3.1825978780745332 4.815e-03 1.96e-01 1.97e-01 3.12144515225805 3.1517249074292664 1.205e-03 9.81e-02 9.83e-02 3.13654849054593 3.14411838524589128 3.012e-04 4.91e-02 4.91e-02 3.14033115695474 3.14222362994244256 7.530e-05 2.45e-02 2.45e-02 3.14127725093262 3.14175036916881512 1.882e-05 1.23e-02 1.23e-02 3.14151380114509 3.141632080703971024 4.706e-06 6.14e-03 6.14e-03 3.14157294036989 3.141602510259612048 1.177e-06 3.07e-03 3.07e-03 3.14158772527060 3.141595117743024096 2.941e-07 1.53e-03 1.53e-03 3.14159142155216 3.141593269670278192 7.353e-08 7.67e-04 7.67e-04 3.14159234553025 3.141592807559781.638e+04 1.838e-08 3.83e-04 3.83e-04 3.14159257570956 3.141592691216943.277e+04 4.596e-09 1.92e-04 1.92e-04 3.14159264036917 3.141592669246016.554e+04 1.149e-09 9.59e-05 9.59e-05 3.14159264171161 3.141592648930821.311e+05 2.872e-10 4.79e-05 4.79e-05 3.14159260647332 3.141592608278122.621e+05 7.181e-11 2.40e-05 2.40e-05 3.14159291071407 3.141592911165275.243e+05 1.795e-11 1.20e-05 1.20e-05 3.14159169662728 3.141591696740091.049e+06 4.488e-12 5.99e-06 5.99e-06 3.14159655369072 3.141596553718922.097e+06 1.122e-12 3.00e-06 3.00e-06 3.14159655370129 3.141596553708344.194e+06 2.804e-13 1.50e-06 1.50e-06 3.14151884046467 3.141518840466438.389e+06 7.017e-14 7.49e-07 7.49e-07 3.14120796828205 3.141207968282491.678e+07 1.754e-14 3.75e-07 3.75e-07 3.14245127249408 3.142451272494193.355e+07 4.441e-15 1.87e-07 1.87e-07 3.14245127249412 3.142451272494156.711e+07 1.110e-15 9.42e-08 9.42e-08 3.16227766016838 3.162277660168381.342e+08 2.220e-16 4.71e-08 4.71e-08 3.16227766016838 3.162277660168382.684e+08 0.000e+00 2.11e-08 2.11e-08 2.82842712474619 2.828427124746195.369e+08 0.000e+00 0.00e+00 0.00e+00 0.00000000000000 0.00000000000000
Man erkennt deutlich am Anfang die Konvergenz gegen . Nach Erreichen etwa der halben Stellenzahl beim 32768-Eck macht sich jedoch die Auslöschung bei der Subtraktion der fast gleich großen Zahlen 2 und
bemerkbar. Das Ergebnis wird jetzt wieder ungenauer und am Ende falsch (2 − 2.000…000xxx = 0).
In vielen Fällen, so auch hier, kann man die Auslöschung vermeiden, einfach indem man die betroffenen Subtraktionen vermeidet. Hier gelingt das mit einer Umformung der Formel in eine äquivalente Form ohne Subtraktion unter Anwendung von
mit
Es ergibt sich:
Natürlich ist es ein glücklicher Zufall, dass sich im Zähler die Subtraktion „weghebt“. Jetzt verläuft die Rechnung wie erwünscht:
![]()
![]()
![]()
![]()
![]()
2.000e+00 1.000e+00 2.00e+00 Inf 0.00000000000000 Inf4.000e+00 2.929e-01 1.41e+00 2.00e+00 2.00000000000000 4.000000000000008.000e+00 7.612e-02 7.65e-01 8.28e-01 2.82842712474619 3.313708498984761.600e+01 1.921e-02 3.90e-01 3.98e-01 3.06146745892072 3.182597878074533.200e+01 4.815e-03 1.96e-01 1.97e-01 3.12144515225805 3.151724907429266.400e+01 1.205e-03 9.81e-02 9.83e-02 3.13654849054594 3.144118385245901.280e+02 3.012e-04 4.91e-02 4.91e-02 3.14033115695475 3.142223629942462.560e+02 7.530e-05 2.45e-02 2.45e-02 3.14127725093277 3.141750369168975.120e+02 1.882e-05 1.23e-02 1.23e-02 3.14151380114430 3.141632080703181.024e+03 4.706e-06 6.14e-03 6.14e-03 3.14157294036709 3.141602510256812.048e+03 1.177e-06 3.07e-03 3.07e-03 3.14158772527716 3.141595117749594.096e+03 2.941e-07 1.53e-03 1.53e-03 3.14159142151120 3.141593269629318.192e+03 7.353e-08 7.67e-04 7.67e-04 3.14159234557012 3.141592807599641.638e+04 1.838e-08 3.83e-04 3.83e-04 3.14159257658487 3.141592692092253.277e+04 4.596e-09 1.92e-04 1.92e-04 3.14159263433856 3.141592663215416.554e+04 1.149e-09 9.59e-05 9.59e-05 3.14159264877699 3.141592655996201.311e+05 2.872e-10 4.79e-05 4.79e-05 3.14159265238659 3.141592654191402.621e+05 7.181e-11 2.40e-05 2.40e-05 3.14159265328899 3.141592653740195.243e+05 1.795e-11 1.20e-05 1.20e-05 3.14159265351459 3.141592653627391.049e+06 4.488e-12 5.99e-06 5.99e-06 3.14159265357099 3.141592653599192.097e+06 1.122e-12 3.00e-06 3.00e-06 3.14159265358509 3.141592653592144.194e+06 2.804e-13 1.50e-06 1.50e-06 3.14159265358862 3.141592653590388.389e+06 7.017e-14 7.49e-07 7.49e-07 3.14159265358950 3.141592653589941.678e+07 1.754e-14 3.75e-07 3.75e-07 3.14159265358972 3.141592653589833.355e+07 4.441e-15 1.87e-07 1.87e-07 3.14159265358978 3.141592653589806.711e+07 1.110e-15 9.36e-08 9.36e-08 3.14159265358979 3.141592653589801.342e+08 2.220e-16 4.68e-08 4.68e-08 3.14159265358979 3.141592653589792.684e+08 0.000e+00 2.34e-08 2.34e-08 3.14159265358979 3.14159265358979
Schon bei dem 268435456-Eck erreicht man die volle Genauigkeit von knapp 16 Dezimalstellen. Das Abbruchsignal gibt die 0 in der zweiten Spalte.
Faustregel
BearbeitenSubtrahiert man zwei -stellige, fast gleich große Zahlen, die in den ersten
Stellen übereinstimmen, so gehen im Ergebnis von den eigentlich möglichen
Stellen
verloren. Es sind also nur noch
Stellen ungleich Null. Die Information, dass die ersten
Stellen sich zu Null aufgehoben haben, geht dabei verloren. Die Genauigkeit des Ergebnisses vermindert sich um diese
Stellen.
Unterscheiden sich die Zahlen in den letzten Stellen lediglich um Rundungsfehler, dann hat das Ergebnis keine Aussagekraft. Es sollte als solches nicht in weitere Berechnungen einfließen.
Differentialrechnung
BearbeitenBei der numerischen Berechnung von Ableitungen durch Differenzenquotienten wie zum Beispiel
tritt bei zu kleinem Auslöschung auf, da die Funktionswerte dann nahezu gleich sind.
Einzelnachweise
Bearbeiten- ↑ Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. 2. Auflage. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2, S. 41 (eingeschränkte Vorschau in der Google-Buchsuche).