LR-Zerlegung einer quadratischen Matrix
Bei der Entwicklung der Schritte des Gaußschen Algorithmus für die Lösung des linearen Gleichungssystems mit n Gleichungen und n Unbekannten
wird nicht deutlich, dass der Eliminationsprozess (mit dem Ziel der Triangularisierung der Koeffizientenmatrix) der Zerlegung der Matrix A in ein Produkt aus einer Links- und einer Rechts-Dreiecksmatrix entspricht. Eine solche Zerlegung, so dass bei der Rückmultiplikation entsprechend
wieder die Matrix A entsteht, ist für eine reguläre Matrix A möglich. Weil in L und R zusammen n2+n Nicht-Null-Elemente vorkommen (in beiden Matrizen sind die Hauptdiagonalen belegt), bei der Rückmultiplikation zur Erzeugung der n2 Elemente von A aber nur n2 Bedingungen erfüllt sein müssen, können in den Dreiecksmatrizen n Elemente frei gewählt werden. Es ist üblich (und sinnvoll), die Hauptdiagonale von L mit Einsen zu belegen.
Falksches Schema für Matrixmultiplikation
Nebenstehend ist das
Falksche Schema
Beispiel für Matrixmultiplikation
für die Rückmultiplikation zu sehen, das den erforderlichen Algorithmus für die Gewinnung von L und R verdeutlicht (zur Erinnerung: Jedes Element ai j der Matrix A muss sich aus dem Skalarprodukt der i-ten Zeile von L mit der j-ten Spalte von R ergeben):
Lösen des linearen Gleichungssystems
Nach der LR-Zerlegung der Matrix A kann in dem linearen Gleichungssystem
für das Produkt aus Rechtsdreiecksmatrix R und dem Vektor der Unbekannten x ein (unbekannter) Vektor y angenommen werden (R x = y), der aus
durch so genanntes Vorwärtseinsetzen berechnet werden kann (weil L eine Dreiecksmatrix ist, kommt in der ersten Gleichung nur die Unbekannte y1 vor, nach Berechnung von y1 kommt in der zweiten Gleichung nur noch y2 als Unbekannte vor usw.).
Wenn y bekannt ist, kann mit analoger Strategie der Vektor x aus
durch Rückwärtseinsetzen berechnet werden.
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 li j 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.
Determinante, Zeilentausch, Singularität, Pivotisierung
det (A) = det (L) · det (R) = (-1) z · r11 · r22 · r33 · .... · rnn
aus dem Produkt der Diagonalelemente von R berechnet werden (z ist die Anzahl der "Zeilentauschoperationen"), weil die Determinante der Links-Dreiecksmatrix L wegen der Eins-Elemente auf der Hauptdiagonalen den Wert 1 hat.
Natürlich müsste ein anschließendes Vorwärtseinsetzen mit der 2. Zeile der Links-Dreiecksmatrix beginnen: Die Information über die Reihenfolge der Bearbeitung muss gespeichert werden. Man kann sich diese Information als zusätzlichen Ergebnisparameter der lu-function ausgeben lassen.