COURS N° 4

LES SYSTEMES LINEAIRES

Méthode de Gauss

1
Classification des méthodes de résolution
Il existe deux grandes familles de méthodes de résolution :

1. Les méthodes directes :

On appelle méthode directe de résolution d’un système linéaire une méthode
qui donne exactement la solution d’un système linéaire après un nombre fini
d’opérations élémentaires (addition, soustraction, multiplication et division) soit
par triangularisation ou soit par décomposition de la matrice A.
Les principales méthodes sont :
• L’élimination de Gauss
• La décomposition LU
• La décomposition de Cholesky
• La décomposition QR
Ces méthodes sont utilisées pour les matrices pleines et les petits systèmes.
2
Classification des méthodes de résolution
2. Les méthodes itératives :
On appelle méthode itérative de résolution d’un système linéaire une méthode
qui construit une suite (𝒙𝒌)𝑘∈𝑁 qui converge vers la solution.
Les principales méthodes sont :
• Méthode de Jacobi
• Méthode de Gauss – Seidel
• Méthode de Gradient conjuguée
Ces méthodes sont utilisées pour les matrices creuses et les grands systèmes.

Remarque :
Le choix entre les méthodes directes et les méthodes itératives dépend de type
(ou forme de la matrice) du système.
3
 Méthode d’Elimination de Gauss
Appelée aussi : a) Méthode de Triangularisation de Gauss
b) Méthode de Pivot de Gauss.

Pour résoudre le système 𝑨 𝒙 = 𝒃 on a besoin :

 d’une triangularisation
 d’une remontée (solution d’un système triangulaire)

La méthode d’élimination de Gauss consiste à construire un système

linéaire triangulaire supérieur (𝑆’) équivalent au système linéaire (𝑆) et le
résoudre par remontée.
4
 Méthode d’Elimination de Gauss
En partant de 𝑨(𝟏) = 𝑨 et 𝒃(𝟏) = 𝒃 on construit par récurrence, pour
𝒌 = 𝟏, 𝟐, … 𝒏 des matrices 𝑨(𝒌) et des vecteurs 𝒃(𝒌) tel que le système :

𝑨𝒙 = 𝒃 soit équivalent à 𝑨(𝒌) 𝒙 = 𝒃(𝒌)

→ La matrice 𝑨(𝒏) est triangulaire supérieure.

→ L’algorithme consiste à remplacer à chaque étape la matrice 𝐴 par

𝒊è𝒎𝒆𝒔
une matrice ( 𝑨(𝒌) ) dont les 𝒌 premiers vecteurs colonnes
correspondent au début d’une matrice triangulaire.

→ A la (𝒌 + 𝟏)ième étape, on conserve les 𝒌 premières lignes et les

(𝒌 − 𝟏) premières colonnes de (𝑨(𝒌) ).
5
 Méthode d’Elimination de Gauss
Etape Générale
• On peut définir l’algorithme général en supposant qu’on a effectué
𝑘 − 1 étape d’élimination de Gauss et on a un système qui s’écrit :

𝑨(𝒌) 𝒙 = 𝒃𝒌
• Avec 𝐴(𝑘) et 𝑏 𝑘 donnés par

a11,1   a11,k  a11,n 

   b11 
0 a2 2, 2 a2 2,k a2 2,n   2  
0 0 a33,3 a33,k a33,n  b2 
   b3 3  
         
A k    b  k     
0  0 0 ak k,k  ak k,n 
  b  k  
   0 ak k1 ,k  ak k1 ,n   k 
    
     b  k  
   n 
 0  0 0 an k,k  an k,n 

6
 Méthode d’Elimination de Gauss
Etape Générale
• Pour passer de la matrice 𝐴(𝑘) à la matrice 𝐴(𝑘+1) , on va effectuer des
combinaisons linéaires entre les lignes qui permettront d’annuler les
coefficients de la 𝑖 − è𝑚𝑒 colonne située en dessous de la ligne 𝑖.
a11,1   a11,k  a11,n 
 
0 a2 2, 2 a2 2,k a22,n 
0 0 a33,3 a33,k a33,n 
 
      
A k    
0  0 0 akk,k  akk,n 
 
   0 akk1 ,k  ak k1 ,n   b11 
        2  
  b2 
 0  0 0 an k,k  k 
an ,n   b3 3  
 
• Il faut également modifier le second membre 𝑏 en b  k     
b  k  
conséquence.  k 
  
