Un article de Wikipedia.y-project.com.
Image:Bisection method.png Étapes successives de la méthode de dichotomie avec comme point de départ, l'intervalle [a1;b1. Le zéro de la fonction est en rouge.]
En mathématiques, la méthode de dichotomie ou méthode de la bissection est 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.
Supposons que nous voulions résoudre l?équation f(x) = 0. Étant donné deux points a et b tels que f(a) et f(b) soient de signes opposés, nous savons par le théorème des valeurs intermédiaires que f doit avoir au moins un zéro dans l?intervalle [a, b]. La méthode de dichotomie divise l?intervalle en deux en calculant c = (a+b) / 2. Il y a maintenant deux possibilités : ou f(a) et f(c) sont de signes opposés, ou f(c) et f(b) sont de signes opposés.
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 en soi récursif.
La méthode de dichotomie est moins efficace que la méthode de Newton mais est moins encline à de mauvais comportements.
L?erreur absolue de la méthode de dichotomie est au plus
- <math> \frac} </math>
après n étapes quand f est continue sur un intervalle [a, b] et f(a)f(b) < 0. En d?autres termes, l?erreur est diminuée de moitié à chaque étape, ainsi la méthode converge linéairement, ce qui est très lent. Le côté positif est que la méthode a la garantie de converger si f(a) et f(b) sont de signes opposés.
Voici une représentation de la méthode en langage Visual Basic. Les variables xL et xR correspondent aux réels a et b précédents. Les valeurs initiales de xL et xR doivent être choisies telles que f(xL) et f(xL) soient de signes opposés (elles encadrent le zéro). La variable epsilon indique avec quelle précision le résultat doit être donné.
'Méthode de dichotomie
'Start loop
Do While (xR - xL) > epsilon
'Calcule le milieu du domaine de définition
xM = (xR + xL) / 2
'Find f(xM)
If ((f(xL) * f(xM)) > 0) Then
'jette la moitié de gauche
xL = xM
Else
'jette la moitié de droite
xR = xM
End If
Loop
[] Voir aussi
[] Référence
Richard L. Burden, J. Douglas Faires (2000), Numerical Analysis, (7th Ed),
Brooks/Cole. ISBN 0534382169
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Méthode de dichotomie
