Dichotomie, et le nombre de tours

Fonctions réelles d'une variable réelle · Continuité, théorème des valeurs intermédiaires et bijection · niveau 3 (difficile)

Énoncé

Écrire une fonction Python dichotomie(f, a, b, eps) qui suppose $f (a) f (b) \leq 0$ et renvoie une racine à $ε$ près. Combien de tours faut-il pour $a = 0$ , $b = 10$ et $ε = 1 0^{- 6}$ ? Vérifier la formule $(b - a) / 2^{n} \leq ε$ .

Corrigé


def dichotomie(f, a, b, eps):
    assert f(a) * f(b) <= 0, "pas de changement de signe sur [a, b]"
    while b - a > eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m          # la racine est dans [a, m]
        else:
            a = m          # elle est dans [m, b]
    return (a + b) / 2

Le nombre de tours. Chaque tour divise la longueur par deux, donc après $n$ tours elle vaut $\frac{b - a}{2 ^{n}}$ . La condition d'arrêt est

$\frac{b - a}{2 ^{n}} \leq ε ⟺ 2^{n} \geq \frac{b - a}{ε} ⟺ n \geq lo g_{2} (\frac{b - a}{ε}) .$

Ici $\frac{10}{1 0 ^{- 6}} = 1 0^{7}$ et $lo g_{2} (1 0^{7}) \approx 23, 25$ : il faut $n = 24$ tours.

Ce qui fait marcher la méthode, c'est le théorème des valeurs intermédiaires, invoqué à chaque tour : $f$ continue et de signes opposés aux bornes garantit une racine dans l'intervalle courant. Sans continuité, la fonction renverrait un nombre sans aucune racine à côté.

La convergence est lente mais sûre : chaque tour gagne un bit, soit environ trois tours par décimale.

Énoncé

Corrigé

Exercices semblables