130
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Le choix d’un bon pr´ econditionneur est donc d’une importance capitale pour
am´ eliorer la convergence d’une m´ ethode de Richardson. Mais il faut bien sˆ ur
faire ce choix en tˆ achant de conserver un coˆ ut de calcul aussi bas que possible.
Nous d´ ecrirons ` a la Section 4.3.2 quelques pr´ econditionneurs couramment utilis´ es dans la pratique.
Corollaire 4.1 Si A est une matrice sym´ etrique d´ efinie positive, de valeurs
propres λ 1 ≥ λ 2 ≥ . . . ≥ λ n . Alors, si 0 < α < 2/λ 1 , la m´ ethode de Richardson stationnaire non pr´ econditionn´ ee est convergente et
e
(k+1)
A ≤ ρ(R α )e
(k)
A , k ≥ 0.
(4.29)
On a le mˆ eme r´ esultat pour la m´ ethode de Richardson pr´ econditionn´ ee, `
a
condition que les matrices P, A et P
−1 A soient sym´ etriques d´ efinies positives.
D´ emonstration. La convergence est une cons´ equence du Th´ eor` eme 4.8. On remarque de plus que
e
(k+1) A = Rαe
(k) A = A
1/2 Rαe
(k) 2 ≤ ≤A
1/2 RαA
−1/2 2A
1/2 e
(k) 2.
La matrice Rα est sym´ etrique d´ efinie positive et semblable `
a A
1/2 RαA
−1/2 . Par
cons´ equent
A
1/2 RαA
−1/2 2 = ρ(Rα).
On en d´ eduit (4.29) en notant que A
1/2 e
(k) 2 = e
(k) A. On peut faire une preuve
analogue dans le cas pr´ econditionn´ e en rempla¸ cant A par P
−1 A.
3
Notons enfin que l’in´ egalit´ e (4.29) reste vraie mˆ eme quand seules P et A sont
sym´ etriques d´ efinies positives (pour la preuve, voir p. ex. [QV94], Chapitre
2).
4.3.2 Matrices de pr´ econditionnement
Toutes les m´ ethodes de la section pr´ ec´ edente peuvent ˆ etre ´ ecrites sous la
forme (4.2). On peut donc les voir comme des m´ ethodes pour r´ esoudre le
syst` eme
(I − B)x = f = P
−1 b.
D’autre part, puisque B=P
−1 N, le syst` eme (3.2) peut s’´ ecrire
P
−1 Ax = P
−1 b.
(4.30)
Ce dernier syst` eme s’appelle syst` eme pr´ econditionn´ e, et P est la matrice de
pr´ econditionnement ou pr´ econditionneur `
a gauche. On peut d´ efinir de mˆ eme
des pr´ econditionneurs ` a droite et des pr´ econditionneurs centr´ es, si le syst` eme (3.2) est transform´ e respectivement en
AP
−1 y = b, y = Px,
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
Le choix d’un bon pr´ econditionneur est donc d’une importance capitale pour
am´ eliorer la convergence d’une m´ ethode de Richardson. Mais il faut bien sˆ ur
faire ce choix en tˆ achant de conserver un coˆ ut de calcul aussi bas que possible.
Nous d´ ecrirons ` a la Section 4.3.2 quelques pr´ econditionneurs couramment utilis´ es dans la pratique.
Corollaire 4.1 Si A est une matrice sym´ etrique d´ efinie positive, de valeurs
propres λ 1 ≥ λ 2 ≥ . . . ≥ λ n . Alors, si 0 < α < 2/λ 1 , la m´ ethode de Richardson stationnaire non pr´ econditionn´ ee est convergente et
e
(k+1)
A ≤ ρ(R α )e
(k)
A , k ≥ 0.
(4.29)
On a le mˆ eme r´ esultat pour la m´ ethode de Richardson pr´ econditionn´ ee, `
a
condition que les matrices P, A et P
−1 A soient sym´ etriques d´ efinies positives.
D´ emonstration. La convergence est une cons´ equence du Th´ eor` eme 4.8. On remarque de plus que
e
(k+1) A = Rαe
(k) A = A
1/2 Rαe
(k) 2 ≤ ≤A
1/2 RαA
−1/2 2A
1/2 e
(k) 2.
La matrice Rα est sym´ etrique d´ efinie positive et semblable `
a A
1/2 RαA
−1/2 . Par
cons´ equent
A
1/2 RαA
−1/2 2 = ρ(Rα).
On en d´ eduit (4.29) en notant que A
1/2 e
(k) 2 = e
(k) A. On peut faire une preuve
analogue dans le cas pr´ econditionn´ e en rempla¸ cant A par P
−1 A.
3
Notons enfin que l’in´ egalit´ e (4.29) reste vraie mˆ eme quand seules P et A sont
sym´ etriques d´ efinies positives (pour la preuve, voir p. ex. [QV94], Chapitre
2).
4.3.2 Matrices de pr´ econditionnement
Toutes les m´ ethodes de la section pr´ ec´ edente peuvent ˆ etre ´ ecrites sous la
forme (4.2). On peut donc les voir comme des m´ ethodes pour r´ esoudre le
syst` eme
(I − B)x = f = P
−1 b.
D’autre part, puisque B=P
−1 N, le syst` eme (3.2) peut s’´ ecrire
P
−1 Ax = P
−1 b.
(4.30)
Ce dernier syst` eme s’appelle syst` eme pr´ econditionn´ e, et P est la matrice de
pr´ econditionnement ou pr´ econditionneur `
a gauche. On peut d´ efinir de mˆ eme
des pr´ econditionneurs ` a droite et des pr´ econditionneurs centr´ es, si le syst` eme (3.2) est transform´ e respectivement en
AP
−1 y = b, y = Px,