b  k   7
 n 
Algorithme de triangularisation

8
Algorithme de triangularisation

9
Algorithme de triangularisation

10
Algorithme de triangularisation

11
Algorithme de triangularisation

12
Algorithme de triangularisation

13
Algorithme de triangularisation

14
Algorithme de triangularisation

15
Algorithme de triangularisation

16
Algorithme de triangularisation

17
Algorithme de triangularisation

18
Algorithme de triangularisation

19
 Description méthode de Gauss
Soit le système 𝑆 : 𝑨𝑥 = 𝒃 en supposant toujours que A est inversible
et on pose :

𝒃(𝟏) = 𝒃 et 𝑨(𝟏) = 𝑨 = 𝒂𝒊,𝒋 (𝟏)

𝟏≤𝒊,𝒋≤𝒏

Le système 𝑆 s’écrit alors 𝑨(𝟏) 𝒙 = 𝒃(𝟏) que l’on note 𝑆

Etape 1 : On suppose que 𝒂1,1 (𝟏) ≠ 0, le nombre 𝒂1,1 (𝟏) est le

premier pivot de l’élimination de Gauss.
𝒂𝐢,𝟏 (𝟏)
On pose : 𝐠
𝐢,𝟏 =
𝒂𝟏,𝟏 (𝟏)

Le 𝑆 1 système devient le nouveau système 𝑆 2 : 𝑨(2) 𝒙 = 𝒃(2) avec :

20
 Description méthode de Gauss et factorisation LU

La matrice 𝑨(2) et le vecteur 𝒃(2) sont de la forme :

21
 Description méthode de Gauss et factorisation LU
Etape k
On arrive au cas : 𝒂𝑘,𝑘 (𝑘) ≠ 0, où 𝒂𝑘,𝑘 (𝑘) est le kième pivot de
l’élimination de Gauss. En suivant la même procédure de
𝒂𝒊,𝒌 (𝒌)
précédemment on obtient : 𝒈
𝒊,𝒌 = (𝒌) pour i > k
𝒂𝒌,𝒌
𝑘+1
On obtient alors 𝑆 : 𝑨(𝑘+1) 𝒙 = 𝒃(𝑘+1) avec :

22
 Description méthode de Gauss et factorisation LU

Etape n-1
Le système 𝑆 𝑛 : 𝑨(𝑛) 𝒙 = 𝒃(𝑛) obtenu est triangulaire supérieure
avec :

23
La description de la méthode de Gauss
sur un exemple
Soit le système 𝑆1 :

10 𝑥1 + 5 𝑥2 + 5 𝑥3 = 25 𝐿1
2 𝑥1 + 5 𝑥2 + 7 𝑥3 + 4 𝑥4 = 1 𝐿2
𝑆1
4 𝑥1 + 4 𝑥2 + 𝑥3 + 4 𝑥4 = 12 𝐿3
−2 𝑥1 − 2 𝑥2 + 𝑥3 − 3 𝑥4 = −10 𝐿3

La représentation matriciel du système 𝑆1 :

10 5 5 0 25
2 5 7 4 1
𝐴(1) = 𝑏 (1)
4 4 1 4 12
−2 −2 1 −3 −10

On va d’abord procéder à la triangularisation du système, cette

partie contient (n-1) étape

24
La description de la méthode de Gauss
sur un exemple
1 ère Etape k=1 (1ère itération)
a. On ne touche pas à la ligne du pivot (L1), le pivot (a11= 10)
b. Pour les autres, on remplace chaque ligne Li par :
(1)
𝑎𝑖1
Li − (1) 𝐿1 𝑖 = 2,3,4
𝑎11
(1)
𝑎21 2
 Pour i=2 on remplace L2 par : L2 − (1) 𝐿1 = L2 − 𝐿1
𝑎11 10

(1)
𝑎31 4
 Pour i=3 on remplace L3 par : L3 − (1) 𝐿1 = L3 − 𝐿1
𝑎11 10

(1)
𝑎41 −2
 Pour i=4 on remplace L4 par : L4 − (1) 𝐿1 = L2 − 𝐿1
𝑎11 10 25
La description de la méthode de Gauss
sur un exemple
On obtient après calcul :

