C HAPITRE 3

M ÉTHODES ITÉRATIVES POUR LA

RÉSOLUTION DES SYSTÈMES LINÉAIRES

Matière : Analyse Numérique

Sommaire
3.1 Description et principe des méthodes itératives. . . . . . . . . . . . . 27
3.2 Quelques exemples de méthodes itératives. . . . . . . . . . . . . . . . 30
3.2.1 Méthode de Jacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Méthode de Gauss-Seidel. . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Méthode de relaxation. . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Vitesse de convergence d’une méthode itérative. . . . . . . . . . . . . 34

3.1 Description et principe des méthodes itératives.

Pour des systèmes linéaires de grande taille, les méthodes directes (telles que la
décomposition LU ou de Cholesky) deviennent coûteuses en temps de calcul ou en
place mémoire. On introduit alors dans ce chapitre, certaines méthodes numériques
dites méthodes itératives.

27
28 Chapitre 3. Méthodes itératives pour la résolution des systèmes linéaires

Ainsi, l’idée est de ne plus chercher à résoudre exactement le système linéaire AX = b,

mais d’approcher sa solution X par une suite de vecteurs (X (k) ) vérifiant :

lim k X (k) − X k= 0
k→+∞

On dit que la suite (X (k) ) converge vers X, l’unique solution du système linéaire AX =
b. La suite (X (k) ) est construite à l’aide d’une relation de récurrence simple de type
X (k+1) = F (X (k) ), pour une application affine F (X) = BX + c où B dépend de A et c
dépend de A et b.

Définition 3.1 (Méthode itérative)

On appelle méthode itérative de résolution du système linéaire AX = b, une méthode qui
construit une suite (X (k) )k∈N , où l’itéré X (k) est calculé à partir des itérés X (0) , . . . , X (k−1) ,
censée converger vers X l’unique solution du système linéaire AX = b.

Afin d’utiliser les méthodes itératives pour résoudre un système linéaire AX = b,

pour A ∈ Mn (R) une matrice inversible et b ∈ Rn , ces méthodes peuvent se formuler
de la manière générale suivante :
• Écrire A comme la différence de deux matrices :

A=M −N où M est une matrice inversible.

Remarque. La matrice M est en général diagonale, triangulaire ou facile à inverser.

Ainsi, on a :

AX = b ⇔ M X = N X + b
⇔ X = M −1 N X + M −1 b

• La matrice M étant inversible, on définit alors la méthode itérative permettant

d’approcher la solution du système linéaire AX = b par la suite de vecteurs (X (k) )
définie par : 
X (0) donné dans Rn ,
M X (k+1) = N X (k) + b, pour k ≥ 0.
−1 −1
En posant B = M N et c = M b, soit l’écriture équivalente :
 (0)
X donné dans Rn ,
X (k+1) = B X (k) + c, pour k ≥ 0.
On dit que B est la matrice de la méthode itérative, appelée matrice d’itération.
3.1. Description et principe des méthodes itératives. 29

Dans la suite, on étudie la convergence des méthodes itératives.

Définition 3.2
1. Si la suite de vecteurs (X (k) ) converge, alors elle converge vers l’unique solution X du
système linéaire AX = b :

pour tout choix initial X (0) , X (k) −→ X quand k → +∞

On dit que la méthode itérative correspondante est convergente pour la résolution du système
linéaire AX = b.
2. Si on définit l’erreur d’approximation à l’itération k par :

e(k) = X (k) − X, k∈N

alors, M e(k+1) = N e(k) et on a la formule de récurrence :

e(k+1) = M −1 N e(k) = . . . = (M −1 N )k+1 e(0) = B k+1 e(0)

La matrice B = M −1 N est appelée matrice d’itération de la méthode itérative. La suite

(X (k) ) vérifie alors
X (k+1) = B X (k) + c, pour c = M −1 b.

