146
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
La k-i` eme it´ eration de la m´ ethode du gradient conjugu´ e n’est bien d´ efinie que
si la direction de descente p
(k) est non nulle. En outre, si p
(k) = 0, alors l’it´ er´ ee
x
(k) doit co¨ ıncider avec la solution x du syst` eme. De plus, on peut montrer
(voir [Axe94], p. 463), ind´ ependamment du param` etre β k , que la suite x
(k)
g´ en´ er´ ee par GC satisfait la propri´ et´ e suivante : ou bien x
(k)
= x, p
(k)
= 0,
α k = 0 pour tout k, ou bien il existe un entier m tel que x
(m) = x, o` u x
(k)
= x,
p
(k)
= 0 et α k = 0 pour k = 0, 1, . . ., m − 1.
Le choix particulier fait pour β k en (4.46) assure que m ≤ n. En l’absence d’erreur d’arrondi, la m´ ethode du gradient conjugu´ e peut donc ˆ etre vue
comme une m´ ethode directe puisqu’elle converge en un nombre fini d’´ etapes.
N´ eanmoins, pour les matrices de grandes tailles, elle est g´ en´ eralement utilis´ ee
comme m´ ethode it´ erative puisqu’on l’interrompt d` es que l’erreur devient inf´ erieure ` a une tol´ erance fix´ ee. De ce point de vue, la d´ ependance de l’erreur
par rapport au conditionnement de la matrice est plus favorable que pour
la m´ ethode du gradient. Signalons ´ egalement que l’estimation (4.48) est souvent beaucoup trop pessimiste et ne prend pas en compte le fait que dans
cette m´ ethode, et contrairement `
a la m´ ethode du gradient, la convergence est
influenc´ ee par la totalit´ e du spectre de A, et pas seulement par les valeurs
propres extr´ emales.
Remarque 4.3 (effet des erreurs d’arrondi) La m´ ethode du gradient
conjugu´ e ne converge en un nombre fini d’´ etapes qu’en arithm´ etique exacte.
L’accumulation des erreurs d’arrondi d´ etruit l’A-orthogonalit´ e des directions
de descente et peut mˆ eme provoquer des divisions par z´ ero lors du calcul des
coefficients α k et β k . Ce dernier ph´ enom` ene (appel´ e breakdown dans la litt´ erature anglo-saxonne) peut ˆ etre ´ evit´ e grˆ ace ` a des proc´ ed´ es de stabilisation ;
on parle alors de m´ ethodes de gradient stabilis´ ees.
Il se peut, malgr´ e ces strat´ egies, que GC ne converge pas (en arithm´ etique
finie) apr` es n it´ erations. Dans ce cas, la seule possibilit´ e raisonnable est de
red´ emarrer les it´ erations avec le dernier r´ esidu calcul´ e. On obtient alors la
m´ ethode du gradient conjugu´ e cyclique ou m´ ethode du gradient conjugu´ e avec
red´ emarrage, qui ne poss` ede pas les propri´ et´ es de convergence de GC.
4.3.5 La m´ ethode du gradient conjugu´ e pr´ econditionn´ e
Si P est une matrice de pr´ econditionnement sym´ etrique d´ efinie positive, la
m´ ethode du gradient conjugu´ e pr´ econditionn´ e consiste ` a appliquer la m´ ethode
du gradient conjugu´ e au syst` eme pr´ econditionn´ e
P
−1/2 AP
−1/2 y = P
−1/2 b
avec y = P
1/2 x.
En pratique, la m´ ethode est impl´ ement´ ee sans calculer explicitement P
1/2 ou
P
−1/2 . Apr` es un peu d’alg` ebre, on obtient le sch´ ema suivant :
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
La k-i` eme it´ eration de la m´ ethode du gradient conjugu´ e n’est bien d´ efinie que
si la direction de descente p
(k) est non nulle. En outre, si p
(k) = 0, alors l’it´ er´ ee
x
(k) doit co¨ ıncider avec la solution x du syst` eme. De plus, on peut montrer
(voir [Axe94], p. 463), ind´ ependamment du param` etre β k , que la suite x
(k)
g´ en´ er´ ee par GC satisfait la propri´ et´ e suivante : ou bien x
(k)
= x, p
(k)
= 0,
α k = 0 pour tout k, ou bien il existe un entier m tel que x
(m) = x, o` u x
(k)
= x,
p
(k)
= 0 et α k = 0 pour k = 0, 1, . . ., m − 1.
Le choix particulier fait pour β k en (4.46) assure que m ≤ n. En l’absence d’erreur d’arrondi, la m´ ethode du gradient conjugu´ e peut donc ˆ etre vue
comme une m´ ethode directe puisqu’elle converge en un nombre fini d’´ etapes.
N´ eanmoins, pour les matrices de grandes tailles, elle est g´ en´ eralement utilis´ ee
comme m´ ethode it´ erative puisqu’on l’interrompt d` es que l’erreur devient inf´ erieure ` a une tol´ erance fix´ ee. De ce point de vue, la d´ ependance de l’erreur
par rapport au conditionnement de la matrice est plus favorable que pour
la m´ ethode du gradient. Signalons ´ egalement que l’estimation (4.48) est souvent beaucoup trop pessimiste et ne prend pas en compte le fait que dans
cette m´ ethode, et contrairement `
a la m´ ethode du gradient, la convergence est
influenc´ ee par la totalit´ e du spectre de A, et pas seulement par les valeurs
propres extr´ emales.
Remarque 4.3 (effet des erreurs d’arrondi) La m´ ethode du gradient
conjugu´ e ne converge en un nombre fini d’´ etapes qu’en arithm´ etique exacte.
L’accumulation des erreurs d’arrondi d´ etruit l’A-orthogonalit´ e des directions
de descente et peut mˆ eme provoquer des divisions par z´ ero lors du calcul des
coefficients α k et β k . Ce dernier ph´ enom` ene (appel´ e breakdown dans la litt´ erature anglo-saxonne) peut ˆ etre ´ evit´ e grˆ ace ` a des proc´ ed´ es de stabilisation ;
on parle alors de m´ ethodes de gradient stabilis´ ees.
Il se peut, malgr´ e ces strat´ egies, que GC ne converge pas (en arithm´ etique
finie) apr` es n it´ erations. Dans ce cas, la seule possibilit´ e raisonnable est de
red´ emarrer les it´ erations avec le dernier r´ esidu calcul´ e. On obtient alors la
m´ ethode du gradient conjugu´ e cyclique ou m´ ethode du gradient conjugu´ e avec
red´ emarrage, qui ne poss` ede pas les propri´ et´ es de convergence de GC.
4.3.5 La m´ ethode du gradient conjugu´ e pr´ econditionn´ e
Si P est une matrice de pr´ econditionnement sym´ etrique d´ efinie positive, la
m´ ethode du gradient conjugu´ e pr´ econditionn´ e consiste ` a appliquer la m´ ethode
du gradient conjugu´ e au syst` eme pr´ econditionn´ e
P
−1/2 AP
−1/2 y = P
−1/2 b
avec y = P
1/2 x.
En pratique, la m´ ethode est impl´ ement´ ee sans calculer explicitement P
1/2 ou
P
−1/2 . Apr` es un peu d’alg` ebre, on obtient le sch´ ema suivant :