LU Decomposition
Die LU-Zerlegung faktorisiert eine Matrix A in das Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix U, A=LU, und beschleunigt wiederholte lineare Lösungsvorgänge.
Zweck
Einmal vorzufaktorisieren und dann lineare Systeme mit mehreren rechten Seiten effizient zu lösen.
Mechanismus
Sie ist die Matrixform der Gauß-Elimination: der Eliminationsprozess liefert L (die Multiplikatoren) und U (das eliminierte Ergebnis). Das Lösen von Ax=b wird zu Ly=b (Vorwärtssubstitution) und Ux=y (Rücksubstitution). Die Zerlegung kostet O(n^3); jede Lösung kostet O(n^2).
Anwendungsfälle
- Lösung linearer Systeme
- Matrixinversion
- Numerische lineare Algebra