122
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
D´ efinition 4.3 Une matrice M telle que les valeurs propres de αD
−1 E +
α
−1 D
−1 F pour α = 0 ne d´ ependent pas de α (o` u D est la diagonale de M,
et E et F ses parties triangulaires resp. inf´ erieure et sup´ erieure) poss` ede la
A-propri´ et´ e si on peut la d´ ecomposer en 2 × 2 blocs de la forme
M =
˜
D 1
M 12
M 21 ˜
D 2
,
o` u ˜
D 1 et ˜
D 2 sont des matrices diagonales.
Pour des matrices g´ en´ erales, l’Exemple 4.2 montre qu’on ne peut tirer aucune
conclusion a priori sur la convergence des m´ ethodes de Jacobi et de GaussSeidel.
Exemple 4.2 Consid´ erons les syst` emes lin´ eaires 3 × 3 de la forme Aix = bi. On
choisit bi de mani` ere ` a ce que la solution du syst` eme soit le vecteur unit´ e, et les
matrices Ai sont donn´ ees par
A1 =
⎡
⎣
3 0 4
7 4 2
−1 1 2
⎤
⎦ ,
A2 =
⎡
⎣
−3 3 −6
−4 7 −8
5 7 −9
⎤
⎦ ,
A3 =
⎡
⎣
4
1
1
2 −9
0
0 −8 −6
⎤
⎦ ,
A4 =
⎡
⎣
7
6
9
4
5 −4
−7 −3
8
⎤
⎦ .
On peut v´ erifier que la m´ ethode de Jacobi ne converge pas pour A1 (ρ(BJ ) = 1.33),
contrairement `
a celle de Gauss-Seidel. C’est exactement le contraire qui se produit
pour A2 (ρ(BGS) = 1. ¯ 1). La m´ ethode de Jacobi converge plus lentement que celle
de Gauss-Seidel pour la matrice A3 (ρ(BJ ) = 0.44 et ρ(BGS) = 0.018), alors que la
m´ ethode de Jacobi est plus rapide pour A4 (ρ(BJ ) = 0.64 et ρ(BGS) = 0.77).
•
Concluons cette section avec le r´ esultat suivant :
Th´ eor` eme 4.6 Si la m´ ethode de Jacobi converge, alors la m´ ethode JOR
converge pour 0 < ω ≤ 1.
D´ emonstration. D’apr` es (4.12), les valeurs propres de BJ ω sont
µk = ωλk + 1 − ω,
k = 1, . . . , n,
o` u λk sont les valeurs propres de BJ . Alors, en posant λk = rke
iθ k , on a
|µk|
2 = ω
2 r
2
k + 2ωrk cos(θk)(1 − ω) + (1 − ω)
2 ≤ (ωrk + 1 − ω)
2 ,
qui est strictement inf´ erieur `
a 1 si 0 < ω ≤ 1.
3
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
D´ efinition 4.3 Une matrice M telle que les valeurs propres de αD
−1 E +
α
−1 D
−1 F pour α = 0 ne d´ ependent pas de α (o` u D est la diagonale de M,
et E et F ses parties triangulaires resp. inf´ erieure et sup´ erieure) poss` ede la
A-propri´ et´ e si on peut la d´ ecomposer en 2 × 2 blocs de la forme
M =
˜
D 1
M 12
M 21 ˜
D 2
,
o` u ˜
D 1 et ˜
D 2 sont des matrices diagonales.
Pour des matrices g´ en´ erales, l’Exemple 4.2 montre qu’on ne peut tirer aucune
conclusion a priori sur la convergence des m´ ethodes de Jacobi et de GaussSeidel.
Exemple 4.2 Consid´ erons les syst` emes lin´ eaires 3 × 3 de la forme Aix = bi. On
choisit bi de mani` ere ` a ce que la solution du syst` eme soit le vecteur unit´ e, et les
matrices Ai sont donn´ ees par
A1 =
⎡
⎣
3 0 4
7 4 2
−1 1 2
⎤
⎦ ,
A2 =
⎡
⎣
−3 3 −6
−4 7 −8
5 7 −9
⎤
⎦ ,
A3 =
⎡
⎣
4
1
1
2 −9
0
0 −8 −6
⎤
⎦ ,
A4 =
⎡
⎣
7
6
9
4
5 −4
−7 −3
8
⎤
⎦ .
On peut v´ erifier que la m´ ethode de Jacobi ne converge pas pour A1 (ρ(BJ ) = 1.33),
contrairement `
a celle de Gauss-Seidel. C’est exactement le contraire qui se produit
pour A2 (ρ(BGS) = 1. ¯ 1). La m´ ethode de Jacobi converge plus lentement que celle
de Gauss-Seidel pour la matrice A3 (ρ(BJ ) = 0.44 et ρ(BGS) = 0.018), alors que la
m´ ethode de Jacobi est plus rapide pour A4 (ρ(BJ ) = 0.64 et ρ(BGS) = 0.77).
•
Concluons cette section avec le r´ esultat suivant :
Th´ eor` eme 4.6 Si la m´ ethode de Jacobi converge, alors la m´ ethode JOR
converge pour 0 < ω ≤ 1.
D´ emonstration. D’apr` es (4.12), les valeurs propres de BJ ω sont
µk = ωλk + 1 − ω,
k = 1, . . . , n,
o` u λk sont les valeurs propres de BJ . Alors, en posant λk = rke
iθ k , on a
|µk|
2 = ω
2 r
2
k + 2ωrk cos(θk)(1 − ω) + (1 − ω)
2 ≤ (ωrk + 1 − ω)
2 ,
qui est strictement inf´ erieur `
a 1 si 0 < ω ≤ 1.
3