AnalyseNotion · Glossaire
Dichotomie
La dichotomie est un procédé de raisonnement ou de recherche qui consiste à diviser un ensemble en deux parties disjointes et complémentaires. En analyse, la méthode de dichotomie est un algorithme de recherche de zéro d'une fonction continue sur un intervalle : on subdivise répétitivement l'intervalle en deux moitiés et on retient celle qui contient le zéro, jusqu'à convergence vers une approximation aussi précise que souhaitée. Cette méthode garantit la convergence en un nombre fini d'étapes pour une précision donnée.
Sommaire
Ce que vous allez apprendre
- Distinguer le partage dichotomique de la méthode numérique.
- Appliquer quatre subdivisions à la fonction x² − 2.
- Contrôler l'erreur à partir de la largeur de l'intervalle.
- Reconnaître les échecs dus à une discontinuité ou à l'absence de changement de signe.
En clair
Un nombre inconnu se cache entre 1 et 2. Pour le cerner, on dispose d'un critère qui indique de quel côté du milieu il peut se trouver : pour la dichotomie, ce critère vient des signes pris par une fonction continue aux bornes et au milieu. On coupe alors l'intervalle en son milieu, puis on élimine la moitié qui ne peut pas contenir le nombre. En recommençant, l'encadrement devient deux fois plus étroit à chaque étape.
La méthode de dichotomie applique ce geste au zéro d'une fonction, c'est-à-dire à une valeur où la fonction vaut 0. Elle garde un intervalle dont les deux extrémités donnent des signes opposés. La continuité assure alors qu'au moins un zéro reste enfermé entre elles.
Définition
Au sens général, une dichotomie partage un ensemble en deux parties disjointes, donc sans élément commun, et complémentaires, donc réunies elles redonnent l'ensemble entier. En analyse numérique, le mot désigne une méthode qui encadre un zéro d'une fonction.
On considère une fonction continue notée f sur un intervalle fermé dont les extrémités sont a et b. Si , le théorème des valeurs intermédiaires garantit au moins un zéro dans cet intervalle fermé, éventuellement à l'une de ses extrémités. On calcule le milieu . Si une extrémité est déjà un zéro, la recherche s'arrête. Sinon, on conserve la moitié dont les valeurs aux extrémités ont des signes opposés, puis on répète l'opération.
Après n subdivisions, la largeur initiale b − a est divisée par 2n. Le milieu de l'intervalle restant approche un zéro avec une erreur au plus égale à la moitié de cette largeur. Une précision fixée est donc atteinte après un nombre fini d'étapes. La méthode assure l'existence d'un zéro dans chaque encadrement conservé, mais pas son unicité si plusieurs zéros sont présents.
Un exemple, pas à pas
On cherche un zéro de la fonction f définie par f(x) = x2 − 2. Les données sont l'intervalle initial [1 ; 2], f(1) = −1 et f(2) = 2. La fonction est continue et les valeurs aux extrémités sont de signes opposés.
1. Le milieu est 1,5. Comme f(1,5) = 0,25, on conserve [1 ; 1,5].
2. Le nouveau milieu est 1,25. Comme f(1,25) = −0,4375, on conserve [1,25 ; 1,5].
3. Le milieu suivant est 1,375. Comme f(1,375) = −0,109375, on conserve [1,375 ; 1,5].
4. Le quatrième milieu est 1,4375. Comme f(1,4375) = 0,06640625, on conserve [1,375 ; 1,4375]. Les encadrements emboîtés rendent visible la réduction régulière de l'incertitude.
Le milieu final, 1,40625, est une approximation du zéro √2. Le contrôle est refaisable : l'intervalle mesure 0,0625, donc l'erreur de cette approximation ne dépasse pas 0,03125. De plus, les valeurs de f aux deux extrémités ont toujours des signes opposés.
En pratique
Pour localiser un zéro numériquement, on cherche d'abord deux valeurs qui l'encadrent et donnent des résultats de signes opposés. Si cet encadrement manque, un balayage préalable de plusieurs valeurs est préférable à une dichotomie lancée au hasard.
La dichotomie est utile lorsqu'une évaluation de la fonction est disponible mais qu'une dérivée ne l'est pas. Une méthode fondée sur la tangente peut aller plus vite près du zéro ; la dichotomie est préférable quand on veut conserver un encadrement vérifiable à chaque étape.
Le critère d'arrêt se choisit avant le calcul. On s'arrête lorsque la largeur de l'intervalle est inférieure à la précision demandée, puis on donne son milieu et une borne d'erreur égale à la moitié de cette largeur.
À ne pas confondre
Dichotomie d'un ensemble et méthode numérique. La première est un partage en deux parties disjointes et complémentaires. La seconde répète ce partage sur un intervalle pour encadrer un zéro. Couper les nombres entiers en pairs et impairs est une dichotomie, mais pas une recherche de zéro.
Zéro et minimum d'une fonction. Un zéro est une valeur de la variable pour laquelle la fonction vaut 0 ; un minimum est une valeur où la fonction prend sa plus petite valeur. Pour f(x) = x2 − 2, √2 est un zéro, tandis que le minimum est atteint en 0.
Limites et pièges
Discontinuité. Des signes opposés ne suffisent pas si la fonction n'est pas continue. La fonction f(x) = 1/x change de signe entre −1 et 1, mais elle n'est pas définie en 0 et ne possède aucun zéro. Il faut vérifier la continuité sur tout l'intervalle.
Zéro sans changement de signe. L'absence de signes opposés aux extrémités ne prouve pas l'absence de zéro. La fonction f(x) = x2 vaut 1 aux deux extrémités de [−1 ; 1], tout en ayant le zéro 0. Un autre procédé de repérage est alors nécessaire.
Plusieurs zéros. Un changement de signe garantit au moins un zéro, pas un seul. Si plusieurs zéros se trouvent dans l'intervalle initial, les choix successifs peuvent n'en isoler qu'un. Il faut subdiviser ou étudier la fonction pour établir l'unicité.
Précision mal interprétée. Dans l'exemple, quatre subdivisions donnent une largeur de 0,0625 et une erreur du milieu au plus égale à 0,03125. Annoncer 1,40625 comme valeur exacte serait faux : il faut conserver le signe ≈ ou fournir l'encadrement [1,375 ; 1,4375].
Pour aller plus loin
La fonction continue précise l'hypothèse qui empêche la courbe de franchir une valeur sans la prendre.
Le zéro d'une fonction approfondit l'objet que la dichotomie cherche à encadrer puis à approcher.
La fiche algorithme replace les subdivisions répétées dans une suite d'opérations assortie d'un critère d'arrêt.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres