Décomposition LU

Nous allons étudier une méthode directe de résolution de système linéaire : la décomposition LU. L’objectif est de mettre A sous la forme d’un produit d’une matrice triangulaire inférieure L à diagonale unité par une matrice triangulaire supérieure U.

Soit $A$ une matrice de taille $n\times n$. La factorisation $LU$, consiste, pour une matrice $A$, à  déterminer une matrice triangulaire inférieure $L$ à  diagonale unité et une matrice triangulaire supérieure $U$ tel que $A=LU$ avec

$$L=\left(\begin{array}{c}1\\ l_{21}& 1\\ ⋮& ⋮& \ddots \\ l_{n1}& l_{n2}& \cdots & 1\end{array}\right)$$

et

$$U=\left(\begin{array}{cccc}{u}_{11}& u_{12}& \cdots & u_{1n}\\ & u_{22}& \cdots & u_{2n}\\ & & \ddots & u_{n-1,n}\\ & & & u_{nn}\end{array}\right)$$

Résolution de système

Pour la résolution de système linéaire de la forme:$Ax=b$, le système devient

$$LUx=b\iff \{\begin{array}{cc}Ly=b& (1),\\ Ux=y& (2).\end{array}$$

On résout le système (1) pour trouver le vecteur $y$, puis le système (2) pour trouver le vecteur $x$. La résolution est facilitée par la forme triangulaire des matrices.

$$Ly=b\iff \{\begin{array}{ll}{y}_1=b_1/l_{11}& \\ y_i={\displaystyle \frac{1}{l_{ii}}(b_i-\sum _{j=1}^{i-1}{l}_{ij}{y}_j)}& \mathrm{\forall }i=2,3,\dots ,n.\end{array}$$ $$Ux=y\iff \{\begin{array}{ll}{x}_n=y_n/u_{nn}& \\ x_i={\displaystyle \frac{1}{u_{ii}}(y_i-\sum _{j=i+1}^n{u}_{ij}{x}_j)}& \mathrm{\forall }i=n-1,n-2,\dots ,1.\end{array}$$

Théorèmes

• Si $A$ admet une décomposition $LU$, alors celle-ci est unique.
• $A$ admet une décomposition $LU$ si, et seulement si, ses mineurs principaux sont non nuls (le mineur principal d’ordre $k$ de $A$ désigne le déterminant de la matrice obtenue à  partir de A en extrayant les k premières lignes et colonnes).
• Si $A$ est simplement supposée inversible, alors $A$ peut s’écrire $A=PLU,$ où $P$ est une matrice de permutation.

Algorithme général de la décomposition LU

On suppose que $A$ admet une décomposition $LU$, on a alors l’algorithme de décomposition LU suivant:

$$k=1,\dots ,n-1\{\begin{array}{lll}{l}_{ik}=0& i=1,\dots ,k-1& \\ l_{kk}=1& & \\ l_{ik}={\displaystyle \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}}& i=k+1,\dots ,n& \\ a_{ij}^{(k+1)}=a_{ij}^{(k)}& i=1,\dots ,k& j=1,\dots ,n\\ a_{ij}^{(k+1)}=0& i=k+1,\dots ,n& j=1,\dots ,k\\ a_{ij}^{(k+1)}=a_{ij}^{(k)}-l_{ik}{a}_{kj}^{(k)}& i=k+1,\dots ,n& j=k+1,\dots ,n\end{array}$$ $$\begin{array}{lll}{l}_{in}=0& i=1,\dots ,n-1& l_{nn}=1\\ U=(a_{ij}^{(n)}{)}_{1\le i,j\le n}& L=(l_{ij}{)}_{1\le i,j\le n}& \end{array}$$

Calcul de déterminant

La décomposition $LU$ permet aussi de calculer le déterminant de $A$, qui est égal au produit des éléments diagonaux de la matrice $U$ si $A$ admet une décomposition $LU$

$$det(A)=det(L)\times det(U)=1\times det(U)=det(U)$$