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 $L$ (comme lower, inférieure en anglais) par une matrice triangulaire supérieure $U$ (comme upper, supérieure). Cette décomposition est utilisée en analyse numérique pour résoudre des systèmes d'équations linéaires.

Définition[modifier | modifier le code]

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

A=LU\;

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

PA=LU\;

où $P$ est une matrice de permutation.

Bien que les décompositions LU et P^-1LU 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[modifier | modifier le code]

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[modifier | modifier le code]

Résoudre un système d'équations linéaires[modifier | modifier le code]

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 $x$ d'inconnues associé au second membre $b$ :

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 $L_{11}y_{1}=b_{1}$ donc $y_{1}=b_{1}/L_{11}$ , puis $L_{22}y_{2}=b_{2}-L_{21}y_{1}$ , donc $y_{2}=(b_{2}-L_{21}y_{1})/L_{22}$ , 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 $x$ en résolvant le système triangulaire supérieur :

Ux=y

,

ce qui se fait de manière similaire, mais en calculant d'abord $x n$ :

x_{n}={\frac {y_{n}}{U_{nn}}}

, etc. en remontant (étape dite de remontée).

Remarque. - Les matrices triangulaires $L$ et $U$ 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 à $n$ é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 $b$ , 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 $b$ 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 $A$ a été factorisée sous forme LU ou Cholesky (cf. infra, § Le cas symétrique), on écrit par abus $x = A -1 b$ pour signifier que le calcul de $x$ 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 $A -1$ de $A$ , ce qui serait inutilement coûteux en temps de calcul.

Inverser une matrice[modifier | modifier le code]

Les matrices $L$ et $U$ 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[modifier | modifier le code]

Si $A$ est sous forme $LU$ et $PLU$ , 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é[modifier | modifier le code]

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

Calcul de la décomposition[modifier | modifier le code]

Idée principale[modifier | modifier le code]

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

Algorithme[modifier | modifier le code]

É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 $A (n -1)$ 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 $N - 1$ itérations, nous avons éliminé tous les éléments sous la diagonale, par conséquent, nous avons maintenant une matrice triangulaire supérieure $A (N -1)$ .

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 $U$ , la matrice triangulaire supérieure $A (N -1)$ . 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, $L$ est donc une matrice triangulaire inférieure. On obtient $A = LU$ , et

L={\begin{pmatrix}1&&&&&\\l_{2,1}&\ddots &&&&\\&\ddots &1&&&\\\vdots &\dots &l_{n+1,n}&1&&\\&&\vdots &\ddots &\ddots &\\l_{N,1}&\dots &l_{N,n}&\dots &l_{N,N-1}&1\end{pmatrix}}.

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 $l {i, n}$ ). 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 un problème car la matrice est inversible). C'est la raison pour laquelle la décomposition LU s'écrit généralement $P -1 A = LU$ .

Le cas symétrique[modifier | modifier le code]

Si la matrice $A$ est une matrice symétrique, il existe une décomposition dite factorisation de Crout $A=LDL^{\mathrm {T} }$ où $L$ est une matrice triangulaire inférieure dont la diagonale ne comprend que des 1, $L T$ est la transposée de $L$ , et $D$ 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 Cholesky $A=LL^{\mathrm {T} }$ où $L$ est une matrice triangulaire inférieure à diagonale positive et $L T$ sa transposée.

Notes et références[modifier | modifier le code]

↑ Pour la démonstration, cf. Ciarlet, chap. 4, §4.3

P. G. Ciarlet, Introduction à l'analyse numérique matricielle et à l'optimisation, éd. Masson, coll. « Math. Appl. pour la Maîtrise », 1985 (réimpr. 2001) (ISBN 2-225-68893-1)

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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

Articles connexes[modifier | modifier le code]

Portail de l’algèbre

[1] Pour la démonstration, cf. Ciarlet, chap. 4, §4.3

[1]

v · m Analyse numérique
Recherche de zéro	Méthode de Josephy-Newton Méthode de la sécante Méthode de Newton Point fixe
Transformations de matrice	Matrice de Hessenberg Décomposition LU Factorisation de Cholesky
Résolutions de systèmes	Méthode de Gauss-Seidel Méthode de surrelaxation successive (SOR) Méthode de Jacobi Décomposition QR Décomposition LU
Intégration numérique	Méthode du point médian Méthode des trapèzes Méthode de Simpson Méthodes de quadrature de Gauss Formule de Newton-Cotes Méthode de Romberg Méthode de Monte-Carlo
Équations différentielles	Méthode d'Euler (et semi-implicite) Méthodes de Runge-Kutta Intégration de Verlet Leapfrog Méthode multi-pas linéaire (en) (Adams-Bashforth, backward differentiation formula (en))
Interpolation numérique	Spline Interpolation polynomiale Interpolation lagrangienne Interpolation d'Hermite Suite de polynômes orthogonaux