Résolution des systèmes

d’équations linéaires
I-Rappel sur les systèmes linéaires :
 Nous cherchons à résoudre un système linéaire de
n équations à n inconnues :

(1)

 Où les aij sont les coefficients du système ; les xi les

inconnues et les bi forment le second membre.
 On associe au système (1), l’équation matricielle :
AX = B : (2) Où :
1. Opérations sur la matrice A :
Le système linéaire (1) reste invariant pour les 3
opérations suivantes, effectuées dans
n’importe quel ordre et un nombre de fois
indéterminé :
❖ Permutation de 2 lignes de la matrice A (et
donc du vecteur B) ;
❖ Multiplication des éléments d’une ligne par
une même constante non nulle ;
❖ Ajouter à une ligne une combinaison
linéaire des autres lignes :

 (4)
2) Cas des systèmes triangulaires :
Définition: On dira que la matrice A est triangulaire
supérieure si pour tout couple i, j tel
que

(4)

NB : Le déterminant d’une matrice triangulaire est

égales au produit des éléments de la diagonale

Théorème : Pour que le système (1) admette une et

une seule solution, il faut et il suffit que
det(A) 0. Dans ce cas, la matrice A est inversible
et l’unique solution est donnée par
(5)
3) Utilisation pratique des formules
de Cramer :
 Théorème : Lorsque det A 0, les solutions
du système (1) sont données par :

(6)

 Malheureusement, les formules de Cramer

nécessitent un nombre d’opération trop
élevé [ (n2-1)n! multiplications] et elles sont
en pratique inutilisables. En effet, si n=20, il
faut 1021 multiplications, si l’ordinateur fait
une multiplication en 3 x 10-10 s, cela fait
presque 100.000 années.
 Il existe 2 types de méthodes numériques plus
pratiques et plus rapide pour résoudre le système
(1): les méthodes directes et les méthodes itératives.
II) Méthodes directes :
 Les méthodes directes permettent d’obtenir la
solution exacte d’un système en un nombre fini
d’étapes. Nous présenterons ici 2 de ces méthodes:
A) Méthode du pivot de Gauss :
 Elle comprend 2 étapes :
➢ Transformer le système (1) en un système
équivalent triangulaire supérieur possédant la
même solution (triangularisation) ;
➢ Résoudre ce système triangulaire.
1) Exemple : Prenons le système suivant (n=3)

(7)
a) Phase 1 :Triangularisation de la matrice A
Etape 1 : Les opérations à faire sont :
➢ Parmi les coefficients de la 1° colonne( ),
on cherche celui dont la valeur absolue est la
plus grande. Ici, m=2 l’indice de sa ligne. Le
coefficient est appelé le 1° pivot ;
➢ On permute (L1) et (L2), le système devient

(8)
 (8)

➢ Ensuite,nous soustrayons a21/a11 (=3/4) fois

l’équation (L1)à l’équation (L2) et a 31/a11
(=2/4) fois l’équation (L1) à l’équation (L3).
Nous obtenons le système (9) équivalent au (8)
 Etape 2 : ‘’ On oublie ‘’ la ligne L1 puis :
➢ On cherche parmi les lignes L2 et L3 , celui qui a le
plus grand coefficient de y en valeur absolue, ici
c’est la ligne L3 .
➢ On permute alors L2 et L3 ,le système devient :

(10)

➢ On laisse L1 et L2 inchangées et on soustraie

fois L2 à L3 ; le coefficient de y dans L3 s’annule
et le système devient :

(11)
 (11)

b)Phase 2: Résolution du système triangulaire

 De (11) On déduit facilement que :

2) Cas général : La méthode de Gauss
Comprend 2 phases pour résoudre le système (1)
a) Phase 1: Triangularisation de la matrice A
Etape 1 : Les opérations à faire sont :
i) Rechercher, parmi les coefficients a11 ,a21 … an1
de la 1ère colonne (celle des x), celui dont la
valeur absolue est la plus grande. Soit m
l’indice de sa ligne. Le coefficient am1 est
appelé le 1er pivot.
ii) Permuter les lignes (1) et (m),

 NB : Les sous-étapes i) et ii) s’appelle le

