4.2 M´ ethodes it´ eratives lin´ eaires
121
Th´ eor` eme 4.2 Si A est une matrice `
a diagonale dominante stricte, les m´ ethodes de Jacobi et de Gauss-Seidel sont convergentes.
D´ emonstration. Nous prouvons la partie du th´ eor` eme concernant la m´ ethode de
Jacobi et nous renvoyons ` a [Axe94] pour la m´ ethode de Gauss-Seidel. La matrice
A ´ etant ` a diagonale dominante, |aii| >
n
j=1 |aij| pour i = 1, . . . , n et j = i. Par
cons´ equent, BJ ∞ = max
i=1,... ,n
n
j=1,j =i
|aij |/|aii| < 1, la m´ ethode de Jacobi est donc
convergente.
3
Th´ eor` eme 4.3 Si A et 2D − A sont sym´ etriques d´ efinies positives, alors la
m´ ethode de Jacobi est convergente et ρ(B J ) = B J A = B J D .
D´ emonstration. Le th´ eor` eme d´ ecoule de la Propri´ et´ e 4.1 en prenant P=D. 3
Dans le cas de la m´ ethode JOR, on peut se passer de l’hypoth` ese sur 2D − A,
comme le montre le r´ esultat suivant.
Th´ eor` eme 4.4 Quand A est sym´ etrique d´ efinie positive, la m´ ethode JOR est
convergente si 0 < ω < 2/ρ(D
−1 A).
D´ emonstration. Il suffit d’appliquer la Propri´ et´ e 4.1 `
a la matrice P =
1
ω D. La
matrice 2P − A ´ etant d´ efinie positive, ses valeurs propres sont strictement positives :
λi(2P − A) = λi
2
ω
D − A
=
2
ω
dii − λi(A) > 0.
Ce qui implique 0 < ω < 2dii/λi(A) pour i = 1, . . . , n, d’o` u le r´ esultat.
3
En ce qui concerne la m´ ethode de Gauss-Seidel, on a le r´ esultat suivant :
Th´ eor` eme 4.5 Si A est sym´ etrique d´ efinie positive, la m´ ethode de GaussSeidel converge de mani` ere monotone pour la norme · · A .
D´ emonstration. On peut appliquer la Propri´ et´ e 4.2 `
a la matrice P=D−E. V´ erifions pour cela que P + P
T − A est d´ efinie positive. En remarquant que (D − E)
T =
D − F, on a
P + P
T − A = 2D − E − F − A = D.
On conclut en remarquant que D est d´ efinie positive (c’est la diagonale de A). 3
Enfin, si A est tridiagonale sym´ etrique d´ efinie positive, on peut montrer que
la m´ ethode de Jacobi est convergente et que
ρ(B GS ) = ρ
2 (B J ).
(4.18)
Dans ce cas, la m´ ethode de Gauss-Seidel converge plus rapidement que celle
de Jacobi. La relation (4.18) est encore vraie si A poss` ede la A-propri´ et´ e :
121
Th´ eor` eme 4.2 Si A est une matrice `
a diagonale dominante stricte, les m´ ethodes de Jacobi et de Gauss-Seidel sont convergentes.
D´ emonstration. Nous prouvons la partie du th´ eor` eme concernant la m´ ethode de
Jacobi et nous renvoyons ` a [Axe94] pour la m´ ethode de Gauss-Seidel. La matrice
A ´ etant ` a diagonale dominante, |aii| >
n
j=1 |aij| pour i = 1, . . . , n et j = i. Par
cons´ equent, BJ ∞ = max
i=1,... ,n
n
j=1,j =i
|aij |/|aii| < 1, la m´ ethode de Jacobi est donc
convergente.
3
Th´ eor` eme 4.3 Si A et 2D − A sont sym´ etriques d´ efinies positives, alors la
m´ ethode de Jacobi est convergente et ρ(B J ) = B J A = B J D .
D´ emonstration. Le th´ eor` eme d´ ecoule de la Propri´ et´ e 4.1 en prenant P=D. 3
Dans le cas de la m´ ethode JOR, on peut se passer de l’hypoth` ese sur 2D − A,
comme le montre le r´ esultat suivant.
Th´ eor` eme 4.4 Quand A est sym´ etrique d´ efinie positive, la m´ ethode JOR est
convergente si 0 < ω < 2/ρ(D
−1 A).
D´ emonstration. Il suffit d’appliquer la Propri´ et´ e 4.1 `
a la matrice P =
1
ω D. La
matrice 2P − A ´ etant d´ efinie positive, ses valeurs propres sont strictement positives :
λi(2P − A) = λi
2
ω
D − A
=
2
ω
dii − λi(A) > 0.
Ce qui implique 0 < ω < 2dii/λi(A) pour i = 1, . . . , n, d’o` u le r´ esultat.
3
En ce qui concerne la m´ ethode de Gauss-Seidel, on a le r´ esultat suivant :
Th´ eor` eme 4.5 Si A est sym´ etrique d´ efinie positive, la m´ ethode de GaussSeidel converge de mani` ere monotone pour la norme · · A .
D´ emonstration. On peut appliquer la Propri´ et´ e 4.2 `
a la matrice P=D−E. V´ erifions pour cela que P + P
T − A est d´ efinie positive. En remarquant que (D − E)
T =
D − F, on a
P + P
T − A = 2D − E − F − A = D.
On conclut en remarquant que D est d´ efinie positive (c’est la diagonale de A). 3
Enfin, si A est tridiagonale sym´ etrique d´ efinie positive, on peut montrer que
la m´ ethode de Jacobi est convergente et que
ρ(B GS ) = ρ
2 (B J ).
(4.18)
Dans ce cas, la m´ ethode de Gauss-Seidel converge plus rapidement que celle
de Jacobi. La relation (4.18) est encore vraie si A poss` ede la A-propri´ et´ e :