Résolution par Décomposition LU
Méthode de Doolittle — Système 4×4
Système à résoudre
Le système linéaire est le suivant :
x1 + x2 + 3x4 = 4
2x1 + x2 - x3 + x4 = 1
3x1 - x2 - x3 + 2x4 = -3
-x1 + 2x2 + 3x3 - x4 = 4
Ce qui donne la matrice augmentée [A | b] :
a11 a12 a13 a14 b
1 1 0 3 4
2 1 -1 1 1
3 -1 -1 2 -3
-1 2 3 -1 4
Formules de la décomposition LU (Doolittle)
La matrice L est triangulaire inférieure à diagonale unité, et U est triangulaire supérieure.
Éléments de U : u_ij = a_ij - sum(k=1 à i-1) [ l_ik × u_kj ]
Éléments de L : l_ij = (1 / u_jj) × ( a_ij - sum(k=1 à j-1) [ l_ik × u_kj ] )
Étape 1 : Calcul de L et U
Ligne 1 de U et colonne 1 de L
Première ligne de U (formule directe, i = 1) :
u11 = a11 = 1 | u12 = a12 = 1 | u13 = a13 = 0 | u14 = a14 = 3
Première colonne de L (l_i1 = a_i1 / u_11) :
l21 = a21 / u11 = 2 / 1 = 2
l31 = a31 / u11 = 3 / 1 = 3
l41 = a41 / u11 = -1 / 1 = -1
Ligne 2 de U et colonne 2 de L
u22 = a22 - l21 × u12 = 1 - 2×1 = -1
u23 = a23 - l21 × u13 = -1 - 2×0 = -1
u24 = a24 - l21 × u14 = 1 - 2×3 = -5
l32 = (1/u22) × (a32 - l31×u12) = (1/-1) × (-1 - 3×1) = (-4)/(-1) = 4
l42 = (1/u22) × (a42 - l41×u12) = (1/-1) × (2 - (-1)×1) = 3/(-1) = -3
Ligne 3 de U et colonne 3 de L
u33 = a33 - l31×u13 - l32×u23 = -1 - 3×0 - 4×(-1) = -1 + 4 = 3
u34 = a34 - l31×u14 - l32×u24 = 2 - 3×3 - 4×(-5) = 2 - 9 + 20 = 13
l43 = (1/u33) × (a43 - l41×u13 - l42×u23)
= (1/3) × (3 - (-1)×0 - (-3)×(-1))
= (1/3) × (3 - 0 - 3) = 0/3 = 0
Ligne 4 de U
u44 = a44 - l41×u14 - l42×u24 - l43×u34
= -1 - (-1)(3) - (-3)(-5) - 0(13)
= -1 + 3 - 15 - 0 = -13
Matrices L et U obtenues
Matrice L (triangulaire inférieure, diagonale = 1) :
L col1 col2 col3 col4
lig1 1 0 0 0
lig2 2 1 0 0
lig3 3 4 1 0
lig4 -1 -3 0 1
Matrice U (triangulaire supérieure) :
U col1 col2 col3 col4
lig1 1 1 0 3
lig2 0 -1 -1 -5
lig3 0 0 3 13
lig4 0 0 0 -13
Étape 2 : Résolution de Ly = b (substitution avant)
On résout le système triangulaire inférieur :
y1 = b1 = 4
y2 = b2 - l21 × y1 = 1 - 2×4 = 1 - 8 = -7
y3 = b3 - l31×y1 - l32×y2 = -3 - 3×4 - 4×(-7) = -3 - 12 + 28 = 13
y4 = b4 - l41×y1 - l42×y2 - l43×y3
= 4 - (-1)(4) - (-3)(-7) - 0×13
= 4 + 4 - 21 - 0 = -13
Vecteur intermédiaire : y = [ 4 , -7 , 13 , -13 ]ᵀ
Étape 3 : Résolution de Ux = y (substitution arrière)
On résout le système triangulaire supérieur :
x4 = y4 / u44 = -13 / -13 = 1
x3 = (y3 - u34×x4) / u33 = (13 - 13×1) / 3 = 0 / 3 = 0
x2 = (y2 - u23×x3 - u24×x4) / u22
= (-7 - (-1)(0) - (-5)(1)) / (-1)
= (-7 + 0 + 5) / (-1) = -2 / -1 = 2
x1 = y1 - u12×x2 - u13×x3 - u14×x4
= 4 - 1×2 - 0×0 - 3×1 = 4 - 2 - 3 = -1
Solution finale
x1 = -1 x2 = 2 x3 = 0 x4 = 1
Vérification
Substitution de la solution dans chaque équation du système :
Équation Calcul Résultat
x1 + x2 + 3x4 (-1) + 2 + 3(1) = -1+2+3 =4 ✓
2x1 + x2 - x3 + x4 2(-1) + 2 - 0 + 1 = -2+2+0+1 =1 ✓
3x1 - x2 - x3 + 2x4 3(-1) - 2 - 0 + 2(1) = -3-2+0+2 = -3 ✓
-x1 + 2x2 + 3x3 - x4 -(-1) + 2(2) + 0 - 1 = 1+4+0-1 =4 ✓
Toutes les équations sont satisfaites — la solution est correcte.