LR - Zerlegung

Stell dir vor du sollst ein lineares Gleichungssystem lösen. Dafür hast du eine invertierbare Matrix und einen Vektor gegeben. Nun besteht das Ziel darin den Vektor zu bestimmen, der die Gleichung erfüllt. Formal bekommst du die Lösung durch . Das Problem ist nun, dass die Berechnung von bei einer großen Matrix extrem aufwendig ist. Es gibt zwar auch andere Möglichkeiten ein Gleichungssystem zu lösen (z.B die im Kapitel "lineare Gleichungssysteme lösen" vorgestellte Craemer-Regel), allerdings sind diese numerisch gesehen meist nicht zu empfehlen.

Bei der im folgenden vorgestellten Methode der LR-Zerlegung hingegen handelt es sich um eine numerisch gutartige Methode, mit deren Hilfe sich Gleichungssysteme mit bis 10000 Zeilen und Unbekannten vorteilhaft lösen lassen (dannach empfehlen sich iterative Verfahren). Dafür wird zuerst die Matrix zerlegt (Vorgehen 1) und anschließend das Gleichungssystem durch einsetzen gelöst (Vorgehen 2).



Zerlegung

Der LR-Algorithmus (Treppeniteration, LR-Verfahren, LR-Iteration) ist ein Verfahren zur Zerlegung einer quadratischen Matrix . Die Matrix kann nach erfolgreicher Zerlegung als das Produkt einer rechte obere Dreiecksmatrix und einer linken unteren Dreieckmatix ausgedrückt werden, also . Dabei hat nur Einsen auf der Diagonalen, wohingegen dort Werte stehen hat. 

Für eine LR-Zerlegung der Matrix benutzen wir das bekannte Gaußverfahren. Allerdings speichern wir in der Matrix statt der durch Zeilenumformung erzeugten Nullen die Information über die Zeilenumformung. Rechnen wir also z.B. so schreiben wir in der Matrix an der Stelle die Zahl Tauschen wir im Laufe des Gaußverfahrens Zeilen, so müssen wir das auch bei diesen Einträgen berücksichtigen.

Merke dir während der Umformungen jede Vetauschung. Diese schreibst kannst du am Ende in eine sogennante Permutationsmatrix schreiben. Die Permutationsmatrix ist einfach eine Einheitsmatrix, die alle durchgeführten Vertauschungen aufweist.

Um also eine LR-Zerlegung zu einer Matrix zu berechnen nutze die folgende Schritte:

Vorgehen

Bestimmung einer LR-Zerlegung

Gegeben ist eine invertierbare Matrix Man erhält Matrizen und mit wie folgt:

  1. Nutze den Gaußalgorithmus, um mit iterativ alle Einträge unterhalb von (Diagonaleinträge) zu eleminieren. 
    Falls sein sollte, so vertausche (permutiere) Zeilen deiner Matrix und merke dir diese Vertauschungen.

    • Starte mit (Pivotelement): Ziehe Vielfache der ersten Zeile von den übrigen ab, sodass die Einträge der ersten Spalte zu Null werden.
    • Überschreibe die entstehenden Nullen mit:

      Wiederhole diese Schritte anschließend mit

  2. Lies die gesuchte und Matrix ab. besteht dabei aus dem linken unteren Teil deiner gefundenen Matrix, ergänzt um Einsen auf der Diagonalen. besteht aus dem rechten oberen Teil inklusive der Diagonaleinträge.



  3. Falls du Zeilen getauscht hast, so musst du noch die Permutationsmatrix aufstellen. Schreibe dafür eine Einheitsmatrix auf und führe alle unter 1) gemerkten Vertauschungen an ihr durch.

Pivotisierung:

In der Numerik wird oft nach der LR-Zerlgung mit Pivotisierung gefragt. Die Pivotisierung wird dazu genutzt bei nicht exakter Rechnung Rundungsfehler zu minimieren. 
Die Idee ist, durch Vertauschung, immer das größtmögliche Pivotelement zu erhalten. Dies bietet den Vorteil, dass je größer die Pivotelemente betragsmäßig sind, desto kleiner sind die Beträge der Eliminationsfaktoren, sodass die Elemente in den noch abzuarbeitenden Spalten möglichst wenig anwachsen.

Hinweis

Bei der Spaltenpivotisierung musst du vor der Elimination deine Zeilen tauschen, sodass immer die betragsmäßig größte Zahl dein Pivotelement bildet.

Gleichungssystem lösen:

Nachdem du nun die Matrix in eine obere Rehte und eine untere Linke Matrix zerlegt hast, ist die Lösung des Gleichungssystems nun recht einfach. Zunächst erstetzen wir durch unsere gefundene Zerlegung:

Hinweis

(ohne Zeilenvertauschung)

Nun musst du 2 Gleichungssysteme lösen, welche allerdings nicht mehr umgeformt werden müssen. Zuerst wird nach durch Vorwärtseinsetzen und anschließend durch Rückwärtseinsetzen gelöst.

Sollten während der LR-Zerlegung für Zeilenvertauschungen durchgeführt worden sein, so musst du vor dem lösen noch den Vektor mit der Permutationsmatrix multiplizieren bzw. alle Vertauschungen auch an dem Vektor durchführen: 

Hinweis

(mit Zeilenvertauschung)

Zusammengefasst gehe also wie folgt vor:

Vorgehen

LGS mit LR-Zerlegung lösen

Gesucht ist die Lösung eines LGS . Gegeben ist eine -Zerlegung von mit

  1. Falls eine Permutationsmatrix vorliegt so multipliziere sie mit dem Vektor . Kurz: Führe alle während der Zerlegung durchgeführten Zeilenvertauschungen auch an durch.


  2. Löse das lineare Gleichungssystem durch Vorwärtseinsetzen:


  3. Löse nun das lineare Gleichungssystem durch Rückwärtseinsetzen:

Verlinkte Themen

LR-Zerlegung