Worldlex Wiki En mathématiques , la méthode de dichotomie est une méthode de recherche de racines applicable à toute fonction continue pour laquelle on connaît deux valeurs de signes opposés. Elle consiste à diviser en deux l' intervalle défini par ces valeurs, puis à sélectionner le sous-intervalle où la fonction change de signe, qui contient donc nécessairement une racine . C'est une méthode très simple et robuste, mais relativement lente. De ce fait, elle est souvent utilisée pour obtenir une approximation grossière de la solution, servant ensuite de point de départ à des méthodes à convergence plus rapide. Cette méthode est également appelée méthode de la moitié d'intervalle , méthode de recherche dichotomique , ou méthode de la dichotomie .
Pour les polynômes , il existe des méthodes plus élaborées pour tester l'existence d'une racine dans un intervalle ( règle des signes de Descartes , théorème de Sturm , théorème de Budan ). Elles permettent d'étendre la méthode de dichotomie en algorithmes efficaces pour trouver toutes les racines réelles d'un polynôme ; voir Isolation des racines réelles .
réelle , où est une fonction continue définie sur un intervalle et où et sont de signes opposés. Dans ce cas, on dit que et encadrent une racine car, d'après le théorème des valeurs intermédiaires , la fonction continue admet au moins une racine dans l'intervalle .Généralisation à des dimensions supérieures
La méthode de dichotomie a été généralisée aux fonctions multidimensionnelles. Ces méthodes sont appelées méthodes de dichotomie généralisées .
Méthodes basées sur le calcul du degré
Certaines de ces méthodes sont basées sur le calcul du degré topologique .
Méthode de bissection caractéristique
La méthode de dichotomie caractéristique utilise uniquement les signes d'une fonction en différents points. Soit f une fonction de R <sup>d </sup> dans R<sup> d</sup> , pour un entier d ≥ 2. Un polyèdre caractéristique (aussi appelé polygone admissible ) de f est un polyèdre de R<sup> d</sup> , à 2 <sup> d </sup> sommets, tel qu'en chaque sommet v , la combinaison des signes de f ( v ) soit unique. Par exemple, pour d = 2, un polyèdre caractéristique de f est un quadrilatère de sommets (disons) A, B, C, D, tel que :
- Sign f (A) = ( − , − ), c'est-à-dire, f 1 (A)<0, f 2 (A)<0.
- Sign f (B) = ( − ,+), c'est-à-dire f 1 (B)<0, f 2 (B)>0.
- Sign f (C) = (+, − ), c'est-à-dire f 1 (C)>0, f 2 (C)<0.
- Sign f (D) = (+,+), c'est-à-dire f 1 (D)>0, f 2 (D)>0.
Une arête propre d'un polygone caractéristique est une arête reliant deux sommets dont les vecteurs de signes diffèrent d'un seul signe. Dans l'exemple ci-dessus, les arêtes propres du quadrilatère caractéristique sont AB, AC, BD et CD. Une diagonale est une paire de sommets dont les vecteurs de signes diffèrent de tous les signes. Dans l'exemple ci-dessus, les diagonales sont AD et BC.
À chaque itération, l'algorithme choisit une arête appropriée du polyèdre (par exemple, A