Livre_silo 30 août 2013 16:32 Page 203
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
203
8 – Résolution numérique d’équations sur les réels
La démonstration de la terminaison donne facilement cette complexité. En effet, il y a une
k-ième itération si et seulement si
b − a
2 k−1 > 2ε, c’est-à-dire k < ln 2
(
b − a
ε
)
. La boucle
sera donc exécutée exactement
⌈
ln 2
(
b − a
ε
)⌉
− 1 fois.
Pour avoir p bits significatifs, si la solution recherchée est de l’ordre de 1, on prend ε =
1
2 p
et le nombre d’itérations requises est alors de l’ordre de p comme annoncé dans le préambule.
8.1.3 Mise en place, essais
C’est à nouveau un simple exercice de traduction. Il faut noter le assert, qui va provoquer
une erreur particulière AssertionError si la condition n’est pas vérifiée à l’exécution.
PROGRAMME 5 Recherche approchée d’une solution d’une équation par dichotomie
def dichotomie(f, a, b, epsilon):
assert f(a) * f(b) <= 0 and epsilon > 0
c, d = a, b
fc, fd = f(c), f(d)
while d - c > 2 * epsilon:
m = (c + d) / 2.
fm = f(m)
if fc * fm <= 0:
d, fd = m, fm
else:
c, fc = m, fm
return (c + d) / 2.
Reprenons l’exemple 1. On pourrait définir une fonction def g(x): return x**2-2, mais c’est
inutile : Python offre la possibilité de définir des fonctions anonymes via l’opérateur lambda :
In [1]: math.sqrt(2), dichotomie(lambda x : x**2-2, 1, 2, 0.000001)
Out[1]: (1.4142135623730951, 1.4142141342163086)
Pour le deuxième exemple, on utilise la fonction sin de la bibliothèque math qu’on aura
préalablement importée :
In [2]: math.pi, dichotomie(math.sin, 3, 4, 10**-10)
Out[2]: (3.141592653589793, 3.141592653642874)
Visualisons enfin les conséquences du choix de la valeur renvoyée. Le programme qu’on
a écrit plus haut assure d’avoir |x 0 − r| ⩽ ε. Cependant, avec ce choix, la précision peut
devenir moins bonne quand la valeur de ε diminue. Si on fait le choix de renvoyer celui
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
203
8 – Résolution numérique d’équations sur les réels
La démonstration de la terminaison donne facilement cette complexité. En effet, il y a une
k-ième itération si et seulement si
b − a
2 k−1 > 2ε, c’est-à-dire k < ln 2
(
b − a
ε
)
. La boucle
sera donc exécutée exactement
⌈
ln 2
(
b − a
ε
)⌉
− 1 fois.
Pour avoir p bits significatifs, si la solution recherchée est de l’ordre de 1, on prend ε =
1
2 p
et le nombre d’itérations requises est alors de l’ordre de p comme annoncé dans le préambule.
8.1.3 Mise en place, essais
C’est à nouveau un simple exercice de traduction. Il faut noter le assert, qui va provoquer
une erreur particulière AssertionError si la condition n’est pas vérifiée à l’exécution.
PROGRAMME 5 Recherche approchée d’une solution d’une équation par dichotomie
def dichotomie(f, a, b, epsilon):
assert f(a) * f(b) <= 0 and epsilon > 0
c, d = a, b
fc, fd = f(c), f(d)
while d - c > 2 * epsilon:
m = (c + d) / 2.
fm = f(m)
if fc * fm <= 0:
d, fd = m, fm
else:
c, fc = m, fm
return (c + d) / 2.
Reprenons l’exemple 1. On pourrait définir une fonction def g(x): return x**2-2, mais c’est
inutile : Python offre la possibilité de définir des fonctions anonymes via l’opérateur lambda :
In [1]: math.sqrt(2), dichotomie(lambda x : x**2-2, 1, 2, 0.000001)
Out[1]: (1.4142135623730951, 1.4142141342163086)
Pour le deuxième exemple, on utilise la fonction sin de la bibliothèque math qu’on aura
préalablement importée :
In [2]: math.pi, dichotomie(math.sin, 3, 4, 10**-10)
Out[2]: (3.141592653589793, 3.141592653642874)
Visualisons enfin les conséquences du choix de la valeur renvoyée. Le programme qu’on
a écrit plus haut assure d’avoir |x 0 − r| ⩽ ε. Cependant, avec ce choix, la précision peut
devenir moins bonne quand la valeur de ε diminue. Si on fait le choix de renvoyer celui