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  :math:`[a,b]` doit forcément prendre la valeur zéro pour une valeur  :math:`\xi \in [a,b]` comme indiqué sur la figure suivante.

.. image:: PICS/dichotomie.svg
    :width: 400px
    :align: center
    :alt: alternate text

En termes mathématiques, cela peut s'écrire comme indiqué par l'équation :eq:`eqdichotomie`. L'intervalle  :math:`[a,b]` est alors appelé *encadrement* de la racine :math:`\xi`


.. math:: \begin{cases} f(x) \:\: \textrm{continue dans} \:\: [a,b] \\ f(a) f(b) < 0 \end{cases} \quad \Longrightarrow \quad \exists \xi \in [a,b] \:\: \textrm{tel que} \:\: f(\xi) = 0 \\
   :label: eqdichotomie

**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 :math:`x^{\ast}`
#. Diviser l'intervalle :math:`[a,b]` en deux sous intervalles égaux et déterminer dans quel sous-intervalle se trouve la racine :math:`x^{\ast}`
#. Répéter la procédure jusqu'à l'obtention de la précision désirée.

**Exemple**

Résoudre l'équation :math:`f(x) = x^2-3=0`

On sait que la solution est :math:`x^{\ast}=\sqrt{3}` et puisque :math:`1 \leq 3 \leq 4` on en déduit que :math:`1 \leq x^{\ast} \leq 2`. Ceci nous donne un encadrement :math:`[1,2]` pour commencer les itérations puisque :math:`f(1) f(2) < 0`. La figure ci-dessous montre l'encadrement initial :math:`[1,2]`. 

.. image:: PICS/dichotomie-intervalsplit.svg
    :width: 400px
    :align: center
    :alt: alternate text

On commence par calculer le milieu :math:`c` de l'intervalle :math:`[a,b]`. On trouve :math:`c=1.5`. Puis on calcule chacun de :math:`f(a)`, :math:`f(c)` et :math:`f(b)` cad pour notre exemple :math:`f(1)`, :math:`f(1.5)` et :math:`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 :math:`[1.5,2]`, on conclue que la racine recherchée :math:`x^{\ast}` est dans cet intervalle. On prend comme nouvel encadrement l'intervalle :math:`[1.5,2]` et on répète le processus. Les résultats obtenus sont condensés dans le tableau suivant:


**Programmation**

Exemple de programme Fortran qui calcule la racine carrée du nombre 3 à l'aide de la méthode de la dichotomie:

.. code-block:: fortran

   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