128
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
La matrice d’it´ eration de ces m´ ethodes ` a la k-i` eme ´ etape est
R αk = I − α k P
−1 A,
avec α k = α dans le cas stationnaire. Si P=I, on dit que la m´ ethode est non
pr´ econditionn´ ee. Les it´ erations de Jacobi et Gauss-Seidel peuvent ˆ etre vues
comme des m´ ethodes de Richardson stationnaires avec α = 1 et respectivement P = D et P = D − E.
On peut r´ ecrire (4.22) et (4.23) sous une forme mieux adapt´ ee aux calculs :
en posant z
(k) = P
−1 r
(k) (qu’on appelle r´ esidu pr´ econditionn´ e), on obtient
x
(k+1) = x
(k) + α k z
(k) et r
(k+1) = b − Ax
(k+1) = r
(k)
− α k Az
(k) .
En r´ esum´ e, une m´ ethode de Richardson instationnaire s’´ ecrit, ` a l’´ etape k + 1 :
r´ esoudre le syst` eme lin´ eaire Pz
(k) = r
(k)
calculer le param` etre d’acc´ el´ eration α k
mettre ` a jour la solution x
(k+1) = x
(k) + α k z
(k)
mettre ` a jour le r´ esidu r
(k+1) = r
(k)
− α k Az
(k) .
(4.24)
4.3.1 Analyse de la convergence des m´ ethodes de Richardson
Consid´ erons tout d’abord les m´ ethodes de Richardson stationnaires (i.e. pour
lesquelles α k = α pour k ≥ 0). On a le r´ esultat de convergence suivant :
Th´ eor` eme 4.8 Pour toute matrice inversible P, la m´ ethode de Richardson
stationnaire (4.22) est convergente si et seulement si
2Reλ i
α|λ i | 2 > 1 ∀i = 1, . . . , n ,
(4.25)
o` u les λ i sont les valeurs propres de P
−1 A.
D´ emonstration. Appliquons le Th´ eor` eme 4.1 `
a la matrice d’it´ eration Rα = I −
αP
−1 A. La condition |1 − αλi| < 1 pour i = 1, . . . , n entraˆ ıne l’in´ egalit´ e
(1 − αReλi)
2 + α
2 (Imλi)
2 < 1 ,
d’o` u (4.25) d´ ecoule imm´ ediatement.
3
Remarquons que, si le signe des parties r´ eelles des valeurs propres de P
−1 A
n’est pas constant, la m´ ethode stationnaire de Richardson ne peut pas converger.
Des r´ esultats plus sp´ ecifiques peuvent ˆ etre obtenus si des hypoth` eses convenables sont faites sur le spectre de P
−1 A :
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
La matrice d’it´ eration de ces m´ ethodes ` a la k-i` eme ´ etape est
R αk = I − α k P
−1 A,
avec α k = α dans le cas stationnaire. Si P=I, on dit que la m´ ethode est non
pr´ econditionn´ ee. Les it´ erations de Jacobi et Gauss-Seidel peuvent ˆ etre vues
comme des m´ ethodes de Richardson stationnaires avec α = 1 et respectivement P = D et P = D − E.
On peut r´ ecrire (4.22) et (4.23) sous une forme mieux adapt´ ee aux calculs :
en posant z
(k) = P
−1 r
(k) (qu’on appelle r´ esidu pr´ econditionn´ e), on obtient
x
(k+1) = x
(k) + α k z
(k) et r
(k+1) = b − Ax
(k+1) = r
(k)
− α k Az
(k) .
En r´ esum´ e, une m´ ethode de Richardson instationnaire s’´ ecrit, ` a l’´ etape k + 1 :
r´ esoudre le syst` eme lin´ eaire Pz
(k) = r
(k)
calculer le param` etre d’acc´ el´ eration α k
mettre ` a jour la solution x
(k+1) = x
(k) + α k z
(k)
mettre ` a jour le r´ esidu r
(k+1) = r
(k)
− α k Az
(k) .
(4.24)
4.3.1 Analyse de la convergence des m´ ethodes de Richardson
Consid´ erons tout d’abord les m´ ethodes de Richardson stationnaires (i.e. pour
lesquelles α k = α pour k ≥ 0). On a le r´ esultat de convergence suivant :
Th´ eor` eme 4.8 Pour toute matrice inversible P, la m´ ethode de Richardson
stationnaire (4.22) est convergente si et seulement si
2Reλ i
α|λ i | 2 > 1 ∀i = 1, . . . , n ,
(4.25)
o` u les λ i sont les valeurs propres de P
−1 A.
D´ emonstration. Appliquons le Th´ eor` eme 4.1 `
a la matrice d’it´ eration Rα = I −
αP
−1 A. La condition |1 − αλi| < 1 pour i = 1, . . . , n entraˆ ıne l’in´ egalit´ e
(1 − αReλi)
2 + α
2 (Imλi)
2 < 1 ,
d’o` u (4.25) d´ ecoule imm´ ediatement.
3
Remarquons que, si le signe des parties r´ eelles des valeurs propres de P
−1 A
n’est pas constant, la m´ ethode stationnaire de Richardson ne peut pas converger.
Des r´ esultats plus sp´ ecifiques peuvent ˆ etre obtenus si des hypoth` eses convenables sont faites sur le spectre de P
−1 A :