Chapitre 3

Résolution de Systèmes Linéaires -

Méthodes Itératives

3.1 Introduction
L’idée des méthodes itératives de résolution des systèmes linéaires est de construire une
suite convergente x(k) , k ∈ IN de vecteurs vérifiant :

lim x(k) = x (3.1)

k→+∞

où x est la solution du système 2.1. Dans ce chapitre, on va présenter des méthodes

itératives parmi les plus simples à mettre en oeuvre, à savoir les méthodes de Jacobi et de
Gauss-Seidel. Dans ces méthodes, qualifiées de méthodes itératives, la suite x(k) , k ∈ IN
est obtenue, à partir d’un vecteur initial arbitraire x(0) , par une relation de récurrence de
la forme

x(k+1) = B × x(k) + c, ∀k ∈ IN (3.2)

où la matrice carrée B, appelée matrice d’itération de la méthode, et le vecteur c dépendent

de la matrice A et du second membre b du système à résoudre. Pour une matrice pleine,
le coût de calcul de ces méthodes est de l’ordre de O(n2 ) opérations à chaque itération.
Alors que le coût total d’une méthode directe pour la résolution d’un système linéaire à n
équations et n inconnues est de l’ordre de O(n3 ) opérations. Ainsi, une méthode itérative
ne sera compétitive que si elle converge en un nombre d’itérations indépendant de, ou
bien croissant de manière sous-linéaire avec, l’entier n. Cependant, les méthodes directes
peuvent s’avérer particulièrement coûteuses pour les grandes matrices et les méthodes
itératives sont souvent associées à la résolution de ce type de systèmes linéaires.

40
3.2 Généralités
Dans cette section, nous abordons quelques aspects généraux sur les méthodes itératives de
résolution de systèmes linéaires et les outils mathématiques utilisés pour démontrer leurs
propriétés. Les méthodes qu’on va présenter dans ce chapitre sont basé sur la méthode de
point fixe qui sert à la résolution d’équations non linéaires. Nous allons commencer dans
la section suivante par la présentation de la méthode de point fixe, puis nous passons aux
méthodes itératives de résolution d’un système linéaire.

3.3 Méthode de Point Fixe

On appelle point fixe d’une fonction g(x) définie de IR dans IR (ou n’importe quelle
application définie d’un ensemble E dans lui même), toute valeur x pour laquelle :

g(x) = x (3.3)

3.3.1 Suite Récurrente et Convergence

Étant donné une fonction g : I −→ I, et une suite numérique (un ) définie par sa valeur
initiale u0 et la relation de récurrence uk+1 = g(uk ). Si (un ) converge vers un élément α de I
lorsque k → ∞, alors cette limite α est nécessairement un point fixe de la fonction g.

Une telle suite ne converge pas forcément, même si la fonction g possède un ou plusieurs
points fixes. Pour assurer la convergence de cette suite, la fonction g doit être contrac-
tante.

3.3.2 Fonction Contractante

On dit qu’une fonction g est k-contractante sur un intervalle I si les deux conditions
suivantes sont satisfaites.

1. g(I) ⊂ I.
2. ∃k tel que :
— 0 ≤ k < 1.
— ∀x, y ∈ I, nous avons :

|g(x) − g(y)| ≤ k · |x − y| (3.4)

La relation 3.4 est vraie si la dérivée de la fonction g sur l’intervalle I est inférieure à 1
en valeur absolue. Autrement dit :

41
 g ′ (x) < 1, ∀x ∈ I (3.5)

Théorème 3.1. Étant donné une fonction g : I → I contractante et ayant un point fixe α
sur l’intervalle i. La série (un ) définie par récurrence avec la relation uk+1 = g(uk ) converge
toujours vers α le point fixe de la fonction g quelque soit la valeur initiale u0 ∈ I.

Démonstration. On pose e0 = |u0 − α|. et en = |un − α|, ∀n. La méthode de point fixe
converge si et seulement si :

lim |ek | = 0. (3.6)

k→∞

Ce qui implique :

lim uk = α. (3.7)
k→∞

vu que alpha est le point fixe de g nous avons

g(α) = α, (3.8)

et donc nous avons

ek = |uk − α| (3.9)
= |g(uk−1 ) − g(α)| (3.10)

Parce que la fonction g est contractante, ∃0 ≤ q < 1 tel que

|g(uk−1 ) − g(α)| ≤ q · |uk−1 − α| = q · |ek−1 | (3.11)

Ce qui signifie que ∀k

|ek | ≤ q · |ek−1 |. (3.12)

Nous pouvons facilement démontrer par récurrence que

|ek | ≤ q k · e0 , (3.13)

42
et donc que

lim |ek | = 0. (3.14)

k→∞