pivotage partiel : il consiste à échanger 2
équations dans le but d’avoir le plus grand
pivot en valeur absolue ;
 Afin d’éliminer x1 dans les lignes i=2 à n, donc
avoir des zéros au dessous de a11 , il suffit de lui
retrancher ai1/a11 fois la ligne L1; càd pour
:transformer la ligne Li en Li(2)= Li – (ai1/a11)L1
 Càd : dans chaque ligne Li (i=2…n), transformer
les coefficients :
✓ aij (j=1…n) en aij(2)= aij - (ai1/a11)a1j (substitution)
✓ et bi en bi(2)=bi - (ai1/a11)b1
 Les matrices A et B prendront la forme suivante :
 Afin d’éliminer maintenant x2 dans les lignes
3 à n, on recommence les mêmes opérations
(1 à 3) en gardant les 1ère et 2ème lignes
inchangées.
 Appelons A(k) la matrice et B(k) le second
membre obtenus avant la k-ième étape :

et (10)
 Etape K : Les opérations à faire sont :
i. En « oubliant » les lignes 1 à k-1, rechercher
parmi les coefficients akk(k)…..ank(k) de la colonne
d’indice k celui dont la valeur absolue est la
plus grande ; soit m l’indice de sa ligne. Le
coefficient amk(k) est appelé le pivot de la k-ième
étape ;
ii. Permuter les lignes k et m.
iii. Afin d’avoir des zéros au dessous de akk(k), on
remplace les lignes (Li) d’indice i=k+1, ….,n
par le résultat de la soustraction d’elle-même à
la k-ième ligne multipliée par aik(k) /akk(k). En
d’autre terme :
Pour i≥k+1 : transformer la ligne Li en
Li(k+1)= Li – (aik(k)/ akk(k)) Lk
 Càd dans chaque ligne Li (i= k+1…n) :
❖ Transformer les coefficients ( j= k…n) aij(k) en
aij(k+1)=aij(k)-(aik(k)/ akk(k))akj(k)
❖ Transformer les bi en bi(k+1)=bi(k)- (aik(k)/ akk(k))bk(k)
 En fait, en utilisant l’affectation en programmation,
on peut supprimer l’indice k. On mettra les
nouveaux aij et bi à la place des anciens.
 Si la méthode a réussi à effectuer avec succès n
étapes, alors la matrice prendra la forme
triangulaire suivante :

A’ =
b) Phase2 : Résolution du système triangulaire
 La matrice A’ correspond au système
triangulaire supérieur suivant, ayant les mêmes
solutions que le système initial (1) :

(12)

 Nous déduisons successivement les inconnues xn

, xn-1 …x1 par substitution en remontant de
l’équation (Ln) à l’équation (L1). Nous aurons :
 L’équation (Ln) donne : xn = bn/ann
 L’équat° (Ln-1) donne : xn-1=(bn-1 –an-1,nxn)/an-1,n-1 ,etc..
 On peut écrire ces équations sous la forme :

(13)

 NB : Pour que l’algorithme de Gauss soit

exécutable, il faut que les pivots akk(k) soient non
nuls. Plus exactement, l’algorithme reste
exécutable si parmi tous les aik(k) (i=k…n), il y en a
un non nul qui puisse servir de pivot après
échange de l’ordre des équations restantes.
 Nombre d’opérations :
 Nous pouvons montrer que l’algorithme de
Gauss nécessite n(n+1)/2 divisions et
n(n-1)(2n+5)/6 multiplications et additions.
Soit pour n grand, environ n2 /2 divisions et
n3/3 multiplications et additions.
 Pour n=20 : Méthode de Cramer nécessite
1021 opérations et celle de Gauss 3x103
opérations.
 Le calcul par la méthode de Gauss est
beaucoup plus raisonnable que celui par la
méthode de Cramer.
 NB : La méthode de Gauss permet également
