AlgèbreMéthode · Glossaire
LU (décomposition)
La décomposition LU est une factorisation d'une matrice carrée A en un produit d'une matrice triangulaire inférieure L (Lower) et d'une matrice triangulaire supérieure U (Upper). Lorsqu'elle existe, elle permet de résoudre efficacement des systèmes linéaires de la forme Ax = b en deux étapes de substitution. La décomposition LU est essentiellement la reformulation matricielle de l'élimination de Gauss. Une variante courante inclut une matrice de permutation P pour assurer la stabilité numérique, donnant la décomposition PLU.
Sommaire
Ce que vous allez apprendre
- Identifier le rôle des matrices triangulaires L et U.
- Construire une factorisation LU sur une matrice 2 × 2 et vérifier son produit.
- Résoudre Ax = b par substitution avant puis arrière.
- Repérer un pivot nul ou fragile et savoir quand employer la variante PLU.
En clair
Vous devez résoudre plusieurs systèmes qui ont le même tableau de coefficients, mais des seconds membres différents. Refaire toute l’élimination à chaque fois serait inutile. La décomposition LU prépare une fois ce tableau sous la forme de deux matrices plus simples.
La première, triangulaire inférieure, ne garde des nombres que sur et sous sa diagonale. La seconde, triangulaire supérieure, en garde sur et au-dessus. Résoudre le système revient alors à avancer ligne après ligne dans la première, puis à remonter dans la seconde.
Définition
Une matrice carrée A admet une décomposition LU lorsqu’elle peut s’écrire comme le produit . La matrice L est triangulaire inférieure : ses coefficients situés au-dessus de la diagonale sont nuls. La matrice U est triangulaire supérieure : ses coefficients situés sous la diagonale sont nuls. Dans la convention la plus courante, les coefficients diagonaux de L valent 1.
L’élimination de Gauss transforme A en U. Les multiplicateurs utilisés pour annuler les coefficients sous chaque pivot sont conservés dans L. Pour résoudre un système dont le second membre est le vecteur b et l’inconnue le vecteur x, on introduit un vecteur intermédiaire y. On résout d’abord par substitution avant, puis par substitution arrière.
Sans échange de lignes, chaque pivot rencontré doit être non nul. Pour une matrice inversible, une permutation des lignes permet d’écrire , où P est une matrice de permutation. Selon la convention adoptée, la même idée peut être notée A = PLU ; la place de P doit donc toujours être vérifiée.
Le principe
Soient une matrice carrée A, un second membre b et le vecteur inconnu x. 1. Éliminer les coefficients sous les pivots et conserver les multiplicateurs afin d’obtenir . 2. Résoudre de la première ligne à la dernière. 3. Résoudre de la dernière ligne à la première. 4. S’arrêter lorsque toutes les composantes de x sont déterminées, puis contrôler que Ax = b. Si un pivot est nul, permuter des lignes et employer la variante ; à l’étape 2, résoudre alors .
Quand l'utiliser
La méthode s’applique à une matrice carrée A et à un second membre b de dimension compatible. La factorisation sans permutation avance si chacun des pivots successifs est non nul. Pour une matrice inversible, un critère vérifiable qui garantit cette situation est que tous les mineurs principaux situés en haut à gauche soient non nuls. Les coefficients diagonaux de U sont alors non nuls, ce qui rend la substitution arrière possible et la solution unique.
La matrice fournit un contre-cas concret : le premier pivot vaut 0, alors que A est inversible. La factorisation LU directe se bloque dès la première colonne. Il faut échanger les deux lignes, enregistrer cet échange dans P et utiliser .
Un exemple, pas à pas
On cherche le vecteur x qui vérifie Ax = b. Les données sont la matrice A et le second membre b :
Les deux pivots utilisés seront 2 puis 1 ; aucun échange de lignes n’est nécessaire.
1. Factoriser A. Pour annuler 4 sous le premier pivot 2, le multiplicateur vaut 4/2 = 2. Il prend place sous la diagonale de L :
Le produit L × U redonne exactement A.
2. Descendre dans L. On résout Ly = b. La première ligne donne y1 = 5. La seconde donne 2y1 + y2 = 11, donc y2 = 11 − 2 × 5 = 1.
3. Remonter dans U. On résout Ux = y. La seconde ligne donne x2 = 1. La première donne 2x1 + x2 = 5, donc x1 = (5 − 1)/2 = 2.
La solution est le vecteur de composantes (2 ; 1). Le contrôle se refait avec le système initial : 2 × 2 + 1 = 5 et 4 × 2 + 3 × 1 = 11. Les deux lignes de Ax = b sont vérifiées.
En pratique
Quand plusieurs systèmes partagent la même matrice A, on factorise A une seule fois, puis on recommence seulement les deux substitutions pour chaque nouveau second membre. Pour un unique petit système, une élimination de Gauss menée directement peut suffire ; LU devient surtout utile lorsque les facteurs doivent être réutilisés.
Dans un calcul numérique, on surveille la taille du pivot avant chaque division. Un pivot nul bloque l’élimination et un pivot très petit peut amplifier les erreurs d’arrondi. On préfère alors PLU : une permutation place un coefficient mieux adapté au rôle de pivot.
Après le calcul, on contrôle les deux niveaux. Le produit LU doit redonner A, ou PA si des lignes ont été permutées. Puis le vecteur obtenu doit satisfaire Ax = b. Ce double contrôle distingue une erreur de factorisation d’une erreur de substitution.
À ne pas confondre
Décomposition LU et élimination de Gauss. L’élimination est la suite d’opérations qui annule les coefficients sous les pivots. La décomposition LU est la forme matricielle qui en conserve le résultat : U contient la matrice triangulaire obtenue et L les multiplicateurs. Avec un seul second membre, les deux calculs suivent les mêmes étapes ; avec plusieurs seconds membres, la présence de L et U permet de réutiliser le travail déjà fait.
Limites et pièges
Pivot exactement nul. La factorisation sans permutation s’arrête, même si la matrice est inversible. Le symptôme est une division par 0 au cours de l’élimination. Il faut permuter les lignes et enregistrer l’opération dans P.
Pivot très petit. En calcul approché, la division produit de grands multiplicateurs et peut amplifier les erreurs d’arrondi. Aucun seuil universel ne sépare « petit » et « acceptable » : l’échelle des coefficients compte. Le pivotement de la variante PLU réduit ce risque.
Matrice singulière. Une factorisation peut parfois exister, mais un coefficient diagonal nul dans U empêche la substitution arrière d’isoler toutes les inconnues. Le système n’a alors pas de solution unique ; il faut examiner sa compatibilité plutôt que poursuivre les divisions.
Place de la permutation. Les notations PA = LU et A = PLU peuvent refléter des conventions différentes pour P. Recopier une formule sans contrôler cette convention permute les mauvaises lignes. Le bon réflexe est de multiplier les facteurs et de vérifier quelle matrice, A ou PA, est effectivement obtenue.
Pour aller plus loin
La méthode de Cramer présente une autre résolution exacte des systèmes carrés et permet de comparer ses conditions à celles de LU.
L’article Tradition et innovation algébriques en Corée replace des procédés d’élimination dans une perspective historique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres