Résolution des systèmes linéaires : méthodes directes

I) Les matrices réelles

On note par A = (aij )1 i n; 1 j m une matrice à éléments dans R ayant
n lignes et m colonnes.
On note par Mn;m (R) l’ensemble des matrices réelles du type (n; m) ou
de taille n m formées de n lignes et de m colonnes.
La matrice nulle de Mn;m (R) est designée par 0n m .
Si n = m, alors on note simplement Mn (R) : c’est l’ensemble des matrices
carrées d’ordre n. La matrice unité (ou identité) de Mn (R) est designée par
In .
Dé…nitions
Soit A = (aij )1 i; j n 2 Mn (R)
1) La diagonale principale de A est faii = i = 1; :::; ng:
P
n
2) La trace tr de A est tr(A) = aii :
i=1
3) A est diagonale si aij = 0 pour tous i 6= j:
4) A est triangulaire supérieure si aij = 0 pour tous j < i:
5) A est triangulaire inférieure si aij = 0 pour tous j > i:
6) A est symétrique si aij = aji pour tous i; j:
7) La transposée de A est notée t A = (a0ij )1 i;j n où a0ij = aji pour tous
i; j.
8) La matrice A est inversible s’il existe A0 2 Mn (R) telle que AA0 =
A0 A = In . Si A0 existe, on écrit alors A0 = A 1 .
Propriétés
Soient A; B 2 Mn (R)
1) La matrice A est symétrique si et seulement si t A = A
2) t (A + B) = t A + t B et t (AB) = t B t A
4) Si A 1 existe alors t (A 1 ) = (t A) 1
5) Si A 1 et B 1 existent alors (AB) 1 = B 1 A 1
6) Si A et B sont triangulaires supérieures (resp. inférieures) alors AB
est triangulaire supérieure (resp. inférieure).
7) Supposons que A 1 existe. Si A est trinagulaire supérieure (resp. tri-
nagulaire inférieure) alors A 1 est trinagulaire supérieure (resp. inférieure).
II) Les déterminants
La notion du déterminant concerne seulement les matrices carrées.
Soit A = (aij )1 i; j n 2 Mn (R), le déterminant de A est le nombre réel
a b a b
noté det(A) ou jAj; il est bien connu que det = = ad cb.
c d c d

1
 On désigne par Ai; j la matrice d’ordre n 1, obtenue à partir de A en
supprimant la i eme ligne et la j eme colonne de A.
Le déterminant de A est donné par :
P
n
1) Pour tout j 2 f1; :::; ng, on a det(A) = ( 1)i+j aij det(Ai; j ) : c’est
i=1
le développement de det(A) selon la j eme colonne de A.
P
n
2) Pour tout i 2 f1; :::; ng, on a det(A) = ( 1)i+j aij det(Ai; j ) : c’est
j=1
le développement de det(A) selon la i eme ligne de A.
Noter que la valeur de det(A) est indépendante du choix de i ou de j.
Propriétés
Soient A = (aij )1 i; j n 2 Mn (R) et 2 R
1) La valeur de det(A) reste inchangée si on ajoute à une ligne (resp.
colonne) de A une combinaison linéaire formée de lignes (resp. colonnes)
restantes de A.
2) La valeur de det(A) est égale au déterminant de la matrice obtenue
à partir de A en multipliant l’une des lignes ou colonnes de A par .
3) Si on permute 2 lignes ou 2 colonnes de A alors le déterminant de la
matrice obtenue est ègal à ( det(A)).
4) Si A est une matrice diagonale, triangulaire supérieure ou inférieure
Qn
alors det(A) = aii :
i=1
Propriétés
Soient A; B 2 Mn (R)
1) A est inversible (i.e A 1 existe) si et seulement si det(A) 6= 0:
2) det(t A) = det(A)
3) det(AB) = det(A) det(B)
1
4) Si A 1 existe alors det(A 1 ) =
det(A)
1 t
5) Si A 1 existe alors A 1 = (( 1)i+j det(Ai; j ))1 i; j n où Ai; j
det(A)
est la matrice d’ordre n 1, obtenue à partir de A en supprimant la i eme
ligne et la j eme colonne de A.
1
a b 1 d b
6) Si ad cb 6= alors =
c d ad cb c a
0 1 1 0 1 1
a11 :: 0 a11 :: 0
7) Si a11 a22 :::ann 6= 0 alors @ :: :: :: A = @ :: :: :: A
0 :: ann 0 :: ann1

