Knowledge base dedicated to Linux and applied mathematics.
Accueil > Mathématiques > Résolution de systèmes linéaires > Décomposition LU
Toutes les versions de cet article : <English> <français>
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 c c c }
1\\
l_{21} & 1\\
\vdots & \vdots & \ddots\\
l_{n1} & l_{n2} & \cdots & 1
\end{array} \right)
]
$$
et
$$ U= [ \left( \begin{array}{c c c c } u_{11} & u_{12} & \cdots & u_{1n}\\ & u_{22} & \cdots & u_{2n}\\ & & \ddots & u_{n-1,n}\\ & & & u_{nn} \end{array} \right) ] $$
Pour la résolution de système linéaire de la forme :$Ax=b$, le système devient
$$LUx = b \Leftrightarrow \left\{\begin{array}{cc} Ly = b& (1),\\ Ux = y &(2). \end{array}\right. $$
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 \Leftrightarrow
\left\{\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) &\forall i=2,3,\ldots,n.
\end{array}\right.
$$
$$Ux = y \Leftrightarrow \left\{\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) &\forall i=n-1,n-2,\ldots,1. \end{array}\right. $$
– 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.
On suppose que $A$ admet une décomposition $LU$, on a alors l’algorithme de décomposition LU suivant :
$$k=1,\ldots,n-1\left\{
\begin{array}{l|ll}
l_{ik}=0&i=1,\ldots,k-1 & \\
l_{kk}=1& & \\
l_{ik}=\displaystyle\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}&i=k+1,\ldots,n & \\
a_{ij}^{(k+1)}=a_{ij}^{(k)}&i=1,\ldots,k & j=1,\ldots,n \\
a_{ij}^{(k+1)}=0 &i=k+1,\ldots,n & j=1,\ldots,k \\
a_{ij}^{(k+1)}=a_{ij}^{(k)}-l_{ik}a_{kj}^{(k)} & i=k+1,\ldots,n &j=k+1,\ldots,n
\end{array}\right.
$$
$$ \begin{array}{lll} l_{in}=0&i=1,\ldots,n-1&l_{nn}=1\\ U=(a^{(n)}_{ij})_{1\leq i,j\leq n}&L=(l_{ij})_{1\leq i,j\leq n} & \end{array} $$
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)$$