Algoritmo del metodo di bisezione con esempi

Cos'è il metodo di bisezione?

Il metodo di bisezione è una delle tecniche numeriche fondamentali per trovare la radice di un'equazione polinomiale o trascendente. Funziona delimitando l'intervallo che contiene la radice e suddividendo tale intervallo a metà ad ogni iterazione, finché la radice non viene individuata entro una tolleranza accettabile. Proprio per questo comportamento di delimitazione, il metodo di bisezione è anche chiamato metodo di delimitazione.

Poiché il suo meccanismo di funzionamento assomiglia alla ricerca binaria, il metodo di bisezione è anche noto come metodo di ricerca binaria, metodo del dimezzamento o metodo della dicotomia. Si basa su solide fondamenta teoriche: il teorema dei valori intermedi, che garantisce che una funzione continua che cambia segno in un intervallo deve necessariamente attraversare lo zero da qualche parte all'interno di tale intervallo.

Ora che abbiamo fornito la definizione di base, esploriamo perché trovare le radici delle equazioni è importante e come il metodo di bisezione si inserisce in questo contesto più ampio.

Trovare le radici delle equazioni

In questa trattazione, ci concentreremo esclusivamente sulle equazioni con una sola variabile indipendente. Tali equazioni possono essere lineari o non lineari. Le equazioni lineari descrivono il grafico di una retta, mentre le equazioni non lineari descrivono curve e forme più complesse.

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

Consideriamo f(x) come una funzione continua reale. Secondo il teorema dei valori intermedi, l'equazione f(x) = 0 ha almeno una radice tra a e b ogni volta che f(a)f(b) < 0. In altre parole, la funzione f(x) ha una radice, "c", da qualche parte tra a e b.

Questa proprietà di cambio di segno è esattamente ciò che sfrutta il metodo di bisezione. La sezione successiva mostra come questo concetto si presenta graficamente.

Rappresentazione grafica del metodo di bisezione

Il grafico seguente rappresenta il meccanismo di funzionamento del metodo di bisezione. Dal grafico si può notare che la radice effettiva dell'equazione è evidenziata in rosso.

La procedura può essere riassunta come segue:

• Per prima cosa scegliamo due ipotesi iniziali, una₁ e B₁, per cui f(a₁)f(b₁) < 0. Secondo il teorema dei valori intermedi, la radice deve trovarsi in [a₁, b₁].
• Calcoliamo quindi il punto medio di un₁ e B₁, che è b₂. L'intervallo iniziale è ora ridotto a [a₁, b₂] perché f(a₁)f(b₂) < 0.
• Allo stesso modo, l'intervallo viene dimezzato ripetutamente fino a quando non si trova una soluzione approssimativa entro la tolleranza desiderata.

Avendo ora chiara l'intuizione geometrica, possiamo formalizzare la procedura come un algoritmo passo-passo.

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 un tasso di tolleranza e.

Passo 2) Se f(a)f(b) >= 0, allora la radice non si trova in questo intervallo. In tal caso, non esiste alcuna soluzione all'interno di [a, b].

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

(i) Se il valore della funzione nel 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 poniamo a = a, b = c.
(iii) Altrimenti, poniamo a = c, b = b.

Passo 4) Se l'errore assoluto è superiore al margine di tolleranza, ovvero (b – a) > e, tornare al passaggio 3.

Passo 5) Visualizza c come radice approssimativa.

Vediamo un esempio pratico dell'algoritmo del metodo di bisezione. Troveremo 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) Supponiamo,

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

Pertanto, la radice della funzione sopra riportata si trova nell'intervallo [-10, 10].

Passo 3) Successivamente, viene calcolato il punto medio c.

Ora è necessario verificare le seguenti condizioni:

(i) Se f(c) = 0:
         f(c) = f(0) = (0)³ - (0)² + 2 = 2, che non è uguale a 0.

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

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

         un = un = -10
         b = c = 0

Passo 4) Poiché (b – a) = (0 – (-10)) = 10 > 0.01, il processo viene ripetuto. Le iterazioni successive sono mostrate nella tabella sottostante.

Passo 5) All'undicesima iterazione, la condizione al punto 4 diventa falsa. Pertanto, la radice approssimativa di questa equazione è -1.00586.

Dopo aver illustrato un esempio numerico, la sezione successiva presenta il diagramma logico che descrive l'intero flusso di controllo.

Diagramma logico del metodo di bisezione

Il diagramma di flusso sottostante riassume la logica decisionale del metodo di bisezione, inclusi il controllo della parentesi, l'aggiornamento del punto medio e il test di tolleranza.

Pseudo-Code

Lo pseudocodice riportato di seguito rispecchia l'algoritmo e funge da modello per implementare il metodo di bisezione in qualsiasi linguaggio di programmazione.

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

Il seguente C/C++ Il programma implementa il metodo di bisezione per trovare la radice di f(x) = x³ - X² + 2 nell'intervallo [-10, 10].

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

Migliori Python La versione seguente produce la stessa radice approssimativa utilizzando una logica identica, il che la rende ideale per esperimenti rapidi e per scopi didattici.

Ingresso:

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)

Produzione:

The root is :  -1.0059

Vantaggi e limiti del metodo di bisezione

Come ogni tecnica numerica, il metodo di bisezione presenta chiari punti di forza e alcuni svantaggi pratici. La tabella seguente riassume i principali vantaggi e svantaggi.

Applicazioni del metodo di bisezione

Il metodo di bisezione viene utilizzato in molti scenari informatici pratici e moderni in cui è richiesto un passaggio robusto per la ricerca delle radici.

• Simulazioni ingegneristiche: Risoluzione di equazioni non lineari che si presentano nel trasferimento di calore, nella fluidodinamica e nell'analisi strutturale.
• Modellazione finanziaria: Calcolo dei rendimenti, dei tassi interni di rendimento e dei punti di pareggio laddove non esistano soluzioni in forma chiusa.
• Apprendimento automatico e intelligenza artificiale: Individuazione delle soglie, calibrazione dei modelli e ottimizzazione degli iperparametri all'interno di risolutori numerici basati sull'intelligenza artificiale.
• Grafica computerizzata: Determinazione delle intersezioni raggio-superficie e dei valori dei parametri lungo le curve.
• Sistemi integrati: Approssimazione delle radici in controllori a risorse limitate, dove semplicità e prevedibilità sono più importanti della velocità.

DOMANDE FREQUENTI