10 𝑥1 + 5 𝑥2 + 5 𝑥3 = 25 𝐿1
2
0 + 4 𝑥2 + 6 𝑥3 + 4 𝑥4 = −4 𝐿2 − 𝐿1
10
𝑆2 4
0 + 2 𝑥2 − 𝑥3 + 4 𝑥4 = 2 𝐿3 − 𝐿1
10
2
0 − 𝑥2 + 2𝑥3 − 3 𝑥4 = −5 𝐿4 + 𝐿1
10

La matrice obtenue :

10 5 5 0 25
0 4 6 4 −4
𝐴(2) = 𝑏 (2)
0 2 −1 4 2
0 −1 2 −3 −5

26
 La description de la méthode de Gauss
sur un exemple
2 ème Etape k=2 (2ème itération)
a. On ne touche pas à la ligne (L1 et L2), la ligne du pivot (L2), pivot
(2)
(𝑎22 = 4)
b. remplace chaque ligne Li par :
(2)
𝑎𝑖2
Li − (2) L2 (i = 3,4)
𝑎22
(2)
𝑎32 2
 Pour i=3 on remplace L3 par L3 − (2) 𝐿2 = L3 − 𝐿2
𝑎22 4

(2)
𝑎42 −1
 Pour i=4 on remplace L4 par L4 − (2) 𝐿2 = L4 − 𝐿2
𝑎22 4
27
La description de la méthode de Gauss
sur un exemple
On obtient après calcul :
10 𝑥1 + 5 𝑥2 + 5 𝑥3 = 25 𝐿1
0 + 4 𝑥2 + 6 𝑥3 + 4 𝑥4 = −4 𝐿2
2
𝑆3 0 + 0 − 4 𝑥3 + 2 𝑥4 = 4 𝐿3 − 𝐿2
4
7 −1
0 − 0 + 𝑥3 + 2 𝑥4 = −6 𝐿4 − 𝐿1
2 4

La matrice obtenue :
10 5 5 0 25
0 4 6 4 −4
𝐴(3) = 0 0 𝑏 (3)
−4 2 4
0 0 7/2 −2 −6

28
 La description de la méthode de Gauss
sur un exemple
3 ème Etape k=3 (3ème itération)

a. On ne touche pas à la ligne (L1, L2 et L3), la ligne du pivot (L4),

pivot
(3)
(𝑎33 = 3,5)
(3)
𝑎𝑖3
b. On remplace la ligne Li par : Li − (3) L3 (i = 4)
𝑎33

(3)
𝑎43 3,5
L4 − (3) L3 = L4 − L3
𝑎33 −4

29
La description de la méthode de Gauss
sur un exemple
On obtient après calcul :
10 𝑥1 + 5 𝑥2 + 5 𝑥3 = 25 𝐿1
0 + 4 𝑥2 + 6 𝑥3 + 4 𝑥4 = −4 𝐿2
𝑆4 2
0 + 0 − 4 𝑥3 + 2 𝑥4 = 4 𝐿3 − 𝐿2
4
0 − 0 + 0 − 0,25 𝑥4 = −2,5 𝐿4 + 0,875 𝐿3

La matrice obtenue :

10 5 5 0 25
0 4 6 4 −4
𝐴(4) = 0 0 𝑏 (4)
−4 2 4
0 0 0 −0,25 −2,5

30
La description de la méthode de Gauss
sur un exemple
La triangularisation est achevée car le système S4 est triangulaire.
Pour la résolution, on commence par le bas (la remontée)

2,5
𝑥4 = − = 10
−0,25
4 − 2𝑥4
𝑥3 = = 4
−4
−4 − (6𝑥3 + 4𝑥4 )
𝑥2 = = −17
4
25 − (5𝑥2 + 5𝑥3 )
𝑥1 = = 9
10

La matrice obtenue : 31
 Problème des pivots
𝑎𝑖𝑘
 La méthode de Gauss repose sur la formule : 𝐿𝑖 = 𝐿𝑖 - 𝐿
𝑎𝑘𝑘 𝑘

 Si le pivot est nul, la méthode de Gauss n’est plus applicable.

 Si le pivot est très petit, l’algorithme conduit à des erreurs
d’arrondi importantes.
C’est pourquoi des algorithmes qui échangent les éléments de
façon à avoir le pivot le plus grand possible ont été développés.
Exemple
0.0003 𝑥1 + 3 𝑥2 = 2.0001
Soit le système: 𝑆
𝑥1 + 𝑥2 = 1

