Livre_silo 30 août 2013 16:32 Page 206
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
206
Informatique pour tous
Cet algorithme d’extraction de racine était probablement connu des Babyloniens (voir en
fin de chapitre l’exercice 8.16), même s’il n’était évidemment pas question de dérivée, mais
plutôt d’un raisonnement géométrique.
8.2.2 Algorithme général, terminaison, correction et complexité
L’algorithme général est celui décrit dans le cas particulier de la section précédente : on
part d’une première valeur et on suit la tangente ; on continue avec l’intersection de cette
tangente avec l’axe des abscisses (figure 8.4) jusqu’à ce que la différence entre deux termes
consécutifs soit assez petite. Il est nécessaire (on croise les doigts) de ne jamais rencontrer
de point en lequel la dérivée de f s’annule.
newton-generique.pdf
Figure 8.4
Dans la méthode de Newton, f ′ (un) =
f (un)
un − u n+1
, donc u n+1 = un −
f (un)
f ′ (un)
·
Données : f, g, u 0 , ε (g représente f
′ )
u ← u 0
v ← u − f (u)/g(u)
tant que |v − u| > ε faire
u ← v
v ← v − f (v)/g(v)
Résultat : v
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
206
Informatique pour tous
Cet algorithme d’extraction de racine était probablement connu des Babyloniens (voir en
fin de chapitre l’exercice 8.16), même s’il n’était évidemment pas question de dérivée, mais
plutôt d’un raisonnement géométrique.
8.2.2 Algorithme général, terminaison, correction et complexité
L’algorithme général est celui décrit dans le cas particulier de la section précédente : on
part d’une première valeur et on suit la tangente ; on continue avec l’intersection de cette
tangente avec l’axe des abscisses (figure 8.4) jusqu’à ce que la différence entre deux termes
consécutifs soit assez petite. Il est nécessaire (on croise les doigts) de ne jamais rencontrer
de point en lequel la dérivée de f s’annule.
newton-generique.pdf
Figure 8.4
Dans la méthode de Newton, f ′ (un) =
f (un)
un − u n+1
, donc u n+1 = un −
f (un)
f ′ (un)
·
Données : f, g, u 0 , ε (g représente f
′ )
u ← u 0
v ← u − f (u)/g(u)
tant que |v − u| > ε faire
u ← v
v ← v − f (v)/g(v)
Résultat : v