Résolution des systèmes linéaires : méthodes directes : Partie II
IV) Méthodes directes de résolution
Soit à résoudre le système linéaire AX = b où A = (aij )1 i; j n 2
Mn (R), A matrice inversible, X = t (x1 x2 ::: xn ) 2 Rn , un vecteur inconnu
et b =t (b1 b2 ::: bn ) 2 Rn , un vecteur donné (second membre).
Une méthode directe de résolution d’un système linéaire AX = b est
une méthode qui détermine la solution X après un nombre …ni d’opérations
élémentaires.
Si la matrice A est inversible alors la solution est X unique.
–1) Cas où A est triangulaire supérieure
Résoudre
8 AX = b est équivalent à résoudre le système d’équations linéaires
>
> a11 1 + a12 x2 + ::: + a1n xn = b1
x
<
a22 x2 + ::: + a2n xn = b2
>
> ::::::::::
:
ann xn = bn
Qn
A est inversible ) det(A) 6= 0 ) aii 6= 0 ) aii 6= 0; 8i 2 f1; :::; ng
i=1
Les
8 xi sont données par l’algorithme de remontée suivant :
>
> bn
< xn =
ann
> Pn
>
: xi = (bi aij xj ) = aii ; pour i = n 1; :::; 1
j=i+1
Exemple
8
< x1 + 2x2 + 3x3 = 2:::::(1)
3 x2 + x3 = 4:::::(2)
:
x3 = 1:::::(3)
l’équation (3) donne x3 = 1;
on remplace x3 par 1 dans l’équation (2), on obtient 3 x2 + 1 = 4 d’où
x2 = 1.
On remplace x3 par 1 et x2 par 1 dans l’équation (1), on obtient x1 +
2( 1) + 3 = 2 d’où x1 = 1:
–2 Cas général : méthode de Gauss
La méthode de Gauss est une méthode directe de résolution du système
linéaire AX = b, elle comporte deux parties :
a) Procédure d’élimination successives qui est équivalente à rendre le
système triangulaire supérieur : échelonnement récursif sur les lignes Li :
ai1
Li Li L1 ; i = 2; 3; :::; n à condition que a11 6= 0
a11
1
Après l’élimination de la 1ere colonne, considérer le système obtenu sans
sa première ligne et sans première colonne puis renommer ses éléments par
(aij )1 i; j n 1 et (bi )1 i n 1 . Refaire les mêmes opérations tant que c’est
possible.
b) Résolution du système triangulaire …nal grâce à l’algorithme de re-
montée.
Exemple
Partie 1 : échelonnement 8
8 >
> L1 : 1 x1 + 2x2 + 3x3 = 2
< L1 : 1 x1 + 2x2 + 3x3 = 2 >
< 1
L2 : 1x1 x2 + 4x3 = 6 !étape 1 L2 L2 L1 : 3x2 + x3 = 4
: > 1
L3 : 2x1 + x2 + 8x3 = 9 >
> 2
: L3 L3 L1 : 3x2 + 2x3 = 5
1
le a11 = 1 est appelé premier pivot.
Garder les deux dernières équations et renomer( les lignes :
L1 : 3x2 + x3 = 4 L 1 : 3 x2 + x3 = 4
!étape 2 3
L2 : 3x2 + 2x3 = 5 L2 L2 L1 : 1 x 3 = 1
3
Après l’étape 1, le a22 = 3 est appelé le 2eme pivot et après l’étape 2, le
a33 = 1 est appelé le 3eme (dernier) pivot.
Parie
8 2 : résolution du système triangulaire 0 1
< 1 x1 + 2x2 + 3x3 = 2 > x1 = 1 1
3 x2 + x3 = 4 > x2 = 1 la solution est X = @ 1 A
:
1x3 = 1 > x3 = 1 1
La méthode de Gauss ordinaire aboutit si et seulement si aucun pivot
n’est nul.
Conséquence : det(A) = produit des pivots =1 ( 3) 1 = 3
Théorème
La méthode de Gauss ordianaire est applicable si et seulement si det A[k] 6=
0 pour tout k = 1; 2; :::; n où A[k] = (aij )1 i; j k .
Exemple
0 1
1 2 3
A=@ 1 1 4 A
2 1 8
on a A[1] = (1) ! det A[1] = 1 6= 0
1 2
A[2] = ! det(A[2] ) = 3 6= 0
1 1
2
0 1
1 2 3 1 2 3 L1
A[3]= @ 1 1 4 A ! det(A[3] ) = 1 1 4 L2
2 1 8 2 1 8 L3 L 3 L1 L2
1 2 3
1 2
det(A[3] ) = 1 1 4 = ( 1)3+3 1 = 3 6= 0
1 1
0 0 1
–3) Stratégies de résolution
Soit AX = b un système linéaire, A 2 Mn (R), A inversible et b 2 Rn .
il est possible que lors de l’élimination de Gauss qu’un pivot soit nul, alors
deux stratégies sont envisageables :
i) Stratégie du pivot partiel : choisir dans la colonne restante contenant
le pivot nul, un élément non nul, puis permuter les lignes correspondantes.
L’ordre des variables xi reste inchangé.
Comme la matrice A est supposée inversible alors il existe au moins un
élément non nul dans la colonne restante contenant le pivot nul car sinon,
par exemple pour n = 5 et après élimination de la 1ère et de la 2ème colonne,
la matrice A devient : 0 1
a11
B 0 a022 C
B C
B 0 0 0 C
B C
@ 0 0 0 A
0 0 0
0 1
a11 0 1
B 0 a022 C 0
B C
alors det BB 0 0 0 C = a11 a022 det @ 0
C
A=0
@ 0 0 0 A 0
0 0 0
ii) Stratégie du pivot total : choisir dans la matrice restante contenant le
pivot nul, un élément non nul, puis permuter les lignes ou/et les colonnes cor-
respondantes. La permutation des colonnes Ci et Cj implique la permutation
des variables xi et xj .
Important : pour des raisons de stabilité numérique (propagation des
erreurs d’arrondis) choisir un pivot qui a la plus grande valeur absolue.
Conséquence : det(A) = ( 1)Nbr_permutations (produit des pivots non nuls
choisis).
Exemple : exo td
Remarque : pivot partiel est un cas particulier du pivot total.
–4) Décomposition (ou factorisation) A = LU
3
Interprétation matricielle de l’élimination de Gauss
ai1
Les opérations linéaires Li Li L1 ; i = 2; 3; :::; n avec a11 6= 0 sont
a11
équivalentes
0 à multiplier A par 1 la matrice notée L1 suivante
1 0 0 :: 0
B a21 C
B 1 0 :: 0 C
B a11 C
B a31 C
L1 = B B 0 1 :: 0 C C
B a11 C
B :: :: :: :: :: C
@ an1 A
0 0 :: 1
a11
si le 2ème pivot est non nul, alors l’élimination de la 2ème colonne du
système revient à multiplier la matrice L1 A par une matrice notée L2 de la
forme 0 1
1 0 ::
B 0 1 :: C
B C
B 0 :: C
L2 = B B C
0 :: C
B C
@ :: :: :: :: :: :: A
0 ::
ainsi de suite
Théorème
Une matrice carrée inversible A admet une unique décomposition A = LU
où L = (lij )1 i; j n est une matrice triangulaire inférieure telle que lii = 1
pour tout i et U = (uij )1 i; j n est une matrice triangulaire supérieure telle
que uii 6= 0 pour tout i si et seulement si det A[k] 6= 0 pour tout k.
Propriétés : si A = LU alors
1) A[k] = L[k] U[k] pour tout k = 1; 2; :::; n
Qk
2) uii = det(A[k] ) pour tout k = 1; 2; :::; n
i=1
Q
n
si k = n alors det(A[n] ) = det(A) = uii
i=1
–Applications : supposons que A = LU
–Application1 : résolution de AX = b
LY = b :::::: (1)
On a AX = b () L(U X) = b () où Y 2 Rn
U X = Y:::::: (2)
Les systèmes (1) et (2) sont des systèmes triangulaires "faciles" à résoudre.
Résoudre d’abord (1) pour obtenir Y puis résoudre (2) pour obtenir X.
4
–Application2 : soit à résoudre plusieurs systèmes linéaires avec la
même matrice A et di¤érents seconds membres b; b0 ; b00 ; :::etc.
il est inutile d’appliquer la méthode de Gauss plusieurs fois sur les sys-
tèmes AX = b; AX = b0 ; AX = b00 ; :::mais il su¢ t d’appeler l’Application1
pour chaque système.
–Détermination de la décomposition A = LU
Méthode : on détermine les éléments des matrices L et U par identi-
…action, en faisant le produit des di¤érentes lignes de L avec les di¤érentes
colonnes de U qu’on identi…e
0 avec les1 éléments de A.
1 2 3
Exemple soit A = @ 1 1 4 A. On démarre de
20 1 8 1
1 2 3
% U =@ 0 3 1 A
0 0 1
0 1 0 1
1 0 0 1 2 3
L=@ 1 1 0 A @ 1 1 4 A=A
2 01 1 12 1 0 8 1
1 0 0 1 2 3
Alors L = @ 1 1 0 A et U = @ 0 3 1 A
2 1 1 0 0 1
–5) Décomposition A = LDV
Soit A une matrice qui admet une décomposition A = LU , alors A
admet une unique décompositon A = LDV avec D = diagonale(U ) et U =
DV i.e V = D 1 U . La matrice V est triangulaire supérieure avec des 1 sur
sa diagonale principale. Si de plus A est symétrique alors L = t V .
Résumé
A = LU
posons D = diagonale(U )
posons V = D 1 U alors U = DV
ainsi A = LU = LDV
–6) Décomposition de Cholesky A = t RR
Dé…nition
On dit qu’une matrice carrée réelle A d’ordre n est dé…nie positive si
det(A[k] ) > 0 pour tout k = 1; 2; :::; n:
Théorème : Soit A 2 Mn (R), la matrice A admet une unique décomposi-
tion de Cholesky A = t RR où R = (rij )1 i; j n est une matrice triangulaire
5
supérieure avec rii > 0 pour tout i, si et seulement si, A est symétrique dé…nie
positive (SDP). (i.e A = t A et det(A[k] ) > 0 pour tout k = 1; 2; :::; n)
–Détermination de la décomposition de Cholesky A = t RR
Soit A 2 Mn (R), une matrice symétrique dé…nie positive donc A = LU
Qk
et comme uii = det(A[k] ) > 0 pour tout k alors ukk > 0 pour tout k =
i=1
1; 2; :::; n: 0 1
u11 0 ::: 0
B 0 u22 ::: 0 C
D = diagonale(U ) = B @ ::: ::: ::: 0 A
C
0 0 ::: unn
0 p 1
u11 0 ::: 0
B 0 p
1
B u22 ::: 0 C C
Notons ainsi D 2 = @
::: ::: ::: 0 A
p
0 0 ::: unn
Méthode 1 : décomposer d’abord A en A = LU puis en A = LDV comme
1 1
A est symétrique alors L = t V donc A = t V DV = (t V D 2 )(D 2 V ) =
1 1 1 1 t
t
(D 2 V ) (D 2 V ), prendre R = D 2 V = D 2 L alors A = t RR:
Méthode 2 : l’identi…cation entre A et t RR.
Exercice
Décomposer
0 A en Cholesky. 1
4 2 0 6
B 2 2 1 1 C
A=B @ 0
C
1 10 1 A
6 1 1 15
la matrice A est SDP
Solution
0 1
2 1 0 3
B 0 1 1 2 C
% B @ 0 0 3
C=R
1 A
0 0 0 1
0 10 1
2 0 0 0 4 2 0 6
B 1 1 0 0 CB 2 2 1 1 C
t
R=B @ 0 1 3 0 A@ 0
CB C=A
1 10 1 A
3 2 1 1 6 1 1 15
2 2
9+4+1+x = 15 !x = 1 !x=-1 ou x=1
6
0 1
2 1 0 3
B 0 1 1 2 C
Alors R = B
@ 0 0 3
C
1 A
0 0 0 1
Remarque : les trois décompositions LU; LDV et t RR sont uniques.