Méthode de bissection – Qu'est-ce que c'est, algorithme et exemple

Qu’est-ce que la méthode de bissection ?

La méthode de bissection est l'une des solutions numériques de base pour trouver la racine d'une équation polynomiale. Il met entre parenthèses l'intervalle dans lequel se trouve la racine de l'équation et le subdivise en moitiés à chaque itération jusqu'à ce qu'il trouve la racine. Ainsi, la méthode de bissection est également appelée méthode de bracketing.

Cependant, comme le mécanisme de travail est similaire à l'algorithme de recherche binaire, la méthode de bissection est également connue sous le nom de méthode de recherche binaire, de méthode de réduction de moitié ou de méthode de dichotomie. Il est principalement basé sur le théorème des valeurs intermédiaires.

Trouver les racines des équations

Dans cet exemple, nous ne considérons que les équations à une variable indépendante. Il peut être linéaire ou non linéaire. Les équations linéaires sont utilisées pour représenter le graphique d'une ligne droite, tandis que les équations non linéaires sont utilisées pour représenter des courbes.

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

Considérons f(x) comme une véritable fonction continue. Selon le théorème des valeurs intermédiaires, l'équation f(x)=0 a au moins une racine entre a et b si f(a)f(b) < 0. La fonction f(x) a une racine, « c », entre A et B.

Représentation graphique de la méthode de bissection

Le graphique suivant représente le mécanisme de fonctionnement de la méthode de bissection. Sur le graphique, nous pouvons voir que la racine de l’équation est marquée en rouge.

Pour commencer:

Nous avons d'abord pris deux hypothèses initiales, une₁ et B_1, pour lequel f(a₁)f(b₁) < 0. Selon le théorème des valeurs intermédiaires, la racine doit se situer dans [a₁, b₁].
On peut trouver le milieu d'un₁ et B_1,qui est b₂. Ainsi, 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 réduit jusqu’à ce que la solution approximative soit trouvée.

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 les suppositions initiales a, b et le taux de tolérance e

Étape 2) Si f(a)f(b) >=0, alors la racine ne se situe pas dans cet intervalle. Il n’y aura donc pas de solution.

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

(i) Si la valeur de fonction du 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 situe entre a et c. Ensuite, définissez 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 ou (ba) > e, passez à l'étape 3.

Étape 5) Affichez c comme racine approximative.

Voyons un exemple de l'algorithme de la méthode de bissection.
Nous devons trouver la racine de la fonction continue suivante en utilisant la formule de la méthode de bissection.

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

Exemple de méthode de bissection

Étape 1) Assumons,

         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)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Par conséquent, la racine de la fonction ci-dessus se situe dans cet intervalle [-10, 10].

Étape 3) Ensuite, le point médian c sera calculé en premier.

Il faut maintenant vérifier les conditions suivantes :

(i) si f(c) = 0 :
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

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

La condition est remplie. Pour la prochaine itération, les valeurs seront,

une = une = -10
b = c = 0

Étape 4) Comme (ba) = (0-(-10)) = 10>0.05, le processus sera répété. Les itérations suivantes sont indiquées dans le tableau.

Itération	a	b	c	ba	f(c)
1	- 10	0	0	10	2
2	-5	0	-5	5	- 148
3	- 2.5	0	- 2.5	2.5	- 19.875
4	- 1.25	0	- 1.25	1.25	- 1.52562
5	- 1.25	- 0.625	- 0.625	0.625	1.36523
6	- 1.25	- 0.9375	- 0.9375	0.3125	0.297119
7	- 1.09375	- 0.9375	- 1.09375	0.15625	- 0.50473
8	- 1.01562	- 0.9375	- 1.01562	0.078125	- 0.0791054
9	- 1.01562	- 0.976562	- 0.976562	0.0390625	0.115003
10	- 1.01562	- 0.996094	- 0.996094	0.0195312	0.0194703
11	- 1.00586	- 0.996094	- 1.00586	0.00976562	- 0.0294344

Étape 5) A la 11ème itération, la condition de l'étape 4 sera fausse. Ainsi, la racine de cette équation est -1.00586.

Diagramme logique de la méthode de bissection

Pseudo-code

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++

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