3.3.3 Résolution d’équations

Il est possible d’utiliser la méthode de point fixe pour résoudre les équations non linéaires
(ou même linéaires) de la forme f (x) = 0. Il est nécessaire de transformer l’équation
f (x) = 0 en équation équivalente g(x) = x, puis chercher α le point fixe de la fonction g.

Étant donné une fonction f , plusieurs choix sont possible pour la fonction g. Il est néces-
saire de prendre une fonction g qui est contractante (|g ′ (x)| < 1).

3.4 Les Normes

La notion de norme est utile en algèbre linéaire numérique pour quantifier l’erreur de
l’approximation de la solution d’un système linéaire par une méthode itérative, on fait
appel à une norme dite vectorielle ou matricielle.

On dit qu’une application ∥ · ∥ de E dans IR (avec E = IRn ou IRn×n ) est une norme sur
si :

1. ∥ v ∥≥ 0, ∀v ∈ E.
2. ∥ v ∥= 0 si et seulement si v = 0.
3. ∥ αv ∥= α ∥ v ∥.
4. ∀u, v ∈ E, ∥ u + v ∥≤∥ u ∥ + ∥ v ∥.

La distance entre deux éléments appartenant à E peut être calculée avec la formule :

∀u, v ∈ E, d(u, v) =∥ u − v ∥ (3.15)

Normes Vectorielles

Pour tout nombre réel p l’application définie dans l’équation 3.16 est une norme.

n
!1/p
X
∥ v ∥p = |vi |p (3.16)
i=1

Les normes vectorielles les plus souvent utilisées sont :

43
 n
X
∥ v ∥1 = |vi | (3.17)
i=1
v
u n
uX 2
∥ v ∥2 = t |vi | (3.18)
i=1

∥ v ∥∞ = max |vi | (3.19)

1≤i≤n

Exemple :

Soit le vecteur v suivant :

 
−7
 
v=
−1

3

Nous avons :

— ∥ v ∥1 = | − 7| + | − 1| + |3| = 11.
p
— ∥ v ∥2 = | − 7|2 + | − 1|2 + |3|2 = 7.68.
— ∥ v ∥∞ = 7.

Normes Matricielles

Nous introduisons ici des normes sur les matrices. Dans toute la suite, on ne va considérer
que des matrices à coefficients réels. En plus des propriétés habituelles d’une norme,
on demande à une norme matricielle de satisfaire la propriété de sous-multiplicativité
suivante :

∥ AB ∥≤∥ A ∥∥ B ∥ (3.20)

On dit qu’une norme matricielle et deux normes vectorielles sont consistantes si pour un
vecteur v et une matrice M nous avons :

∥ M v ∥≤∥ M ∥∥ v ∥ (3.21)

pour chaque norme matricielle, il existe au moins une norme vectorielle avec laquelle elle
est consistante. Ainsi, il n’est pas toujours nécessaire de préciser explicitement la norme
vectorielle avec laquelle la norme matricielle est consistante.

44
Les normes matricielles les plus utilisées sont :

n
X
∥ M ∥1 = max |mi,j | (3.22)
1≤j≤n
i=1

v
u n X
n
uX
∥ M ∥F = t |mi,j |2 (3.23)
i=1 j=1

n
X
∥ M ∥∞ = max |mi,j | (3.24)
1≤i≤n
j=1

Exemple :

Soit la matrice M suivante :

 
−6 −3 9
 
M =
 −4 0 5 

4 −7 −9

nous avons :

— ∥ M ∥1 = 23
— ∥ M ∥2 = 17.69
— ∥ M ∥∞ = 20

3.5 Remarques sur les Méthodes Itératives

Nous expliquons dans cette section les conditions qu’une méthode itérative doit satisfaire
pour converger vers la solution du système. On dit qu’une méthode itérative est conver-
gente, si et seulement si pour chaque vecteur initial x(0) , elle converge vers la solution du
système x.

On dit qu’une méthode itérative de la forme 3.2 est consistante, si la matrice B et le

vecteur c sont choisis tel que pour la solution du système x nous avons :

x = Bx + c

en d’autres termes, la solution du système est obtenue lorsque x(k+1) = x(k) .

Si la solution x existe, on appelle erreur à l’itération k la valeur :

45
 e(k) = x(k) − x. (3.25)

Théorème 3.2. Une méthode itérative consistante est convergente s’il existe une norme
matricielle ∥ · ∥ tel que

∥ B ∥< 1 (3.26)

Démonstration. Posons x la solution du système Ax = b, x(0) la solution initiale devinée

pour notre méthode itérative et pour chaque k, x(k+1) = Bx(k) + c. Soit e(k) = |x − x(k)
l’erreur à l’itération k. Comme nous avons vu pour le théorème de point fixe, une méthode
itérative est convergente si et seulement si :

