Le mot dichotomie vient du grec dikhotomia qui signifie “division en deux parties”.Une méthode de dichotomie est une méthode dans laquelle on met en “opposition” deux sous-intervalles. Dans la méthode de la bissection, à chaque itération, on est amené à choisir entre deux sous-intervalles. Ce choix se base sur le théorème de Bolzano qui est un cas particulier du théorème des valeurs intermédiaires.

Théorèmes des valeurs intermédiaires et de Bolzano

Théorème 1.1. (Théorème des valeurs intermédiaires).
Soit une fonction continue $f:I=[a,b]\subset \mathbb{R}\to \mathbb{R}$, soit $u\in \mathbb{R}$, $u$ compris entre $f(a)$ et $f(b)$, alors $$\exists c\in \mathbb{R},c\in ]a,b[\text{ tel que }f(c)=u.$$

Théorème 1.2. (Théorème de Bolzano).
Soit une fonction continue $f:I=[a,b]\subset \mathbb{R}\to \mathbb{R}$, si $f(a)f(b)<0$, alors $$\exists \alpha \in \mathbb{R},\alpha \in ]a,b[\text{ tel que }f(\alpha )=0.$$

Méthode de la bissection

Dans la méthode de la bissection, on commence par s’assurer que l’hypothèse $f(a)f(b)<0$ du théorème de Bolzano est bien vérifiée pour l’intervalle de départ $I_0=[a,b]$ considéré. On sait alors que $I_0$ contient une racine $\alpha$. On choisit de prendre comme première approximation de cette racine le point milieu de $I_0$, c’est-à-dire le point

Si $f(x_0)=0$, on a trouvé une racine de $f$. Sinon, on choisit parmi les deux sous-intervalles (identiques) définis par $a$, $x_0$ et $b$, celui qui contient nécessairement une racine :

• Si $f(a)f(x_0)<0$, on considère comme nouvel intervalle le sous-intervalle $I_1=[a,x_0]$. Ce dernier contient en effet nécessairement un zéro de $f$ par le théorème de Bolzano.
• Sinon, c’est-à-dire si $f(a)f(x_0)>0$, on considère comme nouvel intervalle le sous-intervalle $I_1=[x_0,b]$. Ce dernier contient en effet nécessairement un zéro de $f$ par le théorème de Bolzano car on doit avoir $f(x_0)f(b)<0$.

On itère alors en prenant comme nouvelle approximation de $\alpha$ le milieu de $I_1$. Et ainsi de suite. La figure suivante permet de visualiser concrètement les premières itérations de la méthode de la bissection :

Algorithme de la méthode de la bissection

• Choix d’un “bon” intervalle de départ $I_0=[a,b]$ tel que $f(a)f(b)<0$$\Rightarrow \exists$ (au moins) un zéro $\alpha \in ]a,b[$.
• Construction d’une suite de sous-intervalles $I_k=[a_k,b_k]$, avec $I_k\subset I_{k-1}$, $k\ge 1$ et tels que $f(a_k)f(b_k)<0$ :
  • Initialisation : on pose $a_0=a$, $b_0=b$ et $x_0=\frac{a_0+b_0}{2}$.
  • Pour $k\ge 0$ :
    • si $f(x_k)=0$, alors $\alpha =x_k$ et on s’arrête ;
    • si $f(a_k)f(x_k)<0$, on pose : $a_{k+1}=a_k$, $b_{k+1}=x_k$ et $x_{k+1}=\frac{a_{k+1}+b_{k+1}}{2}$, et on passe à l’itération suivante ;
    • si $f(x_k)f(b_k)<0$, on pose : $a_{k+1}=x_k$, $b_{k+1}=b_k$ et $x_{k+1}=\frac{a_{k+1}+b_{k+1}}{2}$, et on passe à l’itération suivante.
• On s’arrête $\dots$$\dots$ soit quand $\alpha$ est trouvé ;$\dots$ soit quand une condition d’arrêt est remplie.

Condition d’arrêt et erreur commise

Dans la méthode de la bissection, la longueur des intervalles devient de plus en plus petite, ${\lim }_{k\to \infty }|b_k-a_k|=0$, et les valeurs $x_k$ fournissent des approximations de plus en plus précises de la racine $\alpha$. Souvent, on termine la méthode quand l’intervalle considéré à une étape $m$ est plus petit qu’une certaine tolérance (précision) $\epsilon$ que l’on aimerait atteindre :

où $|I_m|\equiv |b_m-a_m|$ représente la longueur de l’intervalle $I_m$. Intéressons-nous à l’erreur absolue commise à l’étape $k$ en se souvenant qu’à chaque étape la longueur de l’intervalle est divisée par deux :

Pour s’assurer que $e_k<\epsilon$, avec $\epsilon$ la tolérance souhaitée, le nombre minimal d’itérations à effectuer est donc :

Dans cette expression, la fonction ${\log }_2$ est la fonction réciproque de la fonction puissance de $2$. Remarques:

• La méthode de la bissection converge toujours. En effet, on note que ${\lim }_{k\to \infty }|I_k|=0$ et $\forall k\ge 0$, $x_k\in I_k$ et $\alpha \in I_k$. Par conséquent, on a bien ${\lim }_{k\to \infty }{x}_k=\alpha$.
• La convergence est lente : il faut ${\log }_2(10)\cong 3.32$ itérations pour améliorer d’une décimale la précision. ($2^{3.32}\cong 10$)
• On ne peut pas définir d’ordre de convergence (l’erreur n’est pas réduite de façon monotone d’une itération à l’autre).
• Si la fonction $f$ est monotone dans l’intervalle considéré, on n’a qu’un zéro dans cet intervalle.

Exemple : résolution de l’équation de Kepler

import numpy as np

def f(E):
    return E - 0.96727426*np.sin(E) - 0.0073673887 

a = 0
b = 0.5
eps = 1e-8

compteur_iterations = 0 

point_milieu = (a + b)/2

if f(a)*f(b) >= 0:
    print("L'intervalle [a,b] n'est pas approprié !")
else:
    while (b - a)/2 > eps:
        if f(a)*f(point_milieu) < 0:
            a = a
            b = point_milieu
            point_milieu = (a + b)/2
            compteur_iterations += 1
        elif f(point_milieu)*f(b) < 0:
            a = point_milieu
            b = b
            point_milieu = (a + b)/2
            compteur_iterations += 1
        elif f(point_milieu) == 0:
            print('La solution obtenue est exacte !')
            break
        else:
            print("Le zéro n'a pas pu être approché.")
            break

print(f"L'approximation de la racine cherchée est alpha = {point_milieu}.")
print(f"Elle a été obtenue après {compteur_iterations} itérations.")

L'approximation de la racine cherchée est alpha = 0.19091079384088516.
Elle a été obtenue après 25 itérations.