Dichotomie

C'est le jeu du plus et du moins : Je vous demande « devinez un nombre entre 0 et 100 ».

Le jeu ressemble à :

• 50 ? réponse : c'est plus
• 75 ? réponse : c'est moins
• 62 ? réponse : c'est moins
• 56 ? réponse : c'est plus
• 59 ? réponse : gagné !

On formalise le principe :

• je me donne un intervalle $[a;b]$, dans l'exemple, c'était [0;100]
• on vise au centre, en $m = \frac{a+b}{2}$
  • si $m$ est trop grand, on continue à gauche avec $[a;m]$
  • si $m$ est trop petit, on continue à droite avec $[m;b]$

On peut appliquer cette méthode à la recherche de solution d'équation ou de racine.

On considère la fonction définie par $f(x) = -\frac{x^3}{4} + \frac{9\,x^2}{2} - 13\,x - 59$ dont on donne ci-dessous la représentation graphique sur l'intervalle $[0;10]$.

On cherche une racine de $f$.

Dans cet exemple, la zone de recherche est $[a;b] = [0;10]$.

La seule contrainte est que $f(a)$ et $f(b)$ ne soient pas de même signe. Comme $f$ est continue (courbe sans trou) on est certain que $f(x) = 0$ a au moins une solution dans $[a;b]$.

Tout au long de la recherche, on aura donc un intervalle $[a;b]$ qui ira en diminuant mais on aura toujours $f(a)$ et $f(b)$ de signe opposé.

• La zone de recherche initiale est $[0;10]$. On constate que $f(0) = -59$ et $f(10) = 11$. Il y a donc au moins une solution à $f(x) = 0$ avec $x\in[0;10]$.
• On cherche le milieu de $[0;10]$. C'est $5$. On calcule $f(5) = -42,75$. On déduit donc que la solution recherchée doit se trouver dans $[5;10]$.
• On cherche le milieu de $[5;10]$. C'est $7,5$. On calcule $f(7,5) = -8,84375 < 0$. On déduit donc que la solution recherchée doit se trouver dans $[7,5;10]$.

Contrairement au jeu du plus et du moins, il est fort probable que l'on se rapproche de la racine sans jamais l'atteindre. On souhaite se contenter d'une racine approximative.

On décide que quand l'intervalle $[a;b]$ c'est réduit en dessous d'un certain écart $\varepsilon$, par exemple $\varepsilon = 1E-6$, on renvoie $\frac{a+b}{2}$.

Entrées: a, b, bornes de l'intervalle de recherche
         f la fonction
         e taille de l'intervalle final
Prérequis: a < b ; f(a) et f(b) de signe opposé
Renvoie une approximation de la racine
DÉBUT
    TANT QUE taille [a;b] >= e RÉPÉTER
        m prend la valeur du milieu de [a;b]
        SI f(m) et f(a) de signe opposé ALORS
            b prend la valeur de m
        SINON
            a prend la valeur de m
        FIN
    FIN
    RENVOYER (a + b)/2
FIN

Complétez et testez.

def dichotomie(a, b, f, e = 1e-6):
    """
    a,b : bornes de l'intervalle
    f: fonction
    e: taille maximale de la solution désirée. Valeur par défaut : 1e-6
    renvoie un intervalle inclus dans [a;b], de taille < e et contenant une solution de f(x) = 0
    """
    assert f(a) * f(b) < 0 # Vérifie que f(a) et f(b) de signe opposé
    assert e > 0
    
    # à vous
    

# démonstration
def f(x):
    return -1/4*x**3 + 9/2**x**2 - 13*x - 59

sol = dichotomie(0, 10, f)
print(sol)

Modifiez ce programme pour trouver les racines de $f(x)$ dans les cas suivants :

• $f(x) = 3x -2$ pour $0 \leq x \leq 10$
• $f(x) = \frac{3x^{2}+4x}{8x\ -\ 7}-x$ pour $1 \leq x \leq 10$
• $f(x) = x \cdot \exp(x) - 2$ pour $0 \leq x \leq 10$