{"id":3040,"date":"2020-08-05T15:44:57","date_gmt":"2020-08-05T13:44:57","guid":{"rendered":"https:\/\/www.mathweb.fr\/euclide\/?page_id=3040"},"modified":"2023-04-16T16:18:16","modified_gmt":"2023-04-16T14:18:16","slug":"dichotomie","status":"publish","type":"page","link":"https:\/\/www.mathweb.fr\/euclide\/dichotomie\/","title":{"rendered":"Dichotomie"},"content":{"rendered":"\n

La dichotomie<\/em> est une m\u00e9thode pour encadrer une solution \u00e0 une \u00e9quation.<\/p>\n\n\n\n

Par soucis de simplifier le probl\u00e8me, toutes les \u00e9quations seront ramen\u00e9es \u00e0 la forme f<\/em>(x<\/em>) = 0.<\/p>\n\n\n

\n
\"dichotomie
Maman intervalle et ses petits<\/figcaption><\/figure>\n<\/div>\n\n\n
\nhttps:\/\/www.mathweb.fr\/euclide\/produit\/python-en-mathematiques-au-lycee\/\n<\/div><\/figure>\n\n\n\n\n\n\n\n

Principe de la dichotomie<\/h2>\n\n\n\n

Avant tout, il faut s’assurer que la fonction est continue et strictement monotone (soit strictement croissante, soit strictement d\u00e9croissante) sur un intervalle [a<\/em> ; b<\/em>], et que f<\/em>(a<\/em>) et f<\/em>(b<\/em>) n’ont pas le m\u00eame signe (ce qui assure, d’apr\u00e8s le corollaire du th\u00e9or\u00e8me des valeurs interm\u00e9diaires, l’existence d’une unique solution \u00e0 l’\u00e9quation sur l’intervalle consid\u00e9r\u00e9).<\/p>\n\n\n\n

Consid\u00e9rons donc une fonction f<\/em> continue et strictement monotone sur un intervalle [a<\/em>;b<\/em>]. La dichotomie consiste \u00e0:<\/p>\n\n\n\n

    \n
  1. le milieu m<\/em> de l’intervalle [a<\/em> ; b<\/em>] est calcul\u00e9<\/li>\n\n\n\n
  2. son image par la fonction f<\/em> est ensuite calcul\u00e9e<\/li>\n\n\n\n
  3. si f<\/em>(a)\u00d7f<\/em>(m<\/em>) > 0 alors cela signifie que f<\/em>(a<\/em>) et f<\/em>(m<\/em>) ont le m\u00eame signe; comme f<\/em> est strictement monotone, cela signifie donc que la solution \u00e0 l’\u00e9quation f<\/em>(x<\/em>) = 0 n’est pas entre a<\/em> et m<\/em>. Dans ce cas, elle se trouve sur l’intervalle [m<\/em> ; b<\/em>]. On change donc d’intervalle et [a<\/em> ; b<\/em>] devient [m<\/em> ; b<\/em>]. On va alors au point 1 tant que l’amplitude de l’intervalle est sup\u00e9rieur au seuil que l’on se fixe (par exemple, 0,001).<\/li>\n\n\n\n
  4. Dans le cas contraire, [a<\/em> ; b<\/em>] devient [a<\/em> ; m<\/em>] et on repart au point 1 tant que l’amplitude de l’intervalle est sup\u00e9rieure au seuil que l’on se fixe.<\/li>\n<\/ol>\n\n\n\n

    Un exemple pas \u00e0 pas de la dichotomie<\/h2>\n\n\n\n

    Prenons:$$f(x)=x^2-2.$$Pla\u00e7ons-nous sur l’intervalle [0 ; 2] (donc a<\/em> = 0 et b<\/em> = 2). Voici un tableau des \u00e9tapes des calculs (en prenant une marge de 0,1 pour finir plus vite):<\/p>\n\n\n\n

    a<\/em><\/th>b<\/em><\/th>m<\/em><\/th>f<\/em>(a<\/em>)<\/th>f<\/em>(b<\/em>)<\/th>f<\/em>(m<\/em>)<\/th>amplitude<\/th><\/tr><\/thead>
    0<\/td>2<\/td>1<\/td>-2<\/td>2<\/td>-1<\/td>2<\/td><\/tr>
    1<\/td>2<\/td>1.5<\/td>-1<\/td>2<\/td>0.25<\/td>1<\/td><\/tr>
    1<\/td>1.5<\/td>1.25<\/td>-1<\/td>0.25<\/td>-0.4375<\/td>0.5<\/td><\/tr>
    1.25<\/td>1.5<\/td>1.375<\/td>-0.4375<\/td>0.25<\/td>-0.109375<\/td>0.25<\/td><\/tr>
    1.375<\/td>1.5<\/td>1.4375<\/td>-0.109375<\/td>0.25<\/td>0.066406<\/td>0.125<\/td><\/tr>
    1.375<\/td>1.4375<\/td>1.40625<\/td>-0.109375<\/td>0.066406<\/td>-0.02246<\/td>0.0625<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

    D’apr\u00e8s ce tableau, la solution de l’\u00e9quation \\(x^2-2=0\\) qui se trouve dans [0 ; 2] est la valeur \\(\\alpha\\) telle que \\(1,375 < \\alpha < 1,4375\\). On obtient ainsi un encadrement de la solution \u00e0 \\(10^{-1}\\) pr\u00e8s.<\/p>\n\n\n\n

    Calcul de l’erreur<\/h2>\n\n\n\n

    D’apr\u00e8s le principe de la dichotomie, les intervalles successifs sont divis\u00e9s en deux \u00e0 chaque \u00e9tape. Ainsi, le dernier intervalle (apr\u00e8s n<\/em> \u00e9tapes) aura une amplitude \u00e9gale \u00e0 \\(\\displaystyle\\frac{b-a}{2^n}\\). Si \\(\\varepsilon\\) repr\u00e9sente l’amplitude maximale d\u00e9sir\u00e9e, alors:$$\\begin{align}\\frac{b-a}{2^n} \\leqslant \\varepsilon & \\iff \\frac{2^n}{b-a} \\geqslant \\frac{1}{\\varepsilon}\\\\&\\iff 2^n \\geqslant \\frac{b-a}{\\varepsilon}\\\\&\\iff n \\geqslant \\log_2\\left(\\frac{b-a}{\\varepsilon}\\right)\\end{align}$$On dit que la vitesse de convergence est lin\u00e9aire<\/em> car \\(|x_{n+1} – \\alpha| \\leqslant k|x_n – \\alpha|\\).<\/p>\n\n\n\n

    Par exemple, si [a<\/em> ; b<\/em>] = [0 ; 2] comme pr\u00e9c\u00e9demment, et si nous voulons un encadrement \u00e0 \\(\\varepsilon=10^{-5}\\) pr\u00e8s, il faudra:$$n\\geqslant\\log_2\\left(2\\times10^{5}\\right)\\approx17,6$$soit au minimum 18 \u00e9tapes pour avoir un tel encadrement.<\/p>\n\n\n\n

    Je ne suis pas l\u00e0 pour critiquer… mais quand-m\u00eame… Oserais-je dire que la dichotomie est \u00e0 la r\u00e9solution d’\u00e9quation ce que Facebook est aux r\u00e9seaux sociaux (\u00e0 savoir tout pourri) ?<\/p>\n\n\n\n

    La dichotomie en Python<\/h2>\n\n\n\n

    On ne va pas se mentir (on est entre amis), je n’ai pas fait les calculs des nombres qui paraissent dans le tableau pr\u00e9c\u00e9dent \u00e0 la main… car je ne suis pas non plus trop con… Je sais \u00e9crire une fonction Python qui le fait pour moi alors pourquoi me priver ? D’ailleurs, la voici:<\/p>\n\n\n\n

    def dichotomie(f,a,b,e):\n    delta = 1\n    while delta > e:\n        m = (a + b) \/ 2\n        delta = abs(b - a)\n        if f(m) == 0:\n            return m\n        elif f(a) * f(m)  > 0:\n            a = m\n        else:\n            b = m\n    return a, b\n        \nprint( dichotomie(lambda x: x*x - 2, 0, 2, 0.001) )<\/pre>\n\n\n\n
    Dans la fonction dichotomie<\/em>, la variable delta<\/em> repr\u00e9sente l’amplitude de l’intervalle, donc |b<\/em> – a<\/em>|. Notez que tr\u00e8s souvent, on a a<\/em> < b<\/em>, donc la valeur absolue n’est pas n\u00e9cessaire, mais je la mets syst\u00e9matiquement par r\u00e9flexe. Tant que cette amplitude est sup\u00e9rieure \u00e0 celle donn\u00e9e en argument (repr\u00e9sent\u00e9e par la variable e<\/em>), on effectue les op\u00e9rations:<\/p>\n\n\n\n