La dichotomie, rivale de Newton

Exercice supplémentaire · niveau 3 (difficile) · mathématiques (première), chapitre 5 — Variations et courbes représentatives des fonctions · Optimisation avancée et algorithmes

Énoncé

La dichotomie, rivale de Newton. Pour résoudre $f (x) = 0$ sur $[a; b]$ avec $f (a)$ et $f (b)$ de signes contraires, on teste le signe de $f$ au milieu de l'intervalle et on ne garde que la moitié qui change de signe.

Écrire une fonction Python dichotomie(f, a, b, eps) rendant une valeur approchée d'une racine à eps près.
L'appliquer à $f (x) = x^{3} + x - 5$ sur $[1; 2]$ avec $eps = 1 0^{- 6}$ .
Combien d'étapes faut-il ? Comparer au nombre d'itérations de Newton pour la même précision.

Corrigé


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

2. Ici $f (1) = - 3 < 0$ et $f (2) = 5 > 0$ : la fonction change de signe sur $[1; 2]$ . L'appel dichotomie(f, 1, 2, 1e-6) renvoie $\approx 1, 515980$ . 3. Chaque étape divise la longueur de l'intervalle par $2$ : après $n$ étapes elle vaut $\frac{1}{2 ^{n}}$ . La condition $\frac{1}{2 ^{n}} < 1 0^{- 6}$ impose $2^{n} > 1 0^{6}$ , soit $n = 20$ étapes. La méthode de Newton, partant de $x_{0} = 1, 5$ , donne $x_{1} = 1, 516129$ , $x_{2} = 1, 515980$ , et $x_{3}$ est déjà stable à $1 0^{- 9}$ : trois itérations suffisent. Ce que chacune apporte : la dichotomie gagne une décimale toutes les trois ou quatre étapes mais ne peut pas échouer dès lors que les signes sont contraires ; Newton double le nombre de décimales à chaque pas mais peut diverger, comme le montre l'exercice suivant.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.