4.2 M´ ethodes it´ eratives lin´ eaires
123
4.2.3 R´ esultats de convergence pour la m´ ethode de relaxation
Sans hypoth` ese particuli` ere sur A, on peut d´ eterminer les valeurs de ω pour
lesquelles la m´ ethode SOR ne peut pas converger :
Th´ eor` eme 4.7 On a ρ(B(ω)) ≥ |ω − 1| ∀ω ∈ R. La m´ ethode SOR diverge
donc si ω ≤ 0 ou ω ≥ 2.
D´ emonstration. Si {λi} d´ esigne l’ensemble des valeurs propres de la matrice
d’it´ eration de SOR, alors
n
i=1
λi
=
det
(1 − ω)I + ωD
−1 F
= |1 − ω|
n .
Par cons´ equent, au moins une valeur propre λi est telle que |λi| ≥ |1 − ω|. Pour
avoir convergence, il est donc n´ ecessaire que |1 − ω| < 1, c’est-` a-dire 0 < ω < 2. 3
Si on suppose A sym´ etrique d´ efinie positive, la condition n´ ecessaire 0 < ω < 2
devient suffisante pour avoir convergence. On a en effet le r´ esultat suivant
(voir p. ex. [Hac94] pour la preuve) :
Propri´ et´ e 4.3 (Ostrowski) Si A est sym´ etrique d´ efinie positive, alors la
m´ ethode SOR converge si et seulement si 0 < ω < 2. De plus, sa convergence
est monotone pour · · A .
Enfin, si A est ` a diagonale dominante stricte, SOR converge si 0 < ω ≤ 1.
Les r´ esultats ci-dessus montrent que SOR converge plus ou moins vite selon le choix du param` etre de relaxation ω. On ne peut donner de r´ eponses
satisfaisantes ` a la question du choix du param` etre optimal ω opt (i.e. pour
lequel le taux de convergence est le plus grand) seulement dans des cas particuliers (voir par exemple [Axe94], [You71], [Var62] ou [Wac66]). Nous nous
contenterons ici de citer le r´ esultat suivant (dont la preuve se trouve dans
[Axe94]).
Propri´ et´ e 4.4 Si la matrice A poss` ede la A-propri´ et´ e et si les valeurs propres
de B J sont r´ eelles, alors la m´ ethode SOR converge pour toute donn´ ee initiale
x
(0) si et seulement si ρ(B J ) < 1 et 0 < ω < 2. De plus,
ω opt =
2
1 +
1 − ρ(B J ) 2
(4.19)
et le facteur de convergence asymptotique est donn´ e par
ρ(B(ω opt )) =
1 −
1 − ρ(B J ) 2
1 +
1 − ρ(B J ) 2
.
123
4.2.3 R´ esultats de convergence pour la m´ ethode de relaxation
Sans hypoth` ese particuli` ere sur A, on peut d´ eterminer les valeurs de ω pour
lesquelles la m´ ethode SOR ne peut pas converger :
Th´ eor` eme 4.7 On a ρ(B(ω)) ≥ |ω − 1| ∀ω ∈ R. La m´ ethode SOR diverge
donc si ω ≤ 0 ou ω ≥ 2.
D´ emonstration. Si {λi} d´ esigne l’ensemble des valeurs propres de la matrice
d’it´ eration de SOR, alors
n
i=1
λi
=
det
(1 − ω)I + ωD
−1 F
= |1 − ω|
n .
Par cons´ equent, au moins une valeur propre λi est telle que |λi| ≥ |1 − ω|. Pour
avoir convergence, il est donc n´ ecessaire que |1 − ω| < 1, c’est-` a-dire 0 < ω < 2. 3
Si on suppose A sym´ etrique d´ efinie positive, la condition n´ ecessaire 0 < ω < 2
devient suffisante pour avoir convergence. On a en effet le r´ esultat suivant
(voir p. ex. [Hac94] pour la preuve) :
Propri´ et´ e 4.3 (Ostrowski) Si A est sym´ etrique d´ efinie positive, alors la
m´ ethode SOR converge si et seulement si 0 < ω < 2. De plus, sa convergence
est monotone pour · · A .
Enfin, si A est ` a diagonale dominante stricte, SOR converge si 0 < ω ≤ 1.
Les r´ esultats ci-dessus montrent que SOR converge plus ou moins vite selon le choix du param` etre de relaxation ω. On ne peut donner de r´ eponses
satisfaisantes ` a la question du choix du param` etre optimal ω opt (i.e. pour
lequel le taux de convergence est le plus grand) seulement dans des cas particuliers (voir par exemple [Axe94], [You71], [Var62] ou [Wac66]). Nous nous
contenterons ici de citer le r´ esultat suivant (dont la preuve se trouve dans
[Axe94]).
Propri´ et´ e 4.4 Si la matrice A poss` ede la A-propri´ et´ e et si les valeurs propres
de B J sont r´ eelles, alors la m´ ethode SOR converge pour toute donn´ ee initiale
x
(0) si et seulement si ρ(B J ) < 1 et 0 < ω < 2. De plus,
ω opt =
2
1 +
1 − ρ(B J ) 2
(4.19)
et le facteur de convergence asymptotique est donn´ e par
ρ(B(ω opt )) =
1 −
1 − ρ(B J ) 2
1 +
1 − ρ(B J ) 2
.