1 2
La solution du système (S) est : 𝑥1 , 𝑥2 = ,
3 3
32
 Problème des pivots
Retrouvons la solution par la méthode de Gauss

0.0003 𝑥1 + 3 𝑥2 = 2.0001 0.0003 𝑥1 + 3 𝑥2 = 2.0001

≡
𝑥1 + 𝑥2 = 1 0 − 9999𝑥2 = 6666

6666 2222
𝑥2 = = = ???
⇒ 9999 3333
1
𝑥1 = 2.0001 − 3 𝑥2 =? ? ? ?
0.0003
𝑥1 = −3
avec 3 chiffres significatifs 𝑥2 = 0.667
𝑥1 = −0.3333
avec 4 chiffres significatifs : 𝑥2 = 0.6667
𝑥1 = 0.3
avec 5 chiffres significatifs 𝑥2 = 0.66667
33
 Problème des pivots
Remarques

 Les chiffres de la valeur 𝑥2 restent stables ; par contre ceux de 𝑥1

mutent à chaque nouvelle précision.

 Les solutions aux quelles on aboutit, sont à des échelles

différents, éloignées de la solution exacte.

 Cette perte dans la précision est due au pivot 𝑎11 = 0.0003 qui
est très petit.

34
 Stratégie de choix du pivot
Élimination de Gauss à pivot partiel
Dans ce cas-là, on doit permuter les lignes à chaque étape de façon à
placer en pivot le terme de coefficient le plus élevé de la ligne.

(𝒌) (𝒌)
- kième étape: 𝒂𝒌𝒌 = 𝐦𝐚𝐱 𝒂𝒊𝒌 ,𝒊 ≥ 𝒌

Exemple

1 6 9 𝑥1 1
Soit à résoudre le système 2 1 2 𝑥2 = 2
3 6 9 𝑥3 3

35
 Stratégie de choix du pivot
𝑎𝑖𝑘
On a: 𝐿𝑖 = 𝐿𝑖 − 𝐿
𝑎𝑘𝑘 𝑘
1ére étape k=1

𝑝𝑖𝑣𝑜𝑡 = max 𝑎11 , 𝑎21 , 𝑎31 = 𝑎31 = 3

En permutant les lignes 1 et 3, le système précèdent devient

3 6 9 𝑥1 3
2 1 2 𝑥2 = 2
1 6 9 𝑥3 1

On construit les lignes

𝐿1 = 3 6 9 , 3
𝐿2 = 2 1 2 , 2
𝐿1 = 1 6 9 , 1
36
 Stratégie de choix du pivot

On transforme les lignes :

𝐿1 = 3 6 9 , 3 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝑎21 2
𝐿2 = 𝐿2 − 𝐿 = 2 1 2, 2 − 3 6 9, 3 = 0 −3 −4, 0
𝑎11 1 3
𝑎31 1
𝐿3 = 𝐿3 − 𝐿 = 1 6 9, 1 − 3 6 9, 3 = 0 4 6, 0
𝑎11 1 3
On écrit le système obtenu :
3 6 9 𝑥1 3
0 −3 −4 𝑥2 = 0
0 4 6 𝑥3 0

37
 Stratégie de choix du pivot

2éme étape :k=2

𝑝𝑖𝑣𝑜𝑡 = max 𝑎22 , 𝑎32 = 𝑎32 = 4 On permute les lignes 2 et
3.
3 6 9 𝑥1 3
0 4 6 𝑥2 = 0
0 −3 −4 𝑥3 0
On construit les lignes :
𝐿1 = 3 6 9 , 3
𝐿2 = 0 4 6 , 0
𝐿3 = 0 − 3 − 4 , 0

38
 Stratégie de choix du pivot
On transforme les lignes :
𝐿1 = 3 6 9 , 3 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝐿2 = 0 4 6 , 0 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝑎32 −3
𝐿3 = 𝐿3 − 𝐿 = 0 −3 −4, 0 − 0 4 6, 0 = 0 0 0.5 , 0
𝑎22 2 4
On écrit le système obtenu :
3 6 9 𝑥1 3
0 4 6 𝑥2 = 0
0 0 0.5 𝑥3 0
Résolution par remontée : 𝑥3 = 0 𝑥2 = 0 𝑥1 = 1

39
 Stratégie de choix du pivot
