Décomposition LU

En algèbre linéaire, la décomposition LU est une méthode de décomposition d'une matrice comme produit d'une matrice triangulaire inférieure Modèle:Formule (comme Modèle:Lang, inférieure en anglais) par une matrice triangulaire supérieure Modèle:Formule (comme Modèle:Lang, supérieure). Cette décomposition est utilisée en analyse numérique pour résoudre des systèmes d'équations linéaires.

Définition

Soit Modèle:Formule une matrice carrée. On dit que Modèle:Formule admet une décomposition LU s'il existe une matrice triangulaire inférieure formée de 1 sur la diagonale, notée Modèle:Formule, et une matrice triangulaire supérieure, notée Modèle:Formule, qui vérifient l'égalité

$A=LU\;$

Il n'est pas toujours vrai qu'une matrice Modèle:Formule admette une décomposition LU. Cependant dans certains cas, en permutant des lignes de Modèle:Formule, la décomposition devient possible. On obtient alors une décomposition de la forme

$A=PLU\;$

où Modèle:Formule est une matrice de permutation.

Bien que les décompositions LU et PLU conduisent à des formules distinctes, généralement quand on parle de la décomposition LU, on fait référence à l'une ou l'autre de ces décompositions.

Exemple

La matrice symétrique

$A={\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\\\end{pmatrix}}$

se factorise de la façon suivante :

$A=LU\quad {\text{avec}}\quad L={\begin{pmatrix}1&0&0\\-1/2&1&0\\0&-2/3&1\\\end{pmatrix}}\quad {\text{et}}\quad U={\begin{pmatrix}2&-1&0\\0&3/2&-1\\0&0&4/3\\\end{pmatrix}}$.

Applications

Résoudre un système d'équations linéaires

Cette factorisation matricielle permet de résoudre des systèmes d'équations linéaires où les coefficients des inconnues sont les mêmes, mais avec plusieurs seconds membres différents. Soit à déterminer le vecteur Modèle:Formule d'inconnues associé au second membre Modèle:Formule :

$Ax=b$.

Ce problème est donc équivalent à la résolution de

$LUx=b$

que l'on peut mettre, en posant $Ux=y$, sous la forme :

$Ly=b$.

On trouve les composantes de $y$ par des substitutions élémentaires, puisque d'abord $y_{1}=b_{1}$, puis $y_{2}=b_{2}-L_{21}y_{1}$, etc.

Cette étape est appelée descente, puisqu'on résout le système en descendant de $y_{1}$ à $y_{n}$. Il reste à calculer les composantes du vecteur Modèle:Formule en résolvant le système triangulaire supérieur :

$Ux=y$,

ce qui se fait de manière similaire, mais en calculant d'abord Modèle:Formule :

$x_{n}={\frac {y_{n}}{U_{nn}}}$, etc. en remontant (étape dite de remontée).

Remarque. - Les matrices triangulaires Modèle:Formule et Modèle:Formule auraient pu être inversées aisément en utilisant l'élimination de Gauss-Jordan. Mais si l'on compte simplement le nombre d'opérations que cela représente pour un système à Modèle:Formule équations, on trouvera que la complexité algorithmique du calcul des matrices inverses est supérieure, de sorte que si l'on veut résoudre ce système pour divers Modèle:Formule, il est plus intéressant de réaliser la décomposition LU une fois pour toutes et d'effectuer les substitutions de descente-remontée pour les différents Modèle:Formule plutôt que d'utiliser l'élimination de Gauss-Jordan à de multiples reprises. Ainsi, dans la plupart des publications d'analyse numérique, lorsque la matrice Modèle:Formule a été factorisée sous forme LU ou Cholesky (cf. infra, § Le cas symétrique), on écrit par abus Modèle:Formule pour signifier que le calcul de Modèle:Formule peut se faire par cette méthode de descente-remontée. Il est sous-entendu qu'il n'est absolument pas question d'utiliser l'algorithme en calculant la matrice inverse Modèle:Formule de Modèle:Formule, ce qui serait inutilement coûteux en temps de calcul.

Inverser une matrice

Les matrices Modèle:Formule et Modèle:Formule peuvent être utilisées pour déterminer l'inverse d'une matrice. Les programmes informatiques qui implémentent ce type de calcul utilisent généralement cette méthode.

Calcul d'un déterminant

Si Modèle:Formule est sous forme Modèle:Formule et Modèle:Formule, son déterminant se calcule facilement : $\det(A)=\det(P)\det(L)\det(U)$. Les trois déterminants de ce produit sont très simples à calculer (matrices triangulaires ou de permutations).

Existence, unicité

