Die LU-Zerlegung schreibt eine quadratische Matrix A als Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix U um, sodass A = LU. Es handelt sich um die gleiche Arithmetik wie bei der gewöhnlichen Gaußschen Eliminierung, nur so verpackt, dass die Eliminierungsarbeit wiederverwendet werden kann – genau aus diesem Grund ist es die Standardmethode, die die meisten numerischen Bibliotheken verwenden, um lineare Systeme zu lösen, Matrizen zu invertieren und Determinanten zu berechnen.
Warum sollte man sich überhaupt die Mühe machen, A zu faktorisieren?
Wenn Sie Ax = b nur einmal lösen müssen, funktioniert die einfache Gaußsche Eliminierung auf der erweiterten Matrix gut. Die LU-Zerlegung zahlt sich aus, wenn Sie Ax = b für das gleiche A gegen viele verschiedene b-Vektoren lösen müssen – eine häufige Situation bei Simulationen, Schaltkreisanalysen und iterativen Lösern. Sobald A = LU berechnet ist, kostet jedes neue b nur eine kostengünstige Vorwärtssubstitution (solve Ly = b), gefolgt von einer kostengünstigen Rücksubstitution (solve Ux = y), anstatt die vollständige O(n³)-Eliminierung jedes Mal von Grund auf neu durchzuführen.
Wie durch teilweises Schwenken die korrekte Position gewährleistet wird
Gaußsche Eliminierung bricht zusammen, sobald ein Pivot (der diagonale Eintrag, durch den Sie dividieren möchten) Null ist – Sie können nicht durch Null dividieren, und die Division durch eine sehr kleine Zahl verstärkt den Rundungsfehler. Eine teilweise Pivotierung behebt dieses Problem, indem die verbleibenden Zeilen in der aktuellen Spalte gescannt werden und diejenige mit dem größten Absolutwert ausgetauscht wird, bevor sie entfernt wird. Jeder Tausch wird in einer Permutationsmatrix P verfolgt, sodass die Identität, die danach gilt, P·A = L·U und nicht A = L·U ist. Auf der Registerkarte „Schritte“ dieses Rechners wird genau angezeigt, wann und warum jeder Austausch stattfindet.
Die Determinante ist ein freies Nebenprodukt
Da L dreieckig ist und 1s auf der Diagonale hat, ist det(L) immer = 1. Da U dreieckig ist, ist seine Determinante nur das Produkt seiner Diagonale. Und da bei jedem Zeilenwechsel das Vorzeichen einer Determinante umgedreht wird, ergibt sich für det(A) (−1)^(Anzahl der Vertauschungen) × (Produkt der U-Diagonalen) – keine separate Kofaktorerweiterung erforderlich. Dies ist auch der Grund, warum eine Null irgendwo auf der Diagonale von U eine singuläre Matrix signalisiert: Das Produkt wird Null, also ist det(A) = 0, egal was die Pivotierung auf dem Weg bewirkt hat.