Am Beispiel zur Berechnung der «Oktimedeszahl» zeige ich, wie sich Rundungsfehler bei numerischen Verfahren (Berechnungen mit Hilfe von Computern) so auswirken können, dass schliesslich ein total falsches Resultat heraus kommt. Am selben Beispiel zeige ich auf, wie so ein Rechenfehler entsteht, wie er vorausgesagt und abgeschätzt werden kann und schliesslich, wie er verhindert oder zumindest sinnvoll vermindert werden kann.
Bei einem regelmässigen N-Eck gilt folgende Formel für das Verhältnis von Umfang im Quadrat zu Fläche (ohne Herleitung):
(I) |
![]() |
o Oktimedeszahl U Umfang des N-Ecks A Fläche des N-Ecks n Anzahl Ecken |
Der Grenzfall (unendlich viele Ecken)
entspricht einem Kreis. Für
sollte demnach
sein:
(II) |
![]() |
Suchen wir zunächst eine algebraische Lösung für den Grenzwert der Oktimedeszahl:
Würden wir den Grenzwert berechnen, indem wir die Grenzwerte von Zähler und Nenner separat berechnen,
kommen wir zu einem falschen und unsinnigen Resultat:
Für gehen die Winkel von sin() und cos() gegen Null:
(III) |
![]() |
? |
(I) ist für nicht definiert (0 / 0)!
Trotzdem kann ein Grenzwert für
berechnet werden.
Man darf aber nicht die Grenzwerte von Zähler und Nenner separat berechnen, sondern muss den Grenzwert
der ganzen Formel berechnen. Dazu ersetzt man sin() und cos() durch die entsprechenden Näherungsfunktionen
(Taylorpolynome):
(IV) |
![]() |
![]() |
![]() |
![]() |
Für sehr kleine x müssen nur die ersten Terme beachtet werden, da die anderen vernachlässigbar klein werden. Deshalb können für den Limes die obigen Formeln rechts verwendet werden.
In (II) eingesetzt ergibt sich:
(V) |
![]() |
Jetzt kürzt sich n heraus und es
bleibt als
Grenzwert für ein beliebig grosses regelmässiges N-Eck mit unendlich vielen
Ecken. Somit haben wir die genaue algebraische Lösung für den Grenzwert der Oktimedeszahl gefunden.
Ein Computer kann natürlich nicht mit Unendlichkeiten umgehen. Will man den Grenzwert der Oktimedeszahl numerisch bestimmen, lässt man die Formel für immer grössere n durchrechnen und listet die Resultate in einer Tabelle auf und zeichnet sie in eine Grafik. So kann man sehen, ob und auf welchen Grenzwert die Formel tendiert. Mit folgendem kleinen Programm werden die Oktimedes-Werte für verschiedene n berechnet:
function oktimedes( n ) { var winkel = 2 * Math.PI / n; return 4 * n * (1 - Math.cos(winkel)) / Math.sin(winkel); } var i = 1; // Schritt-Zähler var n = 8; // Anzahl Ecken, Start mit einem 8-Eck var o = 0; // Oktimedeszahl var eRel = 1; // Relativer Fehler var eMax = 1e-12; // Abbruchbedingung: wenn rel. Fehler kleiner als eMax while ((Math.abs(eRel) > eMax) && (Math.abs(eRel) < 0.999)) { var o = oktimedes(n); var eRel = (o - (4 * Math.PI)) / (4 * Math.PI); // relativer Fehler Out( i, n, o, eRel ); n = n * 2; i++; }
Schritt | Anz. Ecken | Oktimedeszahl | rel. Fehler |
Das Programm startet mit einem 8-Eck und verdoppelt bei jedem Durchgang die Anzahl Ecken.
In der Schleife wird die Oktimedeszahl und der relative Fehler ) /
Zunächst nimmt der rel. Fehler wie erwartet immer weiter ab. Das heisst, die Oktimedeszahl nähert sich
immer mehr dem Wert .
Bei Schritt 13 ist der rel. Fehler gerade noch 8.6 * 10-10.
Doch nun geschieht etwas Seltsames. In Schritt 14 ist der rel. Fehler mit -3.7 * 10-9
plötzlich wieder grösser und
zudem negativ. Das bedeutet, dass die berechnete Oktimedeszahl den Grenzwert
plötzlich überschritten hat.
Bis zum Schritt 17 wird der Fehler immer grösser und grösser. Ab Schritt 18 schwingt die Oktimedeszahl
immer stärker um den Wert
(wechselndes Vorzeichen des rel. Fehlers),
um schliesslich bei Schritt 28 Null zu werden und zu bleiben!
Wie kommt es, dass sich die Werte zunächst wie erwartet immer mehr an
annähern und die Abweichung (rel. Fehler)
immer kleiner wird, dann aber plötzlich wieder schnell grösser wird, um
schwingt und schliesslich beim total falschen
Wert 0 ankommt?
Die Erklärung hat nichts Mystisches an sich. Es hat lediglich mit Rechenungenauigkeiten zu tun. Nun könnte man argumentieren, dass doch ein Computer mit mindestens 10-12 Stellen genau rechnet, wenn nicht mehr. Woher soll denn diese riesige Ungenauigkeit kommen?
Der Grund liegt darin, dass cos(x) für sehr kleine x immer ungenauer wird (im Gegensatz zu sin(x)). Dies sieht man ein, wenn man weiss, wie cos(x) berechnet wird:
Werden oben die x Werte sehr klein im Vergleich mit 1, gehen immer mehr Stellen verloren, da der Rechner vor dem Addieren der kleinen Werte diese auf die Grössenordnung von 1 normieren muss:
volle Genauigkeit Normiert
1.00000000000 E 0 1.00000000000
-1.23456789012 E-6 - 0.00000123456xxxxxx
In diesem Beispiel gehen 6 Stellen
Genauigkeit verloren! Wo der Sinus für sehr kleine x sich immer noch mit der
vollen Genauigkeit gegen x nähert, wird der Cosinus sehr schnell einfach zu
1.000 und damit immer ungenauer. Würde ein Rechner mit beliebig vielen
Stellen rechnen, würde sich o immer mehr nähern und nicht 0.
Der Computer muss vor dem Addieren und Subtrahieren zweier Zahlen diese so aneinander ausrichten, dass sie denselben Exponenten haben (siehe Beispiel oben). Dabei werden bei der kleineren Zahl immer ein paar Stellen abgeschnitten. Im Extremfall geht die kleinere Zahl ganz verloren: Addiere zum Beispiel 1 + 1.23456789 * 10-20. Das Resultat ist genau 1.000000000! Der zweite Summand hat überhaupt keine Wirkung!
Oder: 1000000000 + 12345.6789 – 1000000000 = 12345 (bei einem Rechner mit 10 Stellen Genauigkeit). Das ist ein absoluter Fehler von 0.6789! Der relative Fehler (normiert auf 12345.6789) ist hier 5.5 * 10-5 und nicht 1 * 10-10 wie es die Rechengenauigkeit des Rechner erwarten lässt!
Der relative Fehler für [1-(1-x)] kann wiefolgt berechnet werden (R = Anzahl Stellen eines Taschenrechners):
(VI) |
![]() |
Für ![]() |
Wenn wir die Annäherungsformel (IV) für den
Cosinus verwenden, erhalten wir einen relativen Fehler für
(VII) |
![]() |
Für ![]() |
Durch Multiplizieren und Dividieren mit Zahlen, die keinen Fehler haben, bleibt die Grössenordnung des Fehlers über die ganze Formel erhalten.
(I) |
![]() |
![]() |
Relativer Fehler von o:
(VIII) |
![]() |
Für ![]() |
Wenn wir nun die Eckenzahl von 8 an beginnend laufend verdoppeln und die Werte für o berechnen nach Formel (I) und daneben den relativen Fehler eines Taschenrechners, der intern mit 12 Stellen rechnet, notieren, berechnet nach Formel (VIII), erhalten wir folgende Tabelle:
i = Anzahl Verdoppelungen des 8-Ecks; Anz. Ecken = 8 * 2i
i |
Anz. Ecken |
Oktimedeszahl |
rel. Fehler |
|
7 |
1024 |
12.5664096 |
|
|
8 |
2048 |
12.5663791 |
|
|
9 |
4096 |
12.5663667 |
|
|
10 |
8192 |
12.5663662 |
|
|
11 |
16384 |
12.5663226 |
|
|
12 |
32768 |
12.5659805 |
|
|
Die Erwartung wäre eigentlich, dass der rel. Fehler
immer kleiner würde, da sich das N-Eck schliesslich immer
mehr einem Kreis annähert. Wie man sieht, schiesst der Wert der Oktimedeszahl sogar über
sein Ziel hinaus (Negative Werte ab der 9. Verdoppelung) und die Oktimedeszahl
entfernt sich sogar immer mehr von
(Tatsächlich strebt er gegen Null)!
Die Erklärung sieht man in der letzten Spalte. Dort wird angegeben, wie genau die Oktimedeszahl berechnet werden kann, wenn ein Rechner mit 12 Stellen Genauigkeit verwendet wird. Wie man sieht, ist bereits ab der 8. Verdoppelung der vorausgesagte Rechenfehler grösser, als die tatsächliche Abweichung. Ab da nimmt der Rechenfehler immer stärker zu. Mit der Formel (I) und einem Taschenrechner lässt sich die Oktimedeszahl also nicht genauer bestimmen!
Eine Lösung brächte ein Rechner, der eine Funktion cosm(x) = 1 – cos(x) eingebaut hätte. Diese Funktion könnte für x gegen Null ebenso genau berechnet werden, wie sin(x) und der Rechenfehler würde im Bereich 10-11 bleiben. Die Formel (I) mit cosm(x) sähe folgendermassen aus:
(I) |
![]() |
![]() |
![]() |
![]() |