Livre_silo 30 août 2013 16:32 Page 200
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
200
Informatique pour tous
Deux méthodes vont être présentées :
• La méthode de dichotomie approche une solution avec p bits significatifs en p étapes,
ce qui est déjà très efficace. Ses conditions d’utilisation sont assez simples : on demande
seulement à la fonction d’être continue et de changer de signe. Ceci en fait une méthode
robuste.
• La méthode de Newton a une vitesse de convergence assez diabolique : à chaque étape
supplémentaire, le nombre de bits (ou décimales) significatifs correct(e)s est multiplié
par deux ! On atteint par exemple une précision de 50 bits en sept étapes. En contrepartie, elle nécessite un ensemble de conditions d’application parfois délicat à vérifier.
Une bonne compréhension de ces deux méthodes aidera à faire un choix raisonné. Comme
dans le chapitre précédent, on programmera et testera ces algorithmes, puis on les comparera aux performances des fonctions fournies par la bibliothèque numpy.
8.1 Méthode dichotomique
8.1.1 Principe théorique
Lorsque f est une fonction continue sur un intervalle [a, b], à valeurs réelles, avec f (a)
et f (b) de signe (large) opposé, le théorème des valeurs intermédiaires nous assure que f
s’annule entre a et b. Une démonstration élégante consiste à considérer la borne supérieure
de l’ensemble des x ∈ [a, b] tels que f (x) soit du signe de f (a) : il est assez simple de
montrer que f s’annule en ce point.
Si une telle démonstration est limpide à rédiger, la démonstration dichotomique a le bon
goût d’être constructive, au sens où elle fournit un algorithme pour approcher une solution.
Il s’agit de construire par récurrence une suite de segments emboîtés, qui va « converger »
vers un singleton {l}, et on démontre alors que f (l) = 0. Le point crucial est de préserver
la propriété (ou invariant, si on pense en informaticien) :
f change de signe entre les deux extrémités du segment.
Exemple 1. Le cas de f : x → x
2
− 2 est simple et démonstratif.
• f (1) = −1 < 0 < 2 = f (2), donc l’équation f (x) = 0 possède une solution dans [1, 2].
La valeur médiane de cet intervalle est 1.5.
• f (1.5) = 0.25 > 0 > f (1), donc l’équation f (x) = 0 possède une solution
dans [1, 1.5].
• f (1.25) = −0.4675 < 0 < f (1.5), donc l’équation f (x) = 0 possède une solution
dans [1.25, 1.5].
• ...
• f (1.41430664062) ≃ 0.000263273715973 > 0 > f (1.4140625), donc l’équation
f (x) = 0 possède une solution dans [1.4140625, 1.41430664062].
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
200
Informatique pour tous
Deux méthodes vont être présentées :
• La méthode de dichotomie approche une solution avec p bits significatifs en p étapes,
ce qui est déjà très efficace. Ses conditions d’utilisation sont assez simples : on demande
seulement à la fonction d’être continue et de changer de signe. Ceci en fait une méthode
robuste.
• La méthode de Newton a une vitesse de convergence assez diabolique : à chaque étape
supplémentaire, le nombre de bits (ou décimales) significatifs correct(e)s est multiplié
par deux ! On atteint par exemple une précision de 50 bits en sept étapes. En contrepartie, elle nécessite un ensemble de conditions d’application parfois délicat à vérifier.
Une bonne compréhension de ces deux méthodes aidera à faire un choix raisonné. Comme
dans le chapitre précédent, on programmera et testera ces algorithmes, puis on les comparera aux performances des fonctions fournies par la bibliothèque numpy.
8.1 Méthode dichotomique
8.1.1 Principe théorique
Lorsque f est une fonction continue sur un intervalle [a, b], à valeurs réelles, avec f (a)
et f (b) de signe (large) opposé, le théorème des valeurs intermédiaires nous assure que f
s’annule entre a et b. Une démonstration élégante consiste à considérer la borne supérieure
de l’ensemble des x ∈ [a, b] tels que f (x) soit du signe de f (a) : il est assez simple de
montrer que f s’annule en ce point.
Si une telle démonstration est limpide à rédiger, la démonstration dichotomique a le bon
goût d’être constructive, au sens où elle fournit un algorithme pour approcher une solution.
Il s’agit de construire par récurrence une suite de segments emboîtés, qui va « converger »
vers un singleton {l}, et on démontre alors que f (l) = 0. Le point crucial est de préserver
la propriété (ou invariant, si on pense en informaticien) :
f change de signe entre les deux extrémités du segment.
Exemple 1. Le cas de f : x → x
2
− 2 est simple et démonstratif.
• f (1) = −1 < 0 < 2 = f (2), donc l’équation f (x) = 0 possède une solution dans [1, 2].
La valeur médiane de cet intervalle est 1.5.
• f (1.5) = 0.25 > 0 > f (1), donc l’équation f (x) = 0 possède une solution
dans [1, 1.5].
• f (1.25) = −0.4675 < 0 < f (1.5), donc l’équation f (x) = 0 possède une solution
dans [1.25, 1.5].
• ...
• f (1.41430664062) ≃ 0.000263273715973 > 0 > f (1.4140625), donc l’équation
f (x) = 0 possède une solution dans [1.4140625, 1.41430664062].