6.7 R´ esolution des syst` emes d’´ equations non lin´ eaires
249
Ce r´ esultat ne donne pas d’indication constructive sur la mani` ere de calculer
les incr´ ements h
(k)
j . Faisons `
a ce propos la remarque suivante : en diminuant les
h
(k)
j , on peut diminuer l’erreur de troncature commise dans (6.47) ; cependant,
des valeurs de h
(k)
j
trop petites peuvent induire des erreurs d’arrondi importantes. On doit donc trouver un bon ´ equilibre entre erreur de troncature et
pr´ ecision des calculs en arithm´ etique flottante.
Un choix possible consiste ` a prendre
h
(k)
j
=
√ M max
|x
(k)
j |, M j
sign(x j ),
o` u M j est un param` etre caract´ erisant la taille typique de la composante x j de
la solution. On peut am´ eliorer encore les r´ esultats en utilisant des diff´ erences
divis´ ees d’ordre sup´ erieur pour approcher la d´ eriv´ ee :
(J
(k)
h ) j =
F(x
(k) + h
(k)
j e j ) − F(x
(k)
− h
(k)
j e j )
2h
(k)
j
∀k ≥ 0.
Pour plus de d´ etails sur ce sujet voir par exemple [BS90].
6.7.3 M´ ethodes de Quasi-Newton
On d´ esigne par ce terme les algorithmes qui couplent des m´ ethodes globalement convergentes avec des m´ ethodes de type Newton qui sont seulement
localement convergentes mais d’ordre sup´ erieur `
a un.
On se donne une fonction continˆ ument diff´ erentiable F : R
n
→ R
n et une
valeur initiale x
(0)
∈ R
n . Une m´ ethode de quasi-Newton consiste ` a effectuer
les op´ erations suivantes `
a chaque ´ etape k :
1. calculer F(x
(k) ) ;
2. d´ eterminer ˜ J F (x
(k) ) ´ egal ` a J F (x
(k) ) ou `
a une de ses approximations ;
3. r´ esoudre le syst` eme lin´ eaire ˜ J F (x
(k) )δx
(k) = −F(x
(k) ) ;
4. poser x
(k+1) = x
(k) + α k δx
(k) , o` u α k est un param` etre d’amortissement.
L’´ etape 4 est caract´ eristique de cette famille de m´ ethodes. Pour une analyse
de ces algorithmes, et pour des crit` eres permettant de choisir la “direction”
δx
(k) , nous renvoyons le lecteur `
a [QSS07], Chapitre 7.
6.7.4 M´ ethodes de type s´ ecante
Sur la base de la m´ ethode de la s´ ecante introduite `
a la Section 6.2 pour les
fonctions scalaires, on se donne x
(0) et x
(1) , on r´ esout pour k ≥ 1 le syst` eme
lin´ eaire
Q k δx
(k+1) = −F(x
(k) )
(6.48)
249
Ce r´ esultat ne donne pas d’indication constructive sur la mani` ere de calculer
les incr´ ements h
(k)
j . Faisons `
a ce propos la remarque suivante : en diminuant les
h
(k)
j , on peut diminuer l’erreur de troncature commise dans (6.47) ; cependant,
des valeurs de h
(k)
j
trop petites peuvent induire des erreurs d’arrondi importantes. On doit donc trouver un bon ´ equilibre entre erreur de troncature et
pr´ ecision des calculs en arithm´ etique flottante.
Un choix possible consiste ` a prendre
h
(k)
j
=
√ M max
|x
(k)
j |, M j
sign(x j ),
o` u M j est un param` etre caract´ erisant la taille typique de la composante x j de
la solution. On peut am´ eliorer encore les r´ esultats en utilisant des diff´ erences
divis´ ees d’ordre sup´ erieur pour approcher la d´ eriv´ ee :
(J
(k)
h ) j =
F(x
(k) + h
(k)
j e j ) − F(x
(k)
− h
(k)
j e j )
2h
(k)
j
∀k ≥ 0.
Pour plus de d´ etails sur ce sujet voir par exemple [BS90].
6.7.3 M´ ethodes de Quasi-Newton
On d´ esigne par ce terme les algorithmes qui couplent des m´ ethodes globalement convergentes avec des m´ ethodes de type Newton qui sont seulement
localement convergentes mais d’ordre sup´ erieur `
a un.
On se donne une fonction continˆ ument diff´ erentiable F : R
n
→ R
n et une
valeur initiale x
(0)
∈ R
n . Une m´ ethode de quasi-Newton consiste ` a effectuer
les op´ erations suivantes `
a chaque ´ etape k :
1. calculer F(x
(k) ) ;
2. d´ eterminer ˜ J F (x
(k) ) ´ egal ` a J F (x
(k) ) ou `
a une de ses approximations ;
3. r´ esoudre le syst` eme lin´ eaire ˜ J F (x
(k) )δx
(k) = −F(x
(k) ) ;
4. poser x
(k+1) = x
(k) + α k δx
(k) , o` u α k est un param` etre d’amortissement.
L’´ etape 4 est caract´ eristique de cette famille de m´ ethodes. Pour une analyse
de ces algorithmes, et pour des crit` eres permettant de choisir la “direction”
δx
(k) , nous renvoyons le lecteur `
a [QSS07], Chapitre 7.
6.7.4 M´ ethodes de type s´ ecante
Sur la base de la m´ ethode de la s´ ecante introduite `
a la Section 6.2 pour les
fonctions scalaires, on se donne x
(0) et x
(1) , on r´ esout pour k ≥ 1 le syst` eme
lin´ eaire
Q k δx
(k+1) = −F(x
(k) )
(6.48)