Méthode de dichotomie - Python

Introduction :

Dans cette fiche, nous allons voir comment programmer en Python un algorithme qui permet de donner un encadrement, avec une précision donnée, de la solution d’une équation de la forme $f(x)=0$ , où $f$ est une fonction strictement monotone et continue sur un intervalle $[a\ ;\, b]$ ( $a$ et $b$ réels tels que $a < b$ ).
Pour cela, nous allons utiliser une méthode dite de dichotomie.

Méthode de dichotomie (fonction strictement croissante)

Principe

Nous considérons une fonction $f$ continue et strictement croissante sur un intervalle $[a\ ;\, b]$ ( $a$ et $b$ deux réels tels que $a < b$ ), avec $f(a) < 0$ et $f(b) > 0$ . Il existe donc un unique réel $\alpha \in [a\ ;\, b]$ tel que : $f(\alpha)=0$ .

Nous cherchons à encadrer $\alpha$ , avec une précision $p$ donnée, c’est-à-dire que nous cherchons un intervalle de longueur inférieure ou égale à $p$ auquel appartient $\alpha$ .

Voici le principe de la dichotomie :

On calcule le milieu $m$ de l’intervalle $[a\ ;\, b]$ :

$m=\dfrac {a+b}2$

On calcule l’image de $m$ par $f$ .
Si $f(m)=0$ , alors on a la solution : $\alpha=m$ .
Si $f(m) < 0$ (c’est-à-dire du même signe que $f(a)$ ), alors $\alpha$ n’appartient pas à $[a\ ;\, m]$ , $\alpha$ appartient donc à $[m\ ;\, b]$ .
Si $f(m) > 0$ (c’est-à-dire du même signe que $f(b)$ ), alors $\alpha$ appartient à $[a\ ;\, m]$ .
On répète, si besoin, le processus à partir du point 1 avec l’intervalle $[a\ ;\, m]$ ou $[m\ ;\, b]$ .
On arrête dès que la longueur de l’intervalle est inférieure ou égale à la précision $p$ trouvée.

Exemple

Nous considérons la fonction $f$ définie sur $\mathbb R$ par :

$f(x)=x^3+2x^2-4x-1$

Comme fonction polynôme, $f$ est continue sur $\mathbb R$ .
Nous admettons en outre que $f$ est strictement croissante sur l’intervalle $[1\ ;\, 2]$ , avec :

$\begin{aligned} f(1)&=-2 \ f(2)&=7 \end{aligned}$

En appliquant le corollaire du théorème des valeurs intermédiaires, nous pouvons donc dire que l’équation $f(x)=0$ admet une unique solution $\alpha$ sur l’intervalle $[1\ ;\, 2]$ .

À notre niveau, nous ne savons pas résoudre une telle équation. Nous utilisons la méthode de dichotomie pour donner un encadrement du résultat, avec la précision $0,1$ .

Première boucle

$2-1=1 > 0,1$ , nous calculons donc le milieu de $[1\ ;\, 2]$ :

$\dfrac {1+2}2=1,5$

Nous calculons :

$f(1,5)= 1,5^3+2\times 1,5^2-4\times 1,5-1=0,875 > 0$

$f(1,5)$ est donc strictement supérieur à $0$ , la solution $\alpha$ appartient à l’intervalle $[1\ ;\, 1,5]$ .

$1,5-1=0,5 > 0,1$ , nous répétons donc le processus avec l’intervalle $[1\ ;\, 1,5]$ .

Deuxième boucle

Nous calculons le milieu de $[1\ ;\, 1,5]$ :

$\dfrac {1+1,5}2=1,25$

Nous calculons :

$f(1,25)= 1,25^3+2\times 1,25^2-4\times 1,25-1=-0,921875 < 0$

$f(1,25)$ est donc strictement inférieur à $0$ , la solution $\alpha$ appartient à l’intervalle $[1,25\ ;\, 1,5]$ .

$1,5-1,25=0,25 > 0,1$ , nous répétons donc le processus avec l’intervalle $[1,25\ ;\, 1,5]$ .

Troisième boucle

Nous calculons le milieu de $[1,25\ ;\, 1,5]$ :

$\dfrac {1,25+1,5}2=1,375$

Nous calculons et obtenons :

$f(1,375) < 0$

$f(1,375)$ est donc strictement inférieur à $0$ , la solution $\alpha$ appartient à l’intervalle $[1,375\ ;\, 1,5]$ .

$1,5-1,375=0,125 > 0,1$ , nous répétons donc le processus avec l’intervalle $[1,375\ ;\, 1,5]$ .

