Zéro d'une fonction continue

Algorithmes dichotomiques · niveau 2

Énoncé

Soit $f$ une fonction continue vérifiant $f (a) \leq 0 \leq f (b)$ . Écrire zero(f, a, b, eps) renvoyant un réel $x$ tel que $f$ possède un zéro dans $[x, x + eps]$ , par dichotomie. Estimer le nombre d'étapes pour approcher $32$ à $1 0^{- 10}$ près.

Corrigé

def zero(f, a: float, b: float, eps: float) -> float:
    """Précondition : f(a) <= 0 <= f(b), a <= b, eps > 0."""
    while b - a > eps:
        # Invariant : f(a) <= 0 <= f(b)
        m = (a + b) / 2
        if f(m) <= 0:
            a = m
        else:
            b = m
    return a

Nombre d'étapes : À chaque étape, la largeur de l'intervalle $b - a$ est divisée par 2. Partant de $a = 0$ et $b = 2$ avec une tolérance $eps = 1 0^{- 10}$ , on cherche le nombre d'itérations $k$ tel que : $\frac{b - a}{2 ^{k}} \leq eps ⟹ \frac{2}{2 ^{k}} \leq 1 0^{- 10} ⟹ 2^{k} \geq 2 \cdot 1 0^{10} ⟹ k \geq ⌈ lo g_{2} (2 \cdot 1 0^{10})⌉ = 35$ L'algorithme demande 35 évaluations de la fonction.

Énoncé

Corrigé

Exercices semblables