Méthode de dichotomie en Python – Terminale spécialité (ch. 6)

Introduction

La méthode de dichotomie permet de calculer une valeur approchée de la solution α d’une équation f(x) = 0, dont l’existence est assurée par le théorème des valeurs intermédiaires. Ce sixième chapitre commence par un rappel du théorème et de son corollaire (théorème de la bijection).

Le principe est expliqué pas à pas : couper l’intervalle en deux et garder la moitié qui contient α, jusqu’à atteindre la précision voulue. Un exemple est traité entièrement à la main avec f(x) = x³ + x − 1 sur [0 ; 1], puis viennent l’algorithme général et sa variante pour résoudre f(x) = k.

Les programmes sont donnés en algorithme, en Python et sur TI-82, avec les erreurs classiques et des exercices, dont une approximation de ln 3 sans la touche ln et un calcul du nombre d’étapes nécessaires.

Chapitre précédent : chapitre 5 – approcher une limite ou une constante · chapitre suivant : chapitre 7 – lire, compléter, corriger un programme (type bac). Retrouvez tous les chapitres dans la rubrique Algorithmique et Python.

Cours proposé par Pr. Elakili sur Mission Maths 360.

Rappel : le théorème des valeurs intermédiaires et son corollaire (théorème de la bijection)

Si $f$ est continue et strictement monotone sur $[a\,;b]$ , alors pour tout réel $k$ compris entre $f(a)$ et $f(b)$ , l’équation $f(x)=k$ admet une unique solution $\alpha$ dans $[a\,;b]$ . En particulier, si $f(a)$ et $f(b)$ sont de signes contraires, $f$ s’annule une seule fois sur $[a\,;b]$ .

Le théorème donne l’existence de $\alpha$ , mais pas sa valeur : la dichotomie permet d’en calculer une valeur approchée.

1. Le principe : couper l’intervalle en deux

On part de $[a\,;b]$ avec $f(a)$ et $f(b)$ de signes contraires. On calcule le milieu $m=\dfrac{a+b}{2}$ :

si $f(a)$ et $f(m)$ sont de signes contraires, c’est-à-dire $f(a)\times f(m)\leqslant 0$ , alors $\alpha\in[a\,;m]$ : on remplace $b$ par $m$ ;
sinon, $\alpha\in[m\,;b]$ : on remplace $a$ par $m$ .

On recommence tant que l’amplitude $b-a$ est supérieure à la précision $\varepsilon$ voulue. À la fin, $a\leqslant\alpha\leqslant b$ avec $b-a\leqslant\varepsilon$ . À chaque étape, l’amplitude est divisée par $2$ : après $n$ étapes, elle vaut $\dfrac{b-a}{2^n}$ .

Exemple à la main : $f(x)=x^3+x-1$ sur $[0\,;1]$ , précision $\varepsilon=0{,}01$

$f$ est continue et $f'(x)=3x^2+1>0$ , donc $f$ est strictement croissante sur $[0\,;1]$ ; $f(0)=-1<0$ et $f(1)=1>0$ . D’après le théorème de la bijection, $f(x)=0$ a une unique solution $\alpha\in[0\,;1]$ .

étape	1	2	3	4	5	6	7
a	0	0,5	0,5	0,625	0,625	0,656 25	0,671 875
b	1	1	0,75	0,75	0,687 5	0,687 5	0,687 5
m	0,5	0,75	0,625	0,687 5	0,656 25	0,671 875	0,679 687 5
signe de f(m)	−	+	−	+	−	−	−

Après 7 étapes : $0{,}679\,687\,5\leqslant\alpha\leqslant 0{,}687\,5$ , amplitude $\dfrac{1}{2^7}\approx 0{,}007\,8<0{,}01$ . Donc $\alpha\approx 0{,}68$ à $10^{-2}$ près (en réalité $\alpha\approx 0{,}682\,3$ ).

2. L’algorithme

Pack 1 – cas général : $f(a)$ et $f(b)$ de signes contraires

Algorithme

Saisir a, b, ε
Tant que b − a > ε
    m ← (a + b)/2
    Si f(a) × f(m) ⩽ 0 alors
        b ← m
    Sinon
        a ← m
    Fin Si
Fin Tant que
Afficher a et b

Python

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

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

TI-82

:Prompt A,B,E
:TantQue B-A>E
:(A+B)/2→M
:Si Y1(A)*Y1(M)⩽0
:Alors
:M→B
:Sinon
:M→A
:Fin
:Fin
:Disp A,B
(avec Y1=X^3+X-1 ; deux Fin :
 un pour Si, un pour TantQue)

