R´ esolution d’un syst` eme non lin´ eaire
499
Consid´ erons maintenant deux mani` eres de choisir les param` etres d’acc´ el´ eration α k . La premi` ere a ´ et´ e propos´ ee dans [BR81] :
α k =
1
1 + ρ k F(u (k) )
,
k = 0, 1, . . .,
(13.7)
o` u · · d´ esigne une norme vectorielle, par exemple · · = · · ∞ , et o` u les
coefficients ρ k ≥ 0 sont des param` etres d’acc´ el´ eration choisis de fa¸ con ` a ce que
la condition de descente F(u
(k) + α k δu
(k) ) ∞ < F(u
(k) ) ∞ soit satisfaite
(voir [BR81] pour les d´ etails d’impl´ ementation de l’algorithme).
Quand F(u
(k) ) ∞ → 0, (13.7) implique α k → 1 et on retrouve ainsi la
convergence quadratique de la m´ ethode de Newton. Quand F(u
(k) ) ∞ 1,
ce qui se produit typiquement dans les premi` eres it´ erations, α k est proche de
z´ ero, les it´ erations de Newton sont donc fortement amorties.
Comme alternative ` a (13.7), la suite {α k } peut ˆ etre obtenue en utilisant la
formule plus simple, sugg´ er´ ee dans [Sel84], Chapitre 7
α k = 2
−i(i−1)/2 ,
k= 0, 1, . . .,
(13.8)
o` u i est le premier entier de l’intervalle [1, It max ] tel que la condition de
descente ci-dessus soit satisfaite, It max ´ etant le nombre maximum de cycles
d’amortissement par it´ eration de Newton (´ egal ` a 10 dans les tests num´ eriques).
Afin de les comparer, on a impl´ ement´ e la m´ ethode de Newton standard et la
m´ ethode de Newton amortie. Pour cette derni` ere, on a utilis´ e (13.7) et (13.8)
pour les coefficients α k . Pour retrouver la m´ ethode de Newton standard, on a
pos´ e dans (13.6) α k = 1 pour tout k ≥ 0.
Les tests num´ eriques ont ´ et´ e effectu´ es avec n = 49, b i = −1 pour i ≤ n/2
et les b i restants ´ egaux `
a 1. On a pris λ
2 = 1.67 · 10
−4 , K = 6.77 · 10
−6 , les
n/2 premi` eres composantes du vecteur initial u
(0) ´ egales ` a V a et les autres
composantes ´ egales ` a V b , o` u V a = 0 et V b = 10.
La tol´ erance sur la diff´ erence en deux it´ er´ ees cons´ ecutives (crit` ere avec
lequel on contrˆ ole la convergence de la m´ ethode de Newton amortie (13.6)) a
´ et´ e choisie ´ egale ` a 10
−4 .
La Figure 13.7 montre (` a gauche), pour les trois algorithmes, l’erreur absolue
en ´ echelle logarithmique en fonction du nombre d’it´ erations. Remarquer la
rapidit´ e de la convergence de la m´ ethode de Newton amortie (8 it´ erations
avec (13.7) et 10 avec (13.8)), alors que la m´ ethode de Newton standard
converge tr` es lentement (192 it´ erations).
Il est int´ eressant d’analyser sur la Figure 13.7 (` a droite) le comportement
de la suite α k en fonction du nombre d’it´ erations. La courbe avec des ´ etoiles
correspond ` a (13.7) et celle avec des cercles ` a (13.8). Comme on l’a not´ e
pr´ ec´ edemment, les α k d´ emarrent avec des valeurs tr` es petites, et convergent
rapidement vers 1 quand la m´ ethode de Newton amortie (13.6) entre dans la
r´ egion d’attraction du minimiseur x
∗ .
499
Consid´ erons maintenant deux mani` eres de choisir les param` etres d’acc´ el´ eration α k . La premi` ere a ´ et´ e propos´ ee dans [BR81] :
α k =
1
1 + ρ k F(u (k) )
,
k = 0, 1, . . .,
(13.7)
o` u · · d´ esigne une norme vectorielle, par exemple · · = · · ∞ , et o` u les
coefficients ρ k ≥ 0 sont des param` etres d’acc´ el´ eration choisis de fa¸ con ` a ce que
la condition de descente F(u
(k) + α k δu
(k) ) ∞ < F(u
(k) ) ∞ soit satisfaite
(voir [BR81] pour les d´ etails d’impl´ ementation de l’algorithme).
Quand F(u
(k) ) ∞ → 0, (13.7) implique α k → 1 et on retrouve ainsi la
convergence quadratique de la m´ ethode de Newton. Quand F(u
(k) ) ∞ 1,
ce qui se produit typiquement dans les premi` eres it´ erations, α k est proche de
z´ ero, les it´ erations de Newton sont donc fortement amorties.
Comme alternative ` a (13.7), la suite {α k } peut ˆ etre obtenue en utilisant la
formule plus simple, sugg´ er´ ee dans [Sel84], Chapitre 7
α k = 2
−i(i−1)/2 ,
k= 0, 1, . . .,
(13.8)
o` u i est le premier entier de l’intervalle [1, It max ] tel que la condition de
descente ci-dessus soit satisfaite, It max ´ etant le nombre maximum de cycles
d’amortissement par it´ eration de Newton (´ egal ` a 10 dans les tests num´ eriques).
Afin de les comparer, on a impl´ ement´ e la m´ ethode de Newton standard et la
m´ ethode de Newton amortie. Pour cette derni` ere, on a utilis´ e (13.7) et (13.8)
pour les coefficients α k . Pour retrouver la m´ ethode de Newton standard, on a
pos´ e dans (13.6) α k = 1 pour tout k ≥ 0.
Les tests num´ eriques ont ´ et´ e effectu´ es avec n = 49, b i = −1 pour i ≤ n/2
et les b i restants ´ egaux `
a 1. On a pris λ
2 = 1.67 · 10
−4 , K = 6.77 · 10
−6 , les
n/2 premi` eres composantes du vecteur initial u
(0) ´ egales ` a V a et les autres
composantes ´ egales ` a V b , o` u V a = 0 et V b = 10.
La tol´ erance sur la diff´ erence en deux it´ er´ ees cons´ ecutives (crit` ere avec
lequel on contrˆ ole la convergence de la m´ ethode de Newton amortie (13.6)) a
´ et´ e choisie ´ egale ` a 10
−4 .
La Figure 13.7 montre (` a gauche), pour les trois algorithmes, l’erreur absolue
en ´ echelle logarithmique en fonction du nombre d’it´ erations. Remarquer la
rapidit´ e de la convergence de la m´ ethode de Newton amortie (8 it´ erations
avec (13.7) et 10 avec (13.8)), alors que la m´ ethode de Newton standard
converge tr` es lentement (192 it´ erations).
Il est int´ eressant d’analyser sur la Figure 13.7 (` a droite) le comportement
de la suite α k en fonction du nombre d’it´ erations. La courbe avec des ´ etoiles
correspond ` a (13.7) et celle avec des cercles ` a (13.8). Comme on l’a not´ e
pr´ ec´ edemment, les α k d´ emarrent avec des valeurs tr` es petites, et convergent
rapidement vers 1 quand la m´ ethode de Newton amortie (13.6) entre dans la
r´ egion d’attraction du minimiseur x
∗ .