Die Links-Rechts-Zerlegung, auch LR-Zerlegung (englisch: Lower-Upper-Zerlegung, LU-Zerlegung) beschreibt eine Lösungsmethode für lineare Gleichungssysteme der Form
Hintergrund
Durch einfaches Auflösen erhält man
, die Berechnung von inversen Matrizen ist aber unnötig aufwendig und numerisch nicht vorteilhaft. Daher wird oft die LR-Zerlegung als Lösungsverfahren verwendet.
Verfahren
Bei der LR-Zerlegung geht man wie folgt vor:
- Zerlege die Matrix
in eine rechte obere Dreiecksmatrix mittels Typ A-Zeilenumformungen. Daraus bildet sich zeitgleich eine linke untere Dreiecksmatrix (siehe Beispiel). - Weil
folgt und daraus die zwei einfachen Gleichungen die jetzt einfach mittels Gaußverfahren aufgelöst werden können.
Anmerkung
Um das Eliminieren der Spalten möglichst günstig zu gestalten, ist es sinnvoll, die Ausgangsmatrix vor jedem Schritt erst mit einer passenden Permutationsmatrix zu multiplizieren, sodass die Zeile ganz oben steht, bei der der Wert der ersten Spalte am kleinsten ist. Die Multiplikation mit einer Permutationsmatrix entspricht Typ B-Zeilenumformungen
Beispiel