Méthode de la dichotomie¶
La méthode de la dichotomie est la méthode la plus simple, la plus lente mais probablement aussi la plus robuste (Donne toujours une solution correcte). La méthode se base l’idée que une fonction continue qui change de signe dans un intervalle \([a,b]\) doit forcément prendre la valeur zéro pour une valeur \(\xi \in [a,b]\) comme indiqué sur la figure suivante.
En termes mathématiques, cela peut s’écrire comme indiqué par l’équation (1). L’intervalle \([a,b]\) est alors appelé encadrement de la racine \(\xi\)
Procédure
L’application de la méthode de la dichotomie à un problème donné nécéssite les étapes suivantes:
- Trouver un encadrement de la racine \(x^{\ast}\)
- Diviser l’intervalle \([a,b]\) en deux sous intervalles égaux et déterminer dans quel sous-intervalle se trouve la racine \(x^{\ast}\)
- Répéter la procédure jusqu’à l’obtention de la précision désirée.
Exemple
Résoudre l’équation \(f(x) = x^2-3=0\)
On sait que la solution est \(x^{\ast}=\sqrt{3}\) et puisque \(1 \leq 3 \leq 4\) on en déduit que \(1 \leq x^{\ast} \leq 2\). Ceci nous donne un encadrement \([1,2]\) pour commencer les itérations puisque \(f(1) f(2) < 0\). La figure ci-dessous montre l’encadrement initial \([1,2]\).
On commence par calculer le milieu \(c\) de l’intervalle \([a,b]\). On trouve \(c=1.5\). Puis on calcule chacun de \(f(a)\), \(f(c)\) et \(f(b)\) cad pour notre exemple \(f(1)\), \(f(1.5)\) et \(f(2)\). Les signes obtenues pour les trois valeurs sont indiqués sur la figure au desus de chaque point de l’intervalle. Puisque le changement de signe se situe dans l’intervalle \([1.5,2]\), on conclue que la racine recherchée \(x^{\ast}\) est dans cet intervalle. On prend comme nouvel encadrement l’intervalle \([1.5,2]\) et on répète le processus. Les résultats obtenus sont condensés dans le tableau suivant:
| k | a | c | b | f(a) | f(c) | f(b) |
|---|---|---|---|---|---|---|
| 0 | 1 | 1.5 | 2 | \(-\) | \(-\) | \(+\) |
| 1 | 1.5 | 1.75 | 2 | \(-\) | \(+\) | \(+\) |
| 2 | 1.5 | 1.645 | 1.75 | \(-\) | \(-\) | \(+\) |
| 3 | 1.625 | 1.6875 | 1.75 | \(-\) | \(-\) | \(+\) |
| 4 | 1.6875 | 1.71875 | 1.75 | \(-\) | \(-\) | \(+\) |
| 5 | 1.71875 | 1.7343 | 1.75 | \(-\) | \(+\) |
Si on s’arrête à l’itération \(k=5\), l’approximation obtenue est \(x^{\ast} \approx c = 1.7343\). De plus l’erreur absolue de l’approximation vérifie:
L’erreur relative peut aussi être estimée comme suit:
Une autre formule peut-être utilisée pour déterminer le nombre d’itérations nécéssaire pour obtenir une approximation \(x^{\ast}\) avec la précision désirée \(e_{\textrm{rel}} = \epsilon\) et cela avant même de commencer les calculs. On démarre de l’encadrement initial \([a,b]\) avec une erreur absolue initiale donnée par la formule (4).
Aprés chaque itération, l’erreur est divisée par deux. Aprés \(k\) itérations, l’erreur absolue est donc donnée par l’équation (5) où les valeurs de \(a\) et \(b\) correspondent à l’encadrement initial.
Initialement, on ne connaît pas la racine \(x^{\ast}\). Mais on peut approximer celle-ci par \(x^{\ast} \approx c = \frac{a+b}{2}\). En combinant cette relation avec l’équation (5), on arrive à la formule (6) qui permet de déterminer le nombre d’itérations \(k\) à partir de l’encadrement initial \([a,b]\).
Programmation
Exemple de programme Fortran qui calcule la racine carrée du nombre 3 à l’aide de la méthode de la dichotomie:
PROGRAM bisection
IMPLICIT NONE
REAL :: x
REAL, PARAMETER :: c = 3.
INTEGER :: i
x = 4.
DO i = 1, 10
x = 0.5 * ( x + c / x )
END DO
END PROGRAM bisection