Méthode de dichotomie

La méthode de dichotomie ou méthode de la bissection est, en mathématiques, un algorithme de recherche d'un zéro d'une fonction qui consiste à répéter des partages d’un intervalle en deux parties puis à sélectionner le sous-intervalle dans lequel existe un zéro de la fonction. On considère deux nombres réels a et b et une fonction réelle f continue sur l'intervalle [a, b] telle que f(a) et f(b) soient de signes opposés. Supposons que nous voulions résoudre l'équation f(x) = 0. D'après le théorème des valeurs intermédiaires, f a au moins un zéro dans l’intervalle [a, b]. La méthode de dichotomie consiste à diviser l’intervalle en deux en calculant m = (a+b)/2. Il y a maintenant deux possibilités : soit f(a) et f(m) sont de signes contraires, soit f(m) et f(b) sont de signes contraires. L’algorithme de dichotomie est alors appliqué au sous-intervalle dans lequel le changement de signe se produit, ce qui signifie que l’algorithme de dichotomie est récursif. L’erreur absolue de la méthode de dichotomie est au plus après n étapes car l'erreur est diminuée de moitié à chaque étape. Réciproquement, si l'on cherche à ce que l'erreur absolue soit inférieure à une certaine valeur ε, on sait dénombrer le nombre d'itérations nécessaires N pour satisfaire cette tolérance sur le résultat final : La méthode converge linéairement, ce qui est très lent par comparaison avec la méthode de Newton. L'avantage par rapport à cette dernière est son domaine d'application plus vaste : il suffit seulement que f(a) et f(b) soient de signes opposés et qu'on puisse déterminer le signe de f(m) à chaque itération. Sous l'hypothèse que le signe de f(m) soit déterminable, voici une représentation de la méthode en pseudo-code, où ε est la précision souhaitée. Tant que (b - a) > ε m ← (a + b) / 2 Si (f(a)*f(m) ≤ 0) alors b ← m sinon a ← m Fin Si Fin Tant que Le principal avantage pratique de cette méthode est sa robustesse, puisque si f est continue, alors l'algorithme est théoriquement convergent (la taille de l'intervalle de recherche tend vers zéro).