D’une manière générale, le critère de convergence de la suite (X (k) ) est assuré sous
certaine condition nécessaire et suffisante sur la matrice d’itération B.

Théorème 3.3 (Convergence d’une méthode itérative)

Si B = M −1 N et c = M −1 b, alors la suite (X (k) ) définie par :
 (0)
X donné dans Rn ,
X (k+1) = B X (k) + c,

converge vers X l’unique solution de X = B X + c, pour tout choix de X (0) , si et seulement si

la matrice d’itération B vérifie :
ρ(B) < 1

où ρ(B) est le rayon spectral de la matrice B.

Ainsi, pour montrer la convergence de la suite (X (k) ) générée par la méthode itéra-
tive, il suffit de vérifier que le rayon spectral de sa matrice d’itération B est plus petit
que 1, ou encore que k| B k|< 1, pour au moins une norme matricielle induite.
30 Chapitre 3. Méthodes itératives pour la résolution des systèmes linéaires

Proposition 3.4
Soit B ∈ Mn (C). Les quatre propriétés suivantes sont équivalentes :
(i) lim B k = 0
k→+∞
(ii) lim B k X = 0, pour tout vecteur X de Cn
k→+∞
(iii) ρ(B) < 1
(iv) |k B |k< 1, pour au moins une norme matricielle induite
Un résultat de convergence d’une méthode itérative est adapté au cas où la matrice
A est symétrique définie positive.
Proposition 3.5 (Cas d’une matrice symétrique définie positive)
Soient A une matrice symétrique définie positive et M , N deux matrices telles que A = M −N ,
où M est inversible. Si la matrice symétrique M T + N est définie positive, alors
ρ(M −1 N ) < 1 et la suite (X (k) ) définie par :
 (0)
X donné dans Rn ,
X (k+1) = M −1 N X (k) + M −1 b,
converge vers X l’unique solution du système linéaire AX = b, pour tout choix de X (0) .

3.2 Quelques exemples de méthodes itératives.

Parmi les méthodes itératives, dont elles font l’objet de ce chapitre, on cite :
– la méthode de Jacobi,
– la méthode de Gauss-Seidel,
– la méthode de relaxation.
Dans ces méthodes itératives classiques, on utilise la décomposition suivante de la
matrice A = (aij )1≤i,j≤n ∈ Mn (R) :
...
 
−F
A=D−E−F = D
 

...
−E
avec D matrice diagonale, E matrice triangulaire inférieure (qui représente l’opposé
de la partie en dessous de la diagonale) et F matrice triangulaire supérieure (qui re-
présente l’opposé de la partie en dessus de la diagonale) :
a11 0 . . . 0 0 0 ... 0 0 −a12 . . . −a1n
     
.. ..  .. .. .. ..
 0 a22
 . .   −a21 0
 . .
 
0 0 . .

D= . . ,E =  . ,F = 
  
 .. .
.. .. 0   .. . .. . .. .. . . .. 
0   . . . −an−1,n 
0 . . . 0 ann −an1 . . . −an,n−1 0 0 ... 0 0
3.2. Quelques exemples de méthodes itératives. 31

3.2.1 Méthode de Jacobi.

Une des méthodes itératives classiques, on considère la méthode de Jacobi. Notons que
cette méthode n’est utilisable que si aii 6= 0 pour tout i = 1, . . . , n.
Dans la méthode de Jacobi, pour décomposer la matrice A = M − N , on choisit :

M =D et N =E+F =D−A

où on suppose que la matrice diagonale D est inversible (aii 6= 0 pour tout i = 1, . . . , n).

La matrice d’itération notée J, appelée "matrice de Jacobi" et est alors

J = D−1 (E + F )

et la suite (X (k) ) dans la méthode de Jacobi est définie par :


 Initialisation : X (0) ∈ Rn donné.
Pour k ≥ 0, calculer X (k+1) solution de :
= J X (k) + D−1 b
 (k+1)
X

