Autor: Mark Probst
[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Vergleich der drei Summationsverfahren

Von N. J. Higham wurden in einer umfangreichen Studie acht verschiedene Summationsalgorithmen theoretisch untersucht und in praktischen Experimenten verglichen. Von diesen Verfahern hatten nur die drei in den vorangehenden Abschnitten behandelten Summationsalgorithmen – rekursive, paarweise und fehlerkompensierende Summation - eine O(n)-Kompexität. Als eines der Resultate der Studie konnte experimentell nachgewiesen werden, daß es sich nicht lohnt, Algorithmen mit höherer Komplexität (meist O(n log n) infolge der erforderlichen Sortiervorgänge) einzusetzen.

Summiert man z.B. n = 4, 8, 16, ..., 2048 Zufallszahlen, die auf [0,1] gleichverteilt sind, so erhält man nach 1000maliger Wiederholung (mit jeweils verschiendenen Zufallszahlen) Resultate, die in diesen Abbildungen dargestellt sind. Obwohl selbst die Extremwerte der bei rekursiver Summation aufgetretenen relativen Rechenfehler weit unter der theoretischen Fehlerschranke liegen, erkennt man die deutliche Überlegenheit der paarweisen und der fehlerkompensierenden Summation.

Um die Fehlerverläufe mit steigendem n genauer zu untersuchen, wurde folgendes Experiment gemacht: n = 4, 5, 6, ..., 2048 auf [1,2] gleichverteilte Zufallszahlen wurden mit jeder der drei Methoden summiert. Dabei wurde die jeweilige Summationsmethode zunächst auf die ersten 4, dann auf die ersten 5, ... Zufallszahlenn angewendet. Bei der rekursiven Summation erhält man damit ein Bild, wie sich der relative Rechenfehler während des Vorgangs der Summation der 2048 Zufallszahlen entwickelt. Man sieht an den Nulldurchgängen des Fehlerverlaufs, wie durch Kompensation aufeinanderfolgender Rundungsfehler immer wieder ein (nahezu) fehlerfreies Zwischenergebnis auftritt.

Bei der paarweisen Summation ist die obige Interpretation einer Verlaufsdarstellung nicht möglich, da das Hinzufügen eines Summanden im allgemeinen eine völlig veränderte "Klammerung" bewirkt.