Essai : dichotomie(0, 1, 0.01) renvoie (0.6796875, 0.6875) : on retrouve le tableau. Avec eps = 10**-6, on obtient 0,682 327… en 20 étapes.

Combien d’étapes ? (une recherche de seuil, chapitre 4)

Après $n$ étapes, l’amplitude vaut $\dfrac{b-a}{2^n}$ . Sur $[0\,;1]$ , on cherche le plus petit $n$ tel que $\dfrac{1}{2^n}\leqslant\varepsilon$ , c’est-à-dire $2^n\geqslant\dfrac{1}{\varepsilon}$ :

ε	$10^{-1}$	$10^{-2}$	$10^{-3}$	$10^{-6}$
étapes	4	7	10	20

car $2^4=16$ , $2^7=128$ , $2^{10}=1\,024$ , $2^{20}\approx 10^6$ . À retenir : environ 3,3 étapes par décimale. C’est sûr mais lent, comparé à la méthode de Héron (chapitre 5) qui double le nombre de décimales à chaque étape.

Pack 2 – l’équation $f(x)=k$ avec $f$ strictement croissante

On résout $\mathrm{e}^x+x=2$ sur $[0\,;1]$ . La fonction $g(x)=\mathrm{e}^x+x$ est continue et strictement croissante (somme de deux fonctions strictement croissantes), $g(0)=1<2$ et $g(1)=\mathrm{e}+1\approx 3{,}72>2$ : l’équation $g(x)=2$ a une unique solution $\beta\in[0\,;1]$ . Comme $g$ est croissante, le test est plus simple : si $g(m)<k$ , la solution est à droite de $m$ .

Algorithme

Saisir ε
a ← 0 ; b ← 1
Tant que b − a > ε
    m ← (a + b)/2
    Si e^m + m < 2 alors
        a ← m
    Sinon
        b ← m
    Fin Si
Fin Tant que
Afficher a et b

Python

from math import exp

def g(x):
    return exp(x) + x

def solution(k, eps):
    a, b = 0, 1
    while b - a > eps:
        m = (a + b) / 2
        if g(m) < k:
            a = m
        else:
            b = m
    return a, b

TI-82

:Prompt E
:0→A
:1→B
:TantQue B-A>E
:(A+B)/2→M
:Si Y2(M)<2
:Alors
:M→A
:Sinon
:M→B
:Fin
:Fin
:Disp A,B
(avec Y2=e^(X)+X : 2nde ln)

Résultat : solution(2, 0.001) renvoie (0.4423828125, 0.443359375) après 10 étapes : $\beta\approx 0{,}443$ à $10^{-3}$ près.

Remarque

Si $f$ est strictement décroissante, on inverse le test : si $f(m)>k$ , la solution est à droite de $m$ ( $a\leftarrow m$ ).

3. Vérifier sur la TI-82 sans programme

Par la table : Y1=X^3+X-1, puis déf table DébTable=0.6, PasTable=0.01 : $f(0{,}68)<0<f(0{,}69)$ , donc $0{,}68<\alpha<0{,}69$ (c’est la méthode du « balayage »).
Par le graphique : tracer la courbe (graphe), puis 2nde trace (menu CALCULS) → zéro : indiquer une borne gauche, une borne droite et une valeur proche ; la TI affiche X=0.68232780. Pour $g(x)=2$ , tracer aussi Y3=2 et utiliser intersection.

Les erreurs classiques

Oublier de justifier l’existence et l’unicité de $\alpha$ (continuité, stricte monotonie, valeurs aux bornes) avant de lancer l’algorithme.
Inverser a ← m et b ← m : faire un test sur un exemple simple.
Sur la TI, oublier l’un des deux Fin.
Confondre la précision ε (l’amplitude finale) et le nombre d’étapes.

4. À vous de jouer

Exercice 1 · À vous de jouer ★★★

Algorithme + Python + TI-82.

Montrer que $x^3-3x+1=0$ a une unique solution $\alpha$ dans $[0\,;1]$ , puis en donner un encadrement d’amplitude $10^{-3}$ par dichotomie. (Attention : la fonction est décroissante sur $[0\,;1]$ .)
Approcher $\ln 3$ sans la touche ln : montrer que l’équation $\mathrm{e}^x=3$ a une unique solution dans $[1\,;2]$ , puis l’approcher à $10^{-3}$ près.
Combien d’étapes faut-il pour obtenir, sur un intervalle de longueur $2$ , un encadrement d’amplitude $10^{-4}$ ? Écrire le programme qui calcule ce nombre.