Pierre Bourdan, une des voix de la France Libre à Londres
Encadrement de la solution α d’une équation avec la méthode par dichotomie
Vidéo : programmation de cet algorithme sous Python
|
Le principe et l’algorithme
La méthode par dichotomie (du grec dikha “en deux” et tomein “couper” ) ou de bissection est un algorithme de recherche du zéro d’une fonction (encadrement de l’unique solution de l’équation f(x) = 0).
Elle consiste à réitérer des partages d’un intervalle en deux moitiés, puis à sélectionner celui dans lequel la fonction f est égale à 0.
Si cela est possible, on dégrossit le plus souvent la recherche en se plaçant initialement sur un intervalle [a ; b] où la fonction est continue, strictement monotone (croissante ou décroissante) et telle que
Pour cela, on calcule le milieu c de l’intervalle [a ; b] (c = (a +b)/2), puis on regarde si la solution α se trouve dans l’intervalle [a ; c] ou [ c ; b].
Si la solution est dans [a ; c], on recommence le procédé dans [a ; c].
Si la solution est dans [c ; b], on recommence le procédé dans [c ; b].
Le cœur de l’algorithme repose sur le test suivant :
| si la condition f(a) x f(c) < 0 la solution se trouve entre a et c alors c “prend la place de b” sinon c “prend la place de a” la solution se trouve entre c et b. |
L’algorithme s’arrête quand l’amplitude de l’intervalle de recherche devient inférieure à la précision choisie.
Il renvoie alors en sortie un encadrement [a ; b] de α.
(Les valeurs de a et de b sont celles du “moment” ; elles ont évidemment été successivement modifiées par l’algorithme).
Remarque : pour une équation du type f(x) = k, il suffit de considérer la fonction g définie par g(x) = f(x) - k.