[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]
Im allgemeinen muss man bei jedem Schritt einer arithmetisch Algorithmus
damit rechnen, dass die im Maschinnenalgorithmus, d.h. im Objektcode, implementierte
Operation 
geringfügig
von der exakten arithmetisch Operation ° abweicht. Bei einem arithmetischen
Algorithmus mit insgesamt N Einzeloperationen können also ebensoviele
einzelne Rechenfehler entstehen, deren relative Grösse in jeder Gleitpunktoperation
(im Bereich der normalisierten Maschinenzahlen) mit eps beschränkt
ist:
x y = (x
°
y)(1+ p) mit | p| <= eps
Dazu kommt ein weiterer Effekt: Auf Grund der Rechenfehler weichen im allgemeinen sämtliche Zwischenergebnisse eines Maschinenalgorithmus von denen des exakten Algorithmus ab. Da die Zwischenergebnisse aber als Operanden in weiteren Schritten des Algorithmus auftreten - sonst wäre ihre Berechnung ja sinnlos gewesen - , haben alle Operationen in den später ausgeführten Schritten auch verfälschte Argumente. Auch wenn bei diesen Operationen keine neuen Rechenfehler entstehen sollten, wirken sich die Fehler der Argumente in der Regel störend auf das Ergebnis dieser Operation aus. Ein einziger Rechenfehler kann also die Zwischenergebnisse vieler späterer Schritte und schliesslich auch das Endergebnis verfälschen. Man bezeichnet diesen Effekt als Fehlerfortpflanzung.
Bei der Analyse eines arithmetischen Algorithmus geht es also darum, festzustellen, wie sich ein Fehler in einem beliebigen Zwischenergebnis durch dessen Weiterverwendung auf das Endresultat auswirkt. Algorithmus , die bei "exakter Rechnung" äquivalent. sind, also bei identischen Daten auch identische Zwischenergebnisse liefern, können ihre Endergebnisse auf verschiedenen Wegen erzeugen. Bei den Implementierung dieser Algorithmen, den "Maschinenalgorithmen", wird im allgemeinen das Ausmaß der Fehlerfortplanzung unterschiedlich sein, d.h. selbst bei identischen Datenn werden sie verschieden genaue Resultate liefern.
Einen Algorithmus mit einer geringen Fehlerfortpflanzung bezeichnet man als "gutartig" oder numerisch stabil, einen solchen mit einer starken Fehlerfortpflanzung als "nicht gutartig" oder numerisch instabil. Natürlich wird man, wenn man die Wahl hat, unter äquivalenten Algorithmen einen möglichst gutartigen für eine Implementierung heranziehen.
Bei der Beurteilung der Fehlerfortpflanzung muß man berücksichtigen, daß ein arithmetisch Algorithmus als Darstellung einer mathmatischer Abbildung zwischen den Daten und den Erfgebnissen ein typische Störungsemfindlichkeit aufweist: Eine "Störung" der Daten bewirkt in ganz bestimmer Weise eine Veränderung der Ergebnisse. Diese Störungsempfdindlichkeit, die man als Kondition bezeichnet, stellt eine fundamentale Eigenschaft des mathematischen Zusammenhangs dar (siehe Kapitel 2).
(S.221)
Ein arithmetischer Algorithmus, der einen schlecht konditionierten (d.h. gegenüber Datenänderungen empfindlichen) Zusammenhang zwischen seinen Daten und Ergebnissen darstellt, wird auch auf Änderungen an seinen Zwischenergebnissen empfindlich reagieren, ein gut konditionierter Algorithmus dagegen kaum. Die für die Fehlerfortpflanzung wesentlich Empfindlichkeit gegenüber Änderungen an Zwischenergebnissen ist also relativ zur Kondition des durch den exakten Algorithmus dargestellten mathematischen Zusammenhangs zu beurteilen.
Beispiel (Quadratische Gleichung) Es lässt sich einfach feststellen, dass die Kondition jener Abbildung, die den Daten (a1,a0) das Resultat (y1,y2) zuordnet, bei Betrachtung der realtiven änderungen in der Grössenordnung 1 liegt. Der mathematische Zusammenhang zwischen Daten und Resultaten ist also gut konditioniert. Die relative Verfälschung des Zwischenergebnisses z4 beim Wurzelziehen in der vierstelligen Dezimalarithmetik von ca. 3*10-4 sollte sich also nur gleich stark auf das Ergebnis auswirken. Eine Verfälschung des Ergenisses um ca. 4*10-3, wie sie beim Algorithmus QG-1 auftritt, ist um 2 Grössenordnungen grösser; der Algorithmus QG-1 ist also (für diese Daten) als instabil zu bezeichnen.