Decomposition LU
Decomposez une matrice carree en produit LU (Lower × Upper). Utile pour resoudre plusieurs systemes avec la meme matrice.
Matrice A
Décomposition LU : factorisation matricielle pour l'algèbre linéaire numérique
Pourquoi utiliser la décomposition LU ?
La décomposition LU est l'une des techniques fondamentales de l'algèbre linéaire numérique. Elle consiste à factoriser une matrice carrée A en un produit de deux matrices triangulaires : une matrice triangulaire inférieure L (Lower) et une matrice triangulaire supérieure U (Upper), telles que A = LU. Cette représentation simplifie considérablement la résolution de systèmes d'équations linéaires, car les matrices triangulaires se traitent de façon bien plus efficace que les matrices générales.
L'un des principaux avantages de la factorisation LU réside dans sa capacité à réutiliser le travail de décomposition. Lorsqu'il faut résoudre plusieurs systèmes linéaires Ax = b₁, Ax = b₂, … avec la même matrice A mais des seconds membres différents, la décomposition LU ne doit être calculée qu'une seule fois. Chaque nouveau système se résout alors par simple substitution avant (forward substitution) dans L, puis substitution arrière (backward substitution) dans U, réduisant drastiquement le coût de calcul total.
Par rapport à la méthode d'élimination de Gauss classique, la décomposition LU offre une approche modulaire et réutilisable. Elle est également à la base du calcul du déterminant d'une matrice (produit des pivots de U) et de l'inversion matricielle. Les bibliothèques numériques professionnelles telles que LAPACK, NumPy ou MATLAB utilisent des variantes optimisées de cette factorisation, souvent avec pivotage partiel ou complet, pour garantir stabilité numérique et précision des résultats.
Cas d'utilisation courants
- Résolution de systèmes linéaires multiples
- En ingénierie structurelle ou en simulation physique, il est fréquent de devoir résoudre le même système Ax = b pour de nombreux vecteurs b distincts représentant différentes conditions de chargement ou de frontière. La décomposition LU permet de factoriser A une seule fois, puis de résoudre chaque instance en O(n²) au lieu de O(n³), ce qui représente un gain majeur dès que le nombre de second membres est élevé.
- Calcul du déterminant et inversion de matrice
- Le déterminant d'une matrice A se déduit immédiatement de la factorisation LU : il est égal au produit des éléments diagonaux de U (multiplié par le signe induit par les permutations de pivotage). De même, l'inversion d'une matrice dense se ramène à la résolution de n systèmes linéaires avec la base canonique, rendant la décomposition LU indispensable pour ces calculs en analyse numérique.
- Éléments finis et méthodes numériques
- Les simulations par éléments finis (FEM) en mécanique, thermique ou électromagnétisme génèrent de grands systèmes linéaires creux. La factorisation LU, appliquée aux blocs denses ou utilisée comme préconditionneur, accélère la convergence des solveurs itératifs. Elle constitue aussi la brique de base des décompositions de Cholesky (pour les matrices symétriques définies positives) et LDLᵀ, largement utilisées en optimisation.
- Traitement du signal et économétrie
- En économétrie et en analyse statistique multivariée, la résolution de systèmes normaux (XᵀX)β = Xᵀy dans la régression linéaire multiple fait appel à la factorisation LU ou à ses dérivées. En traitement du signal, les filtres adaptatifs et la déconvolution matricielle reposent également sur des résolutions de systèmes linéaires répétées, pour lesquelles la décomposition LU est une solution performante et numériquement stable.
Comment fonctionne la décomposition LU ?
Saisie et validation de la matrice : l'utilisateur entre une matrice carrée n × n. L'outil vérifie que la matrice est inversible (déterminant non nul) et, si nécessaire, applique un pivotage partiel par lignes afin d'assurer la stabilité numérique du processus. La matrice de permutation P associée est enregistrée pour que la relation PA = LU soit bien vérifiée.
Élimination de Gauss et construction de L et U : l'algorithme effectue une élimination gaussienne progressive. À chaque étape k, les coefficients d'élimination mᵢₖ = aᵢₖ / aₖₖ sont calculés et stockés dans la matrice L sous la diagonale, tandis que les opérations de ligne correspondantes transforment la partie supérieure de la matrice en la matrice triangulaire supérieure U. La diagonale de L est fixée à 1 (forme de Doolittle).
Affichage des résultats et résolution : l'outil présente les matrices L, U et P de façon claire, avec les valeurs numériques arrondies pour la lisibilité. Si un vecteur second membre b est fourni, la solution x est calculée en deux passes : substitution avant Ly = Pb pour trouver y, puis substitution arrière Ux = y pour obtenir x. Le résidu ‖Ax − b‖ est affiché pour vérifier la précision du résultat.
Questions fréquentes
- Quelle est la différence entre la décomposition LU et l'élimination de Gauss ?
- L'élimination de Gauss est un algorithme qui transforme un système Ax = b en un système triangulaire supérieur en une seule passe, liant la décomposition à un second membre particulier. La décomposition LU, quant à elle, factorise uniquement la matrice A en L et U, indépendamment de tout second membre. Cette séparation permet de réutiliser la factorisation pour résoudre de multiples systèmes avec des seconds membres différents, ce qui rend la décomposition LU bien plus flexible et économique dans les applications pratiques.
- Pourquoi le pivotage partiel est-il important dans la décomposition LU ?
- Sans pivotage, la décomposition LU peut être numériquement instable : si un élément pivot est nul ou très petit, les divisions produisent des erreurs d'arrondi amplifiées qui faussent le résultat. Le pivotage partiel consiste à réordonner les lignes de façon à toujours utiliser le plus grand élément disponible comme pivot, minimisant ainsi la propagation des erreurs. La relation devient alors PA = LU, où P est la matrice de permutation des lignes. La quasi-totalité des implémentations professionnelles intègrent ce pivotage par défaut.
- La décomposition LU fonctionne-t-elle pour toutes les matrices carrées ?
- La décomposition LU sans pivotage existe si et seulement si tous les mineurs principaux de la matrice sont non nuls. Avec pivotage partiel, toute matrice carrée inversible admet une décomposition PA = LU. En revanche, une matrice singulière (de déterminant nul) ne peut pas être inversée et les systèmes linéaires associés n'ont pas de solution unique. Dans ce cas, l'outil signale la singularité et propose des informations sur le rang de la matrice.
- Quelle est la complexité algorithmique de la décomposition LU ?
- La décomposition LU d'une matrice n × n requiert environ 2n³/3 opérations flottantes, soit une complexité en O(n³). Une fois la factorisation effectuée, la résolution d'un système Ax = b par substitutions avant et arrière ne coûte que O(n²). Ce rapport explique l'intérêt de la méthode lorsqu'on résout k systèmes avec la même matrice : le coût total est O(n³ + kn²) au lieu de O(kn³) pour k éliminations de Gauss indépendantes, une différence decisive pour k grand.
- Mes données personnelles sont-elles protégées ?
- Entièrement. Le calcul est réalisé à 100 % côté client, directement dans votre navigateur web. Aucune donnée personnelle n'est envoyée vers un serveur distant ni stockée. Toutes les informations restent sur votre appareil.