Dichotomie : le nombre d'itérations se calcule d'avance

L'unicité d'abord. $g(x)=x^3+x-1$ est continue et $g^{\prime }(x)=3x^2+1>0$ : $g$ est strictement croissante. Comme $g(0)=-1<0<1=g(1)$, elle s'annule une fois et une seule sur $[0,1]$.

Le nombre d'itérations se déduit. Chaque tour divise par deux la longueur de l'intervalle, qui vaut donc $2^{-n}$ après $n$ tours, la racine y étant enfermée. Il suffit que

$$2^{-n}\le 10^{-6}⟺n\ge \frac{6\ln 10}{\ln 2}\approx 19,93.$$

Vingt itérations suffisent, et dix-neuf ne suffisent pas au vu de cette majoration, puisque $2^{-19}\approx 1,9\times 10^{-6}$.

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

def dichotomie(a, b, n):
    for k in range(n):
        m = (a + b) / 2
        # on garde la moitie ou g change de signe
        if g(a) * g(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2

print(dichotomie(0.0, 1.0, 20))     # 0.6823277473449707

Contrôle. La valeur affichée vérifie $g(0,68232775)\approx -1,4\times 10^{-7}$ : la racine est bien là. On gagne même un facteur $2$ sur la précision en rendant le milieu du dernier intervalle plutôt qu'une de ses bornes.

Le point à retenir. Le rang d'arrêt résulte de l'étude mathématique, il ne se choisit pas au juger. Ici l'étude donne un nombre d'itérations connu à l'avance : c'est ce qui distingue une boucle for de vingt tours, dont on sait ce qu'elle garantit, d'une boucle while dont on espère seulement qu'elle s'arrête.