Médaille
N°1 pour apprendre & réviser du collège au lycée.
Méthode de dichotomie - Python
Fiche méthode

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)=0f(x)=0, où ff est une fonction strictement monotone et continue sur un intervalle [a ;b][a\ ;\, b] (aa et bb réels tels que a<ba < 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 ff continue et strictement croissante sur un intervalle [a ;b][a\ ;\, b] (aa et bb deux réels tels que a<ba < b), avec f(a)<0f(a) < 0 et f(b)>0f(b) > 0. Il existe donc un unique réel α[a ;b]\alpha \in [a\ ;\, b] tel que : f(α)=0f(\alpha)=0.

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

Voici le principe de la dichotomie :

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

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

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

Exemple

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

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

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

f(1)=2f(2)=7\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)=0f(x)=0 admet une unique solution α\alpha sur l’intervalle [1 ;2][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,10,1.

Première boucle

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

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

  • Nous calculons :

f(1,5)=1,53+2×1,524×1,51=0,875>0f(1,5)= 1,5^3+2\times 1,5^2-4\times 1,5-1=0,875 > 0

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

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

Deuxième boucle

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

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

  • Nous calculons :

f(1,25)=1,253+2×1,2524×1,251=0,921875<0f(1,25)= 1,25^3+2\times 1,25^2-4\times 1,25-1=-0,921875 < 0

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

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

Troisième boucle

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

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

  • Nous calculons et obtenons :

f(1,375)<0f(1,375) < 0

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

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

Quatrième boucle

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

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

  • Nous calculons et obtenons :

f(1,4375)>0f(1,4375) > 0

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

  • 1,51,375=0,0625<0,11,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,10,0625 < 0,1 :

α[1,375 ;1,4375]\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 ff définie dans la première partie :

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

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

Nous considérons en outre que la précision pp demandée est strictement inférieure à la longueur de l’intervalle (si pp était supérieure ou égale à bab-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 a\purple{\text{a}} entré est bien strictement inférieur au b\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 f\purple{\text{f}}.
  • Elle prend pour paramètre un réel x\purple{\text{x}} et qui renverra l’image de ce réel par la fonction ff.

 def f(x): return x3 + 2  x2 - 4x - 1\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 dichocroiss(a,b,p)\purple{\text{dicho\textunderscore croiss(a,b,p)}}croiss(a,b,p), où a\purple{\text{a}} est la borne inférieure, b\purple{\text{b}} la borne supérieure et p\purple{\text{p}} la précision voulue :

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

    while b - a > p:\text{while b - a > p:}
    • Nous calculons le milieu m\purple{\text{m}} de [a ;b][\purple{\text{a}}\ ;\, \purple{\text{b}}] :

    m = (a + b) / 2\text{m = (a + b) / 2}
    • Nous considérons le cas où l’image de m\purple{\text{m}} par ff est nulle.
    • m\purple{\text{m}} est alors la solution recherchée, nous sortons de la boucle avec l’instruction break\purple{\text{break}}.

    if f(m) == 0:break\begin{aligned} &\text{if f(m) == 0:} \ &\qquad \text{break} \end{aligned}
    • Nous considérons maintenant le cas où l’image de m\purple{\text{m}} par ff est strictement négative.
    • La solution recherchée appartient alors à l’intervalle [m ;b][\purple{\text{m}}\ ;\, \purple{\text{b}}].
    • Nous assignons donc à a\purple{\text{a}} la valeur de m\purple{\text{m}}.

    elif f(m) < 0:a = m\begin{aligned} &\text{elif f(m) < 0:} \ &\qquad \text{a = m} \end{aligned}
    • Le cas restant est celui où l’image de m\purple{\text{m}} par ff est strictement positive.
    • La solution recherchée appartient alors à l’intervalle [a ;m][\purple{\text{a}}\ ;\, \purple{\text{m}}].
    • Nous assignons donc à b\purple{\text{b}} la valeur de m\purple{\text{m}}.

    else:b = 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 m\purple{\text{m}} par ff 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 : p<ba\purple{\text{p}} < \purple{\text{b}}-\purple{\text{a}}.
    • La boucle est au moins exécutée une fois et la variable m\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.

    if f(m) == 0:print(m,est la solution rechercheˊe)\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é.
    • a\purple{\text{a}} contient sa borne inférieure.
    • b\purple{\text{b}} contient sa borne supérieure.
    • Sa longueur ba\purple{\text{b}}-\purple{\text{a}} est bien inférieure ou égale à p\purple{\text{p}}.

    else:print([,a, ;,b, ])\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é :

    1def f(x):2return x3 + 2  x2 - 4  x - 134def dichocroiss(a,b,p):5while b - a > p:6m = (a + b) / 27if f(m) == 0:8¨C11C¨C12C¨C13C¨C14Cbreak9¨C15C¨C16C¨C17Celif f(m) < 0:10¨C18C¨C19C¨C20C¨C21Ca = m11¨C22C¨C23C¨C24Celse:12¨C25C¨C26C¨C27Cmmb = m13[a ;b][a\ ;\, b]¨C30Cif f(m) == 0:14¨C31C¨C32C¨C33C print(m,est la solution rechercheˊe)15¨C34C¨C35Celse:16¨C36C¨C37C¨C38C print([,a, ;,b, ])\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{def f(x):} \ \textcolor{#A9A9A9}{\text{2}}&\quad\text{return x$\ast\ast\,$3 + 2 $\ast$ x$\ast\ast\,$2 - 4 $\ast$ x - 1} \ \textcolor{#A9A9A9}{\text{3}}& \ \textcolor{#A9A9A9}{\text{4}}&\quad\text{def dicho\textunderscore croiss(a,b,p):} \ \textcolor{#A9A9A9}{\text{5}}&\quad\qquad\text{while b - a > p:} \ \textcolor{#A9A9A9}{\text{6}}&\quad\qquad\qquad\text{m = (a + b) / 2} \ \textcolor{#A9A9A9}{\text{7}}&\quad\qquad\qquad\text{if f(m) == 0:} \ \textcolor{#A9A9A9}{\text{8}}&\quad\qquad\qquad\qquad\text{break} \ \textcolor{#A9A9A9}{\text{9}}&\quad\qquad\qquad\text{elif f(m) < 0:} \ \textcolor{#A9A9A9}{\text{10}}&\quad\qquad\qquad\qquad\text{a = m} \ \textcolor{#A9A9A9}{\text{11}}&\quad\qquad\qquad\text{else:} \ \textcolor{#A9A9A9}{\text{12}}&\quad\qquad\qquad\qquad\text{b = m} \ \textcolor{#A9A9A9}{\text{13}}&\quad \qquad\text{if f(m) == 0:} \ \textcolor{#A9A9A9}{\text{14}}&\quad\qquad\qquad\text{ print(m,$^{\backprime\backprime}$est la solution recherchée$^{\prime\prime}$)} \ \textcolor{#A9A9A9}{\text{15}}&\quad \qquad\text{else:} \ \textcolor{#A9A9A9}{\text{16}}&\quad \qquad\qquad\text{ print($^{\backprime\backprime}$[$^{\prime\prime}$,a, $^{\backprime\backprime}$;$^{\prime\prime}$,b, $^{\backprime\backprime}$]$^{\prime\prime}$)} \end{aligned}croiss(a,b,p):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, ])
    bannière exemple

    Exemple

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

    • La fonction affichera en retour : [1.375 ;1.4375]\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,10,1 pour obtenir un encadrement aussi précis que vous le souhaitez.

    bannière astuce

    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 f\purple{\text{f}} ; la fonction dichocroiss\purple{\text{dicho\textunderscore croiss}}croiss reste bien sûr valable.
    • Si, plus généralement, on cherche à encadrer la solution d’une équation du type « f(x)=kf(x)=k », avec kk réel quelconque, on peut se ramener à ce que nous venons de voir en posant la fonction g:xf(x)kg:x\mapsto f(x)-k : l’équation f(x)=kf(x)=k sera alors équivalente à g(x)=0g(x)=0. (Il faudra évidemment montrer auparavant que l’équation f(x)=kf(x)=k admet une unique solution sur l’intervalle considéré.)
    • Exercice : fonction strictement décroissante

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

      • Les modifications sont minimes par rapport à l’algorithme pour une fonction strictement croissante…
      bannière exemple

      Exemple

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

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

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

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

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

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