124
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
4.2.4 Matrices par blocs
Les m´ ethodes des sections pr´ ec´ edentes font intervenir les coefficients de la
matrice. Il existe aussi des versions par blocs de ces algorithmes.
Notons D la matrice diagonale par blocs dont les ´ el´ ements sont les blocs
diagonaux m × m de la matrice A (voir Section 1.6). On obtient la m´ ethode
de Jacobi par blocs en prenant encore P=D et N=D-A. La m´ ethode n’est bien
d´ efinie que si les blocs diagonaux de D sont inversibles. Si A est d´ ecompos´ ee
en p × p blocs carr´ es, la m´ ethode de Jacobi par blocs s’´ ecrit
A ii x
(k+1)
i
= b i −
p
j=1
j =i
A ij x
(k)
j , i = 1, . . . , p,
o` u l’on a aussi d´ ecompos´ e la solution et le second membre en blocs de tailles
p not´ es respectivement x i et b i . A chaque ´ etape, la m´ ethode de Jacobi par
blocs n´ ecessite la r´ esolution de p syst` emes lin´ eaires associ´ es aux matrices A ii .
Le Th´ eor` eme 4.3 est encore vrai en rempla¸ cant D par la matrice diagonale
par blocs correspondante.
On peut d´ efinir de mani` ere analogue les m´ ethodes de Gauss-Seidel et SOR
par blocs.
4.2.5 Forme sym´ etrique des m´ ethodes SOR et de Gauss-Seidel
Mˆ eme pour une matrice sym´ etrique, les m´ ethodes SOR et de Gauss-Seidel
conduisent `
a des matrices d’it´ eration en g´ en´ eral non sym´ etriques. Pour cette
raison, nous introduisons dans cette section une technique permettant de sym´ etriser ces algorithmes. L’objectif `
a terme est de construire des pr´ econditionneurs sym´ etriques (voir Section 4.3.2).
Remarquons tout d’abord qu’on peut construire l’analogue de la m´ ethode
de Gauss-Seidel en ´ echangeant simplement E et F. On d´ efinit alors l’algorithme
suivant, appel´ e m´ ethode de Gauss-Seidel r´ etrograde,
(D − F)x
(k+1) = Ex
(k) + b,
dont la matrice d’it´ eration est donn´ ee par B GSb = (D − F)
−1 E.
On obtient la m´ ethode de Gauss-Seidel sym´ etrique en combinant une it´ eration
de Gauss-Seidel avec une it´ eration de Gauss-Seidel r´ etrograde. Plus pr´ ecis´ ement, la k-i` eme it´ eration de la m´ ethode de Gauss-Seidel sym´ etrique est d´ efinie
par
(D − E)x
(k+1/2) = Fx
(k) + b, (D − F)x
(k+1) = Ex
(k+1/2) + b.
En ´ eliminant x
(k+1/2) , on obtient le sch´ ema suivant
x
(k+1) = B SGS x
(k) + b SGS ,
B SGS = (D − F)
−1 E(D − E)
−1 F,
b SGS = (D − F)
−1 [E(D − E)
−1 + I]b.
(4.20)
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
4.2.4 Matrices par blocs
Les m´ ethodes des sections pr´ ec´ edentes font intervenir les coefficients de la
matrice. Il existe aussi des versions par blocs de ces algorithmes.
Notons D la matrice diagonale par blocs dont les ´ el´ ements sont les blocs
diagonaux m × m de la matrice A (voir Section 1.6). On obtient la m´ ethode
de Jacobi par blocs en prenant encore P=D et N=D-A. La m´ ethode n’est bien
d´ efinie que si les blocs diagonaux de D sont inversibles. Si A est d´ ecompos´ ee
en p × p blocs carr´ es, la m´ ethode de Jacobi par blocs s’´ ecrit
A ii x
(k+1)
i
= b i −
p
j=1
j =i
A ij x
(k)
j , i = 1, . . . , p,
o` u l’on a aussi d´ ecompos´ e la solution et le second membre en blocs de tailles
p not´ es respectivement x i et b i . A chaque ´ etape, la m´ ethode de Jacobi par
blocs n´ ecessite la r´ esolution de p syst` emes lin´ eaires associ´ es aux matrices A ii .
Le Th´ eor` eme 4.3 est encore vrai en rempla¸ cant D par la matrice diagonale
par blocs correspondante.
On peut d´ efinir de mani` ere analogue les m´ ethodes de Gauss-Seidel et SOR
par blocs.
4.2.5 Forme sym´ etrique des m´ ethodes SOR et de Gauss-Seidel
Mˆ eme pour une matrice sym´ etrique, les m´ ethodes SOR et de Gauss-Seidel
conduisent `
a des matrices d’it´ eration en g´ en´ eral non sym´ etriques. Pour cette
raison, nous introduisons dans cette section une technique permettant de sym´ etriser ces algorithmes. L’objectif `
a terme est de construire des pr´ econditionneurs sym´ etriques (voir Section 4.3.2).
Remarquons tout d’abord qu’on peut construire l’analogue de la m´ ethode
de Gauss-Seidel en ´ echangeant simplement E et F. On d´ efinit alors l’algorithme
suivant, appel´ e m´ ethode de Gauss-Seidel r´ etrograde,
(D − F)x
(k+1) = Ex
(k) + b,
dont la matrice d’it´ eration est donn´ ee par B GSb = (D − F)
−1 E.
On obtient la m´ ethode de Gauss-Seidel sym´ etrique en combinant une it´ eration
de Gauss-Seidel avec une it´ eration de Gauss-Seidel r´ etrograde. Plus pr´ ecis´ ement, la k-i` eme it´ eration de la m´ ethode de Gauss-Seidel sym´ etrique est d´ efinie
par
(D − E)x
(k+1/2) = Fx
(k) + b, (D − F)x
(k+1) = Ex
(k+1/2) + b.
En ´ eliminant x
(k+1/2) , on obtient le sch´ ema suivant
x
(k+1) = B SGS x
(k) + b SGS ,
B SGS = (D − F)
−1 E(D − E)
−1 F,
b SGS = (D − F)
−1 [E(D − E)
−1 + I]b.
(4.20)