4.3 M´ ethodes it´ eratives stationnaires et instationnaires
143
plus rapide que la m´ ethode de Richardson quand K 2 (A) est grand. Comme
on a, d’apr` es (4.35),
r
(k+1) = r
(k)
− α k Ap
(k) ,
(4.39)
la relation (4.38) donne
(p
(k) )
T r
(k+1) = 0,
donc le nouveau r´ esidu devient orthogonal `
a la direction de recherche. Pour
l’it´ eration suivante, la stat´ egie consiste ` a trouver une nouvelle direction de
recherche p
(k+1) telle que
(Ap
(j) )
T p
(k+1) = 0,
j = 0, . . ., k.
(4.40)
Voyons comment les k + 1 relations (4.40) peuvent s’obtenir en pratique.
Supposons que pour k ≥ 1, les directions p
(0) , p
(1) , . . ., p
(k) soient deux ` a
deux conjugu´ ees (ou A-orthogonales), c’est-` a-dire
(Ap
(i) )
T p
(j) = 0,
∀i, j = 0, . . ., k, i = j.
(4.41)
Ceci est possible (en arithm´ etique exacte) ` a condition que k < n. Supposons
aussi, sans perte de g´ en´ eralit´ e, que
(p
(j) )
T r
(k) = 0,
j = 0, 1, . . ., k − 1.
(4.42)
Alors, pour tout k ≥ 0, le nouveau r´ esidu r
(k+1) est orthogonal aux directions
p
(j) , j = 0, . . . , k, c’est-` a-dire
(p
(j) )
T r
(k+1) = 0,
j = 0, . . ., k.
(4.43)
Ceci peut se montrer par r´ ecurrence sur k. Pour k = 0, r
(1) = r
(0)
− α 0 Ar
(0) ,
donc (p
(0) )
T r
(1) = 0 puisque α 0 = (p
(0) )
T r
(0) /((p
(0) )
T Ap
(0) ), d’o` u (4.42).
L’´ equation (4.39) implique (A ´ etant sym´ etrique)
(p
(j) )
T r
(k+1) = (p
(j) )
T r
(k)
− α k (Ap
(j) )
T p
(k) .
Mis `
a part pour j = k, (Ap
(j) )
T p
(k) vaut z´ ero d’apr` es (4.41), tandis
(p
(j) )
T r
(k) vaut z´ ero par hypoth` ese de r´ ecurrence. De plus, quand j = k
le second membre est nul ` a cause du choix (4.38) de α k .
Il ne reste qu’` a construire de mani` ere efficace la suite des directions de
recherche p
(0) , p
(1) , . . ., p
(k) en les rendant deux `
a deux A-orthogonales. Pour
cel` a, soit
p
(k+1) = r
(k+1)
− β k p
(k) ,
k= 0, 1, . . .,
(4.44)
o` u p
(0) = r
(0) et o` u β 0 , β 1 , . . . sont `
a d´ eterminer. En utilisant (4.44) dans
(4.40) pour j = k, on trouve
β k =
(Ap
(k) )
T r
(k+1)
(Ap (k) ) T p (k) ,
k= 0, 1, . . ..
(4.45)
143
plus rapide que la m´ ethode de Richardson quand K 2 (A) est grand. Comme
on a, d’apr` es (4.35),
r
(k+1) = r
(k)
− α k Ap
(k) ,
(4.39)
la relation (4.38) donne
(p
(k) )
T r
(k+1) = 0,
donc le nouveau r´ esidu devient orthogonal `
a la direction de recherche. Pour
l’it´ eration suivante, la stat´ egie consiste ` a trouver une nouvelle direction de
recherche p
(k+1) telle que
(Ap
(j) )
T p
(k+1) = 0,
j = 0, . . ., k.
(4.40)
Voyons comment les k + 1 relations (4.40) peuvent s’obtenir en pratique.
Supposons que pour k ≥ 1, les directions p
(0) , p
(1) , . . ., p
(k) soient deux ` a
deux conjugu´ ees (ou A-orthogonales), c’est-` a-dire
(Ap
(i) )
T p
(j) = 0,
∀i, j = 0, . . ., k, i = j.
(4.41)
Ceci est possible (en arithm´ etique exacte) ` a condition que k < n. Supposons
aussi, sans perte de g´ en´ eralit´ e, que
(p
(j) )
T r
(k) = 0,
j = 0, 1, . . ., k − 1.
(4.42)
Alors, pour tout k ≥ 0, le nouveau r´ esidu r
(k+1) est orthogonal aux directions
p
(j) , j = 0, . . . , k, c’est-` a-dire
(p
(j) )
T r
(k+1) = 0,
j = 0, . . ., k.
(4.43)
Ceci peut se montrer par r´ ecurrence sur k. Pour k = 0, r
(1) = r
(0)
− α 0 Ar
(0) ,
donc (p
(0) )
T r
(1) = 0 puisque α 0 = (p
(0) )
T r
(0) /((p
(0) )
T Ap
(0) ), d’o` u (4.42).
L’´ equation (4.39) implique (A ´ etant sym´ etrique)
(p
(j) )
T r
(k+1) = (p
(j) )
T r
(k)
− α k (Ap
(j) )
T p
(k) .
Mis `
a part pour j = k, (Ap
(j) )
T p
(k) vaut z´ ero d’apr` es (4.41), tandis
(p
(j) )
T r
(k) vaut z´ ero par hypoth` ese de r´ ecurrence. De plus, quand j = k
le second membre est nul ` a cause du choix (4.38) de α k .
Il ne reste qu’` a construire de mani` ere efficace la suite des directions de
recherche p
(0) , p
(1) , . . ., p
(k) en les rendant deux `
a deux A-orthogonales. Pour
cel` a, soit
p
(k+1) = r
(k+1)
− β k p
(k) ,
k= 0, 1, . . .,
(4.44)
o` u p
(0) = r
(0) et o` u β 0 , β 1 , . . . sont `
a d´ eterminer. En utilisant (4.44) dans
(4.40) pour j = k, on trouve
β k =
(Ap
(k) )
T r
(k+1)
(Ap (k) ) T p (k) ,
k= 0, 1, . . ..
(4.45)