ENSAE, Dakar

ISE1, ISEP3

Calcul scientifique
Chapitre 3 : Méthodes itératives

Dr. Oumar Diop

[Link]@[Link]

4 novembre 2025
 PLAN
1

Définition et généralités

Construction d’une méthode itérative

La méthode de Jacobi

La méthode de Gauss-Seidel

| ISE CNM Dr Diop

 Définitions et généralités
2

Soit A une matrice carrée d’ordre n et b un vecteur de Rn . On considère tout au long

de ce chapitre le système linéaire
Ax = b. (1)
La résolution de ce système par une méthode itérative consiste à construire une suite
de vecteur {x(k) , k ≥ 0} qui converge vers la solution exacte x. C’est à dire

lim x(k) = x,
pour toute valeur initiale x(0) ∈ Rn .
Par exemple, on considère la relation de récurrence suivante.

x(k+1) = Bx(k) + g k ≥ 0. (2)

B et g vérifient la relation de consistance suivante.
x = Bx + g. (3)
On déduit de cette relation que g = (I − B)A−1 b. En effet x = A−1 b.

| ISE CNM Dr Diop

 Définitions Généralités (suite)
3

Si on définit l’erreur à l’étape k par

e(k) = x − x(k)
En utilisant les relations (2) et (3), on obtient la relation
e(k+1) = Be(k)
Si la matrice d’itération B est symétrique définie positive alors on la formule suivante.
ke(k+1) k = Bke(k) k ≤ ρ(B)ke(k) k ∀k ≥ 0. 1
Par itérations successives, on obtient la relation suiavnte :
ke(k) k ≤ ρ(B)k ke(0) k, ∀k ≥ 0.
On en déduit que si ρ(B) < 1 alors e(k) tend vers 0 c’est à dire que la méthode
converge.
Cette condition suffisante est également nécessaire.

Proposition 1
Soit une méthode itérative de la forme (2) pour le problème (1) on a convergence pour
tout x(0) ssi ρ(B) < 1. Enfin, plus le nombre ρ(B) est petit, moins il est nécessaire
d’effectuer d’itérations pour réduire l’erreur initiale d’un facteur donné.
1. ρ(B) désigne le rayon spectral de B, c-à-d le plus grand module des valeurs propres de B
| ISE CNM Dr Diop
 Construction d’une méthode itérative
4

Une technique générale de construction d’une méthode itérative consiste à décomposer

la matrice A du système (1) sous la forme A = P − (P − A), où P est une matrice
inversible (appelée préconditionneur de A). On a alors :
P x = (P − A)x + b,
On peut définir la méthode itérative correspondante par :
P (x(k+1) − x(k) ) = r(k) ,
où
r(k) = b − Ax(k) ,
désigne le résidu à l’itération k. On peut généraliser cette méthode de la manière sui-
vante :
P (x(k+1) − x(k) ) = αk r(k) , (4)
où αk 6= 0 est un paramètre qui peut changer à chaque itération k et qui sera à priori
utile pour améliorer les propriétés de convergence de la suite {x(k) }.
La formule (4) est appelée la méthode de Richardson. Les itérations sont données par
la formule
x(k+1) = x(k) + αk z (k) ,
où z (k) est le résidu préconditionné, c’est-à-dire la solution du système linéaire
P z (k) = r(k) . (5)
La matrice P doit être choisie de telle sorte que le coût de la résolution de (5) soit assez
faible, (choisir P comme une matrice diagonale ou triangulaire)
| ISE CNM Dr Diop
 La méthode de Jacobi
5

Soit D une matrice diagonale contenant les termes diagonaux de A. On pose

P = D = diag{a11 , a22 , . . . , ann }. La méthode de Jacobi est donnée par la formule
suivante.
Dx(k+1) = b − (A − D)x(k) , k ≥ 0.
Ici αk = 1, pour tout k ≥ 0. Cette formule est équivalente à celle donnée par
composante.
 
n
(k+1) 1  X (k) 
xi = bi − aij xj , i = 1, 2, . . . , n. (6)
aii j=1,j6=i

La matrice d’itération B est donnée par :

−a12
− aa1n
 
0 a
...
11 11
 
 − a21 − aa2n 
 
a22
0 ...
 22 
−1
 
B = D (D − A) =   (7)

 .. .. .. .. 


 . . . . 

 
an1
−a − aan2 ... 0
nn nn

La convergence de la méthode de Jacobi est donnée par la proposition suivante.

| ISE CNM Dr Diop
 La méthode de Jacobi
6

Proposition 2
Soit la matricePA du système (1) est à diagonale strictement dominante par ligne (c’est
à dire |aii | > nj=1,j6=i |aij | pour tout i), alors la méthode de Jacobi converge.

Si B est la matrice d’itération de la méthode de Jacobi. Pour la preuve de cette propo-

