Algorithme de la méthode de dichotomie avec exemples

Qu'est-ce que la méthode de dichotomie ?

La méthode de dichotomie est l'une des techniques numériques fondamentales pour trouver la racine d'un polynôme ou d'une équation transcendante. Elle consiste à encadrer l'intervalle contenant la racine, puis à subdiviser cet intervalle en deux à chaque itération jusqu'à ce que la racine soit localisée dans une tolérance acceptable. C'est pourquoi la méthode de dichotomie est également appelée méthode d'encadrement.

La méthode de dichotomie, dont le mécanisme de fonctionnement s'apparente à la recherche dichotomique, est également connue sous les noms de méthode de recherche dichotomique, méthode de la moitié ou méthode de la dichotomie. Elle repose sur un fondement théorique solide : le théorème des valeurs intermédiaires, qui garantit qu'une fonction continue changeant de signe sur un intervalle s'annule nécessairement à l'intérieur de cet intervalle.

Maintenant que la définition de base est posée, explorons pourquoi la recherche des racines des équations est importante et comment la méthode de dichotomie s'intègre dans ce contexte plus large.

Trouver les racines des équations

Dans cette discussion, nous nous concentrons uniquement sur les équations à une seule variable indépendante. Ces équations peuvent être linéaires ou non linéaires. Les équations linéaires décrivent le graphique d'une droite, tandis que les équations non linéaires décrivent des courbes et des formes plus complexes.

La racine d'une équation est la valeur de la variable indépendante qui satisfait l'équation. Par exemple, la racine de l'équation f(x) = 4 – x² = 0 vaut 2, car f(2) = 4 – 2² = 0.

Considérons f(x) comme une fonction réelle continue. D'après le théorème des valeurs intermédiaires, l'équation f(x) = 0 admet au moins une racine entre a et b dès que f(a)f(b) < 0. Autrement dit, la fonction f(x) possède une racine « c » quelque part entre a et b.

C’est précisément cette propriété de changement de signe que la méthode de dichotomie exploite. La section suivante illustre graphiquement ce principe.

Représentation graphique de la méthode de dichotomie

Le graphique suivant représente le principe de fonctionnement de la méthode de dichotomie. On y voit que la racine réelle de l'équation est indiquée en rouge.

La procédure peut être résumée comme suit :

• Nous choisissons d'abord deux estimations initiales, a₁ et B₁, pour lequel f(a₁)f(b₁) < 0. D'après le théorème des valeurs intermédiaires, la racine doit se trouver dans [a₁, b₁].
• Nous calculons ensuite le point médian d'un₁ et B₁, qui est b₂L'intervalle initial est maintenant réduit à [a₁, b₂] parce que f(a₁)f(b₂) < 0.
• De la même manière, l'intervalle est divisé par deux à plusieurs reprises jusqu'à ce qu'une solution approximative soit trouvée dans la tolérance souhaitée.

L'intuition géométrique étant désormais claire, nous pouvons formaliser la procédure sous forme d'un algorithme étape par étape.

Algorithme de méthode de bissection

Les étapes pour appliquer l'algorithme de la méthode de bissection pour trouver la racine de l'équation f(x) = 0 sont les suivantes.

Étape 1) Choisissez des estimations initiales a, b et un taux de tolérance e.

Étape 2) Si f(a)f(b) >= 0, alors la racine ne se trouve pas dans cet intervalle. Dans ce cas, il n'y a pas de solution dans [a, b].

Étape 3) Trouvez le point médian, c = (a + b)/2.

(i) Si la valeur de la fonction au point médian f(c) = 0, alors c est la racine. Passez à l'étape 5.
(ii) Si f(a)f(c) < 0, la racine se trouve entre a et c. Alors posez a = a, b = c.
(iii) Sinon, définissez a = c, b = b.

Étape 4) Si l'erreur absolue est supérieure au taux de tolérance, c'est-à-dire (b – a) > e, retournez à l'étape 3.

Étape 5) Affichez c comme racine approximative.

Prenons l'exemple de la méthode de dichotomie. Nous allons trouver la racine de la fonction continue suivante à l'aide de la formule de dichotomie.

f(x) = x³ - X² + 2

Exemple de méthode de bissection

Étape 1) Supposons que,

         une = -10,
         b = 10, et
         e = 1% ou 0.01.

Étape 2) Maintenant, nous allons vérifier si f(a)f(b) >= 0 ou non.

         f(a) = f(-10) = (-10)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Par conséquent, la racine de la fonction ci-dessus se trouve dans l'intervalle [-10, 10].

Étape 3) Ensuite, le point médian c est calculé.

Il faut maintenant vérifier les conditions suivantes :

(i) Si f(c) = 0 :
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, ce qui n'est pas égal à 0.

(ii) Si f(a)f(c) < 0 :
         f(c)f(a) = 2 * (-1098) < 0

La condition est remplie. Pour l'itération suivante, les valeurs seront :

         une = une = -10
         b = c = 0

Étape 4) Comme (b – a) = (0 – (-10)) = 10 > 0.01, le processus est répété. Les itérations suivantes sont présentées dans le tableau ci-dessous.

Étape 5) À la 11e itération, la condition de l'étape 4 devient fausse. Par conséquent, la racine approximative de cette équation est -1.00586.

Une fois l'exemple numérique terminé, la section suivante présente le diagramme logique qui capture l'intégralité du flux de contrôle.

Diagramme logique de la méthode de bissection

L'organigramme ci-dessous résume la logique de décision de la méthode de dichotomie, y compris la vérification des supports, la mise à jour du point médian et le test de tolérance.

Pseudo-Code

Le pseudo-code ci-dessous reproduit l'algorithme et sert de modèle pour implémenter la méthode de dichotomie dans n'importe quel langage de programmation.

Start
Set a, b, e
if f(a)*f(b) >= 0
    Output("Root does not exist in this interval")
    Stop
while (b-a) > e do
    c ← (a + b)/2
    if f(c) = 0
        break
    end if
    if f(c)*f(a) < 0 then
        b ← c
    else
        a ← c
end while
Output(c)
Stop

Exemple de méthode de bissection en C/C++

Le C/ suivantC++ Le programme implémente la méthode de dichotomie pour trouver la racine de f(x) = x³ - X² + 2 dans l'intervalle [-10, 10].

Entrées :

#include <bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
    return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
    if (value(a) * value(b) >= 0)
    {
        cout << "The root does not lie in this interval\n";
        return;
    }
    double c = a;
    while ((b-a) >= Error)
    {
        c = (a+b)/2;
        if (value(c) == 0.0)
            break;
        else if (value(c)*value(a) < 0)
            b = c;
        else
            a = c;
    }
    cout << "The root is :" << c;
}
int main()
{
    double a = -10, b = 10;
    bisection_method(a, b);
    return 0;
}

Sortie :

The root is :-1.00586

Exemple de méthode de bissection dans Python

Le Python La version ci-dessous produit la même racine approximative en utilisant une logique identique, ce qui la rend idéale pour des expérimentations et un enseignement rapides.

Entrées :

def value(x):
    return x*x*x - x*x + 2

def bisection_method(a, b):
    if (value(a) * value(b) >= 0):
        return
    c = a
    while ((b-a) >= 0.01):
        c = (a+b)/2
        if (value(c) == 0.0):
            break
        if (value(c)*value(a) < 0):
            b = c
        else:
            a = c
    print("The root is : ", "%.4f" % c)

a = -10
b = 10
bisection_method(a, b)

Sortie :

The root is :  -1.0059

Avantages et limites de la méthode de bissection

Comme toute technique numérique, la méthode de dichotomie présente des atouts indéniables et quelques inconvénients pratiques. Le tableau ci-dessous récapitule les principaux avantages et inconvénients.

Applications de la méthode de dichotomie

La méthode de dichotomie est utilisée dans de nombreux scénarios informatiques pratiques et modernes où une étape de recherche de racines robuste est nécessaire.

• Simulations d'ingénierie : Résolution d'équations non linéaires intervenant dans le transfert de chaleur, la dynamique des fluides et l'analyse structurale.
• Modélisation financière: Calcul des rendements, des taux de rendement internes et des seuils de rentabilité pour lesquels il n'existe pas de solutions analytiques.
• Apprentissage automatique et IA : Localisation des seuils, étalonnage des modèles et réglage des hyperparamètres au sein des solveurs numériques pilotés par l'IA.
• Infographie : Détermination des intersections rayon-surface et des valeurs des paramètres le long des courbes.
• Systèmes embarqués: Approximation des racines dans les contrôleurs à faibles ressources où la simplicité et la prévisibilité sont plus importantes que la vitesse.

FAQ