lim e(k) = 0. (3.27)

k→∞

Vu que la méthode itérative est consistante, nous avons x = Bx + c et donc

e(k+1) = x(k+1) − x
(Bx(k) + c) − (Bx + c)
(3.28)
B(x(k) − x)
Be(k)

On déduit que pour chaque k ≥ 1 :

e(k) = B k × e(0) (3.29)

S’il existe une norme matricielle tel que ∥ B ∥< 1, nous avons :

lim ∥ B k ∥≤ lim ∥ B ∥k = 0. (3.30)

k→∞ k→∞

Et il existe toujours une norme vectorielle consistante avec la norme matricielle précédente
tel que :

lim ∥ e(k) ∥ ≤ lim ∥ B k ∥ × ∥ e(0) ∥

k→∞ k→∞
(3.31)
= 0× ∥ e(0) ∥= 0

46
quelque soit la valeur de e(0) (et par conséquent x(0) ).

Il est aussi possible de démontrer que les méthodes itératives de cette forme convergent
lorsque le rayon spectral (le module max des valeurs propres de la matrice) de la ma-
trice d’itération B est inférieur à 1. Néanmoins, ∀λ valeur propre de la matrice B nous
avons

∥ B ∥≥ λ (3.32)

quelque soit la norme utilisée (plus sur les valeurs propres dans le chapitre 4). Il est donc
suffisant de trouver une seule norme tel que ∥ B ∥< 0 pour assurer la convergence de la
méthode itérative.

En pratique, il est possible d’arrêter la méthode itérative lorsque la norme du vecteur

d’erreur dans 3.25 passe en dessous d’un seuil de tolérance fixé ϵ. Cependant, on ne sait
généralement pas évaluer l’erreur, puisque la solution x n’est pas connue, et il faut donc
avoir recours à un autre critère d’arrêt. Un autre critère parfois utilisé dans la pratique
est basé sur l’incrément est donné par :

x(k+1) − x(k) ≤ ϵ.

Les méthodes de Jacobi et de Gauss-Seidel que nous allons présenter font partie de la
famille de méthodes itératives de la forme :

M x(k+1) = N x(k) + b (3.33)

basées sur la décomposition de la matrice A,

A=M −N (3.34)

avec M une matrice inversible. Pour que la formule 3.33 soit utile en pratique, il faut
par ailleurs que la matrice M soit facilement inversible, c’est-à-dire que l’on doit pou-
voir résoudre simplement et à faible coût un système linéaire ayant M pour matrice
de coefficients. On verra en effet que, pour les méthodes précitées, M est une matrice
respectivement diagonale et triangulaire inférieure. Comme nous l’avons montré dans le
théorème 3.2 la convergence d’une méthode consistante dépend de la norme matricielle
de sa matrice d’itération.

47
3.6 Méthode de Jacobi
Observons que, si les coefficients diagonaux de la matrice A ne sont pas nuls, il est possible
d’isoler la iieme inconnue dans la iieme équation de 2.2, pour 1 ≤ i ≤ n. On obtient alors
le système linéaire équivalent :

