Livre_silo 30 août 2013 16:32 Page 207
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
207
8 – Résolution numérique d’équations sur les réels
Avant même de parler de complexité d’un algorithme, il faut démontrer sa terminaison et
sa correction, c’est-à-dire ici d’une part qu’il n’y aura pas de division par zéro, et d’autre
part que le résultat renvoyé r sera tel qu’il existe x 0 zéro de f tel que |x 0 − r| ⩽ ε.
Or, cet algorithme est un cauchemar pour l’informaticien :
• On peut rencontrer des divisions par zéro.
• La terminaison n’ est pas assurée.
• Même si un résultat est renvoyé, il peut être éloigné d’un zéro de f .
En pratique, les programmes réalisant la méthode de Newton sont donc plus complexes.
Voici une condition suffisante simple qui assure la convergence (au moins mathématique, en
faisant abstraction des erreurs de calcul) : si f est de classe C
1 , convexe sur un intervalle I,
f possède un point d’annulation sur I et u 0 ∈ I est tel que f (u 0 ) > 0, alors la méthode
de Newton appliquée depuis le premier terme u 0 est convergente vers un zéro de f .
Cette condition peut sembler déraisonnablement compliquée. De fait, il ne faut pas espérer
une vérification automatique d’une telle propriété. Cependant, pour une fonction raisonnable, la concavité/convexité locale est la règle : si f est de classe C
2 avec f
′′ (x 0 ) ̸ = 0, alors
f
′′ est de signe strict constant au voisinage de x 0 . Ainsi, si on part de u 0 assez proche d’un
zéro vérifiant cette condition, alors la méthode de Newton convergera vers ce zéro.
Il est à noter enfin qu’ on trouve parfois la condition d’arrêt |u n+1 − u n | ⩽ ε remplacée
par une condition de la forme |f (u n )| ⩽ ε
′ , ce qui est une condition de même nature...
du moins si f
′ (x 0 ) ̸ = 0.
Exercice 8.4 Commenter cette condition d’arrêt, lorsque f ′ (x 0 ) = f ′′ (x 0 ) = 0 et f (3) (x 0 ) ̸ = 0.
8.2.3 Évaluation de la dérivée
La méthode de Newton nécessite la connaissance de la dérivée de la fonction en jeu. Dans
certains contextes, la fonction dérivée est connue a priori (si on souhaite programmer la
méthode de Newton de façon non générique, pour une fonction bien déterminée). Dans
d’autres contextes tels que le calcul formel, on a la possibilité de calculer une expression
de f
′ à l’aide de celle de f .
On peut aussi vouloir appliquer la méthode de Newton avec la simple connaissance de f ,
connue via ses valeurs données par une fonction, et non via une expression. Il convient alors
d’approximer les valeurs de f
′ au mieux.
Une première façon raisonnable de le faire consiste à écrire : f
′ (x) ≃
f (x + h) − f (x)
h
,
avec h différent de zéro mais assez petit. Le théorème de Taylor-Young assure que si f est
deux fois dérivable en x 0 et f
′′ (x 0 ) ̸ = 0, alors :
f (x 0 + h) − f (x 0 )
h
− f
′ (x 0 ) ∼
f
′′ (x 0 )
2
h.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
207
8 – Résolution numérique d’équations sur les réels
Avant même de parler de complexité d’un algorithme, il faut démontrer sa terminaison et
sa correction, c’est-à-dire ici d’une part qu’il n’y aura pas de division par zéro, et d’autre
part que le résultat renvoyé r sera tel qu’il existe x 0 zéro de f tel que |x 0 − r| ⩽ ε.
Or, cet algorithme est un cauchemar pour l’informaticien :
• On peut rencontrer des divisions par zéro.
• La terminaison n’ est pas assurée.
• Même si un résultat est renvoyé, il peut être éloigné d’un zéro de f .
En pratique, les programmes réalisant la méthode de Newton sont donc plus complexes.
Voici une condition suffisante simple qui assure la convergence (au moins mathématique, en
faisant abstraction des erreurs de calcul) : si f est de classe C
1 , convexe sur un intervalle I,
f possède un point d’annulation sur I et u 0 ∈ I est tel que f (u 0 ) > 0, alors la méthode
de Newton appliquée depuis le premier terme u 0 est convergente vers un zéro de f .
Cette condition peut sembler déraisonnablement compliquée. De fait, il ne faut pas espérer
une vérification automatique d’une telle propriété. Cependant, pour une fonction raisonnable, la concavité/convexité locale est la règle : si f est de classe C
2 avec f
′′ (x 0 ) ̸ = 0, alors
f
′′ est de signe strict constant au voisinage de x 0 . Ainsi, si on part de u 0 assez proche d’un
zéro vérifiant cette condition, alors la méthode de Newton convergera vers ce zéro.
Il est à noter enfin qu’ on trouve parfois la condition d’arrêt |u n+1 − u n | ⩽ ε remplacée
par une condition de la forme |f (u n )| ⩽ ε
′ , ce qui est une condition de même nature...
du moins si f
′ (x 0 ) ̸ = 0.
Exercice 8.4 Commenter cette condition d’arrêt, lorsque f ′ (x 0 ) = f ′′ (x 0 ) = 0 et f (3) (x 0 ) ̸ = 0.
8.2.3 Évaluation de la dérivée
La méthode de Newton nécessite la connaissance de la dérivée de la fonction en jeu. Dans
certains contextes, la fonction dérivée est connue a priori (si on souhaite programmer la
méthode de Newton de façon non générique, pour une fonction bien déterminée). Dans
d’autres contextes tels que le calcul formel, on a la possibilité de calculer une expression
de f
′ à l’aide de celle de f .
On peut aussi vouloir appliquer la méthode de Newton avec la simple connaissance de f ,
connue via ses valeurs données par une fonction, et non via une expression. Il convient alors
d’approximer les valeurs de f
′ au mieux.
Une première façon raisonnable de le faire consiste à écrire : f
′ (x) ≃
f (x + h) − f (x)
h
,
avec h différent de zéro mais assez petit. Le théorème de Taylor-Young assure que si f est
deux fois dérivable en x 0 et f
′′ (x 0 ) ̸ = 0, alors :
f (x 0 + h) − f (x 0 )
h
− f
′ (x 0 ) ∼
f
′′ (x 0 )
2
h.