de calculer le rang, l’inverse et le déterminant
d’une matrice.
B) Méthode de Jordan :

 Nous avons vu que la méthode de Gauss

consiste à triangulariser le système (1). La
méthode de Jordan, quant à elle, consiste à
diagonaliser le système (1) ; càd à faire
apparaitre des zéros au dessus et au dessous
de la diagonale.
 2) Exemple : Soit à résoudre le système :

(12)

 Les opérations à faire sont :

a) Phase 1 :
i. On recherche, parmi les coefficients de la
1ère colonne, celui dont la valeur absolue est
la plus grande. Le coefficient 4 est le
premier pivot.
ii. On permute L1 et L3 ; le système devient :

(13)
iii. On divise la 1ère équation par le pivot 4 :

(14)
 (14)

iv. On effectue les soustractions suivantes :

 soit encore :
 (15)

b) Phase 2 :
i) On recherche, entre les lignes L2 et L3 , le
coefficient de y dont la valeur absolue est la
plus grande : ici 3/2 ; On permute L2 et L3 :

(16)
ii) On divise L2 par le 2ème pivot (-3/2), on aura :

(17)

iii) On effectue les opérations suivantes en gardant

L2 inchangée :

(18)
 Soit encore :

(18)
c) Phase 3 :
i) On divise L3 par le coefficient de z = -2 :
(19)

ii) On effectue les opérations suivantes en

gardant L3 inchangée :

(20)
 Ou encore :

 On déduit les solutions dans le 2ème membre :

x=1 ; y=2 et z=-1 ;
3) Cas général :
 La méthode précédente peut être généralisée
à un nombre quelconque d’inconnues.
Supposons que l’élimination a déjà été faite
pour les k-1 premières colonnes :
 Après avoir trouvé, parmi les coefficients de la
colonne k : (akk(k)…..ank(k)), celui dont la valeur
absolue est la plus grande et après avoir
permuté les lignes de façon à rendre akk(k) la
plus grande (pour éviter d’avoir akk(k)=0). On
effectue les opérations suivantes pour avoir
des zéros dans toute la colonne k sauf pour le
coefficient akk(k) qui sera égale à 1 :
 akj(k+1)=akj(k)/ akk(k) pour la k-ième ligne (soit :
akk(k+1)=1)
 aij(k+1)=aij(k)-aik(k)akj(k+1) pour les autres lignes Li (i ≠k)
 bi(k+1)= bi(k) – (aik(k)/ akk(k))bk(k) pour (i ≠ k)
 bk(k+1)=bk(k)/ akk(k) (i=k)
 Après n étapes, le système prendra la forme :

(22)

 On déduit directement les solutions cherchées : x1=

, x2= … xn=
 La variante de Gauss demande un
programme plus long que la méthode
de Jordan car il faut prévoir la phase de
retour en arrière après la phase de
triangularisation, mais elle est plus
rapide pour les grands systèmes
(réduction du nombre d’opérations). En
effet la méthode de Jordan exige
environ n3/2 opérations, tandis que celle
de Gauss exige seulement n3/3
opérations environ.
III) Résolution des systèmes linéaires
par des méthodes itératives :
 La mise en œuvre des méthodes directes (Gauss,
Jordan, LU ..) pour résoudre le système (1) est de
l’ordre de n3, ce qui peut être énorme lorsque n
est grand. On a donc été conduit à utiliser des
méthodes itératives qui s’adaptent mieux aux
grands systèmes linéaires (souvent creux, càd
possédant de nombreux coefficients nuls) et
moins sensible aux erreurs de chute. Ces
méthodes consistent à construire une suite X(k)
qui converge vers la solution X du système (1) :
AX=B . Nous nous limiterons ici à l’exposé de la
méthode de Jacobi.
1) Méthode de Jacobi :
Principe :La méthode de Jacobi consiste à écrire la
matrice (A) sous la forme : A = D – E – F où :
(D) est la matrice diagonale formée des éléments (aii)
(-E) est la matrice formée des éléments sous- diagonaux
de (A),
et (-F) est la matrice formée des éléments sur-
diagonaux de (A). Nous avons donc :

