116
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Consid´ erons, pour commencer, les m´ ethodes it´ eratives de la forme
x
(0) donn´ e, x
(k+1) = Bx
(k) + f , k ≥ 0,
(4.2)
o` u B d´ esigne une matrice carr´ ee n × n appel´ ee matrice d’it´ eration et o` u f est
un vecteur d´ ependant de b (le second membre du syst` eme ` a r´ esoudre).
D´ efinition 4.1 Une m´ ethode it´ erative de la forme (4.2) est dite consistante
avec (3.2) si f et B sont tels que x = Bx + f , x ´ etant la solution de (3.2), ou,
de mani` ere ´ equivalente, si f et B satisfont
f = (I − B)A
−1 b.
Si on note
e
(k) = x
(k)
− x
(4.3)
l’erreur `
a l’it´ eration k, la condition (4.1) revient `
a lim
k→∞
e
(k) = 0 pour toute
valeur initiale x
(0) .
La seule propri´ et´ e de consistance ne suffit pas ` a assurer la convergence
d’une m´ ethode it´ erative, comme le montre l’exemple suivant.
Exemple 4.1 On veut r´ esoudre le syst` eme lin´ eaire 2Ix = b avec la m´ ethode it´ erative
x
(k+1) = −x
(k) + b,
qui est clairement consistante. Cette suite n’est pas convergente pour une donn´ ee
initiale arbitraire. Si par exemple x
(0) = 0, la m´ ethode donne x
(2k) = 0, x
(2k+1) = b,
k = 0, 1, . . ..
En revanche, si x
(0) =
1
2
b la m´ ethode est convergente.
•
Th´ eor` eme 4.1 Si la m´ ethode (4.2) est consistante, la suite de vecteurs
x
(k)
de (4.2) converge vers la solution de (3.2) pour toute donn´ ee initiale
x
(0) si et seulement si ρ(B) < 1.
D´ emonstration. D’apr` es (4.3), et grˆ ace `
a l’hypoth` ese de consistance, on a
e
(k+1) = Be
(k) , d’o` u
e
(k) = B
k e
(0)
∀k = 0, 1, . . .
(4.4)
Il r´ esulte donc du Th´ eor` eme 1.5 que lim
k→∞
B
k e
(0) = 0 pour tout e
(0) si et seulement
si ρ(B) < 1.
R´ eciproquement, supposons que ρ(B) > 1, alors il existe au moins une valeur
propre λ(B) de module plus grand que 1. Soit e
(0) un vecteur propre associ´ e ` a λ ;
alors, Be
(0) = λe
(0) et donc, e
(k) = λ
k e
(0) . Comme |λ| > 1, e
(k) ne peut pas tendre
vers 0 quand k → ∞.
3
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Consid´ erons, pour commencer, les m´ ethodes it´ eratives de la forme
x
(0) donn´ e, x
(k+1) = Bx
(k) + f , k ≥ 0,
(4.2)
o` u B d´ esigne une matrice carr´ ee n × n appel´ ee matrice d’it´ eration et o` u f est
un vecteur d´ ependant de b (le second membre du syst` eme ` a r´ esoudre).
D´ efinition 4.1 Une m´ ethode it´ erative de la forme (4.2) est dite consistante
avec (3.2) si f et B sont tels que x = Bx + f , x ´ etant la solution de (3.2), ou,
de mani` ere ´ equivalente, si f et B satisfont
f = (I − B)A
−1 b.
Si on note
e
(k) = x
(k)
− x
(4.3)
l’erreur `
a l’it´ eration k, la condition (4.1) revient `
a lim
k→∞
e
(k) = 0 pour toute
valeur initiale x
(0) .
La seule propri´ et´ e de consistance ne suffit pas ` a assurer la convergence
d’une m´ ethode it´ erative, comme le montre l’exemple suivant.
Exemple 4.1 On veut r´ esoudre le syst` eme lin´ eaire 2Ix = b avec la m´ ethode it´ erative
x
(k+1) = −x
(k) + b,
qui est clairement consistante. Cette suite n’est pas convergente pour une donn´ ee
initiale arbitraire. Si par exemple x
(0) = 0, la m´ ethode donne x
(2k) = 0, x
(2k+1) = b,
k = 0, 1, . . ..
En revanche, si x
(0) =
1
2
b la m´ ethode est convergente.
•
Th´ eor` eme 4.1 Si la m´ ethode (4.2) est consistante, la suite de vecteurs
x
(k)
de (4.2) converge vers la solution de (3.2) pour toute donn´ ee initiale
x
(0) si et seulement si ρ(B) < 1.
D´ emonstration. D’apr` es (4.3), et grˆ ace `
a l’hypoth` ese de consistance, on a
e
(k+1) = Be
(k) , d’o` u
e
(k) = B
k e
(0)
∀k = 0, 1, . . .
(4.4)
Il r´ esulte donc du Th´ eor` eme 1.5 que lim
k→∞
B
k e
(0) = 0 pour tout e
(0) si et seulement
si ρ(B) < 1.
R´ eciproquement, supposons que ρ(B) > 1, alors il existe au moins une valeur
propre λ(B) de module plus grand que 1. Soit e
(0) un vecteur propre associ´ e ` a λ ;
alors, Be
(0) = λe
(0) et donc, e
(k) = λ
k e
(0) . Comme |λ| > 1, e
(k) ne peut pas tendre
vers 0 quand k → ∞.
3