Einfaches Beispiel
Der oben beschriebene Algorithmus soll an dem einfachen Beispiel demonstriert werden, das auch mit dem klassischen Gauß-Algorithmus berechnet wurde:
Zunächst wird die LR-Zerlegung der Matrix A durchgeführt. Das nachfolgend links zu sehende Falksche Schema ist so zu füllen, dass die Multiplikation der beiden Dreiecksmatrizen die eingetragene Matrix A ergibt:
Rechts sieht man das ausgefüllte Schema. Die blauen Werte in der ersten Zeile der Rechts-Dreiecksmatrix entstehen zuerst, danach die grün eingetragenen Werte der Links-Dreiecksmatrix, dann die roten Werte usw.
Bei einem Vergleich mit dem klassischen Gauß-Algorithmus erkennt man, das die Rechts-Dreiecksmatrix exakt die dort entstandene Matrix R des "gestaffelten Systems" ist und dass die Elemente in der Links-Dreiecksmatrix exakt die Werte lij enthält, mit denen die einzelnen Gleichungen beim Eliminationsprozess multipliziert worden sind: Der verkettete Algorithmus ist nur eine andere Schreibweise für den klassischen Gauß-Algorithmus.
Nachfolgend ist links das Schema für das Vorwärtseinsetzen zu sehen, rechts das ausgefüllte Schema: Die Werte des Vektors y entstehen von oben nach unten ("vorwärts"), der Algorithmus entspricht exakt dem Vorgehen bei der LR-Zerlegung.
Schließlich entsteht der Lösungsvektor x durch Rückwärtseinsetzen (nachfolgend wieder links das Schema dafür, rechts das ausgefüllte Schema). Die Werte des Vektors x entstehen von unten nach oben ("rückwärts"), der Algorithmus entspricht exakt dem Rückwärtseinsetzen des klassischen Gauß-Algorithmus.
Das Falksche Schema gestattet auch hier die kompakte Anordnung aller Matrizen und Vektoren, auch hier wieder links das Schema und rechts das ausgefüllte Schema:
In dieser Darstellung wird besonders deutlich, dass der verkettete Algorithmus dem klassischen Gauß-Algorithmus entspricht: Das Vorwärtseinsetzen kann bei der LR-Zerlegung gleich mit erledigt werden, in dem diese auf den zusätzlichen Vektor ausgedehnt wird. Dies entspricht der Einbeziehung der rechten Seite in den Triangularisierungsprozess beim klassischen Gauß-Algorithmus. Das anschließende Rückwärtseinsetzen ist in beiden Varianten ohnehin identisch. Es ist ersichtlich, dass zusätzliche rechte Seiten einfach rechts an das Schema angefügt werden können.
|