Accueil > Mathématiques > Résolution de systèmes linéaires > Décomposition LU

Décomposition LU

jeudi 1er juin 2006, par Nadir SOUALEM

Mots-clés: , , , , , , , , , , , .

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)
\]

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 \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.

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,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,\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}

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)

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n'apparaîtra qu'après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message
  • Pour créer des paragraphes, laissez simplement des lignes vides.

Si vous souhaitez aider financièrement le projet Math-Linux.com, vous pouvez aider notre équipe. Merci !!!

Links