166
6 Simulation numérique des modèles
f (x) ˜
f (x) = f (x k ) + (∇f (x k ), (x − x k )) .
La direction de plus forte pente, celle qui pour un pas |x − x k | = h donné
(| · | désigne la norme euclidienne) induit la plus forte décroissance de ˜
f , est
la direction opposée au gradient. Cela amène à poser
d k = −∇f (x k ).
Cette méthode élémentaire fonctionne sur le papier : on prouve que si f est
minorée, l’algorithme converge toujours en ce sens que pour tout > 0, il
existe k tel que |g k | ≤ . Cela dit elle est peu efficace en pratique car si
l’opposé du gradient est une bonne direction de descente (en fait la meilleure)
pour un pas infinitésimal, ce n’est pas forcément le cas pour un pas donné.
La méthode de plus forte pente (steepest descent) est donc à proscrire car
beaucoup trop lente.
6.3.1.3 Méthode du gradient conjugué non linéaire
La méthode de plus forte pente a un caractère “markovien” : le choix de la
direction d k se fait en oubliant totalement la façon dont on est arrivé en x k .
C’est pour cela que cet algorithme est si peu performant.
L’algorithme du gradient conjugué garde en un certain sens la mémoire des
itérations précédentes. C’est à l’origine un algorithme de résolution des systèmes linéaires symétriques du type
Ax = b,
(6.27)
A désignant une matrice carrée symétrique définie positive. Ce problème s’écrivant également sous la forme
inf
x∈I R n
f (x),
avec
f (x) =
1
2
x
T Ax − b
T x.
le gradient conjugué est donc de façon équivalente un algorithme de minimisation d’une fonction quadratique fortement convexe. Son principe consiste à
minimiser f à l’itération k + 1, non pas comme dans la méthode de plus forte
pente sur la demi-droite x k − tg k , mais sur le sous-espace affine contenant x k
et engendré par tous les (g l ) 0≤l≤k
K k = x k + Vect(g 0 , · · · , g k ).
La puissance de cet algorithme réside dans les deux propriétés suivantes :
1. Le minimum x k+1 de f sur le sous-espace K k est donné par les formules
de récurrence
6 Simulation numérique des modèles
f (x) ˜
f (x) = f (x k ) + (∇f (x k ), (x − x k )) .
La direction de plus forte pente, celle qui pour un pas |x − x k | = h donné
(| · | désigne la norme euclidienne) induit la plus forte décroissance de ˜
f , est
la direction opposée au gradient. Cela amène à poser
d k = −∇f (x k ).
Cette méthode élémentaire fonctionne sur le papier : on prouve que si f est
minorée, l’algorithme converge toujours en ce sens que pour tout > 0, il
existe k tel que |g k | ≤ . Cela dit elle est peu efficace en pratique car si
l’opposé du gradient est une bonne direction de descente (en fait la meilleure)
pour un pas infinitésimal, ce n’est pas forcément le cas pour un pas donné.
La méthode de plus forte pente (steepest descent) est donc à proscrire car
beaucoup trop lente.
6.3.1.3 Méthode du gradient conjugué non linéaire
La méthode de plus forte pente a un caractère “markovien” : le choix de la
direction d k se fait en oubliant totalement la façon dont on est arrivé en x k .
C’est pour cela que cet algorithme est si peu performant.
L’algorithme du gradient conjugué garde en un certain sens la mémoire des
itérations précédentes. C’est à l’origine un algorithme de résolution des systèmes linéaires symétriques du type
Ax = b,
(6.27)
A désignant une matrice carrée symétrique définie positive. Ce problème s’écrivant également sous la forme
inf
x∈I R n
f (x),
avec
f (x) =
1
2
x
T Ax − b
T x.
le gradient conjugué est donc de façon équivalente un algorithme de minimisation d’une fonction quadratique fortement convexe. Son principe consiste à
minimiser f à l’itération k + 1, non pas comme dans la méthode de plus forte
pente sur la demi-droite x k − tg k , mais sur le sous-espace affine contenant x k
et engendré par tous les (g l ) 0≤l≤k
K k = x k + Vect(g 0 , · · · , g k ).
La puissance de cet algorithme réside dans les deux propriétés suivantes :
1. Le minimum x k+1 de f sur le sous-espace K k est donné par les formules
de récurrence