Exercice 42

1. Supposons $\mu \geqslant 0$, et soit $x \in \,]a_{2}\,,b]$. Le lemme des trois pentes (proposition 8), appliqué à $a_{1} < a_{2} < x$, donne $$\frac{f(x) - f(a_{2})}{x - a_{2}} \geqslant \frac{f(a_{2}) - f(a_{1})}{a_{2} - a_{1}} = \mu \geqslant 0,$$ donc $f(x) \geqslant f(a_{2})$. La fonction continue $f$ atteint son minimum sur le segment $[a\,,a_{2}]$ en un point $c$ (chapitre 8), et $f(c) \leqslant f(a_{2}) \leqslant f(x)$ pour tout $x > a_{2}$ : $c$ réalise le minimum sur $[a\,,b]$. Si $\mu \leqslant 0$, le lemme appliqué à $x < a_{1} < a_{2}$ donne de même $\frac{f(a_{1}) - f(x)}{a_{1} - x} \leqslant \mu \leqslant 0$, donc $f(x) \geqslant f(a_{1})$ pour $x < a_{1}$, et le minimum est atteint sur $[a_{1}\,,b]$. $$\boxed{\mu \geqslant 0 : \text{minimum sur } [a\,,a_{2}] ; \quad \mu \leqslant 0 : \text{minimum sur } [a_{1}\,,b]}$$

2. À chaque étape, on élimine un tiers du segment, et l'amplitude est multipliée par $\frac{2}{3}$. Le signe de $\mu$ est celui de $f(a_{2}) - f(a_{1})$ :

def trichotomie(f, a, b, eps):
    n = 0                       # nombre d'etapes
    while b - a >= eps:
        a1 = (2*a + b) / 3
        a2 = (a + 2*b) / 3
        if f(a2) >= f(a1):      # mu >= 0 : minimum dans [a, a2]
            b = a2
        else:                   # mu < 0 : minimum dans [a1, b]
            a = a1
        n += 1
    return a, b, n

L'invariant de boucle est « $f$ atteint son minimum sur $[a\,,b]$ en un point du segment courant », conservé d'après la question 1, et la boucle termine puisque l'amplitude tend vers $0$.

3. La fonction $x \mapsto \mathrm{e}^{x} + x^{2}$ est convexe, de dérivée seconde $\mathrm{e}^{x} + 2 > 0$. Après $n$ étapes, l'amplitude vaut $\big(\frac{2}{3}\big)^{n}$, et $$\Big(\frac{2}{3}\Big)^{n} < 10^{-6} \iff n > \frac{6\ln 10}{\ln 3 - \ln 2} \approx 34{,}07.$$

$$\boxed{35 \text{ étapes}}$$ L'appel trichotomie(lambda x: exp(x) + x**2, -1, 0, 1e-6) renvoie bien $35$ étapes et un encadrement de $-0{,}351734$, qui est la solution de $\mathrm{e}^{x} + 2x = 0$, où s'annule la dérivée. La dichotomie du chapitre 8 aurait demandé $20$ étapes : la trichotomie, qui n'élimine qu'un tiers à chaque fois, est plus lente, mais elle ne demande pas de connaître la dérivée.