4.2 M´ ethodes it´ eratives lin´ eaires
125
La matrice de pr´ econditionnement associ´ ee ` a (4.20) est
P SGS = (D − E)D
−1 (D − F).
On peut alors prouver le r´ esultat suivant (voir [Hac94]) :
Propri´ et´ e 4.5 Si A est une matrice sym´ etrique d´ efinie positive, la m´ ethode
de Gauss-Seidel sym´ etrique est convergente. De plus, B SGS est sym´ etrique
d´ efinie positive.
On peut d´ efinir de mani` ere analogue la m´ ethode SOR r´ etrograde
(D − ωF)x
(k+1) = [ωE + (1 − ω)D] x
(k) + ωb,
et la combiner ` a chaque pas `
a la m´ ethode SOR pour obtenir la m´ ethode SOR
sym´ etrique ou SSOR
x
(k+1) = B s (ω)x
(k) + b ω ,
o` u
B s (ω) = (D − ωF)
−1 (ωE + (1 − ω)D)(D − ωE)
−1 (ωF + (1 − ω)D),
b ω = ω(2 − ω)(D − ωF)
−1 D(D − ωE)
−1 b.
La matrice de pr´ econditionnement de cet algorithme est
P SSOR (ω) =
1
ω
D − E
ω
2 − ω
D
−1
1
ω
D − F
.
(4.21)
Quand A est sym´ etrique d´ efinie positive, la m´ ethode SSOR est convergente
si 0 < ω < 2 (voir [Hac94] pour la preuve). Typiquement, la m´ ethode SSOR
avec un choix optimal de param` etre de relaxation converge plus lentement que
la m´ ethode SOR correspondante. N´ eanmoins, la valeur de ρ(B s (ω)) est moins
sensible au choix de ω autour de la valeur optimale (voir le comportement des
rayons spectraux des deux matrices d’it´ eration sur la Figure 4.1). Pour cette
raison, on choisit g´ en´ eralement pour SSOR la valeur de ω optimale pour SOR
(voir [You71] pour plus de d´ etails).
4.2.6 Impl´ ementations
Nous pr´ esentons des impl´ ementations MATLAB des m´ ethodes de Jacobi et
Gauss-Seidel avec relaxation.
Le Programme 15 propose la m´ ethode JOR (l’algorithme de Jacobi est
obtenu comme cas particulier en prenant omega = 1). Le test d’arrˆ et contrˆ ole
la norme euclidienne du r´ esidu divis´ ee par sa valeur initiale.
Remarquer que chaque composante x(i) de la solution peut ˆ etre calcul´ ee
ind´ ependamment. Cette m´ ethode est donc facilement parall´ elisable.
125
La matrice de pr´ econditionnement associ´ ee ` a (4.20) est
P SGS = (D − E)D
−1 (D − F).
On peut alors prouver le r´ esultat suivant (voir [Hac94]) :
Propri´ et´ e 4.5 Si A est une matrice sym´ etrique d´ efinie positive, la m´ ethode
de Gauss-Seidel sym´ etrique est convergente. De plus, B SGS est sym´ etrique
d´ efinie positive.
On peut d´ efinir de mani` ere analogue la m´ ethode SOR r´ etrograde
(D − ωF)x
(k+1) = [ωE + (1 − ω)D] x
(k) + ωb,
et la combiner ` a chaque pas `
a la m´ ethode SOR pour obtenir la m´ ethode SOR
sym´ etrique ou SSOR
x
(k+1) = B s (ω)x
(k) + b ω ,
o` u
B s (ω) = (D − ωF)
−1 (ωE + (1 − ω)D)(D − ωE)
−1 (ωF + (1 − ω)D),
b ω = ω(2 − ω)(D − ωF)
−1 D(D − ωE)
−1 b.
La matrice de pr´ econditionnement de cet algorithme est
P SSOR (ω) =
1
ω
D − E
ω
2 − ω
D
−1
1
ω
D − F
.
(4.21)
Quand A est sym´ etrique d´ efinie positive, la m´ ethode SSOR est convergente
si 0 < ω < 2 (voir [Hac94] pour la preuve). Typiquement, la m´ ethode SSOR
avec un choix optimal de param` etre de relaxation converge plus lentement que
la m´ ethode SOR correspondante. N´ eanmoins, la valeur de ρ(B s (ω)) est moins
sensible au choix de ω autour de la valeur optimale (voir le comportement des
rayons spectraux des deux matrices d’it´ eration sur la Figure 4.1). Pour cette
raison, on choisit g´ en´ eralement pour SSOR la valeur de ω optimale pour SOR
(voir [You71] pour plus de d´ etails).
4.2.6 Impl´ ementations
Nous pr´ esentons des impl´ ementations MATLAB des m´ ethodes de Jacobi et
Gauss-Seidel avec relaxation.
Le Programme 15 propose la m´ ethode JOR (l’algorithme de Jacobi est
obtenu comme cas particulier en prenant omega = 1). Le test d’arrˆ et contrˆ ole
la norme euclidienne du r´ esidu divis´ ee par sa valeur initiale.
Remarquer que chaque composante x(i) de la solution peut ˆ etre calcul´ ee
ind´ ependamment. Cette m´ ethode est donc facilement parall´ elisable.