5. Systèmes linéaires
121
est une matrice symétrique définie positive telle que frqg(PD) ¿ frqg(D).
On modifie l’algorithme précédent par les formules
;
A A A A A A A A A A A A ?
A A A A A A A A A A A A =
u 0 = e D{ 0
s 0 = Pu 0
n =
(u n >Pu n )
(s n >Ds n )
{ n+1 = { n + n s n
u n+1 = u n n Ds n
n+1 =
(u n+1 >Pu n+1 )
(u n >Pu n )
s n+1 = Pu n+1 + n+1 s n
5.4.4 Méthode du gradient conjugué pour les moindres carrés
La méthode du gradient conjugué pour les moindres carrés est une méthode issue des recherches d’adaptation de l’algorithme conjugué lorsque
la matrice D n’est pas symétrique. Elle s’appuie sur la remarque suivante :
Si D est une matrice carrée, inversible, les solutions de D
w D{ = D
w e sont
les points critiques de kD{ ek
2 .L ep r o b l è m er e v i e n ta l o r sàm i n i m i s e r
min
{
kD{ ek
2 = L’algorithme est le suivant : On choisit { 0 ,e to np o s e
v 0 = e D{ 0 >u 0 = s 0 = D
w (e D{ 0 )=D
w v 0
et t 0 = Ds 0 .P o u rn =0> 1> 2> === on calcule successivement les quantités
;
A A A A A A A A A A A A ?
A A A A A A A A A A A A =
n+1 =
(u n >u n )
(t n >t n )
{ n+1 = { n + n+1 s n
v n+1 = v n n+1 t n
u n+1 = D
w v n+1
n+1 =
(u n+1 >u n+1 )
(u n >u n )
s n+1 = u n+1 + n+1 s n
t n+1 = Ds n+1
Si la matrice D est mal conditionnée, on procédera à un préconditionnement.
5.4.5 Méthode du gradient biconjugué
La méthode du gradient biconjugué s’applique à une matrice non nécessairement symétrique. L’algorithme repose sur un double traitement de
l’équation D{ = e et de l’équation D
w e
{ = e e, sous la forme du système
µ
D 0
0 D
w
¶µ
{
e
{
¶
=
µ e
e e
¶