Un algorithme de recherche par dichotomie a pour but de déterminer
une valeur approchée (ou un encadrement) permettant de répondre au
problème posé. Ce type d’algorithme consiste à subdiviser l’intervalle de recherche
$[a ; b]$ en deux intervalles $\left[ a; \frac{b-a}{2}\right]$ et
$\left[\frac{b-a}{2}; b\right].$ On réitère la recherche dans le sous-intervalle
le plus pertinent parmi ces deux selon le problème posé.
Soit $f$ une fonction continue et strictement monotone sur un intervalle
$[a ; b]$ tel que 0 soit compris entre $f(a)$ et $f(b).$ La méthode de
recherche par dichotomie permet d’obtenir un encadrement d’amplitude
$10^{–p}$ de la solution de l’équation $f(x) = 0$.
Écrire le code de la fonction dichotomie()
utilisant cet
algorithme et vérifiant les spécifications suivantes :
Paramètres |
f une fonction d'une variable numérique, et
p un nombre entier positif |
Valeur renvoyée |
un intervalle d'amplitude $10^{-p}$ contenant la solution de
l'équation $f(x) = 0$, sous la forme d'une liste à deux éléments
[u, v] contenant les bornes de cet intrevalle. |
Tester cette fonction avec $f : x \to x^3-2x-9$ sur $[1;5]$ et $p = 6$.