Quatrième boucle

Nous calculons le milieu de $[1,375\ ;\, 1,5]$ :

$\dfrac {1,375+1,5}2=1,4375$

Nous calculons et obtenons :

$f(1,4375) > 0$

$f(1,375)$ est donc strictement supérieur à $0$ , la solution $\alpha$ appartient à l’intervalle $[1,375\ ;\, 1,4375]$ .

$1,5-1,375=0,0625 < 0,1$ , nous sortons donc de la boucle, l’intervalle obtenu nous convient.

Encadrement obtenu
Nous obtenons ainsi, avec une précision de $0,0625 < 0,1$ :

$\boxed{\alpha\in [1,375\ ;\, 1,4375]}$

Algorithme pour une fonction strictement croissante

Nous venons de le voir, la méthode de dichotomie nous fait parcourir à plusieurs reprises une boucle, nous pouvons donc programmer un algorithme qui nous renvoie l’intervalle recherché.

Nous allons le faire à partir de la fonction $f$ définie dans la première partie :

$f(x)=x^3+2x^2-4x-1$

Nous travaillerons sur un intervalle $I=[a\ ;\, b]$ tel que $f$ est strictement croissante sur $I$ et où $f(a) < 0$ et $f(b) > 0$ .

Nous considérons en outre que la précision $p$ demandée est strictement inférieure à la longueur de l’intervalle (si $p$ était supérieure ou égale à $b-a$ , alors nous aurions déjà la réponse et un algorithme serait inutile…).
En toute rigueur, pour ne pas risquer d’avoir une erreur dans notre programme, nous devrions le faire, comme nous devrions vérifier que le $\purple{\text{a}}$ entré est bien strictement inférieur au $\purple{\text{b}}$ entré ; nous ne le faisons pas ici pour ne pas alourdir l’algorithme, mais vous pouvez bien sûr le faire de votre côté !

Commençons tout simplement par programmer en Python la fonction $\purple{\text{f}}$ .
Elle prend pour paramètre un réel $\purple{\text{x}}$ et qui renverra l’image de ce réel par la fonction $f$ .

\begin{aligned} &\text{ def f(x):} \ &\qquad\text{ return x$\ast\ast\,$3 + 2 $\ast$ x$\ast\ast\,$2 - 4$\ast$x - 1} \end{aligned}

Nous définissons la fonction Python $\purple{\text{dicho\textunderscore croiss(a,b,p)}}$ , où $\purple{\text{a}}$ est la borne inférieure, $\purple{\text{b}}$ la borne supérieure et $\purple{\text{p}}$ la précision voulue :

\text{def dicho\textunderscore croiss(a,b,p):}

Nous précisons l’instruction de la boucle $\purple{\text{while}}$ : nous voulons qu’elle s’exécute tant que la longueur de l’intervalle $\purple{\text{b - a}}$ est strictement supérieure à la précision $\purple{\text{p}}$ donnée :

\text{while b - a > p:}

Nous calculons le milieu $\purple{\text{m}}$ de $[\purple{\text{a}}\ ;\, \purple{\text{b}}]$ :

\text{m = (a + b) / 2}

Nous considérons le cas où l’image de $\purple{\text{m}}$ par $f$ est nulle.
$\purple{\text{m}}$ est alors la solution recherchée, nous sortons de la boucle avec l’instruction $\purple{\text{break}}$ .

\begin{aligned} &\text{if f(m) == 0:} \ &\qquad \text{break} \end{aligned}

Nous considérons maintenant le cas où l’image de $\purple{\text{m}}$ par $f$ est strictement négative.
La solution recherchée appartient alors à l’intervalle $[\purple{\text{m}}\ ;\, \purple{\text{b}}]$ .
Nous assignons donc à $\purple{\text{a}}$ la valeur de $\purple{\text{m}}$ .

\begin{aligned} &\text{elif f(m) < 0:} \ &\qquad \text{a = m} \end{aligned}

Le cas restant est celui où l’image de $\purple{\text{m}}$ par $f$ est strictement positive.
La solution recherchée appartient alors à l’intervalle $[\purple{\text{a}}\ ;\, \purple{\text{m}}]$ .
Nous assignons donc à $\purple{\text{b}}$ la valeur de $\purple{\text{m}}$ .

\begin{aligned} &\text{else:} \ &\qquad \text{b = m} \end{aligned}

La boucle est maintenant exécutée.

