220
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
x
(2)
a
b
x
f(x)
y
x
(1)
x
(0)
0
5
10
15
20
25
30
35
10
−15
10
−10
10
−5
10
0
(1)
(2)
(3)
(4)
Fig. 6.4. Les deux premi` eres ´ etapes de la m´ ethode de Newton (` a gauche) ; historique
des convergences de l’Exemple 6.4 pour les m´ ethodes de la corde (1), de dichotomie
(2), de la s´ ecante (3) et de Newton (4) (` a droite). Le nombre d’it´ erations est report´ e
sur l’axe des x et l’erreur absolue sur l’axe des y
La m´ ethode de Newton. Supposons f ∈ C
1 (I) et f
(α) = 0 (i.e. α est une
racine simple de f). En posant
q k = f
(x
(k) )
∀k ≥ 0
et en se donnant la valeur initiale x
(0) , on obtient la m´ ethode de Newton
(encore appel´ ee m´ ethode de Newton-Raphson ou des tangentes)
x
(k+1) = x
(k)
−
f(x
(k) )
f (x (k) )
∀k ≥ 0.
(6.16)
A la k-` eme it´ eration, la m´ ethode de Newton n´ ecessite l’´ evaluation des deux
fonctions f et f
au point x
(k) . Cet effort de calcul suppl´ ementaire est plus
que compens´ e par une acc´ el´ eration de la convergence, la m´ ethode de Newton
´ etant d’ordre 2 (voir Section 6.3.1).
Exemple 6.4 Comparons les m´ ethodes introduites jusqu’` a pr´ esent pour approcher
la racine α 0.5149 de la fonction f (x) = cos
2 (2x) − x
2 sur l’intervalle ]0, 1.5[. La
tol´ erance ε sur l’erreur absolue est fix´ ee ` a 10
−10 et l’historique des convergences est
dessin´ e sur la Figure 6.4 (` a droite). Pour toutes les m´ ethodes, on prend x
(0) = 0.75
comme donn´ ee initiale. Pour la m´ ethode de la s´ ecante on se donne aussi x
(−1) = 0.
L’analyse des r´ esultats met en ´ evidence la lenteur de la convergence de la m´ ethode de la corde. L’´ evolution de l’erreur de la m´ ethode de la fausse position est
similaire `
a celle de la m´ ethode de la s´ ecante, on ne l’a donc pas indiqu´ ee sur la
Figure 6.4.
Il est int´ eressant de comparer les performances des m´ ethodes de Newton et de
la s´ ecante (les deux ayant un ordre p > 1) en terme de coˆ ut de calcul. On peut
montrer qu’il est plus avantageux d’utiliser la m´ ethode de la s´ ecante quand le nombre
d’op´ erations sur les flottants pour ´ evaluer f
est environ le double de celui n´ ecessaire
` a l’´ evaluation de f (voir [Atk89], p. 71-73). Dans l’exemple consid´ er´ e, la m´ ethode de
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
x
(2)
a
b
x
f(x)
y
x
(1)
x
(0)
0
5
10
15
20
25
30
35
10
−15
10
−10
10
−5
10
0
(1)
(2)
(3)
(4)
Fig. 6.4. Les deux premi` eres ´ etapes de la m´ ethode de Newton (` a gauche) ; historique
des convergences de l’Exemple 6.4 pour les m´ ethodes de la corde (1), de dichotomie
(2), de la s´ ecante (3) et de Newton (4) (` a droite). Le nombre d’it´ erations est report´ e
sur l’axe des x et l’erreur absolue sur l’axe des y
La m´ ethode de Newton. Supposons f ∈ C
1 (I) et f
(α) = 0 (i.e. α est une
racine simple de f). En posant
q k = f
(x
(k) )
∀k ≥ 0
et en se donnant la valeur initiale x
(0) , on obtient la m´ ethode de Newton
(encore appel´ ee m´ ethode de Newton-Raphson ou des tangentes)
x
(k+1) = x
(k)
−
f(x
(k) )
f (x (k) )
∀k ≥ 0.
(6.16)
A la k-` eme it´ eration, la m´ ethode de Newton n´ ecessite l’´ evaluation des deux
fonctions f et f
au point x
(k) . Cet effort de calcul suppl´ ementaire est plus
que compens´ e par une acc´ el´ eration de la convergence, la m´ ethode de Newton
´ etant d’ordre 2 (voir Section 6.3.1).
Exemple 6.4 Comparons les m´ ethodes introduites jusqu’` a pr´ esent pour approcher
la racine α 0.5149 de la fonction f (x) = cos
2 (2x) − x
2 sur l’intervalle ]0, 1.5[. La
tol´ erance ε sur l’erreur absolue est fix´ ee ` a 10
−10 et l’historique des convergences est
dessin´ e sur la Figure 6.4 (` a droite). Pour toutes les m´ ethodes, on prend x
(0) = 0.75
comme donn´ ee initiale. Pour la m´ ethode de la s´ ecante on se donne aussi x
(−1) = 0.
L’analyse des r´ esultats met en ´ evidence la lenteur de la convergence de la m´ ethode de la corde. L’´ evolution de l’erreur de la m´ ethode de la fausse position est
similaire `
a celle de la m´ ethode de la s´ ecante, on ne l’a donc pas indiqu´ ee sur la
Figure 6.4.
Il est int´ eressant de comparer les performances des m´ ethodes de Newton et de
la s´ ecante (les deux ayant un ordre p > 1) en terme de coˆ ut de calcul. On peut
montrer qu’il est plus avantageux d’utiliser la m´ ethode de la s´ ecante quand le nombre
d’op´ erations sur les flottants pour ´ evaluer f
est environ le double de celui n´ ecessaire
` a l’´ evaluation de f (voir [Atk89], p. 71-73). Dans l’exemple consid´ er´ e, la m´ ethode de