Les composantes du vecteur X (k+1) sont données en fonction de celles du vecteur X (k) :
n
(k+1) 1 X (k)

xi = bi − aij xj , ∀i = 1, . . . , n
aii j=1,j6=i

(k+1)
Remarque. À noter que les composantes xi du vecteur X (k+1) sont calculées les
uns indépendamment des autres et dépendent seulement de l’itéré précédent X (k) .

On rappelle en particulier, la définition d’une matrice à diagonale strictement dominate.

Définition 3.6
Une matrice A = (aij )1≤i,j≤n ∈ Mn (C) est dite à diagonale strictement dominante, si elle
vérifie :
X
|aii | > |aij |, ∀i = 1, . . . , n.
j6=i

Ainsi, la convergence de la méthode de Jacobi est assurée en particulier pour les ma-
trices à diagonale strictement dominate.

Proposition 3.7
Soit A une matrice à diagonale strictement dominate. Alors, A est inversible et la méthode de
Jacobi converge pour résoudre le système linéaire AX = b, pour tout b ∈ Rn .
32 Chapitre 3. Méthodes itératives pour la résolution des systèmes linéaires

3.2.2 Méthode de Gauss-Seidel.

Une deuxième méthode itérative, on considère la méthode de Gauss-Seidel. Dans cette

méthode, pour décomposer la matrice A = M − N , on choisit :

M =D−E et N =F

où on suppose que la matrice M est inversible (aii 6= 0 pour tout i = 1, . . . , n).

La matrice d’itération notée L1 , appelée "matrice de Gauss-Seidel" et est alors

L1 = (D − E)−1 F

et la suite (X (k) ) dans la méthode de Gauss-Seidel est définie par :


 Initialisation : X (0) ∈ Rn donné.
Pour k ≥ 0, calculer X (k+1) solution de :
= L1 X (k) + (D − E)−1 b
 (k+1)
X

(k+1)
La i-ème composante du vecteur X (k+1) est donnée en fonction des composantes xj ,
(k+1) (k) (k)
j < i du vecteur X et des composantes xj , j > i du vecteur X par :

(k+1) 1 X (k+1)
X (k)

xi = bi − aij xj − aij xj , ∀i = 1, . . . , n
aii j<i j>i

Remarque. La méthode de Gauss-Seidel est une amélioration de la méthode de Jacobi.

(k+1)
Contrairement à la méthode de Jacobi, les composantes xi du vecteur X (k+1) dé-
pendent les uns des autres, le calcul doit s’effectuer alors dans l’ordre i = 1, . . . , n.

Bien évidemment, la convergence de la méthode de Gauss-Seidel est assurée pour

les matrices symétriques définies positives et pour les matrices à diagonale strictement
dominante.

Proposition 3.8
• Si A ∈ Mn (R) une matrice symétrique définie positive, alors la méthode de Gauss-Seidel
converge pour résoudre le système linéaire AX = b, pour tout b ∈ Rn .
• Si A ∈ Mn (R) une matrice à diagonale strictement dominate, alors la méthode de Gauss-
Seidel converge pour résoudre le système linéaire AX = b, pour tout b ∈ Rn .
3.2. Quelques exemples de méthodes itératives. 33

3.2.3 Méthode de relaxation.

Dans cette section, on définit une nouvelle méthode itérative, appelée méthode de
relaxation. Notons que pour la méthode de relaxation, on introduit un paramètre réel
ω non nul (ω ∈ R∗ ). Ainsi, pour décomposer la matrice A = M − N , on choisit :
1 1−ω
M= D−E et N= D+F
ω ω
La matrice d’itération notée Lω , appelée "matrice de relaxation" et est alors
1
−1 1 − ω

Lω = D−E D+F
ω ω
−1

−1
(1 − ω)In + ωD−1 F


= In − ωD E

et la suite (X (k) ) dans la méthode de relaxation est définie par :

(0) n

 Initialisation : X ∈ R
 donné.
