Exercice 27 Méthode de dichotomie

Partie A : le principe, à la main

1. $f$ est continue sur $[1\,;2]$ (fonction polynôme) et $f(1)=-1<0<9=f(2)$. D'après le théorème des valeurs intermédiaires, l'équation $f(x)=0$ admet au moins une solution dans $]1\,;2[$ ; et comme $f$ est strictement croissante, cette solution est unique. Donc $\boxed{\alpha\in\,]1\,;2[.}$

2. $f(1{,}5)=1{,}5^{3}+3\times 1{,}5-5=3{,}375+4{,}5-5=\boxed{2{,}875>0}$

Cette valeur est du même signe que $f(2)$, et de signe contraire à $f(1)$ : le changement de signe a donc lieu entre $1$ et $1{,}5$. On en déduit donc que $$\boxed{\alpha\in\,]1\,;1{,}5[ \qquad \text{amplitude : } 0{,}5}$$

3. On poursuit, en calculant à chaque étape le milieu puis le signe de son image :

Règle de mise à jour : si $f(m_n)<0$, alors $\alpha>m_n$ (car $f$ est croissante) et l'on remplace $a_n$ par $m_n$ ; si $f(m_n)>0$, alors $\alpha<m_n$ et l'on remplace $b_n$ par $m_n$.

4. Après $4$ étapes : $$\boxed{1{,}125<\alpha<1{,}1875 \qquad\text{d'amplitude}\qquad 0{,}0625=\frac{1}{16}}$$ Vérification : on avait trouvé $\alpha\approx 1{,}155$ à l'exercice 24, ce qui appartient bien à cet intervalle. ✓

Partie B : pourquoi cela fonctionne, et à quelle vitesse

5. À chaque étape, on conserve exactement l'une des deux moitiés de $[a_n\,;b_n]$, donc $$b_{n+1}-a_{n+1}=\frac{b_n-a_n}{2}$$ La suite des amplitudes est donc géométrique de raison $\frac{1}{2}$ et de premier terme $b_0-a_0=2-1=1$. On en déduit donc que $$\boxed{b_n-a_n=1\times\left(\frac{1}{2}\right)^{n}=\frac{1}{2^{n}}}$$

6. Le théorème des valeurs intermédiaires sert à garantir qu'un changement de signe entraîne la présence d'une racine : c'est lui qui autorise, à chaque étape, à affirmer que la moitié conservée contient bien $\alpha$. La stricte monotonie sert à garantir que cette racine est unique, donc que les deux moitiés ne peuvent pas en contenir chacune une, et que l'intervalle conservé est bien le bon.

Sans continuité, tout s'effondre : la fonction $x\mapsto \dfrac{1}{x}$ sur $[-1\,;1]$ vérifie $f(-1)=-1<0<1=f(1)$, et pourtant elle ne s'annule jamais. La dichotomie appliquée à cette fonction convergerait vers $0$, qui n'est pas une racine mais un point de discontinuité.

7. On cherche le plus petit entier $n$ tel que $\dfrac{1}{2^{n}}<10^{-2}$, c'est-à-dire $2^{n}>100$. Or $2^{6}=64$ et $2^{7}=128$, donc $\boxed{n=7}$.

De même, $\dfrac{1}{2^{n}}<10^{-3}$ équivaut à $2^{n}>1\,000$. Or $2^{9}=512$ et $2^{10}=1\,024$, donc $\boxed{n=10}$.

8. La dichotomie demande $\boxed{10 \text{ calculs de } f}$ pour une précision de $10^{-3}$, contre jusqu'à $1\,000$ pour le balayage.

Commentaire. Le balayage divise l'amplitude par $10$ au prix de $10$ fois plus de calculs : le coût est proportionnel à la précision. La dichotomie, elle, divise l'amplitude par $2$ à chaque calcul supplémentaire : gagner un chiffre décimal ne coûte que $3$ ou $4$ étapes de plus. C'est la différence entre une croissance linéaire et une croissance exponentielle du gain de précision.

9. La méthode n'échoue pas. À chaque étape, le signe de $f(m_n)$ est soit celui de $f(a_n)$, soit celui de $f(b_n)$ : dans les deux cas, l'une au moins des deux moitiés présente encore un changement de signe, et c'est celle que l'on conserve. Le procédé converge donc vers une racine.

En revanche, $\boxed{\text{on ne contrôle pas laquelle des trois racines on obtient}}$ : cela dépend entièrement des valeurs des milieux successifs. C'est bien la stricte monotonie, et elle seule, qui garantissait jusqu'ici que la racine trouvée était la racine.

Partie C : mise en œuvre en Python

10. Comme $f$ est croissante, $f(m)<0$ signifie $m<\alpha$ : c'est donc la borne gauche que l'on remonte. Dans le cas contraire, on abaisse la borne droite.

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

11. À chaque tour de boucle, la quantité b - a est divisée par $2$ : elle vaut $\dfrac{b_0-a_0}{2^{n}}$ après $n$ tours. Comme $\left(\frac{1}{2}\right)^{n}$ tend vers $0$, elle finit par devenir strictement inférieure à e, et la condition du while devient fausse. $\boxed{\text{La boucle se termine donc toujours.}}$

12. Il suffit d'ajouter un compteur :

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