Méthode de dichotomie
La méthode de dichotomie est une méthode pour trouver une solution approchée à une équation $f(x)=0$. Précisément, supposons que la fonction $f$ est continue sur l'intervalle $[a,b]$, avec $f(a)\leq 0$ et $f(b)\geq 0$. On sait donc qu'il existe au moins un réel $c$ dans l'intervalle $[a,b]$ tel que $f( c)=0$.
L'idée est alors d'évaluer ce que vaut $f$ au milieu de $[a,b]$, et de distinguer les deux cas suivants :
- si $f\left(\frac{a+b}2\right)\leq 0$, alors on sait qu'on a une racine dans l'intervalle $\left[\frac{a+b}2,b\right]$.
- sinon, $f\left(\frac{a+b}2\right)> 0$ et on sait qu'on a une racine dans l'intervalle $\left[a,\frac{a+b}2\right]$.
Ainsi, dans les deux cas, on a trouvé un intervalle de longueur moitié dans lequel est située une racine de l'équation $f(x)=0$. On recommence alors avec cet intervalle, et ainsi de suite jusqu'à ce qu'on trouve une approximation qui nous convienne.
Formellement, on définit les suites $(a_n)$ et $(b_n)$ en posant
- $a_0=a$ et $b_0=b$.
- si $f\left(\frac{a_n+b_n}2\right)\leq 0$, alors $a_{n+1}=\frac{a_n+b_n}2$ et $b_{n+1}=b_n$.
- sinon, $a_{n+1}=a_n$ et $b_{n+1}=\frac{a_n+b_n}2$.
On a toujours une solution à l'équation $f(x)=0$ dans l'intervalle $[a_n,b_n]$, qui est de longueur $(b-a)/2^n$.
Voici le fonctionnement de l'algorithme de dichotomie sur la fonction $f(x)=x^3-3x+1$.
L'algorithme implémentant la méthode de dichotomie sous Python, avec précision fixée, s'écrit simplement :
Il existe des méthodes plus efficaces que la dichotomie pour rechercher pratiquement les solutions d'une équation $f(x)=0,$ sous certaines hypothèses plus fortes de régularité. La plus connue est sans doute la méthode de Newton.
Autrefois, chaque fois que les chirurgiens opéraient un patient,
ils versaient une certaine somme au médecin généraliste qui le lui avait envoyé.
Cette pratique faisait que les généralistes envoyaient leurs patients non pas vers le meilleur chirurgien,
mais vers celui qui leur reversait le plus. Elle portait le nom de dichotomie.
L'algorithme de dichotomie que nous avons décrit ici semble être dû à Cauchy en 1821 dans son ouvrage Analyse géométrique.