La décomposition de Crout consiste à écrire une matrice carrée comme le produit d’une matrice triangulaire inférieure et d’une matrice triangulaire supérieure. Elle doit son nom au mathématicien américain Prescott Crout, qui l’a proposée dans les années 1940 pour accélérer la résolution des systèmes linéaires.
Introduction
Tu connais déjà la méthode du pivot de Gauss pour résoudre un système \(AX=B\). Son défaut est qu’il faut tout recommencer à chaque nouveau second membre \(B\). La décomposition de Crout fait le travail une fois pour toutes : une fois \(A\) factorisée, chaque système se ramène à deux systèmes triangulaires, très rapides à résoudre.
Cette notion est hors programme en prépa ECG. Elle peut toutefois apparaître dans un sujet de concours, notamment aux épreuves parisiennes ainsi qu’aux oraux de mathématiques. Elle peut ainsi apparaître dans un sujet sous la forme d’un algorithme Python à compléter, ou dans un problème guidé sur les matrices triangulaires.
Dans cet article, nous allons définir la décomposition de Crout, calculer ses coefficients, l’appliquer à un système, puis étudier son unicité et son existence.
Définition de la décomposition de Crout
Soit \(A\in M_n(\mathbb R)\). On appelle décomposition de Crout de \(A\) une écriture :
\[
A=LU
\]
où \(L\) est triangulaire inférieure et où \(U\) est triangulaire supérieure avec des coefficients diagonaux tous égaux à \(1\).
En taille \(3\), on cherche donc :
\[
A=
\begin{pmatrix}
l_{1,1}&0&0\\
l_{2,1}&l_{2,2}&0\\
l_{3,1}&l_{3,2}&l_{3,3}
\end{pmatrix}
\begin{pmatrix}
1&u_{1,2}&u_{1,3}\\
0&1&u_{2,3}\\
0&0&1
\end{pmatrix}
\]
Calcul des coefficients
Comme \(L\) est triangulaire inférieure et \(U\) triangulaire supérieure, le produit s’écrit :
\[
a_{i,j}=\sum_{k=1}^{\min(i,j)}l_{i,k}u_{k,j}
\]
Les colonnes de \(L\)
Pour \(i\geq j\), on a \(\min(i,j)=j\). Comme \(u_{j,j}=1\), le dernier terme de la somme vaut \(l_{i,j}\) :
\[
a_{i,j}=\sum_{k=1}^{j-1}l_{i,k}u_{k,j}+l_{i,j}
\]
Donc :
\[
l_{i,j}=a_{i,j}-\sum_{k=1}^{j-1}l_{i,k}u_{k,j}
\]
Les lignes de \(U\)
Pour \(i<j\), on a \(\min(i,j)=i\), et le dernier terme vaut \(l_{i,i}u_{i,j}\) :
\[
a_{i,j}=\sum_{k=1}^{i-1}l_{i,k}u_{k,j}+l_{i,i}u_{i,j}
\]
Donc, à condition que \(l_{i,i}\neq0\) :
\[
u_{i,j}=\displaystyle \frac{a_{i,j}-\displaystyle\sum_{k=1}^{i-1}l_{i,k}u_{k,j}}{l_{i,i}}
\]
On calcule alors successivement la première colonne de \(L\), la première ligne de \(U\), la deuxième colonne de \(L\), la deuxième ligne de \(U\), et ainsi de suite. Chaque formule n’utilise que des coefficients déjà connus.
Un exemple entièrement résolu
Considérons :
\[
A=
\begin{pmatrix}
2&4&-2\\
1&5&2\\
4&7&-3
\end{pmatrix}
\]
La première colonne de \(L\) est celle de \(A\) :
\[
l_{1,1}=2,\qquad l_{2,1}=1,\qquad l_{3,1}=4
\]
La première ligne de \(U\) s’obtient en divisant par \(l_{1,1}\) :
\[
u_{1,2}=\displaystyle \frac{4}{2}=2,\qquad u_{1,3}=\displaystyle \frac{-2}{2}=-1
\]
Deuxième colonne de \(L\) :
\[
l_{2,2}=5-1\times2=3,\qquad l_{3,2}=7-4\times2=-1
\]
Deuxième ligne de \(U\) :
\[
u_{2,3}=\displaystyle \frac{2-1\times(-1)}{3}=1
\]
Enfin :
\[
l_{3,3}=-3-4\times(-1)-(-1)\times1=2
\]
On obtient :
\[
L=
\begin{pmatrix}
2&0&0\\
1&3&0\\
4&-1&2
\end{pmatrix}
\qquad\text{et}\qquad
U=
\begin{pmatrix}
1&2&-1\\
0&1&1\\
0&0&1
\end{pmatrix}
\]
Tu peux vérifier en effectuant le produit \(LU\) que l’on retrouve bien \(A\).
Résoudre un système avec Crout
Le système \(AX=B\) s’écrit \(L(UX)=B\). On pose \(Y=UX\) et on résout successivement :
\[
LY=B
\qquad\text{puis}\qquad
UX=Y
\]
Le premier système se résout de haut en bas, le second de bas en haut.
Avec la matrice précédente et :
\[
B=
\begin{pmatrix}
0\\
3\\
1
\end{pmatrix}
\]
le système \(LY=B\) donne :
\[
2y_1=0,\qquad y_1+3y_2=3,\qquad 4y_1-y_2+2y_3=1
\]
donc \(y_1=0\), \(y_2=1\) et \(y_3=1\). Le système \(UX=Y\) donne ensuite :
\[
x_3=1,\qquad x_2+x_3=1,\qquad x_1+2x_2-x_3=0
\]
On obtient \(x_3=1\), \(x_2=0\) et \(x_1=1\). Pour un autre second membre, il suffit de refaire ces deux étapes, sans recalculer \(L\) ni \(U\).
Unicité de la décomposition
Supposons \(A\) inversible et :
\[
A=L_1U_1=L_2U_2
\]
Les matrices \(U_1\) et \(U_2\) sont inversibles, car triangulaires à diagonale non nulle. Ainsi \(L_1=AU_1^{-1}\) est inversible, et de même pour \(L_2\). On en déduit :
\[
L_2^{-1}L_1=U_2U_1^{-1}
\]
Le membre de gauche est triangulaire inférieur, comme produit de matrices triangulaires inférieures. Le membre de droite est triangulaire supérieur avec des \(1\) sur la diagonale.
Cette matrice est donc à la fois triangulaire inférieure et supérieure, c’est-à-dire diagonale, avec des \(1\) sur la diagonale :
\[
L_2^{-1}L_1=U_2U_1^{-1}=I_n
\]
Donc, \(L_1=L_2\) et \(U_1=U_2\) : la décomposition de Crout d’une matrice inversible est unique.
Attention : la décomposition n’existe pas toujours
Considérons la matrice inversible :
\[
A=
\begin{pmatrix}
0&1\\
1&0
\end{pmatrix}
\]
On obtient \(l_{1,1}=0\), puis il faudrait écrire \(1=l_{1,1}u_{1,2}=0\) : c’est impossible. Inversible ne suffit donc pas.
Notons \(A_k\) la sous-matrice formée des \(k\) premières lignes et \(k\) premières colonnes de \(A\). Comme les coefficients \(a_{i,j}\) avec \(i,j\leq k\) ne font intervenir que des indices inférieurs à \(k\), on a :
\[
A_k=L_kU_k
\]
Si \(A\) est inversible et admet une décomposition de Crout, \(L_k\) et \(U_k\) sont triangulaires à diagonale non nulle, donc \(A_k\) est inversible pour tout \(k\). On admet la réciproque : une matrice inversible admet une décomposition de Crout si et seulement si toutes ses sous-matrices \(A_k\) sont inversibles.
Dans l’exemple ci-dessus, \(A_1=(0)\) n’est pas inversible. Comme dans le pivot de Gauss, on contourne le problème en échangeant des lignes de \(A\) avant de la décomposer.
Cas remarquable : les matrices à diagonale dominante
Si \(A\) est strictement à diagonale dominante, chaque \(A_k\) l’est aussi : en supprimant des coefficients d’une ligne, on ne fait que diminuer la somme des valeurs absolues hors diagonale. Chaque \(A_k\) est donc inversible, et \(A\) admet une décomposition de Crout.
Par exemple :
\[
A=
\begin{pmatrix}
4&1\\
2&3
\end{pmatrix}
\]
donne \(l_{1,1}=4\), \(l_{2,1}=2\), puis :
\[
u_{1,2}=\displaystyle \frac{1}{4},\qquad l_{2,2}=3-2\times\displaystyle \frac{1}{4}=\displaystyle \frac{5}{2}
\]
Crout et le pivot de Gauss
La décomposition de Crout est très proche du pivot de Gauss. Lorsqu’on échelonne \(A\) sans échanger de lignes, on obtient une écriture \(A=L’U’\) où, cette fois, c’est \(L’\) qui a des \(1\) sur la diagonale : c’est la décomposition de Doolittle.
Si \(D\) est la matrice diagonale formée des coefficients diagonaux de \(U’\), supposés non nuls, alors :
\[
A=(L’D)(D^{-1}U’)
\]
et l’on retrouve la décomposition de Crout. Les deux méthodes diffèrent seulement par la matrice qui porte les \(1\) sur sa diagonale.
Comment utiliser la décomposition de Crout dans un exercice ?
Lorsqu’un énoncé demande de factoriser une matrice ou de résoudre plusieurs systèmes de même matrice, il est utile :
- d’écrire \(L\) et \(U\) avec des coefficients inconnus, en plaçant les \(1\) sur la diagonale de \(U\) ;
- de calculer alternativement une colonne de \(L\) et une ligne de \(U\) ;
- de vérifier qu’aucun \(l_{i,i}\) n’est nul, ou que les sous-matrices \(A_k\) sont inversibles ;
- de résoudre \(LY=B\) de haut en bas, puis \(UX=Y\) de bas en haut ;
- de contrôler le résultat en calculant le produit \(LU\).
Conclusion
La décomposition de Crout écrit une matrice sous la forme :
\[
A=LU
\]
avec \(L\) triangulaire inférieure et \(U\) triangulaire supérieure à diagonale unité. Elle est unique lorsque \(A\) est inversible, et existe dès que les sous-matrices \(A_k\) sont inversibles.
Son intérêt est surtout pratique : elle transforme un système quelconque en deux systèmes triangulaires et permet de réutiliser le même calcul pour plusieurs seconds membres. Retiens que c’est, au fond, le pivot de Gauss rangé dans deux matrices.
Tu peux retrouver le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder à toutes nos autres ressources mathématiques !
