Décomposition LU

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant l'algèbre, vous pouvez partager vos connaissances en le modifiant.

En algèbre linéaire, la décomposition LU est une méthode de décomposition d'une matrice en une matrice triangulaire inférieure L (comme "Low", bas) et une matrice triangulaire supérieure U (comme "Up", haut). Cette décomposition est utilisée en analyse numérique pour résoudre des systèmes d'équations linéaires.

Sommaire

1 Définition
2 Existence
3 Notes
4 Idée principale
5 Algorithme
6 Applications
- 6.1 Résoudre un systéme d'équations linéaires
- 6.2 Inverser une matrice
7 Voir aussi

[modifier] Définition

Soit A une matrice inversible. La matrice A peut être décomposée ainsi

$P^{-1}A = L U \;$

$A = P L U \;$

où P est une matrice de permutation (de même pour P^-1), L est une matrice triangulaire inférieure et U une matrice triangulaire supérieure. Parfois, la matrice de passage peut être choisie afin d'être une matrice identité. Dans ce cas, la décomposition devient $A = L U .$

[modifier] Existence

La décomposition LU existe si et seulement si toutes les sous matrices principales d'ordre 1 à n-1 sont inversibles

[modifier] Notes

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 = L . t L

où L est une matrice triangulaire inférieure à diagonale positive et $t L$ est la transposée de L.

[modifier] Idée principale

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 commencant par la gauche, en multipliant A par la gauche avec une matrice triangulaire inférieure.

[modifier] Algorithme

Étant donné une matrice de dimension NxN

$A= (a_{n,n})\;$

on définit

$A^{(0)} := A\;$

et les itérations se font pour n = 1,...,N-1 de la manière suivante.

Sur 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 2 matrices triangulaires inférieures est encore une matrice triangulaire inférieure, L est donc une matrice triangulaire inférieure. On obtient $A = L U$ .

A la vue de l'algorithme, il est nécessaire que $a_{n,n}^{(n-1)}\not=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 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 = L U$ .

[modifier] Applications

[modifier] Résoudre un systéme d'équations linéaires

Étant donné l'équation

A x = L U x = b

nous voulons inverser A pour un b donné. Les matrices triangulaires peuvent être inversées aisément en utilisant l'élimination de Gauss-Jordan. C'est pourquoi, 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 toute et d'inverser les matrices triangulaires pour les différents b plutôt que d'utiliser l'élimination de Gauss-Jordan à de multiples reprises.

[modifier] Inverser une matrice

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.