2
 (l’inverse d’une matrice diagonale inversible est une matrice diagonale)
III) Décomposition par blocs
Soit A une matrice du type (n; m). On peut exprimer la matrice A comme
un tableau
0 de matrices comme suit : 1
A11 ::: ::: A1M
B ::: ::: C
B C
A=B B A IJ
C avec 1 I N et 1 J M
C
@ ::: ::: A
AN 1 ::: ::: AN M
P
N PM
où AIJ est une matrice du type (nI ; mJ ) et on a n = nI et m = mJ .
I=1 J=1
L’interêt de la décomposition par blocs de matrices, réside dans le fait
que certaines opératrions valables sur les éléments, restent valablent sur les
blocs : par exemple la somme et le produit de matrices.
– Le produit par blocs : soient A = (aij ) du type (n; p), B = (bij ) du
type (p; m) et C = AB.
P
N P
P
On décompose A et B en blocs comme suit : n = nI , p = pk et
I=1 K=1
P
M
m= mJ
J=1
P
p
Les éléments de C sont donnés par : cij = aik bkj avec 1 i n et
k=1
1 j m.
P
P
Les blocs de C sont donnés par : CIJ = AIK BKJ avec 1 I N et
K=1
1 J M.
Théorème 1
Soit A une matrice carrée diagonale (resp. trinagulaire supérieure),(resp.
trinagulaire inférieure) par blocs telle que les blocs diagonaux Aii ; i = 1; :::; r
Qr
de A sont carrés alors det(A) = det(Aii ).
i=1
Théorème 2
Soit A une matrice carrée0inversible et diagonale1par blocs carrés, notée
A111 0 ::: 0
B 0 A221 ::: 0 C
Aii ; i = 1; :::; r, alors A 1 = B
@ :::
C:
::: ::: 0 A
0 0 ::: Arr1
IV) Méthodes directes de résolution

3
 Soit à résoudre le système linéaire Ax = b où A = (aij )1 i; j n 2 Mn (R),
A inversible, x = t (x1 x2 ::: xn ) 2 Rn , vecteur inconnu et b =t (b1 b2 ::: bn ) 2
Rn , 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.
–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 x1 + a12 x2 + ::: + a1n xn = b1
<
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
–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
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 + 3x2 = 2
< L1 : 1 x1 + 2x2 + 3x2 = 2 >
< 1
L2 : x1 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

4
 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 + 3x2 = 2 > x1 = 1 1
3 x2 + x3 = 4 > x2 = 1 la solution est x = @ 1 A
:
1 x3 = 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 i = 1; 2; :::; n où A[k] = (aij )1 i; j k .
–3) Stratégies de résolution
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é.
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).
–4) Décomposition (ou factorisation) A = LU
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 i.
Propriétés : si A = LU alors

5
 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
–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.
–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 les
1 éléments de A.
1 2 3
Exemple soit A = @ 1 1 4 A. On démarre de
20 1 8 1

% U =@ 0 A
0 0
0 1 0 1
1 0 0 1 2 3
L=@ 1 0 A @ 1 1 4 A=A
0 1 1 2 1 08 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 .
–6) Décomposition de Cholesky A = t RR
Dé…nition

6
 On dit qu’une matrice carrée réelle A d’ordre n est dé…nie positive si
det(A[k] ) > 0 pour tout i = 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
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 i = 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 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
1 1 1 1
comme L = t V donc A = t V DV = (t V D 2 )(D 2 V ) = t (D 2 V ) (D 2 V )
1
prendre R = D 2 V .
Méthode 2 : l’identi…cation entre A et t RR.
Exemple
0 1 0 10 1
4 2 0 6 2 0 0 0 2 1 0 3
B 2 2 1 1 C B CB C
B C = B 1 1 0 0 CB 0 1 1 2 C
@ 0 1 10 1 A @ 0 1 3 0 A@ 0 0 3 1 A
6 1 1 15 3 2 1 1 0 0 0 1