Les différentes variables contiennent donc les valeurs qui nous intéressent.
Considérons à nouveau le cas particulier où nous avons obtenu une image de $\purple{\text{m}}$ par $f$ nulle.
Rappelons que nous sommes partis du principe que la précision demandée était strictement inférieure à la longueur de l’intervalle entré en paramètre, soit : $\purple{\text{p}} < \purple{\text{b}}-\purple{\text{a}}$ .
La boucle est au moins exécutée une fois et la variable $\purple{\text{m}}$ est bien définie.
Dans ce cas, nous demandons à notre programme d’afficher qu’il a trouvé la solution exacte et de la donner.

\begin{aligned} &\text{if f(m) == 0:} \ &\qquad \text{print(m,$^{\backprime\backprime}$est la solution recherchée$^{\prime\prime}$)} \end{aligned}

Nous considérons enfin les autres cas.
Nous demandons alors au programme d’afficher l’intervalle recherché.
$\purple{\text{a}}$ contient sa borne inférieure.
$\purple{\text{b}}$ contient sa borne supérieure.
Sa longueur $\purple{\text{b}}-\purple{\text{a}}$ est bien inférieure ou égale à $\purple{\text{p}}$ .

\begin{aligned} &\text{else:} \ &\qquad \text{print($^{\backprime\backprime}$[$^{\prime\prime}$,a, $^{\backprime\backprime}$;$^{\prime\prime}$,b, $^{\backprime\backprime}$]$^{\prime\prime}$)} \end{aligned}

L’algorithme est terminé :

m

while b - a > p:m = (a + b) / 2if f(m) == 0:breakelif f(m) < 0:a = melse:b = mif f(m) == 0: print(m,‵‵est la solution rechercheˊe′′)else: print(‵‵[′′,a, ‵‵;′′,b, ‵‵]′′)

Exemple

Reprenons l’exemple de la première partie, où nous partions de l’intervalle $[1\ ;\, 2]$ et souhaitions une précision de $0,1$ .
Nous entrons donc la commande $\purple{\text{dicho\textunderscore croiss(1,2,0.1)}}$ .

La fonction affichera en retour : $\purple{\text{[1.375\ ;\, 1.4375]}}$ .
Il s’agit bien du résultat que nous avons trouvé.

Vous pouvez bien sûr donner une valeur (positive) inférieure à $0,1$ pour obtenir un encadrement aussi précis que vous le souhaitez.

Astuce

Si vous travaillez avec une fonction différente, qui est continue et strictement croissante sur un intervalle, il suffit de modifier en conséquence la fonction $\purple{\text{f}}$ ; la fonction $\purple{\text{dicho\textunderscore croiss}}$ reste bien sûr valable.
Si, plus généralement, on cherche à encadrer la solution d’une équation du type « $f(x)=k$ », avec $k$ réel quelconque, on peut se ramener à ce que nous venons de voir en posant la fonction $g:x\mapsto f(x)-k$ : l’équation $f(x)=k$ sera alors équivalente à $g(x)=0$ . (Il faudra évidemment montrer auparavant que l’équation $f(x)=k$ admet une unique solution sur l’intervalle considéré.)

Exercice : fonction strictement décroissante

Écrire une fonction Python $\purple{\text{dicho\textunderscore decroiss(a,b,p)}}$ qui permet d’encadrer la solution de $f(x)=0$ , avec $f$ une fonction continue et, cette fois, strictement décroissante sur $[a\ ;\, b]$ , et $f(a) > 0$ et $f(b) < 0$ .

Les modifications sont minimes par rapport à l’algorithme pour une fonction strictement croissante…

Exemple

Considérons encore la fonction $f:x\mapsto x^3+2x^2-4x-1$ , dont nous pouvons montrer la stricte décroissance sur $[-1\ ;\, 0]$ , avec :

$\begin{aligned} f(-1)&=4 \ f(0)&=-1 \end{aligned}$

Par le corollaire du TVI, l’équation $f(x)=0$ admet une unique solution sur l’intervalle $[-1\ ;\, 0]$ .

Si vous exécutez l’algorithme que vous venez d’écrire en entrant $\purple{\text{dicho\textunderscore decroiss(-1,0,0.1)}}$ et si vous n’avez pas commis d’erreur, vous obtiendrez en retour : $\purple{\text{[-0.25\ ;\, -0.1875]}}$ .

Vous pouvez aussi étudier de manière complète la fonction $f$ et montrer que l’équation $f(x)=0$ admet exactement $3$ solutions sur $\mathbb R$ .

En vous servant des deux algorithmes, vous donnerez alors un encadrement avec une précision inférieure ou égale à $10^{-3}$ de ces $3$ solutions.