Méthode de dichotomie

Fichier:Bisection method.svg

Étapes successives de la méthode de dichotomie avec comme point de départ, l'intervalle Modèle:Math. Le zéro de la fonction est en rouge.

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.

Principe

On considère deux nombres réels Modèle:Mvar et Modèle:Mvar et une fonction réelle Modèle:Mvar continue sur l'intervalle Modèle:Math telle que Modèle:Math et Modèle:Math soient de signes opposés. Supposons que nous voulions résoudre l'équation Modèle:Math D'après le théorème des valeurs intermédiaires, Modèle:Mvar a au moins un zéro dans l’intervalle Modèle:Math. La méthode de dichotomie consiste à diviser l’intervalle en deux en calculant Modèle:Math. Il y a maintenant deux possibilités : soit Modèle:Math et Modèle:Math sont de signes contraires, soit Modèle:Math et Modèle:Math 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

<math> \frac{b-a}{2^{n+1}} </math>

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 Modèle:Math, on sait dénombrer le nombre d'itérations nécessaires Modèle:Mvar pour satisfaire cette tolérance sur le résultat final :

<math> \quad N=\lceil \ \log_2\frac{b-a}{\varepsilon} \ \rceil </math>

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 Modèle:Math et Modèle:Math soient de signes opposés et qu'on puisse déterminer le signe de Modèle:Math à chaque itération.

Programmation

Sous l'hypothèse que le signe de Modèle:Math soit déterminable, voici une représentation de la méthode en pseudo-code, où Modèle:Math 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

Limite de la méthode

Le principal avantage pratique de cette méthode est sa robustesse, puisque si Modèle:Mvar est continue, alors l'algorithme est théoriquement convergent (la taille de l'intervalle de recherche tend vers zéro). Le principal défaut de l'algorithme est que seul le signe de Modèle:Mvar est utilisé, ce qui mène à une convergence plutôt lente (convergence quasiment linéaire). La méthode de Newton, qui utilise la valeur de Modèle:Mvar ainsi que la valeur de la pente de Modèle:Mvar, est, quand elle converge, significativement plus rapide (convergence quadratique).

Par exemple, supposons que le zéro, simple, est égal à 1, que la fonction est deux fois continûment différentiable et que Modèle:Math. Supposons, de plus qu'on utilise des nombres à virgule flottante binaire de type IEEE-754 avec 64 bits, dont 53 bits de précision. Supposons qu'on recherche une erreur absolue inférieure à 10^-16. Si l'intervalle de recherche initial est de longueur égale à 1, alors la dichotomie nécessite 52 itérations. Au contraire, si le point initial est associé à une erreur absolue inférieure à 0,1, alors la méthode de Newton converge en seulement 5 itérations.

Cette méthode d'une grande robustesse nécessite cependant de connaître à chaque étape le signe de Modèle:Math. Dans quelques cas, il peut arriver que la valeur de Modèle:Math soit si proche de 0 que la précision du logiciel de calcul ne permette plus de déterminer le signe de Modèle:Math (les erreurs d'arrondi peuvent conduire au signe opposé, ou à 0). L'application de l'algorithme risque alors de conduire à l'élimination erronée d'une moitié de l'intervalle et à la convergence vers une valeur éloignée de la racine.

D'une manière plus générale, la détermination du signe de Modèle:Math peut se révéler impossible, même en augmentant la précision du calcul du logiciel. Considérons par exemple un réel Modèle:Mvar dont on peut calculer des valeurs approchées décimales ou rationnelles Modèle:Math à toute précision Modèle:Sfrac désirée. Considérons maintenant la fonction Modèle:Mvar affine sur les intervalles Modèle:Math, Modèle:Math et Modèle:Math et telle que Modèle:Math, Modèle:Math, Modèle:Math. La méthode de dichotomie demande de déterminer le signe de Modèle:Math. Or il n'existe aucun algorithme général permettant de décider si Modèle:Math, Modèle:Math ou Modèle:Math. En effet, un tel algorithme, s'il existait, ne devant effectuer qu'un nombre fini de calculs, devrait prendre sa décision au vu d'un nombre fini de valeurs approchées Modèle:Math, ce qui est insuffisant pour conclure.

Cette limite conduit les théoriciens<ref>{{#invoke:Langue|indicationDeLangue}} Modèle:Lien et Douglas Bridges, Modèle:Langue, Springer-Verlag, 1985, Modèle:P..</ref> de l'analyse constructive à qualifier la méthode de dichotomie de non constructive et à privilégier l'énoncé alternatif : rechercher une valeur x telle que Modèle:Math soit inférieur à une erreur donnée. Modèle:Article détaillé

Notes et références

• {{#invoke:Langue|indicationDeLangue}} Richard L. Burden et J. Douglas Faires, Modèle:Langue, Modèle:7e éd., Brooks/Cole, 2000 Modèle:ISBN

<references/>