Chapitre 1
Méthodes Itératives
Les méthodes directes sont très efficaces : elles donnent la solution exacte
(aux erreurs d’arrondi près) du système linéaire considéré. Elles ont l’in-
convénient de nécessiter une assez grande place mémoire car elles nécessitent
le stockage de toute la matrice en mémoire vive.
1.1 Principes et définitions
Soit A une matrice inversible et b un vecteur de RN . On cherche à re-
soudre l’équation Ax = b (1). Le principe de base est d’engendrer une suite
de vecteurs x(k) (les itérés) convergente vers la solution x de (1).
Partant d’un vecteur arbitraire x(0) , on construit (x(k) ) définie par
x(k+1) = Bx(k) + c (2)
avec B une matrice et c un vecteur.
Définition : Une méthode itérative (2) est dite convergente si pour tout
x(0) , on a x(k) → x quand k tend vers ∞ et la limite x est solution de (1).
On veut que cette suite soit simple à calculer. L’idée est de trouver une
matrice P proche de A est facile à inverser.
Si on écrit A sous la forme A− = P − (P − A) = P − N , alors sytème Ax = b
devient P x = (P − A)x + b = N x + b. Cette relation suggère la construction
de la suite x(x) à partir d’un choix initial x(0) donné, la formule suivante
P x(k+1) = N x(k) + b (2∗)
ce qui peut également s’écrire x(k+1) = Bx(k) + c, avec B = P −1 (P − A) et
c = P −1 b.
Remarque 1.1.1 Si x(k) tend vers x̄, alors on a P x̄ = N x̄ + b, ie Ax̄ = b.
Donc si la suite définie par (2*) converge alors elle converge la solution du
système.
1
Page 2
Définition L’erreur d’approximation s’écrit
e(k) = x(k) − x = B(x(k−1) − x) = B k (x(0) − x) = e(0) .
Une méthode itérative (2) est convergente si pour tout x(0) , limk→∞ e(k) = 0.
lim e(k) = 0 ≡ lim B k = 0 ≡ lim kBkk = 0 pour toute norme matricielle
k→∞ k→∞ k→∞
Theorem 1.1.1 (convergence des méthodes itératives) Soient A et P
deux matrices inversibles. Soit x(0) donné et (x(k) ) la suite définie par (2*).
Alors
1. la suite (x(k) ) converge quel que soit x(0) donné ssi ρ(B) < 1.
2. la suite (x(k) ) converge quel que soit x(0) donné ssi limk→∞ B k = 0
où ρ(B) = maxi |λi (B)| est le rayon spectral. Les λi sont les valeurs
propres de B.
x(k+1) − x̄ x(k+1) − x(k)
lim = ρ(B) lim = ρ(B).
x(k) − x̄ x(k) − x(k−1)
1.2 Méthode de Richardson
Une méthode simpliste consiste à prendre P = I (matrice identité),
alors la matrice B = I − A. On verra par un exemple que cette méthode ne
converge pas forcement.
Si on pose P = βI alors B = I − β1 A ≡ I − αA avec α = β1 . On obtient la
méthode dite de Richardson, elle est généralement donnée sous la forme
(
x(0) ∈ Rn donné
x(k+1) = x(k) + αr (k) ,
où r (k) = b − Ax(k) appelé residue.
1.3 Méthode de Jacobi
On suppose que les coefficients aii 6= 0 et on décompose A = D − E − F
avec D la diagonale de A, −E la partie inférieure stricte de A et −F la
partie supérieure stricte de A. On pose P = D, alors BJ = D −1 (E + F ).
(
x(0) donné
Dx(k+1) = (E + F )x(k) + b
ou alors
x(k+1) = D −1 (E + F )x(k) + D −1 b = BJ x(k) + c
Analyse Numérique & EDO M. Mbehou UY1
Page 3
(k+1) (k)
X
xi = aij xj + bi /aii
j=1,j6=i
(k) (k)
X X
= aij x − aij x + bi /aii .
j j
j<i j>i
La méthode de Jacobi converge ssi ρ(BJ ) < 1.
1.4 Méthode de Gauss-Seidel
Pour cette méthode, P = D − E, alors BGS = (D − E)−1 F
(
x(0) donné
(D − E)x(k+1) = F x(k) + b
D − E est une matrice triangulaire inférieure et pour calculer x(k+1) en
fonction de x(k) , il suffit d’appliquer l’algorithme de descente :
i−1 N
(k+1) (k+1) (k)
X X
xi = − aij xj − aij xj + bi /aii .
j=1 j=i+1
La méthode converge ssi ρ(BGS ) < 1.
Theorem 1.4.1 (Comparaison de Jacobi et G-S pour les matrices tridiagonales)
On considère une matrice A tridiagonale, ie.. telle que aij = 0 si |i − j| > 1 ;
soient BGS et BJ les matrices d’itération respectives des méthodes de Gauss-
Seidel et Jacobi, alors :
ρ(BGS ) = (ρ(BJ ))2 .
Pour les matrices tridiagonales, la méthode de Gauss-Seidel converge (ou
diverge) donc plus vite que celle de Jacobi.
Preuve 1.4.1 La démo de ce résultat se fait en montrant que pour les ma-
trices tridiagonales, λ est valeur propre de la matrice d’itération de Jacobi
ssi λ2 est valeur propre de la matrice d’itération de Gauss-Seidel.
2 −1
Exercice On considère la matrice A = . I- On pose P = I.
−1 2
Ecrire la méthode simpliste associée à la matrice A.
1. Déterminer les valeurs propres ainsi que les vecteurs propres associés
à la matrice d’itération B.
2. En déduire que la methode diverge.
Analyse Numérique & EDO M. Mbehou UY1
Page 4
3. On suppose qu’il existe a, b ∈ R tel que e(0) = au1 + bu2 où u1 et u2
sont les vecteurs propres B. Montrer que si a 6= 0 alors |e(k) | tend vers
l’infini quand k tend vers l’infini.
II- On pose P = α1 I. On considère la méthode de Richardson.
1. Montrer que la méthode de Richardson est équivalente à
(
x(0) donné
x(k+1) = Bx(k) + c
où les matrices B et c sont à déterminer.
2. Pour quelle(s) valeur(s) de α la méthode est-elle convergente.
3. Quelle est la valeur de α qui minimise le rayon spectral. En déduire la
valeur de α pour laquelle on a la meilleur convergence.
III- Ecrire la méthode de Jacobi associée ‘a A et étudier sa convergence.
1.5 Méthode de relaxation (SOR)
Soit ω un réel non nul. On décompose A = (D/ω − E) + (D − D/ω − F ).
si on pose N = (D − D/ω − F ), alors P = (D/ω − E) et Bω = P −1 N . La
méthode s’écrit
(
x(0) donné
(D/ω − E)x(k+1) = ((1 − ω)/ωD + F )x(k) + b.
ou bien (
x(0) donné
x(k+1) = Bω x(k) + c
Pour ω = 1 on retrouve la méthode de Gauss-Seidel.
Si on note
i−1 N
(k+1/2) (k+1) (k)
X X
xi = − aij xj − aij xj + bi /aii
j=1 j=i+1
alors
(k+1) (k) (k+1/2) (k)
xi = xi + ω(xi − xi ).
Exo : Demontrer la relation précédente.
Proposition 1.5.1 (CN de la convergence de SOR) Soit A une ma-
trice carrée d’ordre n. Soit Bω la matrice d’itération associée à la méthode
de SOR.
Si ρ(Bω ) < 1 alors 0 < ω < 2.
Analyse Numérique & EDO M. Mbehou UY1
Page 5
Preuve 1.5.1 Calculer det(Bω ). On rappelle que Bω = P −1 N et que les
matrices P et N sont triangulaires donc leurs déterminants sont les produits
des coefficients diagonaux. On a donc
( 1−ω n
ω ) det(D)
det(Bω ) = det(P −1 )det(N ) = = (1 − ω)n .
( ω1 )n det(D)
Or le déterminant d’une matrice est aussi le produit des ses valeurs propres
(comptés avec leurs multiplicités), dont les valeurs absolues sont toutes inférieures
au rayon spectral. On a donc |det(Bω )| = |(1 − ω)n | ≤ (ρ(Bω ))n , d’où le
résultat.
Lemma 1.5.1 (CS de la convergence de SOR pour SDP) Soit A une
matrice SDP. Soit P et N avec A = P − N telle que P est inversible. Si
P t + N est SDP, alors ρ(P −1 N ) = ρ(B) < 1 et donc la méthode SOR
converge.
Theorem 1.5.1 (CNS de la convergence de SOR pour SDP) Soit A
une matrice SDP. Soit Bω avec ω 6= 0 la matrice d’itération associée à la
méthode SOR. Alors
ρ(Bω ) < 1 ssi 0 < ω < 2.
En particulier la méthode de Gauss-Seidel converge pour les matrices SDP.
Preuve 1.5.2 Si ρ(Bω ) < 1, d’après la proposition ci-dessus, on 0 < ω < 2.
Pour la réciproque d’après le lemme, il suffit de montrer que P t +N est SDP.
Or P t = (D/ω − E)t = (D/ω − F ) et P t + N = 2−ω ω D qui est bien sdp.
Test d’arrêt
D’une manière idéale, une méthode itérative poursuit les itérations jusqu’à ce
que une approximation x(k) de la solution exacte x est obtenue. En pratique,
x étant inconnu, les méthodes itératives s’arrêtent quand un test d’arrêt basé
sur quelconque information disponible est satisfait. Les deux tests d’arrêt
les plus communs sont basés sur
1) l’incrément de la solution approchée, ie. kx(k+1) − x(k) k ≤ T ol
2) le résidu de la solution approchée, ie kr (k) k = kb − Ax(k) k ≤ T ol.
Analyse Numérique & EDO M. Mbehou UY1