Localiser avant d'affiner

def f(x):
    return x ** 3 + x - 1

def balayage(a, b, pas):
    x = a
    while x < b:
        if f(x) * f(x + pas) <= 0:
            return (x, x + pas)
        x = x + pas
    return None

def dichotomie(a, b, eps):
    tours = 0
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
        tours = tours + 1
    return (a + b) / 2, tours

Le balayage rend $(0,6;0,7)$ : en effet $f(0,6)=-0,184<0$ et $f(0,7)=0,043>0$. La fonction $f$ est continue, donc le théorème des valeurs intermédiaires garantit une racine dans cet intervalle.

Le nombre de tours. Chaque tour divise la largeur par deux : après $t$ tours elle vaut $0,1\times 2^{-t}$. La boucle s'arrête dès que cette largeur atteint $10^{-10}$, soit

$$2^t\ge 10^9,t\ge 9{\log }_{2}10\approx 29,9.$$

Donc 30 tours, et dichotomie(0.6, 0.7, 1e-10) rend $0,6823278038$.

Pourquoi balayer d'abord. Ici $f(0)f(2)<0$ et l'on pourrait partir de $[0,2]$ directement. Mais si la fonction avait deux racines dans l'intervalle, le produit $f(a)f(b)$ serait positif et la dichotomie ne démarrerait pas — sans la moindre erreur, en renvoyant un nombre faux. Le balayage isole un intervalle où le changement de signe est constaté.

Le point à retenir. Trente tours pour dix décimales : c'est le ${\log }_2$ à l'œuvre, la même loi que pour la recherche dans une liste triée. Diviser par deux à chaque étape est ce qu'un algorithme peut faire de mieux quand il ne sait rien d'autre que le signe.