138
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
4.3.3 La m´ ethode du gradient
Le principal probl` eme quand on utilise les m´ ethodes de Richardson est le choix
du param` etre d’acc´ el´ eration α. La formule du param` etre optimal donn´ ee par
le Th´ eor` eme 4.9 requiert la connaissance des valeurs propres extr´ emales de
la matrice P
−1 A, elle donc inutile en pratique. N´ eanmoins, dans le cas particulier des matrices sym´ etriques d´ efinies positives, le param` etre d’acc´ el´ eration
optimal peut ˆ etre calcul´ e dynamiquement ` a chaque ´ etape k comme suit.
On remarque tout d’abord que, pour ces matrices, la r´ esolution du syst` eme (3.2) est ´ equivalente `
a la d´ etermination de x ∈ R
n minimisant la forme
quadratique
Φ(y) =
1
2
y
T Ay − y
T b,
appel´ ee ´ energie du syst` eme (3.2). En effet, si on calcule le gradient de Φ, on
obtient
∇Φ(y) =
1
2
(A
T + A)y − b = Ay − b,
(4.33)
car A est sym´ etrique. Par cons´ equent, si ∇Φ(x) = 0 alors x est une solution
du syst` eme original. Inversement, si le vecteur x est une solution, alors il
minimise la fonctionnelle Φ. Cette propri´ et´ e est imm´ ediate si on remarque
que
Φ(y) = Φ(x + (y − x)) = Φ(x) +
1
2
(y − x)
T A(y − x)
∀y ∈ R
n
et donc Φ(y) > Φ(x) pour y = x.
Des consid´ erations similaires nous permettent de relier la recherche d’un
minimiseur de Φ `
a la minimisation de l’erreur y − x en norme-A ou norme de
l’´ energie, d´ efinie en (1.30) ; en effet
1
2
− x
2
A = Φ(y) − Φ(x).
(4.34)
Le probl` eme est donc de d´ eterminer le minimiseur x de Φ en partant d’un
point x
(0)
∈ R
n , ce qui revient `
a d´ eterminer des directions de d´ eplacement
qui permettent de se rapprocher le plus possible de la solution x. La direction
optimale, i.e. celle qui relie le point de d´ epart x
(0) ` a la solution x, est ´ evidemment inconnue a priori. On doit donc effectuer un pas `
a partir de x
(0) le
long d’une direction p
(0) , puis fixer le long de celle-ci un nouveau point x
(1)
` a partir duquel on it` ere le proc´ ed´ e jusqu’` a convergence.
Ainsi, `
a l’´ etape k, x
(k+1) est d´ etermin´ e par
x
(k+1) = x
(k) + α k p
(k) ,
(4.35)
o` u α k est la valeur qui fixe la longueur du pas le long de d
(k) . L’id´ ee la plus
naturelle est de prendre la direction de descente de pente maximale ∇Φ(x
(k) ).
C’est la m´ ethode du gradient ou m´ ethode de plus profonde descente.
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
4.3.3 La m´ ethode du gradient
Le principal probl` eme quand on utilise les m´ ethodes de Richardson est le choix
du param` etre d’acc´ el´ eration α. La formule du param` etre optimal donn´ ee par
le Th´ eor` eme 4.9 requiert la connaissance des valeurs propres extr´ emales de
la matrice P
−1 A, elle donc inutile en pratique. N´ eanmoins, dans le cas particulier des matrices sym´ etriques d´ efinies positives, le param` etre d’acc´ el´ eration
optimal peut ˆ etre calcul´ e dynamiquement ` a chaque ´ etape k comme suit.
On remarque tout d’abord que, pour ces matrices, la r´ esolution du syst` eme (3.2) est ´ equivalente `
a la d´ etermination de x ∈ R
n minimisant la forme
quadratique
Φ(y) =
1
2
y
T Ay − y
T b,
appel´ ee ´ energie du syst` eme (3.2). En effet, si on calcule le gradient de Φ, on
obtient
∇Φ(y) =
1
2
(A
T + A)y − b = Ay − b,
(4.33)
car A est sym´ etrique. Par cons´ equent, si ∇Φ(x) = 0 alors x est une solution
du syst` eme original. Inversement, si le vecteur x est une solution, alors il
minimise la fonctionnelle Φ. Cette propri´ et´ e est imm´ ediate si on remarque
que
Φ(y) = Φ(x + (y − x)) = Φ(x) +
1
2
(y − x)
T A(y − x)
∀y ∈ R
n
et donc Φ(y) > Φ(x) pour y = x.
Des consid´ erations similaires nous permettent de relier la recherche d’un
minimiseur de Φ `
a la minimisation de l’erreur y − x en norme-A ou norme de
l’´ energie, d´ efinie en (1.30) ; en effet
1
2
− x
2
A = Φ(y) − Φ(x).
(4.34)
Le probl` eme est donc de d´ eterminer le minimiseur x de Φ en partant d’un
point x
(0)
∈ R
n , ce qui revient `
a d´ eterminer des directions de d´ eplacement
qui permettent de se rapprocher le plus possible de la solution x. La direction
optimale, i.e. celle qui relie le point de d´ epart x
(0) ` a la solution x, est ´ evidemment inconnue a priori. On doit donc effectuer un pas `
a partir de x
(0) le
long d’une direction p
(0) , puis fixer le long de celle-ci un nouveau point x
(1)
` a partir duquel on it` ere le proc´ ed´ e jusqu’` a convergence.
Ainsi, `
a l’´ etape k, x
(k+1) est d´ etermin´ e par
x
(k+1) = x
(k) + α k p
(k) ,
(4.35)
o` u α k est la valeur qui fixe la longueur du pas le long de d
(k) . L’id´ ee la plus
naturelle est de prendre la direction de descente de pente maximale ∇Φ(x
(k) ).
C’est la m´ ethode du gradient ou m´ ethode de plus profonde descente.