LU Decomposition
La décomposition LU factorise une matrice A en le produit d'une matrice triangulaire inférieure L et d'une triangulaire supérieure U, A=LU, accélérant les résolutions linéaires répétées.
Objectif
Préfactoriser une fois puis résoudre efficacement des systèmes linéaires avec plusieurs seconds membres.
Mécanisme
C'est la forme matricielle de l'élimination de Gauss : le processus d'élimination produit L (les multiplicateurs) et U (le résultat éliminé). Résoudre Ax=b devient Ly=b (substitution avant) puis Ux=y (substitution arrière). La décomposition coûte O(n^3) ; chaque résolution coûte O(n^2).
Cas d’usage
- Résolution de systèmes linéaires
- Inversion de matrices
- Algèbre linéaire numérique