La première fois que j'ai du enseigner la décomposition LU, je ne l'avais pas étudié auparavant. J'ai donc du trouver des références pour comprendre de quoi il s'agissait. A mon grand étonnement, j'ai trouvé beaucoup d'exemples du fonctionnement de l'algorithme de la décomposition mais aucune explication simple du pourquoi ça marche. Evidemment on trouve de jolies récurrences effectuées par des profs de prépas qui sont satisfaisantes pour un matheux, mais s'avèrent imbuvables pour un étudiant. J'ai donc du déconstruire ces preuves pour en faire quelque chose de lisible. C'est ce travail que je vous propose dans les lignes qui suivent.
Public : Ce tutoriel est lisible par toutes personnes connaissant l'algèbre matricielle ainsi que les techniques élémentaires d'éliminations de Gauss. Il conviendra tout particulièrement à celles et ceux qui ont appris l'algorithme de décomposition LU sans comprendre pourquoi cela fonctionne effectivement.
Soit $A$ une matrice carrée de taille $n$, on appelle décomposition $LU$ de $A$, le fait de pouvoir écrire $A=LU$, où $L$ désigne une matrice carrée de taille $n$, triangulaire inférieure, composée de $1$ sur la diagonale, et $U$ désigne une matrice carrée de taille $n$, triangulaire supérieure. C'est à dire, plus concrètement $$A=\begin{pmatrix} 1 & 0 & \dots & 0\\ * & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \vdots\\ * & \dots & \dots & 1 \end{pmatrix} \begin{pmatrix} * & * & \dots & *\\ 0 & * & \ddots & *\\ \vdots & \ddots & \ddots & \vdots\\ 0 & \dots & 0 & * \end{pmatrix}$$ où les * représente des coefficients à déterminer
Il faut savoir que la décomposition n'est pas toujours possible, nous n'aborderons pas les conditions d'existence dans ce tutoriel.
Commençons par faire quelques calculs matriciels simples. Considérons la matrice dite d'élimination suivante en dimension 3 $$E=\begin{pmatrix}1 & 0 & 0\\ a & 1 & 0\\ c & 0 & 1 \end{pmatrix}$$ et multiplions la à gauche par une matrice carrée quelconque $A$ de taille 3. On a : $$EA= \begin{pmatrix}1 & 0 & 0\\ a & 1 & 0\\ b & 0 & 1 \end{pmatrix} \begin{pmatrix}a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\end{pmatrix} =\begin{pmatrix}a_{11} & a_{12} & a_{13}\\ a_{21}+aa_{11} & a_{22}+aa_{12} & a_{23}+aa_{13}\\ a_{31}+ba_{11} & a_{32}+ba_{12} & a_{33}+ba_{13}\end{pmatrix}$$ En observant notre calcul final, nous voyons que la matrice d'élimination $E$ a pour effet
Si on recommence l'opération mais cette fois en dimension 4 et avec la matrice d'élimination suivante : $$E=\begin{pmatrix}1 & 0 & 0 & 0\\ a & 1 & 0 & 0\\ b & 0 & 1 & 0 \\ c & 0 & 0 & 1 \end{pmatrix}$$ on a $$EA= \begin{pmatrix}1 & 0 & 0 & 0\\ a & 1 & 0 & 0\\ b & 0 & 1 & 0 \\ c & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix}a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34}\\ a_{41} & a_{42} & a_{43} & a_{44}\end{pmatrix} =\begin{pmatrix}a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21}+aa_{11} & a_{22}+aa_{12} & a_{23}+aa_{13} & a_{24}+aa_{14}\\ a_{31}+ba_{11} & a_{32}+ba_{12} & a_{33}+ba_{13} & a_{34}+ba_{14}\\ a_{41}+ca_{11} & a_{42}+ca_{12} & a_{43}+ca_{13} & a_{44}+ca_{14}\end{pmatrix}$$ On observe donc que la multiplication à gauche par cette matrice
Exemple : Pour bien saisir le fonctionnement, effectuons une élimination de Gauss avec les matrices d'éliminations. Considérons la matrice suivante : $$A=\begin{pmatrix} 2 & 1 & 4\\ 4 & 3 & 1\\ 6 & 5 & 1 \end{pmatrix}$$ Pour faire une élimination de Gauss, nous voulons faire enlever à la deuxiéme ligne 2 fois la première, et enlever à la troisième ligne 3 fois la première. La matrice d'élimination qui fait se travail est $$E=\begin{pmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ -3 & 0 & 1 \end{pmatrix}$$ et le calcul de l'élimination de Gauss donne : $$EA=\begin{pmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ -3 & 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 & 4\\ 4 & 3 & 1\\ 6 & 5 & 1 \end{pmatrix}=\begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 2 & -11 \end{pmatrix} $$
Exemple généralisé : Considérons maintenant la matrice $$A=\begin{pmatrix} a & b & c\\ d & e & f\\ g & h & i \end{pmatrix}$$ où $a$ est un réel non nul. Alors pour faire une élimination de Gauss sur la première colonne, on observe que la matrice d'élimination qui fonctionne bien est $$E=\begin{pmatrix} 1 & 0 & 0\\ -d/a & 1 & 0\\ -g/a & 0 & 1 \end{pmatrix}$$ Ce dernier exemple nous montre donc qu'il est très simple de trouver la matrice d'élimination de Gauss sur la première colonne à partir des coefficients de $A$.
En guise d'application de ce dernier exemple, voici un petit exercice :
Exercice : Soit la matrice $$A=\begin{pmatrix} 3 & 2 & 1\\ 2 & 1 & 1\\ 6 & 2 & 2 \end{pmatrix}$$ Donner la matrice d'élimination de Gauss de la première colonne puis effectuer l'élimination.
On trouve pour la matrice d'élimination $$E=\begin{pmatrix} 1 & 0 & 0\\ -2/3 & 1 & 0\\ -2 & 0 & 1 \end{pmatrix}$$ et la matrice réduite de $A$ $$EA=\begin{pmatrix} 3 & 2 & 1\\ 0 & -1/3 & 1/3\\ 0 & -2 & 0 \end{pmatrix}$$
Exercice : Donner la matrice d'élimination associée à $$A=\begin{pmatrix} a & b & c & d\\ e & f & g & h\\ i & j & k & l\\ m & n & o & p \end{pmatrix}$$ où $a$ est un réel non nul.
On trouve $$E=\begin{pmatrix} 1 & 0 & 0 & 0\\ -e/a & 1 & 0 & 0\\ -i/a & 0 & 1 & 0\\ -m/a & 0 & 0 & 1 \end{pmatrix}$$
Nous avonc vu comment faire une élimination de Gauss sur la première colonne d'un matrice. Maintenant nous allons voir comment faire une élimination de Gauss de bout en bout matriciellement. Comme dans la section précédente commençons par des calculs préliminaires.
Considérons la matrice dite d'élimination suivante en dimension 3 $$E=\begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & a & 1 \end{pmatrix}$$ et multiplions la à gauche par une matrice carrée quelconque $A$ de taille 3. On a : $$EA= \begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & a & 1 \end{pmatrix} \begin{pmatrix}a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\end{pmatrix} =\begin{pmatrix}a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31}+aa_{21} & a_{32}+aa_{22} & a_{33}+aa_{23}\end{pmatrix}$$ On observe donc que la multiplication par $E$ à gauche a pour effet d'ajouter à la troisième ligne $a$ fois la deuxième.
Poursuivons maintenant en dimension 4 et considérons $$E=\begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & a & 1 & 0 \\ 0 & b & 0 & 1 \end{pmatrix}$$ et faisont le calcul suivant : $$EA= \begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & a & 1 & 0 \\ 0 & b & 0 & 1 \end{pmatrix} \begin{pmatrix}a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34}\\ a_{41} & a_{42} & a_{43} & a_{44}\end{pmatrix} =\begin{pmatrix}a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31}+aa_{21} & a_{32}+aa_{22} & a_{33}+aa_{23} & a_{34}+aa_{24}\\ a_{41}+ba_{21} & a_{42}+ba_{22} & a_{43}+ba_{23} & a_{44}+ba_{24}\end{pmatrix}$$ Donc si l'on résume, la matrice $E$ a pour effet :
On peut encore refaire le travail avec des matrices qui ont une forme semblable.
Exercice : Décrire l'effet de la matrice $$E=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \\ 0 & 0 & a & 1 \end{pmatrix}$$ sur une matrice carrée de taille 4.
La matrice ajoute à la quatrième ligne $a$ fois la seconde.
En guise d'application, effectuons une élimination de Gauss à l'aide des matrices d'éliminations.
Exemple : Soit la matrice : $$A=\begin{pmatrix} 2 & 2 & 1 & 2\\ 4 & 2 & 1 & 3\\ 6 & 1 & 4 & 2\\ -2 & 2 & 2 & 1 \end{pmatrix}$$ Pour éliminer la première colonne, il nous faut la matrice : $$E_1=\begin{pmatrix} 1 & 0 & 0 & 0\\ -2 & 1 & 0 & 0\\ -3 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 \end{pmatrix}$$ on a alors : $$E_1A=\begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & -5 & 1 & -4\\ 0 & 4 & 3 & 3 \end{pmatrix}$$ Pour élmininer maintenant sur la seconde colonne, on a besoin de $$E_2=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & -5/2 & 1 & 0\\ 0 & 2 & 0 & 1 \end{pmatrix}$$ et donc $$E_2E_1A=\begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & 0 & 7/2 & -3/2\\ 0 & 0 & 1 & 1 \end{pmatrix}$$ Enfin pour finir d'éliminer sur la troisième colonne, on a besoin de $$E_3=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & -2/7 & 1 \end{pmatrix}$$ et le résultat final est $$E_3E_2E_1A=\begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & 0 & 7/2 & -3/2\\ 0 & 0 & 0 & 10/7 \end{pmatrix}$$
Ce dernier exemple nous montre que comme pour l'élimination sur une première colonne, la matrice d'élimination sur d'autres colonne est facile à déterminer. Prenons la situation abstraite suivante :
Exemple : La matrice d'alimination associée à la matrice $$A=\begin{pmatrix} a & b & c & d\\ 0 & e & f & g\\ 0 & h & i & j\\ 0 & k & l & m \end{pmatrix}$$ avec $e$ non nul, est $$E=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & -h/e & 1 & 0\\ 0 & -k/e & 0 & 1 \end{pmatrix}$$
En guise d'exercice je vous laisse formaliser vous-même la règle correspondante dans le cas d'une élimination sur une colonne quelconque pour des matrices de taille $n$!
Dans les deux sous sections précédentes nous avons fait connaissance avec les matrices d'éliminations. Nous avons appris à les construire et à nous en servir pour effectuer une élimination du type Gauss sur une matrice. Pour bien saisir le fonctionnement de la décomposition LU, nous devons maintenant apprendre à inverser et multiplier ces matrices déliminations. La grande force de la décomposition LU réside dans la simplicité de ces deux opérations. Regardons un peu.
Rappelons qu'une matrice d'élimination a pour effet d'ajouter à une ligne un multiple d'une autre ligne. Imaginons que nous ayons ajouté à la ligne 3, 10 fois la ligne 2, c'est à dire $$L3\longrightarrow L3+10L2$$ puis supposons que nous nous sommes trompés et que nous voulons faire l'opération à l'envers. Il faudra donc ajouter -10 fois la ligne 2 à notre opération précédente, c'est à dire $$L3\longrightarrow L3+10L2\longrightarrow L3+10L2-10L2=L3$$ et nous sommes revenu au point de départ.
Examinons cela matriciellement. Considérons la matrice d'élimination $$\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 10 & 0 \end{pmatrix}$$ Cette matrice fait l'opération de tout à l'heure et son inverse devrait donc être $$\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -10 & 0 \end{pmatrix}$$ Et en effet, si on fait le calcul $$\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 10 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -10 & 0 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{pmatrix}=Id$$ Avec un raisonnement analogue, on montre que la matrice inverse de $$\begin{pmatrix} 1 & 0 & 0\\ a & 1 & 0\\ b & 0 & 0 \end{pmatrix}$$ est en fait $$\begin{pmatrix} 1 & 0 & 0\\ -a & 1 & 0\\ -b & 0 & 0 \end{pmatrix}$$ Et en effet un petit calcul nous donne que $$\begin{pmatrix} 1 & 0 & 0\\ a & 1 & 0\\ b & 0 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\ -a & 1 & 0\\ -b & 0 & 0 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{pmatrix}=Id$$
Commençons par un petit calcul simple. Multiplions entre elles les deux matrices d'éliminations suivantes : $$E_1=\begin{pmatrix} 1 & 0 & 0\\ a & 1 & 0\\ b & 0 & 1 \end{pmatrix}\text{ et } E_2=\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & c & 1 \end{pmatrix}$$ On trouve alors que $$E_1E_2=\begin{pmatrix} 1 & 0 & 0\\ a & 1 & 0\\ b & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & c & 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0\\ a & 1 & 0\\ b & c & 1 \end{pmatrix}$$Tout se passe comme ci les deux matrices fusionnaient.
Recommençons maintenant avec trois matrices d'élimination en dimension 4 $$\begin{pmatrix} 1 & 0 & 0 & 0\\ a & 1 & 0 & 0\\ b & 0 & 1 & 0\\ c & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & d & 1 & 0\\ 0 & e & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & f & 1 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 & 0\\ a & 1 & 0 & 0\\ b & d & 1 & 0\\ c & e & f & 1 \end{pmatrix}$$ et là encore ça fusionne.
Je vous fait grâce d'une démonstration laborieuse et inutile. Ce qui m'importe c'est en fait cette règle générale à retenir :
Voilà, nous en avons fini avec les calculs préliminaires et nous allons pouvoir entrer dans le vif du sujet : l'algorithme de la décomposition LU.
Comme à notre habitude, nous allons partir d'un exemple. Prenons la matrice suivante : $$A=\begin{pmatrix} 2 & 1 & 4\\ 4 & 3 & 1\\ 6 & 5 & 1 \end{pmatrix}$$ La matrice d'éilimination de la première colonne est $$E_1=\begin{pmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ -3 & 0 & 1 \end{pmatrix}$$ et l'élimination conduit à $$E_1A=\begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 2 & -11 \end{pmatrix} $$ puis effectuons l'élimination sur la deuxième colonne. La matrice d'élimination est $$E_2=\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -2 & 1 \end{pmatrix}$$ et l'élimination donne $$E_2E_1A=\begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 0 & 3 \end{pmatrix}$$
Repartons maintenant de cette dernière équation, on observe alors que $$A=E_2^{-1}E_1^{-1}\begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 0 & 3 \end{pmatrix}$$ Or nous avons vu dans la section précédente comment inverser facilement des matrices d'éliminations. En appliquant cette règle on a alors $$A=\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 0 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 0 & 3 \end{pmatrix}$$ mais nous avons également vu comment multiplier des matrices d'éliminations, on obtient alors $$A=\begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 2 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 0 & 3 \end{pmatrix}$$ Nous venons finalement d'obtenir la décomposition LU de la matrice $A$, la matrice $L$ étant $$L=\begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 2 & 1 \end{pmatrix}$$ tandis que la matrice $U$ est $$U=\begin{pmatrix} 2 & 1 & 4\\ 0 & 1 & -7\\ 0 & 0 & 3 \end{pmatrix}$$
Pour bien entériner le processus, revisitons un exemple que nous avons déjà commencé à faire. Nous avions vu que la matrice $$A=\begin{pmatrix} 2 & 2 & 1 & 2\\ 4 & 2 & 1 & 3\\ 6 & 1 & 4 & 2\\ -2 & 2 & 2 & 1 \end{pmatrix}$$ avait pour réduite de Gauss $$E_3E_2E_1A=\begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & 0 & 7/2 & -3/2\\ 0 & 0 & 0 & 10/7 \end{pmatrix}$$ où $$E_1=\begin{pmatrix} 1 & 0 & 0 & 0\\ -2 & 1 & 0 & 0\\ -3 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 \end{pmatrix}\text{ et }E_2=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & -5/2 & 1 & 0\\ 0 & 2 & 0 & 1 \end{pmatrix} \text{ et } E_3=\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & -2/7 & 1 \end{pmatrix}$$ Il suit alors en utilisant les techniques d'inversion et de multiplication de matrices de réductions que $$A=E_1^{-1}E_2^{-1}E_3^{-1}\begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & 0 & 7/2 & -3/2\\ 0 & 0 & 0 & 10/7 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 & 0\\ 2 & 1 & 0 & 0\\ 3 & 5/2 & 1 & 0\\ -1 & -2 & 2/7 & 1 \end{pmatrix} \begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & 0 & 7/2 & -3/2\\ 0 & 0 & 0 & 10/7 \end{pmatrix}$$ Nous avons donc $$L=\begin{pmatrix} 1 & 0 & 0 & 0\\ 2 & 1 & 0 & 0\\ 3 & 5/2 & 1 & 0\\ -1 & -2 & 2/7 & 1 \end{pmatrix}\text{ et }U=\begin{pmatrix} 2 & 2 & 1 & 2\\ 0 & -2 & -1 & -1\\ 0 & 0 & 7/2 & -3/2\\ 0 & 0 & 0 & 10/7 \end{pmatrix}$$
Si on fait la synthèse de ces deux exemples, on observe les deux points importants suivants :
Quand on a bien compris cela, on observe que les calculs intermédiaires d'expression des matrices d'éliminations sont inutiles. Il suffit de noter au fur et à mesure les calculs faits dans la matrice $L$. Donnons un exemple pour expliquer ceci.
Exemple concret de fonctionnement de l'algorithme : Considérons la matrice $$A=\begin{pmatrix} 3 & 2 & 2\\ 3 & 3 & 1\\ -6 & 3 & 3 \end{pmatrix}$$ On commence par se munir d'une matrice $L$ "vierge" qui va se remplir au fur et à mesure de nos éliminations, c'est à dire $$L=\begin{pmatrix} 1 & 0 & 0\\ & 1 & 0\\ & & 1 \end{pmatrix}$$
Etape 1 : On commence par éliminer la première colonne. Il faut donc faire ligne 2 moins une fois ligne 1, et ligne 2 plus deux fois ligne 1. N'oublions pas que contrèrement à la matrice d'élimination, $L$ doit contenir l'opposé du coefficient d'élimination. On a donc pour $L$ : $$L=\begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ -2 & & 1 \end{pmatrix}$$ Puis on fait l'élimination correspondante dans la matrice $A$ ce qui nous conduit à une matrice que nous noterons $A^{(1)}$ $$A^{(1)}=\begin{pmatrix} 3 & 2 & 2\\ 0 & 1 & -1\\ 0 & 7 & 7 \end{pmatrix}$$
Etape 2 : On élimine sur la deuxième colonne de $A^{(1)}$ en enlevant 7 fois la ligne 2 à la ligne 3. La matrice $L$ devient : $$L=\begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ -2 & 7 & 1 \end{pmatrix}$$ tandis que la matrice $A^{(1)}$ après élimination nous donne la fameuse matrice $U$ recherchée : $$U=\begin{pmatrix} 3 & 2 & 2\\ 0 & 1 & -1\\ 0 & 0 & 14 \end{pmatrix}$$
La décomposition $LU$ de $A$ est donc $$A=\begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ -2 & 7 & 1 \end{pmatrix}\begin{pmatrix} 3 & 2 & 2\\ 0 & 1 & -1\\ 0 & 0 & 14 \end{pmatrix}$$
Passons maintenant à l'algorithme général. Considérons une matrice $$A=\begin{pmatrix} a_{11} & \dots & a_{1n}\\ \vdots & \vdots & \vdots\\ a_{n1} & \dots & a_{nn} \end{pmatrix}$$ et une matrice d'élimination vierge qui représentera la matrice $L$ à la fin des opérations : $$L=\begin{pmatrix} 1 & 0 & \dots & \dots & 0\\ & 1 & \ddots & \dots & 0\\ & & \ddots & \ddots & \vdots\\ & & & \ddots & 0\\ & & & & 1 \end{pmatrix}$$
Etape 1 : On commence par remplir la première colonne de $L$ par les coefficients d'éliminations sans le signe moins, ce qui nous donne : $$L=\begin{pmatrix} 1 & 0 & \dots & \dots & 0\\ a_{21}/a_{11} & 1 & \ddots & \dots & 0\\ a_{31}/a_{11} & & \ddots & \ddots & \vdots\\ \vdots & & & \ddots & 0\\ a_{n1}/a_{11} & & & & 1 \end{pmatrix}$$ puis on fait les éliminations correspondantes sur la $A$, ce qui nous donne une nouvelle matrice notée $A^{(1)}$ qui a pour forme : $$A^{(1)}=\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n}\\ 0 & a^{(1)}_{22} & \dots & a^{(1)}_{1n}\\ \vdots & \vdots & \dots & \vdots\\ 0 & a^{(1)}_{n2} & \dots & a^{(1)}_{nn}\\ \end{pmatrix}$$
Etape 2 : On poursuit le remplissage de $L$ à l'aide de $A^{(1)}$ $$L=\begin{pmatrix} 1 & 0 & \dots & \dots & 0\\ a_{21}/a_{11} & 1 & \ddots & \dots & 0\\ a_{31}/a_{11} & a^{(1)}_{23}/a^{(1)}_{22} & \ddots & \ddots & \vdots\\ \vdots & \vdots & & \ddots & 0\\ a_{n1}/a_{11} &a^{(1)}_{n3}/a^{(1)}_{22} & & & 1 \end{pmatrix}$$ puis on fait les éliminations correspondantes sur la matrice $A^{(1)}$, on obtient alors une matrice $A^{(2)}$ : $$A^{(2)}=\begin{pmatrix} a_{11} & a_{12} & a_{13} & \dots & a_{1n}\\ 0 & a^{(1)}_{22} & a^{(1)}_{22} & \dots & a^{(1)}_{1n}\\ 0 & 0 & a^{(2)}_{33} & \dots & a^{(2)}_{1n}\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & a^{(2)}_{n2} & \dots & a^{(2)}_{nn}\\ \end{pmatrix}$$
On réitère ainsi de suite jusqu'à l'étape $n-1$. La matrice $A^{(n-1)}$ obtenue au final est alors notre matrice $U$.
Comme nous l'avons vu, la décomposition LU, n'est qu'une forme organisée de la simplification de Gauss. La matrice $U$ n'est autre que la simplifiée de Gauss de la matrice $A$ et la matrice $L$ rassemble en quelque sorte les manipulations qui ont été effectuées pour obtenir la matrice $U$. On notera qu'il n'est pas toujours possible de faire fonctionner l'algorithme que nous avons donné. C'est le cas par exemple de $$A=\begin{pmatrix}0 & 1\\ 1& 1\end{pmatrix}$$ car le $0$ en haut à gauche ne peut être utilisé comme pivot. Malgré tout, la décomposition devient possible en permutant les deux lignes de la matrice $A$. Dans ce cas on peux faire ce que l'on appelle une décomposition $PLU$, où $P$ désigne une matrice de permutation associée à la permutation des deux lignes de $A$.
Notons enfin que la décomposition s'effectue en un temps polynomial. Elle peut donc s'avérer plus efficace que la méthode de Cramer en grande dimension pour la résolution de systèmes ou l'inversion de matrice.
Contacter l'auteur du site : frederic.millet @ math-sup.fr
