114
Méthodes itératives
démontre que la convergence de la méthode ne dépend pas du choix de
{ 0 et le résultat suivant : la méthode itérative { n+1 = P
1 Q{ n + P
1 e
converge si et seulement si le rayon spectral de la matrice P
1 Q est strictement inférieur à 1, (P
1 Q ) ? 1. Selon les choix des matrices P et Q
on a diérentes méthodes itératives. On note G la matrice formée des seuls
éléments diagonaux de D, H la matrice formée des d lm si lAmet I la
matrice formée des d lm si l?m,d es o r t eq u eD = G (H + I ).
G =
3
E
E
E
E
C
d 11 0 ···
0
0 d 22
. . .
. . .
. . .
. . .
. . .
0
0 ···
0 d qq
4
F
F
F
F
D
H =
3
E
E
E
E
C
00
···
0
d 21
0
. . .
. . .
. . .
. . .
. . .
0
d q>1 ··· d q>q1 0
4
F
F
F
F
D
I =
3
E
E
E
E
C
0 d 12 ···
d 1q
00
. . .
. . .
. . .
. . .
. . . d q1>q
0 ···
00
4
F
F
F
F
D
5.3.1 Méthode de Jacobi
Dans la méthode de Jacobi, encore appelée méthode des déplacements
simultanés,lamatriceD du système D{ = e est décomposée en D = P Q .
La matrice P correspond à la diagonale de D (et des zéros en dehors de la
diagonale) P = G = d lm lm et la matrice Q est la matrice D dans laquelle
on a remplacé les éléments de la diagonale par des zéros Q = H + I .L a
matrice M = P
1 Q = G
1 (H + I )=L G
1 D est appelée matrice de
Jacobi. À chaque pas, on calcule
{
(n+1)
l
=(e l
q
X
m6 =l>m=1
d lm {
(n)
m )@d ll
À chaque itération, on eectue (q 1) multiplications, q additions et une
division. Pour stocker D et les vecteurs e, { n et { n+1 on utilise (q
2 +3q)
mémoires. La méthode ne converge pas toujours. On démontre que si D est
une matrice définie positive, la méthode itérative converge. De même, si D
est une matrice diagonalement dominante, c’est-à-dire si
|d ll | A
X
m6 =l
|d lm |
alors la méthode de Jacobi converge. Par conséquent, on peut avoir intérêt à
réarranger les termes de D de façon à mettre D sous la forme d’une matrice
dont les éléments diagonaux sont les plus grands possibles. On démontre
que si D est une matrice tridiagonale par blocs, la méthode converge.