140
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
D´ emonstration. Soit x
(k) la solution construite par la m´ ethode du gradient `
a
la k-i` eme it´ eration et soit x
(k+1)
R
le vecteur construit apr` es un pas de Richardson `
a
pas optimal non pr´ econditionn´ e en partant de x
(k) , autrement dit x
(k+1)
R
= x
(k) +
αoptr
(k) .
Grˆ ace au Corollaire 4.1 et `
a (4.27), on a
(k+1)
R
A ≤
K2(A) − 1
K2(A) + 1
(k) A,
o` u e
(k+1)
R
= x
(k+1)
R
− x. De plus, d’apr` es (4.34), le vecteur x
(k+1) g´ en´ er´ e par la
m´ ethode du gradient est celui qui minimise la A-norme de l’erreur sur l’ensemble des
vecteurs de la forme x
(k) + θr
(k) , o` u θ ∈ R. Par cons´ equent, e
(k+1) A ≤ ≤e
(k+1)
R
A.
C’est le r´ esultat voulu.
3
On consid` ere maintenant la m´ ethode du gradient pr´ econditionn´ e et on
suppose que la matrice P est sym´ etrique d´ efinie positive. Dans ce cas, la
valeur optimale de α k dans l’algorithme (4.24) est
α k =
z
(k) T r
(k)
z (k) T Az (k)
et on a
(k+1)
A ≤
K 2 (P
−1 A) − 1
K 2 (P −1 A) + 1
(k)
A .
Pour la preuve de ce r´ esultat de convergence, voir par exemple [QV94], Section 2.4.1.
La relation (4.37) montre que la convergence de la m´ ethode du gradient
peut ˆ etre assez lente si K 2 (A) = λ 1 /λ n est grand. On peut donner une interpr´ etation g´ eom´ etrique simple de ce r´ esultat dans le cas n = 2. Supposons que
A=diag(λ 1 , λ 2 ), avec 0 < λ 2 ≤ λ 1 et b = [b 1 , b 2 ]
T . Dans ce cas, les courbes correspondant `
a Φ(x 1 , x 2 ) = c, pour c d´ ecrivant R
+ , forment une suite d’ellipses
concentriques dont les demi-axes ont une longueur inversement proportionnelle ` a λ 1 et λ 2 . Si λ 1 = λ 2 , les ellipses d´ eg´ en` erent en cercles et la direction
du gradient croise directement le centre. La m´ ethode du gradient converge
alors en une it´ eration. Inversement, si λ 1 λ 2 , les ellipses deviennent tr` es
excentriques et la m´ ethode converge assez lentement le long d’une trajectoire
en “zigzag”, comme le montre la Figure 4.5.
Le Programme 19 donne une impl´ ementation MATLAB de la m´ ethode
du gradient avec param` etre dynamique. Ici, comme dans les programmes des
sections ` a venir, les param` etres en entr´ ee A, x, b, P, nmax et tol repr´ esentent
respectivement la matrice du syst` eme lin´ eaire, la donn´ ee initiale x
(0) , le second membre, un pr´ econditionneur ´ eventuel, le nombre maximum d’it´ erations
admissible et une tol´ erance pour le test d’arrˆ et. Ce test d’arrˆ et v´ erifie que le
quotient r
(k)
2 /b 2 est inf´ erieur `
a tol. Les param` etres de sortie du code
sont : le nombre d’it´ erations iter effectu´ ees pour remplir les conditions de
convergence, le vecteur x contenant la solution calcul´ ee apr` es iter it´ erations
et le r´ esidu normalis´ e relres = r
(iter)
2 /b 2 . Si flag vaut z´ ero, l’algo-
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
D´ emonstration. Soit x
(k) la solution construite par la m´ ethode du gradient `
a
la k-i` eme it´ eration et soit x
(k+1)
R
le vecteur construit apr` es un pas de Richardson `
a
pas optimal non pr´ econditionn´ e en partant de x
(k) , autrement dit x
(k+1)
R
= x
(k) +
αoptr
(k) .
Grˆ ace au Corollaire 4.1 et `
a (4.27), on a
(k+1)
R
A ≤
K2(A) − 1
K2(A) + 1
(k) A,
o` u e
(k+1)
R
= x
(k+1)
R
− x. De plus, d’apr` es (4.34), le vecteur x
(k+1) g´ en´ er´ e par la
m´ ethode du gradient est celui qui minimise la A-norme de l’erreur sur l’ensemble des
vecteurs de la forme x
(k) + θr
(k) , o` u θ ∈ R. Par cons´ equent, e
(k+1) A ≤ ≤e
(k+1)
R
A.
C’est le r´ esultat voulu.
3
On consid` ere maintenant la m´ ethode du gradient pr´ econditionn´ e et on
suppose que la matrice P est sym´ etrique d´ efinie positive. Dans ce cas, la
valeur optimale de α k dans l’algorithme (4.24) est
α k =
z
(k) T r
(k)
z (k) T Az (k)
et on a
(k+1)
A ≤
K 2 (P
−1 A) − 1
K 2 (P −1 A) + 1
(k)
A .
Pour la preuve de ce r´ esultat de convergence, voir par exemple [QV94], Section 2.4.1.
La relation (4.37) montre que la convergence de la m´ ethode du gradient
peut ˆ etre assez lente si K 2 (A) = λ 1 /λ n est grand. On peut donner une interpr´ etation g´ eom´ etrique simple de ce r´ esultat dans le cas n = 2. Supposons que
A=diag(λ 1 , λ 2 ), avec 0 < λ 2 ≤ λ 1 et b = [b 1 , b 2 ]
T . Dans ce cas, les courbes correspondant `
a Φ(x 1 , x 2 ) = c, pour c d´ ecrivant R
+ , forment une suite d’ellipses
concentriques dont les demi-axes ont une longueur inversement proportionnelle ` a λ 1 et λ 2 . Si λ 1 = λ 2 , les ellipses d´ eg´ en` erent en cercles et la direction
du gradient croise directement le centre. La m´ ethode du gradient converge
alors en une it´ eration. Inversement, si λ 1 λ 2 , les ellipses deviennent tr` es
excentriques et la m´ ethode converge assez lentement le long d’une trajectoire
en “zigzag”, comme le montre la Figure 4.5.
Le Programme 19 donne une impl´ ementation MATLAB de la m´ ethode
du gradient avec param` etre dynamique. Ici, comme dans les programmes des
sections ` a venir, les param` etres en entr´ ee A, x, b, P, nmax et tol repr´ esentent
respectivement la matrice du syst` eme lin´ eaire, la donn´ ee initiale x
(0) , le second membre, un pr´ econditionneur ´ eventuel, le nombre maximum d’it´ erations
admissible et une tol´ erance pour le test d’arrˆ et. Ce test d’arrˆ et v´ erifie que le
quotient r
(k)
2 /b 2 est inf´ erieur `
a tol. Les param` etres de sortie du code
sont : le nombre d’it´ erations iter effectu´ ees pour remplir les conditions de
convergence, le vecteur x contenant la solution calcul´ ee apr` es iter it´ erations
et le r´ esidu normalis´ e relres = r
(iter)
2 /b 2 . Si flag vaut z´ ero, l’algo-