sition, on vérifie que ρ(B) < 1 c’est-à-dire que toutes les valeurs propres de B sont
de module strictement inférieur à 1. On remarque ici que les éléments diagonaux de A
sont non nuls, la matrice étant à diagonale dominante stricte. Soit λ une valeur propre
quelconque de B et x un vecteur propre associé. Alors
n
X
bij xj = λxi , i = 1, 2, . . . , n.
j=1

Pour simplifier, on suppose ici que maxk=1,...,n |xk | = 1. On a alors :

n n n
X X X aij
|λ| = bij xj = bij xj ≤ .
j=1 j=1,j6=i j=1,j6=i
aii

Puisque A est à diagonale strictement dominante, on en déduit alors que |λ| < 1.
| ISE CNM Dr Diop
 La méthode de Gauss-Seidel
7

(k+1)
Dans la méthode de Jacobi les composantes xi du nouveau vecteur x(k) sont
calculées indépendemment des autres.
On modifie la méthode de Jacobi pour accélérer la vitesse de convergence en exploitant
(k+1) (k+1)
cette fois-ci les nouvelles composantes xi dans le calcul de xi . On obtient la
méthode de Gauss-Seidel donnée par la formule suivante.
 
i−1 n
(k+1) 1  X (k+1)
X (k) 
xi = bi − aij xj − aij xj , i = 1, 2, . . . , n. (8)
aii j=1 j=i+1

La mise à jour des composantes est donc à présent séquentielle, alors que dans la
méthode originale de Jacobi, elle se faisait simultanément (ou en parallèle).
Dans cette méthode, on considère
P = D − E et αk = 1 ∀k ≥ 0.
La matrice d’itération de la méthode de Gauss-Seidel est alors donnée par :
B = (D − E)−1 (D − E − A).

| ISE CNM Dr Diop

 Convergence
8

Proposition 3
Soit A ∈ Rn×n une matrice tridiagonale inversible dont les coefficients diagonaux sont
tous non nuls. Alors les méthodes de Jacobi et de Gauss-Seidel sont soit toutes les
deux convergentes soit toutes les deux divergentes. En cas de convergence, la
méthode de Gauss-Seidel est plus rapide que celle de Jacobi ; plus précisément le
rayon spectral de sa matrice d’itération est égal au carré de celui de Jacobi.

Exercice 4
Ecrire le code python de la méthode de Jacobi permettant de résoudre le système
Ax = b

Exercice 5
Ecrire le code python de la méthode de Gauss-Seidel permettant de résoudre le
système Ax = b.

| ISE CNM Dr Diop

 Exercices
9

Exercice 6
Soit la matrice A d’ordre 3 donnée par
 
1 α α
A= α 1 α  (9)
α α 1
1. Pour qu’elles valeurs de a A est-elle définie positive ?
2. Pour qu’elles valeurs de α la méthode de Gauss-Seidel est-elle convergente ?
3. Ecrire la matrice B1 de l’itération de Jacobi.
4. Pour qu’elles valeurs de α la méthode de Jacobi converge-t-elle ?
5. Ecrire la matrice B2 de l’itération de Gauss–Seidel.
6. Calculer le rayon spectral ρ(B2 ).
7. Pour quelles valeurs de α la méthode de Gauss-Seidel converge-t-elle plus vite
que celle de Jacobi ?

| ISE CNM Dr Diop

 Exercices
10

Exercice 7
Soit la matrice A donnée par
3 1 0 0 0
 
 1 2 1 0 0 
A= 0 2 3 1 0
 

 0 0 1 4 3 
0 0 0 1 1
1. Décomposer la matrice A sous la forme LU et en
2. Déduire de la question précédente que le système Ax = b admet une solution
unique qu’on notera par x∗ .
3. On rappelle que les itération de Gauss-Seidel sont données par la formule
suivante : (D − E)Xn+1 = F Xn + b. Déterminer les matrices D − E et F .
4. Pour tout nN, on pose en = Xn − x∗ . Montrer qu’il existe α ∈ [0, 1[ tel que :
∀ n ∈ N ken+1 k ≤ ken k.
En déduire la convergence de la suite.
5. Déterminer la matrice de Gauss–Seidel B associée à A. Calculer kBk∞ . En
déduire la convergence de (Xn ) vers x∗ .
| ISE CNM Dr Diop
 Exercices
11

Exercice 8
Analyser la convergence des méthodes de Jacobi et Gauss-Seidel pour la résolution
d’un système lin2aire associé à la matrice suivante
 
α 0 1
A=  0 α 0 α ∈ R (10)
1 0 α

Exercice 9
Donner une condition suffisante sur α pour que les méthodes de Jacobi et de
Gauss-Seidel convergent toutes les deux quand on les applique à un système associé
à la matrice.
 
−10 2
A= ,α ∈ R (11)
α 5

| ISE CNM Dr Diop