Chapitre 12Suites de réels

ThéoriesMéthode de dichotomie

Soit $f$ une fonction continue et strictement monotone sur $I=[a;b]$ telle que $f(a)\times f(b) \lt 0$.Nous savons qu’alors $f$ est une bijection de $I$ sur son image et donc nous savons que l’équation « $f(x)=0$ » admet une unique solution $\alpha$ dans $I$.La méthode de dichotomie permet d’obtenir de manière algorithmique une valeur approchée de $\alpha$ à une précision donnée.
Méthode
Nous construisons deux suites de réels $(a_n)_n$ et $(b_n)_n$ adjacentes telles que pour tout entier naturel $n$, $a_n\le \alpha \le b_n$. La construction de ces deux suites se fait par l’intermédiaire d’une suite d’intervalles $I_n=[a_n;b_n]$.Pour cela, nous procédons par récurrence :
  • Posons $a_0=a$ et $b_0=b$ donc $I_0=[a;b]$.
  • Supposons qu’il existe deux entiers $a_n$ et $b_n$ tels que $a_n\le \alpha \le b_n$ et $I_n=[a_n;b_n]$.Considérons le milieu $\dfrac{a_n+b_n}{2}$ de l’intervalle $I_n$. Deux cas se présentent :
    1. Si $f(a_n)f\left(\dfrac{a_n+b_n}{2}\right)\le 0$, alors $\alpha \in \left[a_n;\dfrac{a_n+b_n}{2}\right]$.Dans ce cas, nous posons $a_n+1=a_n$ et $b_n+1=\dfrac{a_n+b_n}{2}$.
    2. Sinon $\alpha\in\left[\dfrac{a_n+b_n}{2};b_n\right]$.Nous posons alors $a_n+1=\dfrac{a_n+b_n}{2}$ et $b_n+1=b_n$.
    A chaque étape, nous prenons une moitié de l’intervalle précédent, d’où le nom de cette méthode puisque dichotomie signifie partage en deux parties.On montre facilement que les suites $(a_n)_n$ et $(b_n)_n$ sont adjacentes.D’autre part :\[\text{Pour tout entier naturel $n$,}\ a_n\le \alpha \le b_n.\]Nous en déduisons :\[\lim a_n=\lim b_n=\alpha.\]Enfin :\[\text{Pour tout entier naturel $n$,}\ b_n-a_n=\frac{1}{2^n}(b-a).\]
  • Nous avons donc :\[\text{Pour tout entier naturel $n$,}\ 0\le\alpha -a_n\le\frac{1}{2^n}(b-a).\]Cette dernière relation permet de dire que le réel $a_n$ est une valeur approchée de $\alpha$ à la précision $\dfrac{1}{2^n}(b-a)$.
Cette méthode fournit un algorithme de calcul de résolution d’une équation de la forme « $y=f(x)$ ».
Exemple

Soient $f$ la fonction définie par : $f(x)=x^3-5$, $a=1$ et $b=2$.

  • On vérifie que $f$ est strictement croissante sur $\mathbb{R}$.
  • Nous avons $f(1)\lt 0$ et $f(2)\gt 0$.

$f$ admet donc une unique racine $\alpha$ qui est comprise entre $1$ et $2$. Un calcul direct fournit : $\alpha=\sqrt[3]{5}$.On peut aussi appliquer la méthode de dichotomie pour avoir une valeur approchée de $\sqrt[3]{5}$.

Problème : Comment faut-il choisir $n$ pour avoir une valeur approchée à $10^{-3}$ prés ?
On doit résoudre $\dfrac{1}{2^n}\le 10^{-3}$. A l’aide de la calculatrice on obtient : $n\ge 10$.
Voir l'animation

Vous pourrez résoudre directement cette inéquation à l’aide des logarithmes dès que vous aurez vu cette nouvelle fonction.