AlgèbreMéthode · Glossaire
Crout (décomposition de)
L'algorithme de Crout et la décomposition de Crout sont deux aspects d'une même méthode de factorisation LU d'une matrice. La décomposition de Crout factorise une matrice A en produit LU, où L est triangulaire inférieure et U triangulaire supérieure à diagonale unité. L'algorithme calcule les coefficients de L et U colonne par colonne. Une fois la décomposition effectuée, la résolution d'un système linéaire Ax = b se ramène à deux substitutions triangulaires en O(n^2) opérations.
Sommaire
Ce que vous allez apprendre
- Identifier la convention de Crout parmi les factorisations LU.
- Calculer les coefficients de L et U colonne par colonne sur une matrice 3 × 3.
- Résoudre le système associé par deux substitutions triangulaires et contrôler le résultat.
- Reconnaître les pivots qui imposent un échange de lignes ou une méthode plus stable.
En clair
Imaginez une grille de nombres qui décrit plusieurs équations à résoudre ensemble. La méthode de Crout remplace cette grille par deux grilles plus simples : l'une ne conserve des nombres que sur et sous sa diagonale, l'autre sur et au-dessus.
Le produit des deux redonne exactement la grille initiale. Ce rangement permet ensuite de remonter vers la solution en deux parcours : d'abord de haut en bas, puis de bas en haut.
Définition
Pour une matrice carrée A d'ordre n, une décomposition de Crout est une factorisation A = LU. 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 et tous ses coefficients diagonaux valent 1. Cette convention distingue la forme de Crout parmi les factorisations LU.
L'algorithme remplit successivement une colonne de L, puis la ligne correspondante de U. Sans échange de lignes, chaque coefficient diagonal de L utilisé comme diviseur doit être non nul. Une condition suffisante classique est que tous les mineurs principaux dominants de A soient non nuls. Sous cette condition, les facteurs respectant la diagonale unité de U sont uniques.
Pour résoudre le système dont le second membre est le vecteur b, on calcule d'abord le vecteur intermédiaire y par Ly = b, puis le vecteur inconnu x par Ux = y. La factorisation coûte en général un nombre d'opérations proportionnel à n3. Une fois L et U disponibles, chaque nouveau second membre se traite par deux substitutions, en un nombre d'opérations proportionnel à n2.
Le principe
On note aij, lij et uij les coefficients de A, L et U. Pour chaque colonne d'indice j, de 1 à n, l'algorithme applique les deux calculs suivants :
Si le pivot ljj n'est pas nul, on pose ujj = 1 et l'on calcule la suite de la ligne de U :
Après la colonne n, le produit LU est égal à A.
Quand l'utiliser
La procédure directe s'applique à une matrice carrée dont les calculs sont effectués dans un corps, par exemple les nombres réels. À l'étape j, le pivot ljj doit être non nul, car il sert à calculer la ligne correspondante de U. Pour une matrice inversible, la non-nullité de tous les mineurs principaux dominants garantit que l'algorithme arrive au bout sans échange de lignes.
Être inversible ne suffit pas toujours à cette version. La matrice dont les lignes sont (0, 1) et (1, 0) est inversible, mais son premier pivot vaut 0. Il faut alors échanger des lignes et factoriser une matrice permutée, ce qui conduit usuellement à une relation de la forme PA = LU.
Un exemple, pas à pas
On veut résoudre Ax = b. La matrice A et le vecteur b sont les données suivantes :
1. Première colonne. On obtient l11 = 2, l21 = 4 et l31 = −2. La diagonale de U vaut 1, puis u12 = 1/2 et u13 = 1/2.
2. Deuxième colonne. Les calculs donnent l22 = −6 − 4 × 1/2 = −8 et l32 = 7 − (−2) × 1/2 = 8. On en déduit u23 = (0 − 4 × 1/2)/(−8) = 1/4.
3. Dernière colonne. Le dernier pivot vaut l33 = 2 − (−2) × 1/2 − 8 × 1/4 = 1. Les facteurs sont donc :
La figure matérialise le produit des deux facteurs et l'ordre des substitutions utilisées pour résoudre le système.
4. Substitution avant. Le système Ly = b donne successivement y1 = 3/2, y2 = 7/4 et y3 = −1.
5. Substitution arrière. Le système Ux = y donne x3 = −1, puis x2 = 2 et x1 = 1. Le contrôle direct fournit Ax = (3, −8, 10), exactement le vecteur b.
En pratique
Pour résoudre plusieurs systèmes qui partagent la même matrice A mais possèdent des seconds membres différents, on factorise A une seule fois. Chaque nouveau vecteur b ne demande ensuite que les deux substitutions triangulaires.
Dans un calcul numérique général, on surveille la taille des pivots. Si un pivot est nul ou très petit par rapport aux coefficients voisins, une factorisation avec pivot partiel est préférable afin d'échanger des lignes et de limiter l'amplification des erreurs d'arrondi.
Si la matrice réelle est symétrique définie positive, la décomposition de Cholesky exploite cette structure et demande moins de stockage et de calculs. La forme de Crout reste utile lorsque cette symétrie positive n'est pas disponible.
À ne pas confondre
Décomposition de Doolittle. C'est aussi une factorisation LU, mais la diagonale fixée à 1 est celle de L, et non celle de U. Dans l'exemple, voir des 1 sur toute la diagonale de U signale la convention de Crout.
Élimination de Gauss. Elle transforme le système jusqu'à obtenir une matrice triangulaire supérieure. La décomposition LU enregistre cette élimination dans deux facteurs réutilisables ; ce stockage devient décisif lorsque plusieurs seconds membres partagent A.
Décomposition de Cholesky. Elle écrit une matrice réelle symétrique définie positive comme le produit d'un facteur triangulaire et de sa transposée. La matrice de l'exemple n'est pas symétrique : Cholesky ne s'y applique donc pas, tandis que Crout aboutit.
Limites et pièges
Pivot exactement nul. Un pivot nul arrête la formule, même si la matrice est inversible. Pour la matrice dont les lignes sont (0, 1) et (1, 0), le premier pivot est 0 : on échange les deux lignes avant de poursuivre.
Pivot très petit en calcul approché. La division peut amplifier les erreurs d'arrondi sans être mathématiquement interdite. On emploie généralement un pivot partiel, choisi par comparaison des valeurs absolues dans la colonne, plutôt qu'un seuil universel indépendant de l'échelle des données.
Matrice singulière. La factorisation peut rencontrer un pivot nul et le système Ax = b n'a alors pas nécessairement une solution unique. Une méthode adaptée au rang, telle qu'une élimination avec pivotement, doit déterminer si le système est compatible et décrire ses solutions.
Coût mal interprété. Le coût proportionnel à n2 concerne les substitutions après factorisation. Construire L et U pour une matrice dense demande un nombre d'opérations proportionnel à n3 ; l'avantage est surtout visible quand les facteurs servent plusieurs fois.
Pour aller plus loin
Crout (algorithme de). Suivre la procédure de calcul colonne par colonne et relier chaque mise à jour aux coefficients des deux facteurs.
Factorisation. Replacer l'écriture LU parmi les décompositions qui transforment un objet algébrique en facteurs plus simples.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres