160
5 Systèmes linéaires
pour n’importe quelle donnée initiale x
(0)
∈ R
n . On peut par exemple
considérer la relation de récurrence suivante
x
(k+1) = Bx
(k) + g,
k ≥ 0,
(5.45)
où B est une matrice bien choisie (dépendant de A) et g est un vecteur
(dépendant de A et b), qui vérifient la relation de consistance
x = Bx + g.
(5.46)
Comme x = A
−1
b, ceci implique g = (I − B)A
−1
b.
Soit e
(k) = x − x
(k) l’erreur à l’étape k. En soustrayant (5.45) de
(5.46), on obtient
e
(k+1) = Be
(k) .
Pour cette raison, on appelle B matrice d’itération associée à (5.45). Si
B est symétrique définie positive, on a d’après (5.25)
e
(k+1)
= Be
(k)
≤ ρ(B)e
(k)
,
∀k ≥ 0,
où ρ(B) désigne le rayon spectral de B, c’est-à-dire le plus grand module
des valeurs propres de B. Si B est symétrique définie positive, alors ρ(B)
est égal à la plus grande valeur propre de B. En itérant cette relation,
on obtient
e
(k)
≤ [ρ(B)]
k
e
(0)
, k ≥ 0.
(5.47)
Donc, si ρ(B) < 1, alors e
(k)
→ 0 quand k → ∞ pour tout e
(0) (et donc
pour tout x
(0) ), autrement dit la méthode converge. Cette condition
suffisante est également nécessaire.
Si, par chance, on connaissait une valeur approchée de ρ(B), (5.47)
nous permettrait de déduire le nombre minimum d’itérations k min nécessaire pour multiplier l’erreur initiale par facteur ε. En effet, k min serait
alors le plus petit entier positif pour lequel [ρ(B)]
kmin
≤ ε.
En conclusion, pour une matrice quelconque, on a le résultat suivant
Proposition 5.2 Pour une méthode itérative de la forme (5.45)
dont la matrice d’itération satisfait (5.46), 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é.