( n
!
1 X
xi = × bi − ai,j xj ,i = 1···n (3.35)
ai,i j=1j̸=i

Le méthode de Jacobi se base sur ces relations pour construire, à partir d’un vecteur
initial x(0) donné, une suite x(k) , k ∈ IN par récurrence

( n
!
(k+1) 1 X (k)
xi = × bi − ai,j xj ,i = 1···n (3.36)
ai,i j=1j̸=i

l’équation 3.36 est équivalente à la relation de reccurence suivante 3.37

x(k+1) = M −1 × (b − N × x(k) ) (3.37)

ce qui équivalent à la décomposition 3.34 de la matrice A avec M = D et N = E + F , où

D est la matrice diagonale dont les coefficients sont les coefficients diagonaux de A.

(
di,i = ai,i pour 1 ≤ i ≤ n
(3.38)
di,j = 0 pour i ̸= j

E est la matrice triangulaire inférieure de coefficients

(
ei,j = −ai,j si i > j
(3.39)
ei,j = 0 sinon

et F est la matrice triangulaire supérieure tel que :

(
fi,j = −ai,j si i < j
(3.40)
fi,j = 0 sinon

On a ainsi A = D − (E + F ) avec :

48
  
a 0 0 ··· 0
 1,1 
 0 a
 2,2 0 ··· 0 
 
D=
 0 0 a3,3 ··· 0 ,
 . .. .. .. .. 
 .. . . . . 
 
0 0 0 · · · an,n
   
0 0 0 ··· 0 0 −a1,2 −a1,3 · · · −a1,n
   
 −a 0 0 ··· 0 0 0 −a2,3 · · · −a2,n 
 2,1   
   
 −a3,1 −a3,2
E= 0 ··· 0  , F = 0 0 0 · · · −a3,n 


 . . .. .. ..  . . .. .. .. 
 .. .. . . .  .. .. . . . 
   
−an,1 −an,2 −an,3 ··· 0 0 0 0 ··· 0

et la matrice d’itération est calculée comme suit :

Ax = b
(D − (E + F ))x = b
Dx − (E + F )x = b
Dx = (E + F )x + b
x = D−1 (E + F )x + D−1 b

Donc la méthode de Jacobi de la forme :

x(k+1) = BJ x(k) + cJ (3.41)

est consistante pour la matrice d’itération BJ et le vecteur xJ suivants :

(
BJ = D−1 (E + F )
(3.42)
cJ = D−1 b

et elle est convergente s’il existe une norme matricielle tel que ∥ BJ ∥< 1.

On note que la matrice diagonale D doit être inversible. Cette condition n’est cependant
pas très restrictive dans la mesure où l’ordre des équations et des inconnues peut être
modifié comme nous l’avons fait dans la méthode de Gauss avec échange.

49
3.6.1 Méthode de Jacobi avec "Sur Relaxation"
Une généralisation de la méthode de Jacobi est la méthode de sur-relaxation de Jacobi
dans laquelle un paramètre de relaxation ω est introduit. La relation de récurrence sera
écrite comme suit :

x(k+1) = ωD−1 (M x + b) + (1 − ω)x(k) (3.43)

cette méthode reste consistante car l’égalité dans la relation 3.43 est vérifiée pour x(k+1) =
x(k) = x (avec x étant la solution du système). Cette méthode est une généralisation de
la méthode de Jacobi. Elle coïncide avec cette dernière pour ω = 1. L’objectif est de
choisir le bon paramètre de relaxation ω qui minimise la norme de la matrice d’itération
BJ (ω) dans le but d’accélérer la convergence. La matrice d’itération de la méthode de sur
relaxation est définie comme suit :

BJ (ω) = ωBJ + (1 − ωIn ) (3.44)

donc formellement, il faut trouver ω0 tel que :

∥ BJ (ω0 ) ∥= inf (∥ BJ (ω) ∥), ω ∈ IR (3.45)

3.7 Méthode de Gauss-Seidel

Remarquons à présent que, lors du calcul du vecteur x(k+1) par la formule de récur-
rence 3.36, les premières (i + 1)iemes composantes de x(k+1) sont connues lors de la dé-
termination de iieme pour 2 ≤ i ≤ n. La méthode de Gauss-Seidel utilise ce fait en se
servant des composantes du vecteur x(k+1) déjà obtenues pour le calcul des suivantes. On
a alors :

( i−1 n
!
(k+1) 1 X (k+1)
X (k)
xi = × bi − ai,j xj − ai,j xj ,i = 1···n (3.46)
ai,i j=1 j=i+1

Ce qui est équivalent à mettre M = D − E et N = F , Sous la forme matricielle ça

donne :

x(k+1) = (D − E)−1 × (b − F × x(k) ) (3.47)

dans la décomposition 3.37, d’où la matrice d’itération associée :

50
 BGS = (D − E)−1 F (3.48)

Pour que la méthode soit bien définie, il faut que la matrice D soit inversible, mais, là
encore, cette condition n’est pas très restrictive en pratique. On peut également introduire
dans cette méthode un paramètre de relaxation ω. On parle alors de méthode de sur-
relaxation successive définie par :

( i−1 n
!
(k+1) ω X (k+1)
X (k) (k)
xi = × bi − ai,j xj − ai,j xj + (1 − ω)xi , i = 1 · · · n (3.49)
ai,i j=1 j=i+1

3.8 Matrices à Diagonale Strictement Dominante

Dans le contexte des méthodes itératives, on est en mesure d’établir des résultats de
convergence a priori pour de telles matrices. Si A est une matrice à diagonale stricte-
ment dominante par lignes, alors les méthodes de Jacobi et de Gauss-Seidel sont conver-
gentes.

Une matrice à diagonale strictement dominante par ligne est une matrice sur laquelle sur
chaque ligne, la valeur absolue de l’élément de la diagonale est strictement supérieure à
la somme des valeurs absolues des autres éléments de la même ligne. Formellement, la
matrice A est à diagonale strictement dominante par ligne si :

n
X
|ai, i| > |ai,j | (3.50)
j=1j̸=i

Il est aussi possible de trouver une permutation de ligne pour trouver un système équi-
valent avec une matrice de coefficients à diagonale strictement dominante.

51