168
6 Simulation numérique des modèles
Remarque 6.7 Pour une recherche linéaire exacte, une direction de la forme
(6.29) est toujours une direction de descente puisque
(d k , g k ) = −|g k |
2 + c k−1 (d k−1 , g k ) = −|g k |
2 .
En revanche, du fait que les recherches linéaires ne sont en pratique qu’approchées, il peut arriver que la direction calculée par la formule (6.29) et l’une des
deux règles de Fletcher-Reeves ou de Polak-Ribière ne soit pas une direction
de descente (d k · g k ≥ 0). Si cela se produit, on peut par exemple réinitialiser
l’algorithme en posant d k = −g k .
L’algorithme du gradient conjugué non linéaire se met donc sous la forme :
1. Initialisation : choix de x 0 ∈ IR
n et de > 0 ; k = 0.
2. Test d’arrêt : calcul de g k = ∇f (x k ), et arrêt de l’algorithme si |g k | ≤ .
3. Calcul de la direction de descente : si k = 0, d 0 = −g 0 , sinon d k =
−g k + c k−1 d k−1 avec c k−1 donné par (6.31). Si (d k , g k ) ≥ 0 (d k est une
direction de “remontée”), poser d k = −g k .
4. Recherche linéaire le long de d k pour obtenir t k .
5. Poser x k+1 = x k + t k d k , remplacer k par k + 1 et aller en 2.
6.3.1.4 Méthode de Newton
La méthode de Newton consiste à considérer un modèle au second ordre de
f :
f (x) ˜
f (x) = f (x k ) + (∇f (x k ), (x − x k )) +
1
2
(x − x k , f
(x k ) · (x − x k )) .
Le minimum x min de ˜
f est solution de
f
(x k ) · (x min − x k ) + ∇f (x k ) = 0.
On prendra donc comme direction de descente la solution d k de
f
(x k ) · d k + g k = 0,
(6.32)
où comme ci-dessus g k = ∇f (x k ).
Lorsque la fonction f est quadratique f = ˜
f , l’algorithme de Newton converge
du premier coup si on prend une longueur de descente égale à 1 (on parle
de pas de Newton). Dans le cas général, la convergence de la méthode de
Newton avec recherche linéaire converge superlinéairement (i.e. pour tout >
0, |x k+1 − x min | ≤ |x k+1 − x min | lorsque k est assez grand) et la convergence
devient quadratique si f est de classe C
3 au voisinage d’un minimum elliptique
pour un pas de descente constant égal à un.
La méthode de Newton est donc très performante mais coûte cher : il faut à
chaque pas calculer la matrice hessienne et résoudre le système linéaire (6.32).
6 Simulation numérique des modèles
Remarque 6.7 Pour une recherche linéaire exacte, une direction de la forme
(6.29) est toujours une direction de descente puisque
(d k , g k ) = −|g k |
2 + c k−1 (d k−1 , g k ) = −|g k |
2 .
En revanche, du fait que les recherches linéaires ne sont en pratique qu’approchées, il peut arriver que la direction calculée par la formule (6.29) et l’une des
deux règles de Fletcher-Reeves ou de Polak-Ribière ne soit pas une direction
de descente (d k · g k ≥ 0). Si cela se produit, on peut par exemple réinitialiser
l’algorithme en posant d k = −g k .
L’algorithme du gradient conjugué non linéaire se met donc sous la forme :
1. Initialisation : choix de x 0 ∈ IR
n et de > 0 ; k = 0.
2. Test d’arrêt : calcul de g k = ∇f (x k ), et arrêt de l’algorithme si |g k | ≤ .
3. Calcul de la direction de descente : si k = 0, d 0 = −g 0 , sinon d k =
−g k + c k−1 d k−1 avec c k−1 donné par (6.31). Si (d k , g k ) ≥ 0 (d k est une
direction de “remontée”), poser d k = −g k .
4. Recherche linéaire le long de d k pour obtenir t k .
5. Poser x k+1 = x k + t k d k , remplacer k par k + 1 et aller en 2.
6.3.1.4 Méthode de Newton
La méthode de Newton consiste à considérer un modèle au second ordre de
f :
f (x) ˜
f (x) = f (x k ) + (∇f (x k ), (x − x k )) +
1
2
(x − x k , f
(x k ) · (x − x k )) .
Le minimum x min de ˜
f est solution de
f
(x k ) · (x min − x k ) + ∇f (x k ) = 0.
On prendra donc comme direction de descente la solution d k de
f
(x k ) · d k + g k = 0,
(6.32)
où comme ci-dessus g k = ∇f (x k ).
Lorsque la fonction f est quadratique f = ˜
f , l’algorithme de Newton converge
du premier coup si on prend une longueur de descente égale à 1 (on parle
de pas de Newton). Dans le cas général, la convergence de la méthode de
Newton avec recherche linéaire converge superlinéairement (i.e. pour tout >
0, |x k+1 − x min | ≤ |x k+1 − x min | lorsque k est assez grand) et la convergence
devient quadratique si f est de classe C
3 au voisinage d’un minimum elliptique
pour un pas de descente constant égal à un.
La méthode de Newton est donc très performante mais coûte cher : il faut à
chaque pas calculer la matrice hessienne et résoudre le système linéaire (6.32).