Plan

Chapitre 1 :Rappels et compléments d’analyse matricielle

Chapitre 2 : fondements du calcul scientifique

Chapitre 3 : Méthodes directes de résolution des systèmes linéaires

Chapitre 4 : Méthodes itératives de résolution des systèmes linéaires

L%µ 1
Chapitre 4 : Méthodes itératives de résolution des
systèmes linéaires
4.1 Introduction
4.2 construction d’une méthode itérative
4.2.1 Méthode de Jacobi
4.2.2 Méthode de JOR
4.2.3 Méthode de Gauss-Seidel
4.2.4 Méthode de SOR
4.3 Convergence
4.4 vitesse de convergence
4.5 Critère d'arrêt
4.6 Conditionnement
2
4.1 Introduction

 Les méthodes directes sont utilisées surtout lorsque l’ordre de la

matrice est petit (100×100 par exemple) ou lorsque la matrice est
pleine (peu de coefficient nuls)

 Dans la pratique, beaucoup de pb nécessitent la résolution d’un

système Ax=b d’ordre assez portant avec A une matrice creuse
=> on utilise les méthodes itératives

 l’idée de base des méthodes itératives est, en partant d’une donnée

initiale 𝑥 0 , de construire une suite convergente 𝑥 𝑘 telle que
lim 𝑥 𝑘 = 𝑥
𝑥→∞
où 𝑥 solution de Ax=b.

3
4.2 Construction d’une méthode itérative
 On considère le système linéaire 𝐴𝑥 = 𝑏, avec 𝐴 une matrice
carrée d’ordre 𝑛 inversible et 𝑏 un vecteur de ℝ𝑛 .

 On décompose 𝐴 = 𝑀 − 𝑁 , où M = matice inversible

𝐴𝑥 = 𝑏 ⇔ 𝑀 − 𝑁 𝑥 = 𝑏
⇔ 𝑀𝑥 = 𝑁𝑥 + 𝑏
⇔ 𝑥 = 𝑀−1 𝑁𝑥 + 𝑀−1 b

 En posant 𝐵 = 𝑀−1 𝑁 et 𝐶 = 𝑀−1 b,

𝐴𝑥 = 𝑏 ⇔ 𝑥 = 𝐵𝑥 + 𝐶
Ce qui nous permet de définir la méthode itérative :
𝑥 0 ∈ ℝ𝑛 , vecteur initial
(*) ቊ
𝑥 𝑘+1 = 𝐵𝑥 𝑘 + 𝐶
B=matrice carrée n × n appelée matrice d’itération et
C =vecteur dépendant de b
4
 Remarques
1. On n'a pas toujours besoin de calculer 𝑀 −1 , mais il faut savoir
calculer la solution de 𝑀 𝑥 𝑘+1 = 𝑁𝑥 𝑘 + 𝑏, pour 𝑥 0 donnée.
2. Il est clair que si la suite (𝑥 𝑘 ) converge, elle converge vers la
solution unique 𝑥 de 𝐴𝑥 = 𝑏.
On dit dans ce cas que la méthode itérative correspondante est
convergente pour la résolution de système 𝐴𝑥 = 𝑏.

3. Si on considère 𝑒 𝑘 l'erreur a l‘étape k, 𝑒 𝑘 = |𝑥 𝑘 -𝑥 |,

alors la suite (𝑥 𝑘 ) donnée par la méthode itérative
𝑥 𝑘+1 = 𝐵𝑥 𝑘 + 𝐶, 𝑥 0 ∈ ℝ𝑛 𝑑𝑜𝑛𝑛é𝑒,
converge si la suite (𝑒 𝑘 ) converge vers zéro pour tout choix du
vecteur initial 𝑥 0

5 / 27
Soit 𝐴 = (𝑎𝑖𝑗 )1≤𝑖,𝑗≤𝑛 ∈ 𝑀𝑛 (ℝ ) telle que 𝑎𝑖𝑖 ≠ 0.
Dans les méthodes itératives classiques qu'on va étudier, on utilise la
décomposition suivante:
𝐴 = 𝐷 −𝐸 −𝐹

• La matrice diagonale D qui

représente la diagonale de A

• La matrice triangulaire inférieure E

qui représente l'opposé de la partie
en dessous de la diagonale de A.

• La matrice triangulaire supérieure F

qui représente l'opposé de la partie
au dessus de la diagonale de A.

6 / 27
 Méthode de Jacobi
• Résoudre 𝐴𝑥 = 𝑏 ⇔ 𝐷𝑥 = (𝐸 + 𝐹)𝑥 + 𝑏
• La méthode de Jacobi s’écrit alors
𝑥 0 𝑑𝑜𝑛𝑛é𝑒
ቊ 𝑘+1
𝐷𝑥 = (𝐸 + 𝐹)𝑥 𝑘 + 𝑏

• la matrice diagonale D est inversible (𝑎𝑖𝑖 ≠ 0 pour tout 𝑖 = 1, … , 𝑛).

La matrice d'itération est 𝐵𝐽 = 𝐷−1 (E + F)

• Les composantes de 𝑥 𝑘+1 sont données en fonction de celles de

𝑥 𝑘 par 𝑛
1
𝑥𝑖𝑘+1 = (𝑏 − ෍ 𝑎𝑖𝑗 𝑥𝑖𝑘 ) , 𝑖 = 1, ⋯ , 𝑛
𝑎𝑖𝑖 𝑖
𝑗=1
𝑗≠𝑖
• il est bien de noter qu’on a besoin de stocker tout le vecteur
𝑥 𝑘 pour calculer 𝑥 𝑘+1
7 / 27
  Exemple 1 2 −2
A= 1 1 1
2 2 1

0 −2 2
La matrice d’itération 𝐵𝐽 = 𝐷−1 (E + F)= −1 0 −1
−2 −2 0
 Méthode JOR (Jacobi over relaxation)
Elle est une généralisation de la méthode de Jacobi. On introduit un
paramètre réel non nul 𝜔 et on prend
𝐵𝐽 (𝜔) = 𝜔𝐵𝐽 + 1 − 𝜔 𝐼
Pour ω = 1, elle coïncide avec la méthode de Jacobi.

8 / 27
 Méthode Gauss- Seidel
• Résoudre 𝐴𝑥 = 𝑏 ⇔ (𝐷 − 𝐸)𝑥 = 𝐹𝑥 + 𝑏
• La méthode de Jacobi s’écrit alors
𝑥 0 𝑑𝑜𝑛𝑛é𝑒
ቊ
(𝐷 − 𝐸)𝑥 𝑘+1 = 𝐹𝑥 𝑘 + 𝑏
• la matrice D-E est triang inf inversible. La matrice d'itération est
𝐵𝐺𝑆 = (𝐷 − 𝐸)−1 F

• Les composantes de 𝑥 𝑘+1 sont données en fonction de celles de

𝑥 𝑘 par 1
𝑖−1 𝑛
𝑘+1 𝑘+1
𝑥𝑖 = (𝑏𝑖 − ෍ 𝑎𝑖𝑗 𝑥𝑗 − ෍ 𝑎𝑖𝑗 𝑥𝑗𝑘 ) , 𝑖 = 1, ⋯ , 𝑛
𝑎𝑖𝑖
𝑗=1 𝑗=𝑖+1

• A l’étape k + 1 les valeurs 𝑥𝑖𝑘+1 déjà calculées sont utilisées pour

mettre à jour la solution. On peut utiliser un seul vecteur pour
programmer un seul vecteur
9 / 27
 Exemple 1 2 −2
A= 1 1 1
2 2 1

 Méthode SOR (successive over relaxation)

On introduit un paramètre réel non nul 𝜔 et on prend
𝐵𝐺𝑆 (𝜔) = (I − ω𝐷−1 E)−1 [(1 − ω)I + ω𝐷−1 F].

Pour ω = 1, elle coïncide avec la méthode de Gauss-Seidel.

10 /
4.3 Convergence

 Une méthode itérative de la forme

𝑥 0 ∈ ℝ𝑛 , vecteur initial
(∗) ቊ
𝑥 𝑘+1 = 𝐵𝑥 𝑘 + 𝐶 𝑘≥0
est dite consistante avec 𝐴𝑥 = 𝑏 si C et B sont tel que 𝑥 = 𝐵𝑥 + 𝐶
où B une matrice carrée 𝑛 × 𝑛 et C un vecteur dépendant de b

 Si la méthode (∗) est consistante, la suite de vecteurs 𝑥 𝑘 𝑘 de(∗)

converge vers la solution de 𝐴𝑥 = 𝑏 pour toute donnée initiale 𝑥 0
si et seulement si ρ(B) < 1.

Remarque: Il est important de remarquer que la convergence est

d’autant plus rapide que ρ(B) est petit.

11 /
 Si A est une matrice à diagonale dominante stricte, les méthodes
de Jacobi et de Gauss-Seidel sont convergentes.

 Si A et 2D − A sont symétriques définies positives, alors la

méthode de Jacobi est convergente

 Si A est symétrique définie positive, alors la méthode de JOR

converge si et seulement si 𝜔 ∈ ]0,2[
 Si la méthode de Jacobi converge, alors la méthode JOR converge
pour 0 < ω ≤ 1.

 (Ostrowski) Si A est symétrique définie positive, alors la

méthode SOR converge si et seulement si 0 < ω < 2.

 Si A est à diagonale dominante stricte, SOR converge si 0 < ω ≤ 1.

12
4.4 Vitesse de convergence

 En pratique, entre deux méthodes itératives convergentes, on choisit

celle qui donne la solution plus rapidement que l'autre: tenir compte
de la vitesse de convergence

 Un critère de mesure de cette vitesse est l’évolution de l'erreur

𝑥 𝑘 − 𝑥 qui dépend du rayon spectral de la matrice d'itération.

En effet, si on a une suite convergente 𝑥 𝑘 définie par

𝑥 𝑘+1 = 𝐵𝑥 𝑘 + 𝐶 pour 𝑥 0 donné, sa limite est 𝑥 vérifiant 𝑥 = 𝐵𝑥 + 𝑐,

et on a 𝑥 𝑘 − 𝑥 = 𝐵 𝑥 𝑘−1 − 𝑥 = 𝐵 𝑘 (𝑥 0 − 𝑥)

𝑘
Par conséquent 𝑥 𝑘 − 𝑥 2
= 𝐵 𝑘 (𝑥 0 − 𝑥) 2
≤ 𝐵 2 𝑥0 − 𝑥 2

13
si B est symétrique, alors, 𝐵 2= 𝜌(𝐵)
et il vient
𝑥𝑘 − 𝑥 2
≤ 𝜌(𝐵)𝑘 𝑥 0 − 𝑥 2

Ainsi, la suite 𝑥 𝑘 cv plus vite vers 𝑥 d'autant que 𝜌(𝐵) est plus petit.

 Comparaison de vitesse de convergence de deux méthodes

itératives:
une méthode itérative de matrice d'itération B est dite plus rapide
qu'une autre de matrice d'itération ෩ ෨
𝐵, si ρ(B) < ρ(𝐵).

14
4.5 Critère ou test d’arrêt

• Pour la détermination de x solution d'un problème quelconque

par les méthodes itératives , on construit une suite (𝑥 𝑘 ) qui
converge vers x.

• En pratique, et si on n'exige pas un critère d'arrêt, le nombre

d'itérations pour calculer les termes de cette suite pourrait être
infini.

• Le calcul est donc interrompu des qu'on obtient une solution

approchée à 𝜀 prés, vérifiant par exemple

 𝐴𝑥 𝑘 − 𝑏 ≤ 𝜀

 𝑥 𝑘+1 − 𝑥 𝑘 ≤ 𝜀
pour une tolérance 𝜀 donnée et une norme vectorielle choisie.
15
4.6 Conditionnement

• En pratique, pour un système linéaire Ax = b, les données A et b

ne sont données qu'a une erreur près. Cette perturbation des
données peut engendrer une grande erreur de la solution.

Exemple:
soit le système linéaire Ax = b, pour
1 2 3
A= et b = ,
2 4 + 10−6 6 + 10−6
1
Ce système admet une solution unique x = .
1
ෘ avec 𝑏ෘ = 3
Si on change légèrement b par 𝑏, , la solution
6 − 10−6
5
du système Ax = 𝑏ෘ est 𝑥ු = .
−1

Ainsi une petite perturbation de la donnée b implique une grande

modification de la solution.
16
• La notion du conditionnent d'une matrice peut servir à établir des
majorations des erreurs d'arrondi dues au erreurs sur les données.

Proposition: Soient A et 𝛿A deux matrices d’ordre n, avec A inversible

et soient b et 𝛿 b deux vecteurs tel que b≠ 0.

On remarque que pour 𝛿𝑥 soit assez petit pour une petite

perturbation de b, il suffit que le cond(A) soit aussi assez petit
17