= - -

A = D - E - F
 Si D est inversible, ce qui est le cas si et
seulement si aii≠0 (pour tout i), alors la
matrice (J) définie par :
J = D-1(E+F) = D-1(D-A) = I – D-1A
 Est appelée matrice de Jacobi de (A) ; avec :
D-1 = diag (a11-1, a22-1,…..,ann-1)
 Le système (1) AX = B
devient B = DX – (E+F)X
DX = (E+F)X + B
X = D-1(E+F) X + D-1B
 Soit : X = JX + D-1B
 L’égalité (44) nous suggère la méthode itérative
suivante : Le principe de l’algorithme de Jacobi
est de partir d’un n-vecteur X0 quelconque dont
les composantes xi0 sont choisies arbitrairement
et de chercher à affiner au fur et à mesure des
itérations de ce vecteur X0. Pour n= 0, 1….n, on
calcule :
Xn+1= JXn + D-1B
NB : Les indices n de Xn sont placées en haut du
symbole X pour ne pas confondre Xn avec sa
i-ième composante xin .
 Puisque D-1= diag (a11-1, a22-1,…..,ann-1), on peut
écrire l’égalité (m) composante par composante
de la manière suivante :
 Les relations (46) permettent de calculer
explicitement les composantes xin+1 du
vecteur Xn+1 à partir des composantes xin
( ) du vecteur Xn.
b) Convergence de la méthode de Jacobi :
i) Condition suffisante de convergence :
 On dit que la matrice (A) est diagonale
dominante par lignes (ou resp par colonne) si
elle vérifie les inégalités
( ) (47) (par lignes)

( ) (48) (/colonne)]
 Théoréme : Si (A) est diagonale dominante (par
ligne ou par colonne) alors, quelque soit le
vecteur de départ X0, la suite de Jacobi Xn définie
ci-dessus converge vers l’unique solution du
système linéaire : AX = B
 (voir f)
 NB :
 Pour que la suite de Jacobi converge, il suffit que
l’une des inégalités (47) ou (48) soit satisfaite (et
non nécessairement les 2)
 Les conditions (47) et (48) sont suffisantes mais
elles ne sont pas nécessaires ; càd qu’il peut y
avoir convergence même si elles ne sont pas
satisfaites.
❖ Pivotage total : c’est un échange de lignes
et de colonnes (≠ pivotage partiel : échange
de lignes seulement): Avant d’appliquer la
méthode de Jacobi, on commence par écrire
les équations du système de telle sorte que
les éléments de la diagonale soient les plus
grands possibles. On met le plus grand
coefficient en haut et à gauche du tableau
de la matrice des coefficients (a11). On
cherche ensuite dans les (n-1) équations
restantes, le plus fort coefficient qui ne soit
pas un coefficient de la 1ère colonne. On
placera ce coefficient en 2ème position sur la
diagonale principale (a22), etc…
❖ On a alors les meilleurs conditions possibles
pour la convergence. Mais cette dernière n’est
pas assurée.
 Exemple :

(51)

 Après ces étapes, on ne touche plus à la 1ère

ligne, et même si 9 /2 est le plus grand
coefficient, on l’oublie car il fait partie de la
1ère colonne. On regarde entre le plus
grand coefficient. C’est 4:
on change les 2 dernières lignes :
❖ Condition d’arrêt : On détermine une condition
d’arrêt :
➢ Convergence absolue : ; si

➢ la distance entre 2 itérations successives est

inférieure à un seuil Sinf fixé. On continue la boucle
jusqu’à ce que d’une itération à l’autre, les
changements soient très proches de 0;
➢ Nombre maximal d’itérations

➢ Convergence relative : , si la
distance entre 2 itérations (n et n+1) successives
est inférieure à un seuil Sr fixé relativement à xn
➢ Divergence, si la distance (de Hausdorff) entre 2
itérés est supérieure à un seuil Ssup fixé.