Was die LR-Zerlegung leistet
Die LR-Zerlegung, im Englischen LU decomposition, schreibt eine quadratische Matrix A als Produkt einer linken unteren Dreiecksmatrix L mit Einsen auf der Diagonale und einer rechten oberen Dreiecksmatrix R. Sie ist nichts anderes als das gaußsche Eliminationsverfahren in Matrixform: R ist die Stufenform, die bei der Elimination entsteht, und in L stehen die Faktoren, mit denen die Zeilen voneinander abgezogen wurden.
In der Praxis wird fast immer mit Zeilenvertauschung gearbeitet. Bevor in Spalte k eliminiert wird, sucht das Verfahren in dieser Spalte unterhalb der Diagonale den betragsgrößten Eintrag und tauscht seine Zeile nach oben. Diese Spaltenpivotsuche verhindert eine Division durch null und begrenzt die Rundungsfehler, weil alle Faktoren in L höchstens den Betrag 1 haben. Die Vertauschungen werden in einer Permutationsmatrix P festgehalten, sodass PA = LR gilt.
Der Rechner folgt dem Standardalgorithmus, wie er in Lehrbüchern zur numerischen Mathematik beschrieben ist, etwa bei Dahmen und Reusken oder bei Golub und Van Loan. Ist eine Matrix singulär, findet das Verfahren in einer Spalte keinen Pivot ungleich null und meldet das. Matrizen bis 6×6 werden unterstützt.
Gleichungssysteme lösen und Determinante bestimmen
Der große Vorteil der Zerlegung zeigt sich, wenn dasselbe Gleichungssystem mit vielen rechten Seiten gelöst werden muss. Die Zerlegung kostet bei einer n×n-Matrix etwa n³/3 Multiplikationen, das anschließende Vorwärts- und Rückwärtseinsetzen nur etwa n² je rechter Seite. In Simulationsprogrammen, in der Statik oder beim Berechnen einer inversen Matrix wird die Zerlegung deshalb einmal ausgeführt und dann immer wieder verwendet.
Zum Lösen von Ax = b wird zuerst b mit der Permutation umsortiert. Dann ergibt sich aus Ly = Pb der Zwischenvektor y von oben nach unten, weil L eine untere Dreiecksmatrix ist. Anschließend liefert Rx = y die Lösung von unten nach oben. Der Rechner zeigt zur Kontrolle das größte Residuum |Ax − b|, das bei gut konditionierten Matrizen im Bereich der Rechengenauigkeit liegt.
Die Determinante fällt als Nebenprodukt ab: Sie ist das Produkt der Diagonaleinträge von R, mit umgekehrtem Vorzeichen, wenn eine ungerade Zahl von Zeilenvertauschungen nötig war. Das ist bei größeren Matrizen wesentlich schneller als die Entwicklung nach Laplace, deren Aufwand mit n! wächst.
Die Permutationsmatrix P hat in jeder Zeile und Spalte genau eine Eins. Steht in Zeile i die Eins in Spalte j, so ist Zeile i von PA die Zeile j von A. Bei symmetrisch positiv definiten Matrizen kann man statt der LR-Zerlegung die Cholesky-Zerlegung verwenden, die nur halb so viel Aufwand hat und ohne Pivotsuche stabil ist. Bei fast singulären Matrizen sollten Sie die Ergebnisse mit Vorsicht interpretieren, weil kleine Eingabefehler große Wirkung haben.
Tipps und typische Fehler
Matrizen zerlegen.
- Pivot: Betragsgrößtes Element.
- Probe: PA = LR prüfen.
- Determinante: Vorzeichen beachten.
- Residuum: Kontrollieren.
Mehr zum Thema Vektoren, Matrizen und Koordinaten
Häufige Fragen
Was ist der Unterschied zwischen LR- und LU-Zerlegung?
Keiner. LR steht für links und rechts, LU für lower und upper. Beide Bezeichnungen meinen dieselbe Zerlegung in eine untere und eine obere Dreiecksmatrix.
Warum braucht man die Zeilenvertauschung?
Ohne sie scheitert das Verfahren schon an Matrizen mit einer Null an einer Pivotstelle, und kleine Pivots verstärken Rundungsfehler stark. Die Spaltenpivotsuche vermeidet beides.
Hat jede Matrix eine LR-Zerlegung?
Mit Zeilenvertauschung ja, jede reguläre Matrix. Ohne Vertauschung nur, wenn alle führenden Hauptminoren ungleich null sind.
Wie berechnet man die Inverse mit der LR-Zerlegung?
Man löst Ax = e_i für jeden Einheitsvektor e_i mit derselben Zerlegung. Die Lösungen sind die Spalten der Inversen.
Was ist eine Permutationsmatrix?
Eine Matrix mit genau einer Eins in jeder Zeile und Spalte. Die Multiplikation von links vertauscht die Zeilen einer Matrix.
- LR-Zerlegung berechnen
- LU-Zerlegung online
- PA = LR
- Gauß-Elimination Pivot
- LR-Zerlegung mit Pivotisierung
- Dreieckszerlegung Matrix
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.