Décomposition LU

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

$L=\begin{pmatrix} 1\\ l_{21} & 1\\ \vdots & \vdots & \ddots\\ l_{n1} & l_{n2} & \cdots & 1 \end{pmatrix}$

$U=\begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n}\\ & u_{22} & \cdots & u_{2n}\\ & & \ddots & u_{n-1,n}\\ & & & u_{nn} \end{pmatrix}$

Résolution de système

Pour la résolution de système linéaire de la forme :, 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 , puis le système (2) pour trouver le vecteur . 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 admet une décomposition , alors celle-ci est unique.
admet une décomposition si, et seulement si, ses mineurs principaux sont non nuls (le mineur principal d’ordre de désigne le déterminant de la matrice obtenue à partir de A en extrayant les k premières lignes et colonnes).
Si est simplement supposée inversible, alors peut s’écrire où est une matrice de permutation.

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

On suppose que admet une décomposition , 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 permet aussi de calculer le déterminant de , qui est égal au produit des éléments diagonaux de la matrice si admet une décomposition

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

Mots-clés:

Résolution de système

Théorèmes

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

Calcul de déterminant

2 Messages de forum

Rubriques

Dans la même rubrique

Mots-clés