Exercice 24

1. Soit $P(x) = x^{3} + x^{2} - 4x + 1$. On calcule $$P(-3) = -5, \qquad P(-2) = 5, \qquad P(0) = 1, \qquad P(1) = -1, \qquad P(2) = 5.$$ Par le théorème des valeurs intermédiaires, $P$ s'annule dans chacun des intervalles $]-3\,,-2[$, $]0\,,1[$ et $]1\,,2[$, qui sont disjoints : il y a au moins trois solutions. Il n'y en a pas d'autre : la dérivée $P'(x) = 3x^{2} + 2x - 4$ a deux racines $x_{1} < x_{2}$, et $P$ est strictement monotone sur chacun des intervalles $]-\infty\,,x_{1}]$, $[x_{1}\,,x_{2}]$, $[x_{2}\,,+\infty[$, où elle s'annule donc au plus une fois. $$\boxed{\text{trois solutions, dans } ]-3\,,-2[,\ ]0\,,1[ \text{ et } ]1\,,2[}$$

2. On applique la dichotomie à partir de $[1\,,2]$, où $P(1) < 0 < P(2)$ : $$\begin{array}{c|c|c|c} \text{segment} & \text{milieu } m & P(m) & \text{nouveau segment} \\ \hline \relax[1\,,2] & 1{,}5 & 0{,}625 > 0 & [1\,,1{,}5] \\ \relax[1\,,1{,}5] & 1{,}25 & \approx -0{,}48 < 0 & [1{,}25\,,1{,}5] \\ \relax[1{,}25\,,1{,}5] & 1{,}375 & \approx -0{,}010 < 0 & [1{,}375\,,1{,}5] \\ \relax[1{,}375\,,1{,}5] & 1{,}4375 & \approx 0{,}29 > 0 & [1{,}375\,,1{,}4375] \end{array}$$ Après quatre étapes, $$\boxed{1{,}375 \leqslant \alpha \leqslant 1{,}4375},$$ encadrement d'amplitude $0{,}0625 < 10^{-1}$. Après $n$ étapes, l'amplitude vaut $\frac{1}{2^{n}}$, et $2^{-n} < 10^{-6}$ équivaut à $n \geqslant 20$, puisque $2^{19} = 524\,288 < 10^{6} < 2^{20} = 1\,048\,576$. $$\boxed{20 \text{ étapes}}$$

3. À chaque étape, on garde la moitié aux extrémités de laquelle $f$ prend des valeurs de signes contraires, au sens large :

def dichotomie(f, a, b, eps):
    while b - a >= eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:   # une solution dans [a, m]
            b = m
        else:                  # f(m) et f(b) de signes contraires
            a = m
    return a, b

L'appel dichotomie(lambda x: x**3 + x**2 - 4*x + 1, 1, 2, 1e-6) renvoie un encadrement de $\alpha \approx 1{,}377202$. La terminaison est assurée par la division par deux de l'amplitude, et la correction par l'invariant $f(a)f(b) \leqslant 0$, qui est celui de la démonstration du théorème 8.