Une dichotomie et son nombre de tours

Le code.

def f(x):
    return x * x - 2

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

print(dichotomie(f, 1, 2, 1e-6))    # (1.4142136..., 20)
print(2 ** 0.5)                     #  1.4142135623730951

Les hypothèses sont vérifiées. $f$ est continue sur $[1,2]$ (c'est une fonction polynomiale), et

$$f(1)=-1<0,f(2)=2>0.$$

Le théorème des valeurs intermédiaires garantit donc l'existence d'une racine dans $]1,2[$ ; et $f$ y est strictement croissante, donc cette racine est unique. C'est $\sqrt{2}$.

Le nombre de tours. L'intervalle a pour longueur $1$ au départ, et chaque tour la divise par $2$ : après $n$ tours elle vaut $2^{-n}$. La condition d'arrêt $2^{-n}\le 10^{-6}$ s'écrit

$$n\ge \frac{6\ln 10}{\ln 2}\approx 19,93,$$

donc $20$ tours, ce que confirme l'exécution.

Ce que la dichotomie coûte, et ce qu'elle garantit. Chaque tour ne gagne qu'un facteur $2$, soit environ un tiers de décimale : atteindre $10^{-12}$ demanderait $40$ tours. En échange, elle ne réclame que la continuité et un changement de signe — aucune dérivée, aucune hypothèse fine. C'est la méthode la plus lente et la plus sûre.