Metodo di bisezione: cos'è, algoritmo ed esempio

Cos'è il metodo della bisezione?

Il metodo di bisezione è una delle soluzioni numeriche di base per trovare la radice di un'equazione polinomiale. Mette tra parentesi l'intervallo in cui si trova la radice dell'equazione e li suddivide a metà in ogni iterazione finché non trova la radice. Quindi, il metodo di bisezione è anche chiamato metodo di parentesi.

Tuttavia, poiché il meccanismo di funzionamento è simile all'algoritmo di ricerca binaria, il metodo di bisezione è noto anche come metodo di ricerca binaria, metodo di dimezzamento o metodo di dicotomia. Si basa principalmente sul teorema del valore intermedio.

Trovare le radici delle equazioni

In questo esempio consideriamo solo equazioni con una variabile indipendente. Può essere lineare o non lineare. Le equazioni lineari vengono utilizzate per rappresentare il grafico di una linea retta, mentre le equazioni non lineari vengono utilizzate per rappresentare le curve.

La radice di un'equazione indica il valore della variabile indipendente che soddisfa l'equazione. Ad esempio: la radice di un'equazione f(x)= 4-x² = 0 è 2 perché f(2) = 4-2² = 0.

Consideriamo f(x) come una funzione continua reale. Secondo il teorema del valore intermedio, l’equazione f(x)=0 ha almeno una radice tra a e b se f(a)f(b) < 0. La funzione f(x) ha una radice, “c”, tra a e b.

Rappresentazione grafica del metodo di bisezione

Il grafico seguente rappresenta il meccanismo di funzionamento del metodo di bisezione. Dal grafico, possiamo vedere che la radice dell'equazione è contrassegnata in rosso.

Iniziare con:

Per prima cosa abbiamo preso due ipotesi iniziali, a₁ e B_1, per cui f(a₁)f(b₁) < 0. Secondo il teorema del valore intermedio, la radice dovrebbe trovarsi in [a₁, b₁].
Possiamo trovare il punto medio di a₁ e B_1,che è b₂. Pertanto, l'intervallo iniziale è ora ridotto a [a₁, b₂] perché f(a₁)f(b₂) < 0.
Allo stesso modo, l'intervallo si riduce fino a trovare la soluzione approssimata.

Algoritmo del metodo di bisezione

I passaggi per applicare l'algoritmo del metodo di bisezione per trovare la radice dell'equazione f(x)=0 sono i seguenti

Passo 1) Scegli le ipotesi iniziali a, b e il tasso di tolleranza e

Passo 2) Se f(a)f(b) >=0, allora la radice non si trova in questo intervallo. Pertanto, non ci sarà alcuna soluzione.

Passo 3) Trova il punto medio, c = (a+b)/2

(i) Se il valore della funzione del punto medio f(c) = 0, allora c è la radice. Vai al passaggio 5.
(ii) Se f(a)f(c) < 0 la radice si trova tra a e c. Quindi poni a = a, b = c.
(iii) Altrimenti poniamo a = c, b = b.

Passo 4) Se l'errore assoluto è superiore al tasso di tolleranza o (ba) > e, andare al passaggio 3.

Passo 5) Visualizza c come radice approssimativa.

Vediamo un esempio dell'algoritmo del metodo di bisezione.
Dobbiamo trovare la radice della seguente funzione continua utilizzando la formula del metodo di bisezione.

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

Esempio di metodo di bisezione

Passo 1) Assumiamo,

         un = -10,
         b = 10 e
         e = 1% o 0.01

Passo 2) Ora controlleremo se f(a)f(b) >= 0 oppure no.

         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

Quindi, la radice della funzione di cui sopra si trova in questo intervallo [-10, 10].

Passo 3) Quindi verrà calcolato per primo il punto medio c.

Ora è necessario verificare le seguenti condizioni:

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

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

La condizione è soddisfatta. Per la successiva iterazione, i valori saranno,

un = un = -10
b = c = 0

Passo 4) Poiché (ba) = (0-(-10)) = 10>0.05, il processo verrà ripetuto. Le iterazioni successive sono mostrate nella tabella.

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

Passo 5) Nell'undicesima iterazione, la condizione del passaggio 11 sarà falsa. Pertanto, la radice di questa equazione è -4.

Diagramma logico del metodo di bisezione

Pseudo-codice

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

Esempio di metodo di bisezione in C/C++

Ingresso:

#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;
}

Produzione:

The root is :-1.00586

Esempio del metodo di bisezione in Python