Encadrer une solution par dichotomie

5.1 Le principe

On sait que l'équation $x^3 - 3x + 1 = 0$ a une unique solution $\beta$ dans $[0\,;1]$, mais aucune formule simple ne la donne. La méthode de dichotomie (du grec « couper en deux ») l'encadre aussi finement qu'on veut.

On part d'un intervalle $[a\,;b]$ sur lequel $f$ est continue et change de signe.

1. On calcule le milieu $m = \dfrac{a + b}{2}$.
2. Si $f(a)$ et $f(m)$ sont de signes contraires (ou si $f(m) = 0$), une solution se trouve dans $[a\,;m]$ : on remplace $b$ par $m$.
3. Sinon, $f$ change de signe entre $m$ et $b$ : on remplace $a$ par $m$.
4. On recommence. À chaque étape, l'amplitude de l'intervalle est divisée par $2$.

5.2 À la main

Exemple 14. $f(x) = x^3 - 3x + 1$ sur $[0\,;1]$ : $f(0) = 1 > 0$ et $f(1) = -1 < 0$.

étape	intervalle	milieu $m$	$f(m)$	nouvel intervalle
$1$	$[0\,;1]$	$0{,}5$	$-0{,}375 < 0$	$[0\,;0{,}5]$
$2$	$[0\,;0{,}5]$	$0{,}25$	$\approx 0{,}266 > 0$	$[0{,}25\,;0{,}5]$
$3$	$[0{,}25\,;0{,}5]$	$0{,}375$	$\approx -0{,}072 < 0$	$[0{,}25\,;0{,}375]$
$4$	$[0{,}25\,;0{,}375]$	$0{,}3125$	$\approx 0{,}093 > 0$	$[0{,}3125\,;0{,}375]$

Après quatre étapes, $0{,}3125 < \beta < 0{,}375$ : l'amplitude est $\dfrac{1}{16} = 0{,}0625$.

5.3 Combien d'étapes ?

En partant d'un intervalle d'amplitude $b - a$, l'amplitude après $n$ étapes vaut $\dfrac{b - a}{2^n}$. Pour $[0\,;1]$ et une précision de $10^{-3}$, il faut $2^n \geq 1000$. Comme $2^9 = 512$ et $2^{10} = 1024$, il faut dix étapes. Chaque décimale coûte donc un peu plus de trois étapes, car $2^3 = 8 < 10 < 16 = 2^4$.

5.4 L'algorithme

En langage naturel (« $\leftarrow$ » se lit « prend la valeur ») :

Tant que b − a > e
    m ← (a + b) / 2
    Si f(a) × f(m) ≤ 0
        b ← m
    Sinon
        a ← m
    Fin Si
Fin Tant que

En Python :

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

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

dichotomie(0, 1, 0.001) renvoie (0.3466796875, 0.34765625) après dix étapes. Donc $0{,}3466 < \beta < 0{,}3477$ et $\beta \approx 0{,}347$ à $10^{-3}$ près.

5.5 Remarques

• Le test $f(a) \times f(m) \leq 0$ détecte un changement de signe, que $f$ soit croissante ou décroissante.
• L'algorithme suppose que $f$ est continue et change de signe sur l'intervalle de départ ; sinon, rien ne garantit l'existence d'une solution.
• S'il y a plusieurs solutions dans $[a\,;b]$, l'algorithme n'en encadre qu'une.