WaBis

walter.bislins.ch

Fehlerberechnung Pi

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.

Algebraische Berechnung der Oktimedeszahl

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.

Numerische Berechnung der Oktimedeszahl

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 eRel = (o - ) / berechnet und ausgegeben. Wenn der rel. Fehler kleiner als eMax wird, bricht das Programm ab, weil dann die gewünschte Genauigkeit erreicht ist. eMax ist abhängig von der Rechengenauigkeit des Computers. Ausserdem bricht das Programm ab, wenn der rel. Fehler grösser als 0.999 wird, wenn also die Oktimedeszahl total wegdriftet.

Ergebnis der Berechnung

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!

Erklärung des Rechenfehlers

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.

Relativer Fehler bei Addition und Subtraktion mit beschränkter Stellenzahl

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!

Berechnung des Rechenfehlers einer Formel

Der relative Fehler für [1-(1-x)] kann wiefolgt berechnet werden (R = Anzahl Stellen eines Taschenrechners):

(VI) Für hat x überhaupt keinen Einfluss mehr und der Fehler ist undefiniert (beliebig gross)!

Wenn wir die Annäherungsformel (IV) für den Cosinus verwenden, erhalten wir einen relativen Fehler für [1 – cos(x)] ~ [1 – (1 – x2/2)] von:

(VII) Für hat x überhaupt keinen Einfluss mehr und der Fehler ist undefiniert (beliebig gross)!

Relativer Fehler der Oktomedeszahl

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 hat n überhaupt keinen Einfluss mehr und der Fehler ist undefiniert (beliebig gross)!

Beispiel

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

3.102 10-6

2.656 10-7

8

2048

12.5663791

6.753 10-7

1.062 10-6

9

4096

12.5663667

-3.115 10-7

4.250 10-6

10

8192

12.5663662

-3.513 10-7

1.700 10-5

11

16384

12.5663226

-3.821 10-6

6.800 10-5

12

32768

12.5659805

-3.104 10-5

2.720 10-4

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!

Lösung des Rundungsproblems

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)

 

Weitere Infos zur Seite
Erzeugt Sonntag, 3. Januar 2010
von wabis
Zum Seitenanfang
Geändert Sonntag, 6. Dezember 2015
von wabis