Université de Jijel
Fa c u l t é d e s S c i e n c e s E x a c t e s e t
Informatique
Département
d’Informatique
Résolution des Systèmes Linéaires
Les Méthodes Directes
La Méthode de Gauss
La Méthode de Gauss -
Jordan
La factorisation LU
1
Université de Jijel
Fa c u l t é d e s S c i e n c e s E x a c t e s e t
Informatique
Département
d’Informatique
Résolution des Systèmes Linéaires
Les Méthodes Directes
La Méthode de Gauss
La Méthode de Gauss -
Jordan
La factorisation LU
2
La Factorisation LU :
Système linéaire :
a11X1 + a12X2 + .. + a1nXn = b1 a11 a12 . . . a1n b1
a21X1 + a22X2 + .. + a2nXn = b2 a21 a22 . . . a2n b2
(S) : :
. . . . . .
an1X1 + an2X2 + .. + annXn = bn an1 an2 ann bn
. . .
Système linéaire Matrice Associée
( carré ) (augmentée)
3
3 - Fa c t o r i s a t i o n LU :
Principe de la méthode
:
Factoriser la matrice associée A en deux matrices L et U
(A=L*U) tels que :
• L est une matrice triangulaire
inférieure
• U est une matrice triangulaire
supérieure
L*y =
Le système linéaire Ax = b sera b
remplacé par : U*x =
y
Résoudre le système :
• R é s o u d r e l e s y s t è m e L * y = b ( p a r d e s c e n t e « Fo r w a r d
substitution »)
• Résoudre le système U*x = y (par remontée « Back
substitution »)
𝟐 𝟑
Complexité =O(n 2 ) + ¿ 𝑶( 𝒏 )
: O(2N 3 /3)
𝟑
3 - Fa c t o r i s a t i o n LU :
Algorithmes :
Algorithme de Algorithme de résolution
factorisation : :
A, L, U matrices carrées (n*n éléments)
n, i, j, k: entiers (Forward substitution)
L = I, U = A For i = 1 to n do
For k = 1 to n-1 do Yi = bi
(Choisir le pivot dans la matrice U For j = 1 to i-1 do
(pivot = Ukk) et faire les
Yi = Yi – Lij*yj
permutations nécessaires)
End For
For i = k+1 to n do Yi = Yi/Lii
Lik = Uik / Ukk End For
End for
(Back substitution)
For i = k+1 to n do For i = n to 1 (-1) do
For j = k to n do Xi = bi
Uij = Uij – Lik * Ukj
For j = i+1 to n do
End for Xi = Xi – Uij*Xj
End for
End For
Xi = Xi/Uii
End for
End For
5
3 - Fa c t o r i s a t i o n LU :
Exemple : Soit le système linéaire
suivant :
2 𝑥 1− 𝑥 2+3 𝑥 3 +𝑥 4 =10 2 -1 3 1 10
6 1 14 1 31
(S) 6 𝑥 1+𝑥 2+14 𝑥 3+𝑥 4=3 𝟏
4 -10 -3 9 31
4 𝑥1−10 𝑥2−3 𝑥3+9 𝑥4=31
8 0 20 15 96
8 𝑥 1+20 𝑥 3+15 𝑥 4=96
Système linéaire Matrice Associée
( carré ) (augmentée)
6
3 - Fa c t o r i s a t i o n LU :
1 0 0 0
0 1 0 0
2 -1 3 1 L 0 0 1 0
6 1 14 1 = 0 0 0 1
A 4 -10 -3 9
=
8 0 20 15 2 -1 3 1
Matrice
6 1 14 1
Associée U 4 -10 -3 9
=
8 0 20 15
- L = I.
- U = A.
7
3 - Fa c t o r i s a t i o n LU :
Itération
1: 22 -1 3 1
Pivot 66 1 14 1 3
U 4 -10 -3 9 = / = 2
4
= 8 0 20 15
8 4
1 0 0 0
0 1 0 0
L
= 0 0 1 0
0 0 0 1
- Itération 1 : K = 1 Pivot = Ukk = U11 = 2.
- Li1 = Ui1/U11 = Ui1/2 (i = 2 ..4).
8
3 - Fa c t o r i s a t i o n LU :
Itération
1: 22 -1-1 33 1 -
Pivot 66 1
1 14
14 1
1 x
A 4 -10 -3 9
=
= 8 0 20 15 = 00 44 55 -2
-2
1 0 0 0
3
3 1 0 0
L
= 2 0 1 0
4 0 0 1
- U2j = U2j – L21 * U1j (j = 1 ..4).
9
3 - Fa c t o r i s a t i o n LU :
Itération
1: 2 -1
-1 33 11 -
Pivot 0 4 5 -2 x
U 44 -10
-10 -3-3 99
=
= 8 0 20 15 = 00 -8
-8 -9
-9 77
1 0 0 0
3 1 0 0
L
2
2 0 1 0
=
4 0 0 1
- U2j = U2j – L21 * U1j (j = 1 ..4).
- U3j = U3j – L31 * U1j (j = 1 ..4).
10
3 - Fa c t o r i s a t i o n LU :
Itération
1: 22 -1
-1 33 1 -
Pivot 0 4 5 -2 x
U 0 -8 -9 7
=
= 8
8 0
0 20
20 15 = 00 4 8 11
1 0 0 0
3 1 0 0
L
= 2 0 1 0
4
4 0 0 1
- U2j = U2j – L21 * U1j (j = 1 ..4).
- U3j = U3j – L31 * U1j (j = 1 ..4).
- U4j = U4j – L41 * U1j (j = 1 ..4).
11
3 - Fa c t o r i s a t i o n LU :
Itération
1: 2 -1 3 1
Pivot 0 4 5 -2
U 0 -8 -9 7
= 0 4 8 11
1 0 0 0
3 1 0 0
L
= 2 0 1 0
4 0 0 1
- U2j = U2j – L21 * U1j (j = 1 ..4).
- U3j = U3j – L31 * U1j (j = 1 ..4).
- U4j = U4j – L41 * U1j (j = 1 ..4).
12
3 - Fa c t o r i s a t i o n LU :
Itération
2: 2 -1 3 1
Pivot 0 4 5 -2
U 0 -8
-8 -9 7 = / = -2
= 0 44 8 11 1
1 0 0 0
3 1 0 0
L
= 2 0 1 0
4 0 0 1
- Itération 2 : K = 2 Pivot = Ukk = U22 = 4.
- Li2 = Ui2/U22 = Ui2/4 (i = 3 ..4).
13
3 - Fa c t o r i s a t i o n LU :
Itération
2: 2 -1 3 1
Pivot 0 4 5 -2
U 0 -8 -9 7
= 0 4 8 11
1 0 0 0
3 1 0 0
L
= 2 -2 1 0
4 1 0 1
- Itération 1 : K = 1 Pivot = Ukk = U11 = 2.
- Li1 = Ui1/U11 = Ui1/2 (i = 2 ..4).
14
3 - Fa c t o r i s a t i o n LU :
Itération
2: 2 -1 3 1 -
Pivot 0 44 5 -2
-2 x
U 0 -8-8 -9
-9 77
=
= 0 4 8 11 = 00 1 1 3 3
1 0 0 0
3 1 0 0
L
= 2 -2
-2 1 0
4 1 0 1
- U3j = U3j – L32 * U2j. (2 ≤ j ≤ 4)
15
3 - Fa c t o r i s a t i o n LU :
Itération
2: 2 -1 3 1 -
Pivot 0 4 55 -2
-2 x
U 0 0 1 3
0 3 13 =
= 0 44 88 11
11 = 0 3 13
1 0 0 0
3 1 0 0
L
= 2 -2 1 0
4 1 0 1
- U3j = U3j – L32 * U2j. (2 ≤ j ≤ 4)
- U4j = U4j – L42 * U2j. (2 ≤ j ≤ 4)
16
3 - Fa c t o r i s a t i o n LU :
Itération
3: 2 -1 3 1
Pivot 0 4 5 -2
U 0 0 1 3 = / = 3
= 0 0 3
3 13
1 0 0 0
3 1 0 0
L
= 2 -2 1 0
4 1 0 1
- Itération 3 : K = 3 Pivot = Ukk = U33 = 1.
- Li2 = Ui2/U22 = Ui2/4 (i = 4).
17
3 - Fa c t o r i s a t i o n LU :
Itération
3: 2 -1 3 1 -
Pivot 0 4 5 -2 x
1 3
U 0 0 1 3
=
= 0 0 3 13
13 = 0 4
1 0 0 0
3 1 0 0
L
= 2 -2 1 0
4 1 3 1
- U4j = U4j – L42 * U2j. (2 ≤ j ≤ 4)
18
3 - Fa c t o r i s a t i o n LU :
Itération
3: 2 -1 3 1
Pivot 0 4 5 -2
A 0 0 1 3
= 0 0 0 4
1 0 0 0
3 1 0 0
L
= 2 -2 1 0
4 1 3 1
- U4j = U4j – L42 * U2j. (2 ≤ j ≤ 4)
19
3 - Fa c t o r i s a t i o n LU :
Résultat fi nal (matrices
triangulaires) :
2 -1 3 1
6 1 14 1
A 4 -10 -3 9 =
=
8 0 20 15
1 0 0 0 2 -1 3 1
3 1 0 0 0 4 5 -2
L
2 -2 1 0
X U
0 0 1 3
= =
4 1 3 1 0 0 0 4
20
3 - Fa c t o r i s a t i o n LU :
Résultat fi nal (matrices
triangulaires) :
2 𝑥 1− 𝑥 2+3 𝑥 3 +𝑥 4 =10
6 𝑥 1+𝑥 2+14 𝑥 3+𝑥 4=3 𝟏
(S)
4 𝑥1−10 𝑥2−3 𝑥3+9 𝑥4=31
8 𝑥 1+20 𝑥 3+15 𝑥 4=96
y 1=10 2 𝑥1− 𝑥2+3 𝑥3+𝑥4= y 1
3 𝑦 1+ y 2=3 𝟏 4 𝑥2+5 𝑥3 − 2𝑥 4= 𝑦 2
(S1 (S2 𝑥 3+ 3 𝑥 4= y 3
2 y 1− 2 𝑦 2+ y 3=31
) ) 4 𝑥 4= y 4
4 𝑦 1+ y 2+3 y3+ y 4=96
21
3 - Fa c t o r i s a t i o n LU :
Résolution du système
:
y 1=10 y 1=𝟏𝟎
3 𝑦 1+ y 2=3 𝟏 y 2=31− 3 ∗10=𝟏
(S1
2 y 1− 2 𝑦 2+ y 3=31 2*10+2*1=13
) 4 𝑦 1+ y 2+3 y3+ y 4=96 y 4=96− 4 ∗ 10−1−3∗ 13=𝟏𝟔
2 𝑥1− 𝑥2+3 𝑥3+𝑥4= y 1 (10 +1– 3*1 -4)/2 = 2
4 𝑥2+5 𝑥3 − 2𝑥 4= 𝑦 2 (1 – 5*1 +2*4)/4 = 1
(S2 𝑥 3+ 3 𝑥 4= y 3 13 – 3*4 = 1
) 4 𝑥 4= y 4 /4=4
22
3 - Fa c t o r i s a t i o n LU :
Résolution du système
:
2 𝑥 1− 𝑥 2+3 𝑥 3 +𝑥 4 =10 2
(S) 6 𝑥 1+𝑥 2+14 𝑥 3+𝑥 4=3 𝟏 1
4 𝑥1−10 𝑥2−3 𝑥3+9 𝑥4=31 1
8 𝑥 1+20 𝑥 3+15 𝑥 4=96 4
Système linéaire
( carré )
23
3 - Fa c t o r i s a t i o n LU :
Avantage majeur de la factorisation
LU:
Lorsqu’on cherche à résoudre le même système linéaire Ax
= b avec plusieurs valeurs de b (b1, b2, b3, ..) :
On fait la factorisation de la matrice A une seule fois.
On remplace les valeurs des vecteurs b1, b2,.. dans la
dernière étape de résolution à chaque fois, et on fait la
résolution pardescente puis par remontée.
24
3 - Fa c t o r i s a t i o n LU :
Avantage majeur de la factorisation
LU:
Pour l’exemple précédent si on cherche à résoudre le même système
mais pour b = (55 , 270 , -100 , 305)t. On remplace directement les
valeurs du vecteur b précédent par ces nouvelles valeurs dans le
système (S1) obtenu, on obtient ainsi :
y 1=55 y 1=𝟓𝟓
3 𝑦 1+ y 2=270 y 2 =𝟏𝟎𝟓
(S1
2 y 1− 2 𝑦 2+ y 3=−100 y 3 =𝟎
) 4 𝑦 1+ y 2+3 y3+ y 4=305 y 4 =− 𝟐𝟎
2 𝑥1− 𝑥2+3 𝑥3+𝑥4= y 1 10
4 𝑥2+5 𝑥3 − 2𝑥 4= 𝑦 2 5
15
(S2 𝑥 3+ 3 𝑥 4= y 3
) 4 𝑥 4= y 4 -5 25
FIN
26
Annexes :
Exercice1
:
S o i t l e s y s t è m e re p ré s e n t é p a r l a m a t r i c e a u g m e n t é e
suivante :
Ré s o u d re c e s y s t è m e p a r l a m é t h o d e d e f a c t o r i s a t i o n LU s a n s é c h a n g e
de pivot (méthode simple).
Solution
:
27
Annexes :
Exercice1
:
S o i t l e s y s t è m e re p ré s e n t é p a r l a m a t r i c e a u g m e n t é e
suivante :
Ré s o u d re c e s y s t è m e p a r l a m é t h o d e d e f a c t o r i s a t i o n LU s a n s é c h a n g e
de pivot (méthode simple).
Solution
:
28
Annexes :
Exercice1
:
S o i t l e s y s t è m e re p ré s e n t é p a r l a m a t r i c e a u g m e n t é e
suivante :
Ré s o u d re c e s y s t è m e p a r l a m é t h o d e d e f a c t o r i s a t i o n LU s a n s é c h a n g e
de pivot (méthode simple).
Solution
:
29
Annexes :
Exercice1
:
S o i t l e s y s t è m e re p ré s e n t é p a r l a m a t r i c e a u g m e n t é e
suivante :
Ré s o u d re c e s y s t è m e p a r l a m é t h o d e d e f a c t o r i s a t i o n LU s a n s é c h a n g e
de pivot (méthode simple).
Solution
:
30
FIN
31