(k+1)
Pour k ≥ 0, calculer X solution de :
1
 X (k+1)
= Lω X + ( D − E)−1 b
(k)

ω
Définition 3.9
Le paramètre réel non nul ω est "le facteur de relaxation".
• Si ω < 1, alors on parle de sous-relaxation.
• Si ω > 1, alors on parle de sur-relaxation.
• Si ω = 1, alors on retrouve la méthode de Gauss-Seidel.

Indépendamment de la matrice A, on a un résultat de divergence pour certaines va-

leurs du paramètre ω :

Proposition 3.10
La méthode de relaxation diverge pour tout ω ∈ R\]0,2[ .

Ainsi, le critère de convergence de la méthode de relaxation n’est assuré que pour

0<ω<2:

Proposition 3.11
Soit A ∈ Mn (R) une matrice symétrique définie positive. Alors la méthode de relaxation
converge si et seulement si
ω ∈]0, 2[
34 Chapitre 3. Méthodes itératives pour la résolution des systèmes linéaires

3.3 Vitesse de convergence d’une méthode itérative.

En pratique, il faut tenir compte de la vitesse de convergence d’une méthode itérative.
Autrement dit, entre deux méthodes itératives convergentes, on choisit celle qui donne
la solution plus rapidement que l’autre. Un critère de mesure de cette vitesse de conver-
gence est l’evolution de l’erreur d’approximation k X (k) − X k qui dépend du rayon
spectral de la matrice d’itération.

En effet, si on a une suite convergente (X (k) ) définie par :

 (0)
X donné,
X (k+1) = B X (k) + c,
sa limite est X la solution de X = BX + c, et on a l’erreur d’approximation :
X (k) − X = B (X (k−1) − X) = B k (X (0) − X)
Par conséquent,
k X (k) − X k2 = k B k (X (0) − X) k2 ≤ k| B |kk2 k X (0) − X k2
En particulier, si la matrice B est symétrique, alors k| B |k2 = ρ(B). Par suite,
k X (k) − X k2 ≤ ρ(B)k k X (0) − X k2
Ainsi, on voit clairement que la suite (X (k) ) converge plus vite vers Xd’autant que ρ(B)
est plus petit. Le rayon spectral ρ(B) de la matrice d’itération B est donc une bonne
estimation de la vitesse de convergence.

Ceci reste encore vrai pour une norme matricielle quelconque et pour une matrice B
quelconque, d’après le résultat suivant :
Lemme 3.12
Si B ∈ Mn (C) et k| . |k est une norme matricielle induite, alors
ρ(B) = lim k| B k |k1/k
k→+∞

Afin de comparer la vitesse de convergence de deux méthodes itératives, on suit alors

la façon suivante :
Définition 3.13
À la recherche d’une solution X d’un système linéaire AX = b, on dit qu’une méthode itérative
de matrice d’itération B, converge plus rapidement qu’une autre méthode itérative de matrice
d’itération B,
e si
ρ(B) < ρ(B)
e
3.3. Vitesse de convergence d’une méthode itérative. 35

Comparaison de Jacobi et Gauss-Seidel.

Il n’y a pas de résultat général établissant que la méthode de Gauss-Seidel converge

toujours plus vite que celle de Jacobi. On peut cependant l’affirmer dans certains cas,comme
le montre la proposition suivante :

Proposition 3.14 (Jacobi et Gauss-Seidel pour les matrices tri-diagonales)

Soit A ∈ Mn (R) une matrice tri-diagonale (c-à-d : aij = 0 si |i − j| > 1). Alors, les rayons
spectraux des matrices de Jacobi et de Gauss-Seidel sont liés par la relation suivante :

2
ρ(L1 ) = ρ(J)

Donc, les deux méthodes convergent ou divergent simultanément. Lorsqu’elles convergent, la

méthode de Gauss-Seidel est plus rapide que celle de Jacobi.