Pour toute matrice carrée, on a existence d'une décomposition Modèle:Formule. Pour une matrice inversible, la décomposition LU existe si et seulement si toutes les sous-matrices principales d’ordre 1 à Modèle:Formule sont inversibles. [Pour une matrice carrée de rang r < n, il y a des conditions suffisantes analogues.] Si toutes les sous-matrices principales d'ordre 1 à Modèle:Formule sont inversibles, elle est même unique.

Calcul de la décomposition

Idée principale

La décomposition LU est une forme particulière d'élimination de Gauss-Jordan. On transforme la matrice Modèle:Formule en une matrice triangulaire supérieure Modèle:Formule en éliminant les éléments sous la diagonale. Les éliminations se font colonne après colonne, en commençant par la gauche, en multipliant Modèle:Formule par la gauche avec une matrice triangulaire inférieure.

Algorithme

Étant donné une matrice de dimension $N\times N$

$A=(a_{i,j})_{1\leq i,j\leq N}$

on définit

$A^{(0)}:=A\;$

et on va construire les matrices $A^{(1)},...,A^{(n)},...,A^{(N-1)}$ itérativement, en ayant pour objectif que la matrice $A^{(n)}$ ait ses n premières colonnes de coefficients nuls sous la diagonale.

Soit la matrice $A^{(n-1)}$, on construit la matrice $A^{(n)}$ de la manière suivante : considérant la nième colonne de $A^{(n-1)}$, on élimine les éléments sous la diagonale en ajoutant à la ième ligne de cette matrice, la nième ligne multipliée par

$l_{i,n}:=-{\frac {a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}}$

pour $i=n+1,\ldots ,N$. Ceci peut être fait en multipliant par la gauche Modèle:Formule avec la matrice triangulaire inférieure

$L_{n}={\begin{pmatrix}1&&&&&0\\&\ddots &&&&\\&&1&&&\\&&l_{n+1,n}&\ddots &&\\&&\vdots &&\ddots &\\0&&l_{N,n}&&&1\\\end{pmatrix}}.$

$A^{(n)}:=L_{n}A^{(n-1)}.\;$

Après Modèle:Formule itérations, nous avons éliminé tous les éléments sous la diagonale, par conséquent, nous avons maintenant une matrice triangulaire supérieure Modèle:Formule.

Nous obtenons la décomposition

$A=L_{1}^{-1}L_{1}A^{(0)}=L_{1}^{-1}A^{(1)}=L_{1}^{-1}L_{2}^{-1}L_{2}A^{(1)}=L_{1}^{-1}L_{2}^{-1}A^{(2)}=\ldots =L_{1}^{-1}\ldots L_{N-1}^{-1}A^{(N-1)}.$

Notons Modèle:Formule, la matrice triangulaire supérieure Modèle:Formule. et $L=L_{1}^{-1}\ldots L_{N-1}^{-1}$. Sachant que l'inverse d'une matrice triangulaire inférieure est aussi une matrice triangulaire inférieure et que le produit de deux matrices triangulaires inférieures est encore une matrice triangulaire inférieure, Modèle:Formule est donc une matrice triangulaire inférieure. On obtient Modèle:Formule.

Au vu de l'algorithme, il est nécessaire que $a_{n,n}^{(n-1)}\neq 0$ à chaque itération (voir la définition de Modèle:Formule). Si, au cours du calcul, ce cas de figure venait à se produire, il faut intervertir la nième ligne avec une autre pour pouvoir continuer (il est toujours possible de trouver un élément non nul sur la colonne qui pose problème car la matrice est inversible). C'est la raison pour laquelle la décomposition LU s'écrit généralement Modèle:Formule.

Le cas symétrique

• Si la matrice Modèle:Formule est une matrice symétrique, il existe une décomposition dite factorisation de CroutModèle:Retraitoù Modèle:Formule est une matrice triangulaire inférieure dont la diagonale ne comprend que des 1, Modèle:Formule est la transposée de Modèle:Formule, et Modèle:Formule est une matrice diagonale.
• Si la matrice A est symétrique définie positive, il existe une décomposition plus simple, donnée par la méthode de CholeskyModèle:Retraitoù Modèle:Formule est une matrice triangulaire inférieure à diagonale positive et Modèle:Formule est la transposée de Modèle:Formule.

Notes et références

• P. G. Ciarlet - « Introduction à l'analyse numérique matricielle et à l'optimisation » (1985, rééd. 2001), éd. Masson, coll. Math. Appl. pour la Maîtrise Modèle:ISBN

Voir aussi

Liens externes

• Cours d'analyse numérique de licence (2010) de R. Herbin, Université d'Aix-Marseille
• Tutoriel Pourquoi l'algorithme de la décomposition LU fonctionne-t-il?

Articles connexes

• Factorisation de Cholesky
• Décomposition QR
• M-matrice