AlgèbreMéthode · Glossaire
Crout (algorithme 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é. À chaque étape, l'algorithme calcule une colonne de L, puis une ligne de U. 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 L et U puis résoudre un système par deux substitutions.
- Reconnaître un pivot bloquant et savoir quand employer un pivotement.
- Distinguer la méthode de Crout de la décomposition de Cholesky.
En clair
Imaginez une grande grille de nombres qui décrit plusieurs équations liées. La méthode de Crout remplace cette grille par deux grilles plus simples : l’une ne garde des nombres que sur et sous sa diagonale, l’autre sur et au-dessus. Dans la seconde, la diagonale ne contient que des 1.
Ce rangement transforme ensuite une résolution difficile en deux parcours faciles : on calcule les inconnues du haut vers le bas, puis du bas vers le haut. Le travail de factorisation peut aussi servir pour plusieurs seconds membres différents.
Définition
Soit A une matrice carrée d’ordre n. Une décomposition de Crout est une factorisation dans laquelle L est triangulaire inférieure et U triangulaire supérieure, avec des 1 sur toute la diagonale de U. Cette convention fixe la répartition des coefficients diagonaux entre les deux facteurs.
Sans échange de lignes, la factorisation existe et est unique lorsque tous les mineurs principaux en tête de A sont non nuls. De façon équivalente, chaque coefficient diagonal de L produit pendant le calcul doit être non nul. Si cette condition échoue, un pivotement peut conduire à une factorisation d’une matrice dont les lignes ont été permutées, et non nécessairement à A = LU dans l’ordre initial.
La construction coûte un nombre d’opérations de l’ordre de n3. Une fois L et U connus, résoudre Ax = b revient à résoudre successivement Ly = b puis Ux = y ; ces deux substitutions coûtent chacune de l’ordre de n2.
Le principe
À l’étape j, les coefficients déjà calculés servent d’abord à former la colonne j de L, puis la ligne j de U. Pour les indices i allant de j à n :
Après avoir vérifié que le pivot ljj n’est pas nul, on pose ujj = 1 et, pour i strictement supérieur à j :
Le calcul s’arrête après j = n : le produit des deux facteurs doit alors redonner A.
Quand l'utiliser
La méthode directe s’applique à une matrice carrée A. Elle demande que chaque pivot ljj obtenu soit non nul ; cette vérification équivaut à demander que les mineurs principaux en tête, d’ordres 1 à n, soient non nuls. Dans ce cadre, L et U sont déterminés de manière unique par la convention ujj = 1.
Contre-cas concret : la matrice dont les lignes sont (0, 1) et (1, 0) est inversible, mais son premier pivot vaut 0. Le calcul de Crout sans échange de lignes se bloque dès la première étape. Il faut permuter les lignes et factoriser PA, où P représente cette permutation. En calcul numérique, on pivote aussi lorsqu’un pivot non nul est trop petit, afin de limiter l’amplification des erreurs d’arrondi.
Un exemple, pas à pas
On veut résoudre Ax = b avec la matrice A et le second membre b suivants :
1. Appliquons les récurrences colonne par colonne. Pour j = 1, on obtient l11 = 2, l21 = 4 et l31 = −2, puis u12 = 2 / 2 = 1 et u13 = −2 / 2 = −1. Pour j = 2, l22 = 7 − 4 × 1 = 3 et l32 = −1 − (−2) × 1 = 1, puis u23 = (2 − 4 × (−1)) / 3 = 2. Enfin, l33 = 5 − (−2) × (−1) − 1 × 2 = 1. On obtient ainsi les deux facteurs ; leur produit ligne par colonne permet de contrôler chaque coefficient de A.
2. La substitution avant dans Ly = b donne successivement y1 = 4, y2 = 0 et y3 = −1.
3. La substitution arrière dans Ux = y donne x3 = −1, puis x2 = 2 et x1 = 1. Ainsi, x = (1, 2, −1)T.
Le contrôle est refaisable directement : le produit Ax vaut bien (8, 16, −9)T, soit exactement b.
En pratique
Pour résoudre plusieurs systèmes ayant la même matrice A mais des seconds membres différents, on factorise A une seule fois. Chaque nouveau second membre ne demande ensuite que deux substitutions triangulaires.
Dans un calcul en virgule flottante, on surveille la taille des pivots. Si un pivot devient nul ou très petit par rapport aux coefficients de la colonne, une factorisation LU avec pivotement est préférable.
Lorsque A est symétrique définie positive, la méthode de Cholesky exploite cette structure et économise du stockage et des opérations. Pour une matrice générale, la forme de Crout reste une convention LU adaptée.
À ne pas confondre
La décomposition de Crout n’est pas la décomposition de Cholesky. Crout impose une diagonale unité à U et s’adresse à une matrice carrée sous les conditions de pivot requises ; Cholesky impose des facteurs transposés et demande une matrice symétrique définie positive. Une matrice carrée non symétrique peut relever de Crout, jamais de Cholesky.
Elle ne se confond pas non plus avec l’élimination de Gauss, même si les calculs sont étroitement liés. Gauss transforme directement le système, tandis que les facteurs de Crout encodent les multiplicateurs et les pivots : les pivots sont les coefficients diagonaux de L, et chaque multiplicateur s’obtient en divisant le coefficient sous-diagonal correspondant de L par son pivot diagonal. Plusieurs seconds membres rendent cette différence immédiatement utile.
Limites et pièges
Un pivot nul ne prouve pas que A est singulière. Il signale seulement que l’ordre actuel des lignes ne permet pas de poursuivre la factorisation sans pivotement ; une permutation peut lever le blocage.
Un pivot très petit peut rendre les divisions numériquement fragiles, même s’il n’est pas exactement nul. Le symptôme est une forte croissance des coefficients ou un résidu Ax − b anormalement grand ; il faut alors employer un pivotement et contrôler le résidu.
Le coût en O(n2) concerne les substitutions après factorisation, pas la construction de L et U, qui est en O(n3) pour une matrice dense. Confondre ces deux étapes sous-estime le coût du premier système résolu.
La convention de Crout place les 1 sur la diagonale de U. D’autres présentations LU placent les 1 sur la diagonale de L : elles peuvent produire des facteurs différents tout en représentant la même matrice.
Pour aller plus loin
Mineur principal — Relier ces déterminants à l’existence d’une factorisation de Crout sans échange de lignes.
méthode de Cholesky — Voir la factorisation spécialisée qui exploite une matrice symétrique définie positive.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres