Décomposition LU

Ce document présente la méthode de décomposition LU, une technique fondamentale en analyse numérique pour résoudre des systèmes linéaires. Destiné aux étudiants en mathématiques appliquées ou en sciences de l’ingénieur, il détaille les conditions d’existence, la construction des matrices L et U, ainsi que la résolution du système par étapes.

Définition et conditions de la décomposition LU

Considérons un système linéaire (S) défini par :

(S) : A X = b

où A est une matrice carrée dont tous les mineurs principaux sont non nuls.

Le mineur principal M_p,p de A est le déterminant de la sous-matrice formée par les p premières lignes et p premières colonnes de A.

Si A est d’ordre n, elle admet donc n mineurs principaux.

Exemple de mineurs principaux

Soit la matrice :

A = 
⎛ 5  -1  2 ⎞
⎜ 4   1  0 ⎟
⎝-1  9  2 ⎠

Les mineurs principaux sont :

• M_1,1 = 5
• M_2,2 = det

  ⎛ 5  -1 ⎞
  ⎝ 4   1 ⎠
  

• M_3,3 = det(A)

Principe de la méthode

La décomposition LU consiste à factoriser la matrice A en produit de deux matrices :

• L : matrice triangulaire inférieure avec des 1 sur la diagonale
• U : matrice triangulaire supérieure

On écrit :

A = L U

Cette factorisation permet de résoudre le système (S) en deux étapes :

1. Résolution du système triangulaire inférieur : L Y = b (descente)
2. Résolution du système triangulaire supérieur : U X = Y (remontée)

Existence et unicité de la décomposition LU

Le théorème fondamental garantit que :

Si A ∈ M_n(ℝ) est une matrice dont tous les mineurs principaux sont non nuls, alors il existe un unique couple (L, U) avec :

• L triangulaire inférieure avec 1 sur la diagonale
• U triangulaire supérieure

tel que A = L U.

Exemple détaillé de décomposition LU

Considérons le système (S) avec :

A = 
⎛ 3   1   1 ⎞
⎜ 1   1  -3 ⎟
⎝ 1   1  -3 ⎠
, 
b = 
⎛  1  ⎞
⎜ -3  ⎟
⎝  1  ⎠
, 
X = 
⎛ x₁ ⎞
⎜ x₂ ⎟
⎝ x₃ ⎠

Vérification des mineurs principaux

Calculons les mineurs principaux :

• det(3) = 3 ≠ 0
• det

  ⎛ 3  1 ⎞
  ⎝ 1  1 ⎠
  

  = 3×1 - 1×1 = 2 ≠ 0
• det(A) = 32 ≠ 0

Donc A admet une décomposition LU.

Calcul des matrices L et U

On pose :

U = 
⎛ u₁,₁  u₁,₂  u₁,₃ ⎞
⎜  0     u₂,₂  u₂,₃ ⎟
⎝  0      0    u₃,₃ ⎠
, 
L = 
⎛ 1      0      0  ⎞
⎜ l₂,₁   1      0  ⎟
⎝ l₃,₁  l₃,₂    1  ⎠

En développant A = L U, on obtient :

A = 
⎛ 
u₁,₁                                  u₁,₂                                  u₁,₃
l₂,₁ u₁,₁                            l₂,₁ u₁,₂ + u₂,₂                     l₂,₁ u₁,₃ + u₂,₃
l₃,₁ u₁,₁                          l₃,₁ u₁,₂ + l₃,₂ u₂,₂               l₃,₁ u₁,₃ + l₃,₂ u₂,₃ + u₃,₃
⎞

Identification des coefficients

• u₁,₁ = 3
• u₁,₂ = 1
• u₁,₃ = 1
• l₂,₁ × 3 = 1 ⇒ l₂,₁ = 1/3
• l₃,₁ × 3 = 1 ⇒ l₃,₁ = 1/3
• l₂,₁ u₁,₂ + u₂,₂ = 1/3 × 1 + u₂,₂ = 1 ⇒ u₂,₂ = 2/3
• l₂,₁ u₁,₃ + u₂,₃ = 1/3 × 1 + u₂,₃ = -3 ⇒ u₂,₃ = -10/3
• l₃,₁ u₁,₂ + l₃,₂ u₂,₂ = 1/3 × 1 + l₃,₂ × 2/3 = 1 ⇒ l₃,₂ = 1/2
• l₃,₁ u₁,₃ + l₃,₂ u₂,₃ + u₃,₃ = 1/3 × 1 + 1/2 × (-10/3) + u₃,₃ = -3 ⇒ u₃,₃ = -48/15

Matrices obtenues

L = 
⎛ 1      0      0  ⎞
⎜ 1/3    1      0  ⎟
⎝ 1/3   1/2     1  ⎠
, 
U = 
⎛ 3      1       1    ⎞
⎜ 0     2/3   -10/3   ⎟
⎝ 0      0    -48/15  ⎠

Résolution du système LY = b

On résout :

L Y = b

avec :

⎛ 1      0      0  ⎞ ⎛ y₁ ⎞   ⎛  1  ⎞
⎜ 1/3    1      0  ⎟ ⎜ y₂ ⎟ = ⎜ -3  ⎟
⎝ 1/3   1/2     1  ⎠ ⎝ y₃ ⎠   ⎝  1  ⎠

Calculs :

• y₁ = 1
• (1/3) y₁ + y₂ = -3 ⇒ y₂ = -3 - 1/3 = -10/3
• (1/3) y₁ + (1/2) y₂ + y₃ = 1 ⇒ y₃ = 1 - 1/3 - (1/2)(-10/3) = 0

Résolution du système UX = Y

On résout :

U X = Y

avec :

⎛ 3      1       1    ⎞ ⎛ x₁ ⎞   ⎛  1     ⎞
⎜ 0     2/3   -10/3   ⎟ ⎜ x₂ ⎟ = ⎜ -10/3  ⎟
⎝ 0      0    -48/15  ⎠ ⎝ x₃ ⎠   ⎝  0     ⎠

Calculs :

• De la dernière équation : (-48/15) x₃ = 0 ⇒ x₃ = 0
• Deuxième équation : (2/3) x₂ - (10/3) x₃ = -10/3 ⇒ (2/3) x₂ = -10/3 ⇒ x₂ = -5
• Première équation : 3 x₁ + 1 x₂ + 1 x₃ = 1 ⇒ 3 x₁ - 5 + 0 = 1 ⇒ 3 x₁ = 6 ⇒ x₁ = 2

Solution finale

X = 
⎛  2  ⎞
⎜ -5  ⎟
⎝  0  ⎠

Remarques importantes

• La matrice U correspond exactement à la matrice triangulaire supérieure obtenue par la méthode du pivot de Gauss.
• La matrice L est triangulaire inférieure avec des 1 sur la diagonale. Ses coefficients hors diagonale (l₂,₁, l₃,₁, l₃,₂) s’obtiennent à partir des transformations élémentaires de Gauss :

L₂ ← L₂ - l₂,₁ L₁
L₃ ← L₃ - l₃,₁ L₁
L₃ ← L₃ - l₃,₂ L₂

Glossaire des termes clés

• Décomposition LU : Factorisation d’une matrice carrée A en produit de deux matrices triangulaires L et U.
• Matrice triangulaire inférieure (L) : Matrice carrée dont tous les coefficients au-dessus de la diagonale sont nuls et dont la diagonale est composée de 1.
• Matrice triangulaire supérieure (U) : Matrice carrée dont tous les coefficients en dessous de la diagonale sont nuls.
• Mineur principal : Déterminant de la sous-matrice formée par les p premières lignes et p premières colonnes d’une matrice carrée.
• Système triangulaire : Système d’équations linéaires dont la matrice des coefficients est triangulaire (inférieure ou supérieure).
• Pivot de Gauss : Méthode d’élimination pour transformer une matrice en forme triangulaire supérieure.

Points clés à retenir

• La décomposition LU permet de résoudre efficacement un système linéaire en le réduisant à deux systèmes triangulaires.
• Elle existe et est unique si tous les mineurs principaux de la matrice A sont non nuls.
• La matrice L a des 1 sur sa diagonale et ses coefficients hors diagonale sont liés aux opérations de Gauss.
• La matrice U est la forme triangulaire supérieure obtenue par élimination de Gauss.
• La résolution se fait en deux étapes : résolution de LY = b puis de UX = Y.