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:

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.

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:

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: 

Zusammengefasst gehe also wie folgt vor:

Bestimme eine LR-Zerlegung der Matrix und löse anschließend das lineare Gleichungssystem mit mit Hilfe der Zerlegung. Gib außerdem die Determinante von an.

Bestimme eine LR-Zerlegung der Matrix und löse anschließend das lineare Gleichungssystem mit mit Hilfe der Zerlegung.

Bestimme eine LR-Zerlegung der Matrix und löse anschließend das lineare Gleichungssystem mit mit Hilfe der Zerlegung. Gib zusätzlich noch die Determinante der Matrix an.

Bestimme eine LR-Zerlegung der Matrix und löse anschließend das lineare Gleichungssystem mit mit Hilfe der Zerlegung. Gib zusätzlich noch die Determinante der Matrix an.