On transforme les lignes :
𝐿1 = 3 6 9 , 3 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝐿2 = 0 4 6 , 0 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝑎32 −3
𝐿3 = 𝐿3 − 𝐿 = 0 −3 −4, 0 − 0 4 6, 0 = 0 0 0.5 , 0
𝑎22 2 4
On écrit le système obtenu :
3 6 9 𝑥1 3
0 4 6 𝑥2 = 0
0 0 0.5 𝑥3 0
Résolution par remontée : 𝑥3 = 0 𝑥2 = 0 𝑥1 = 1

40
 Stratégie de choix du pivot
Élimination de Gauss à pivot total
- kième étape, on échange à la fois les lignes 𝑘 𝑒𝑡 𝑘 ′ 𝑘 ≥ 𝑘 ′ et les
colonnes 𝑘 𝑒𝑡 𝑘′′ 𝑘 ≥ 𝑘 ′′ de telle sorte que
(𝒌) (𝒌)
kième étape 𝒂𝒌𝒌 = 𝐦𝐚𝐱 𝒂𝒊𝒋 ,𝒊 ≥ 𝒌 𝒋 ≥ 𝒌

Attention: Si on fait des échanges de colonnes cela modifie

l’ordre des composantes du vecteur solution 𝒙 donc il faut
penser à rétablir le bon ordre des composantes à la fin.
Exemple

1 3 3 𝑥1 −2
Soit à résoudre le système 2 2 5 𝑥2 = 7
3 2 6 𝑥3 12
41
 Stratégie de choix du pivot
1ére étape k=1
𝑝𝑖𝑣𝑜𝑡 = 𝑚𝑎𝑥 𝑎𝑖𝑗 , 𝑖 = 1: 3 𝑗 = 1: 3 = |𝑎33 | = 6
En permutant les lignes 1 et 3, le système devient :
3 2 6 𝑥1 12
2 2 5 𝑥2 = 7
1 3 3 𝑥3 −2
Puis en permutant les colonnes 1 et 3, le système devient
6 2 3 𝑥3 12
5 2 2 𝑥2 = 7
3 3 1 𝑥1 −2
Attention A chaque permutation de colonnes, les inconnues
changent de place. Dans notre cas, l’inconnue 𝑥1 a changé de
place avec 𝑥3

42
 Stratégie de choix du pivot
On construit les lignes
𝐿1 = 6 2 3 , 12
𝐿2 = 5 2 2 , 7
𝐿3 = 3 3 1 , −2
On transforme les lignes :
𝐿1 = 6 2 3 , 12 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝑎21 5 1 −1
𝐿2 = 𝐿2 − 𝐿 = 5 2 2, 7 − 6 2 3, 12 = 0 , −3
𝑎11 1 6 3 2
𝑎31 3 −1
𝐿3 = 𝐿3 − 𝐿 = 3 3 1 , −2 − 6 2 3, 12 = 0 2 , −8
𝑎11 1 6 2
On écrit le système obtenu :
6 2 3 𝑥3 12
1 −8
0 −0.5 𝑥2 =
3 5
𝑥1 −
0 2 −0.5 3 43
 Stratégie de choix du pivot
2éme étape :k=2
𝑝𝑖𝑣𝑜𝑡 = *max 𝑎𝑖𝑗 , 𝑖 = 1: 3 𝑗 = 1: 3+ = 𝑎32 = 2
On permute les lignes 2 et 3.
6 2 3 𝑥3 12
0 2 −0,5 𝑥2 = −5/3
0 1/3 −0,5 𝑥1 −8
On construit les lignes :
𝐿1 = 6 2 3 , 12
𝐿2 = 0 2 − 0,5 , −5/3
𝐿3 = 0 1/3 − 0,5 , −8

44
 Stratégie de choix du pivot
On transforme les lignes :
𝐿1 = 6 2 3 , 12 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝐿2 = 0 2 − 0,5 , −5/3 𝑖𝑛𝑐ℎ𝑎𝑛𝑔é𝑒
𝑎32 1 −1/3 5 5
𝐿3 = 𝐿3 − 𝐿2 = 0 − 0,5 , −8 − 0 4 6 , −5/3 = 0 0 ,−
𝑎22 3 2 12 3
On écrit le système triangulaire obtenu :
6 2 3 𝑥3 12
0 2 −0,5 𝑥2 = −8
0 0 −5/12 𝑥1 −5/3
Résolution par remontée : 𝑥1 = 4 𝑥2 = −3 𝑥3 = 1

45