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

Lineares Gleichungssystem mit quadratischer Koeffizientenmatrix (n Gleichungen mit 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

LR-Zerlegung der Matrix A

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 die LR-Zerlegung 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):

Formeln für das Erzeugen der Linksdreiecksmatrix L und der Rechtsdreiecksmatrix R (LR-Zerlegung)

Lösen des linearen Gleichungssystems

Nach der LR-Zerlegung der Matrix A kann in dem linearen Gleichungssystem

Lineares Gleichungssystem nach der LR-zerlegung der Koeffizientenmatrix

für das Produkt aus Rechtsdreiecksmatrix R und dem Vektor der Unbekannten x ein (unbekannter) Vektor y angenommen werden (R x y), der aus

System mit Linksdreiecksmatrix L für das Vorwärtseinsetzen

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

System mit der Rechtsdreiecksmatrix R für das Rückwärtseinsetzen

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:

Einfaches Beispiel für die Demonstration der LR-Zerlegung

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:

Falksches Schema für den Start der LR-ZerlegungFalksches Schema für die LR-Zerlegung

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.

VEGlSyst1

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.

REGlSyst1

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:

Schema für den kompletten verketteten Algorithmus (LR-Zerlegung, Vorwärts- und Rückwärtseinsetzen)

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

Matlab-Script für die LR-Zerlegung einer quadratischen Matrix