Il metodo di bisezione
il metodo di bisezione (o metodo della ricerca degli zeri) è una tecnica numerica che permette di trovare una soluzione approssimata di un'equazione senza doverla risolvere esattamente. Si applica a una funzione continua in un intervallo \([a, b]\), quando assume valori di segno opposto agli estremi. $$ f(a) \cdot f(b) < 0 $$ E' anche detto metodo dicotomico o metodo del dimezzamento.
L'idea è semplice: individuo un intervallo che contiene una radice dell'equazione e lo dimezzo ripetutamente, conservando ogni volta la metà che contiene la radice.
Perché il metodo funziona sempre?
Se una funzione \( f(x) \) è continua e assume valori di segno opposto agli estremi di un intervallo \([a, b] \), allora quell'intervallo contiene almeno una radice \( f(p) = 0 \), cioè uno zero della funzione \( f(x) \).
Ogni volta che dimezzo l'intervallo, scelgo la metà in cui gli estremi continuano ad avere segno opposto. In questo modo non perdo mai la radice e l'errore massimo si dimezza a ogni passaggio.
A ogni passaggio l'intervallo si dimezza e la stima dell'errore diminuisce, fino a raggiungere la precisione desiderata.
Questo mi permette di approssimare una radice senza conoscerne il valore esatto.
Come funziona il metodo
- Trovo un intervallo \( [a,b]\) in cui la funzione continua \( f(x) \) cambia segno $ f(a) \cdot f(b) < 0 $
- Calcolo il punto medio dell'intervallo \( p = \frac{a + b}{2} \)
- Valuto \( f(p) \)
- A seconda del segno di \( f(p) \), sostituisco \( a \) o \( b \) per restringere l'intervallo contenente la radice
- Ripeto il processo (iterazioni) fino a soddisfare una condizione di arresto, come:
- Errore assoluto \( |p_n - p_{n-1}| < \varepsilon \)
- Errore relativo \( \frac{|p_n - p_{n-1}|}{|p_n|} < \varepsilon \)
- Valore piccolo della funzione \( |f(p_n)| < \varepsilon \)
Questo metodo è semplice da implementare e robusto, perché converge sempre se \( f(a) \cdot f(b) < 0 \).
D'altra parte, è un processo lento e richiede molte iterazioni per una buona precisione.
In più richiede che \( f(a) \) e \( f(b) \) abbiano segni opposti e può scartare approssimazioni migliori.
Nota. Il metodo di bisezione è un ottimo punto di partenza per trovare zeri, soprattutto quando non si ha un’ottima approssimazione iniziale. Tuttavia, per efficienza e velocità, è spesso affiancato o sostituito da metodi più rapidi come Newton-Raphson o il metodo della secante.
Un esempio pratico
Ecco un esempio passo-passo del metodo di bisezione applicato a una funzione.
Devo trovare una radice di \( f(x) = \cos(x) - x \) nell'intervallo \([0, 1]\).
Per prima cosa calcolo e verifico se la funzione ha segno opposto agli estremi dell'intervallo.
$$ f(0) = \cos(0) - 0 = 1 $$
$$ f(1) = \cos(1) - 1 \approx 0.5403 - 1 = -0.4597 $$
Poiché la funzione è continua e ha segno opposto agli estremi dell'intervallo \( f(0) \cdot f(1) < 0 \), deduco che esiste almeno una radice in \([0, 1]\)
Fisso una precisione di 3 cifre decimali: usando una tolleranza \( \text{TOL} = 0.001 \).
Ecco le prime iterazioni:
| n | a | b | p = (a + b)/2 | f(p) = cos(x)-x | Intervallo scelto |
|---|---|---|---|---|---|
| 1 | 0.000 | 1.000 | 0.500 | cos(0.5) - 0.5 ≈ 0.3776 | f(p) > 0 ⇒ [0.5, 1] |
| 2 | 0.500 | 1.000 | 0.750 | cos(0.75) - 0.75 ≈ -0.0183 | f(p) < 0 ⇒ [0.5, 0.75] |
| 3 | 0.500 | 0.750 | 0.625 | cos(0.625) - 0.625 ≈ 0.1850 | f(p) > 0 ⇒ [0.625, 0.75] |
| 4 | 0.625 | 0.750 | 0.6875 | cos(0.6875) - 0.6875 ≈ 0.0844 | [0.6875, 0.75] |
| 5 | 0.6875 | 0.750 | 0.71875 | cos(0.71875) - 0.71875 ≈ 0.0333 | [0.71875, 0.75] |
| 6 | 0.71875 | 0.750 | 0.734375 | cos(0.734375) - 0.734375 ≈ 0.0073 | [0.734375, 0.75] |
| 7 | 0.734375 | 0.750 | 0.7421875 | cos(0.7421875) - 0.7421875 ≈ -0.0055 | [0.734375, 0.7421875] |
| 8 | 0.734375 | 0.7421875 | 0.73828125 | cos(0.73828125) - 0.73828125 ≈ 0.0009 ✅ | Stop! |
Spiegazione. Nella prima iterazione \( n =1 \) il punto medio dell'intervallo è \( p = 0.5 \) e il valore della funzione in questo punto è $ f(0.5) = \cos(0.5) - 0.5 = 0.3776 $. Poiché è un valore positivo, deduco che la radice, ossia il punto in cui la funzione è nulla e cambia di segno, si trova più a destra rispetto a 0.5, quindi riduco l'intervallo da \( [0,1] \) a \( [0.5,1] \) e procedo con la seconda iterazione. Nella seconda iterazione \( n=2 \) il punto medio dell'intervallo è \( p = 0.750 \) in cui la funzione ha un valore negativo \( f(0.75) = -0.0183 \). In questo caso, deduco che la radice si trovi a sinistra di 0.75. Quindi riduco l'intervallo da \( [0.5,1] \) a \( [0.5,0.75] \) e procedo con la terza iterazione. Il processo continua finché non trovo un punto \( p \) in cui la funzione \( f(p) = 0 \pm 0.001 \) sia vicina a zero con un margine di tolleranza di ±0.001.
Dopo 8 iterazioni, trovo che un risultato vicino allo zero con una precisione inferiore a 0.001:
\[ p \approx 0.73828125 \quad \text{con } |f(p)| < 0.001 \]
Quindi la radice di \( \cos(x) = x \) è approssimativamente 0.738, che è corretta a 3 cifre decimali.
Ma funziona sempre? Il metodo di bisezione funziona, ma solo se la funzione cambia segno nell’intervallo, come in questo esempio, ed è una funzione continua (senza buchi). Se in un intervallo si verifica \( f(a) \cdot f(b) > 0 \), questo metodo non trova la radice nemmeno se c'è veramente. Inoltre, è un metodo molto lento. Un altro limite è che bisogna individuare gli intervalli in cui si trovano le radici di una funzione e non sempre è facile trovarli a priori. E' un po' come cercare le chiavi perse in salotto… è facile solo se sai già che stanno da qualche parte tra il divano e la finestra.
Esempio 2
Utilizzo il metodo di bisezione per cercare le soluzioni approssimate dell'equazione seguente con un errore inferiore a \(0,1\)
\[ x^5+x^3-4=0 \]
Considero la funzione:
\[ f(x)=x^5+x^3-4 \]
Cerchiamo due valori di \(x\) per i quali la funzione assume segni opposti.
Ad esempio, $ x=1 $ e $ x=0 $
\[ f(1)=1^5+1^3-4=-2<0 \]
\[ f(2)=2^5+2^3-4=36>0 \]
La funzione è continua perché è un polinomio.
Poiché \(f(1)<0\) e \(f(2)>0\), per il teorema degli zeri esiste almeno una radice \(c\) nell'intervallo \( [1,2] \).
Inoltre, la funzione è strettamente crescente, perché \( f'(x)=5x^4+3x^2 \) è positiva per ogni \(x\ne0\). Quindi la radice è unica.
1] Primo dimezzamento
L'intervallo iniziale è:
\[ [a_0,b_0]=[1,2] \]
Calcolo il punto medio:
\[ m_0=\frac{a_0+b_0}{2} =\frac{1+2}{2}=1,5 \]
Il punto medio divide l'intervallo in due parti:
\[ [1;1,5]\qquad [1,5;2] \]
Per capire quale delle due contiene la radice, calcolo il valore della funzione agli estremi.
So già che
\[ f(1)=1^5+1^3-4=-2<0 \]
\[ f(2)=2^5+2^3-4=36>0 \]
Calcolo il valore della funzione nel punto medio \( x=1,5 \).
\[ f(1,5)=(1,5)^5+(1,5)^3-4 \]
\[ f(1,5)=7,59375+3,375-4 \]
\[ f(1,5)=6,96875>0 \]
Poiché:
\[ f(1)<0,\qquad f(1,5)>0 \]
la radice si trova nell'intervallo \( [1;1,5] \).
Scarto quindi la metà destra e scelgo \(m_0=1,5\) come soluzione approssimata.
A questo punto calcolo l'errore massimo.
\[ \varepsilon_0=\frac{b_0-a_0}{2} \]
\[ \varepsilon_0=\frac{2-1}{2}=0,5 \]
Poiché \( 0,5>0,1 \) l'approssimazione non è ancora sufficientemente precisa. Quindi, reitero il procedimento.
2] Secondo dimezzamento
Il nuovo intervallo è:
\[ [a_1,b_1]=[1;1,5] \]
Calcolo il punto medio:
\[ m_1=\frac{1+1,5}{2}=1,25 \]
Valuto la funzione quando $ x=1,25 $.
\[ f(1,25)=(1,25)^5+(1,25)^3-4 \]
\[ f(1,25)=3,0517578125+1,953125-4 \]
\[ f(1,25)=1,0048828125>0 \]
Poiché:
\[ f(1)<0,\qquad f(1,25)>0 \]
la radice si trova nell'intervallo \( [1;1,25] \).
La stima dell'errore ora è
\[ \varepsilon_1=\frac{1,5-1}{2} \]
\[ \varepsilon_1=0,25 \]
Poiché \( 0,25>0,1 \) l'errore non è ancora accettabile e devo continuare.
3] Terzo dimezzamento
Il nuovo intervallo è:
\[ [a_2,b_2]=[1;1,25] \]
Calcolo il punto medio:
\[ m_2=\frac{1+1,25}{2}=1,125 \]
Valuto la funzione quando $ x=1,125 $
\[ f(1,125)=(1,125)^5+(1,125)^3-4 \]
\[ f(1,125)=1,8020324707+1,423828125-4 \]
\[ f(1,125)\approx-0,77414<0 \]
Poiché:
\[ f(1,125)<0,\qquad f(1,25)>0 \]
la radice si trova nell'intervallo \( [1,125;1,25] \).
La stima dell'errore è
\[ \varepsilon_2=\frac{1,25-1}{2} \]
\[ \varepsilon_2=0,125 \]
Poiché \( 0,125>0,1 \) devo ancora continuare.
4] Quarto dimezzamento
Il nuovo intervallo è:
\[ [a_3,b_3]=[1,125;1,25] \]
Calcolo il punto medio dell'intervallo:
\[ m_3=\frac{1,125+1,25}{2} \]
\[ m_3=1,1875 \]
La stima dell'errore è:
\[ \varepsilon_3=\frac{1,25-1,125}{2} \]
\[ \varepsilon_3=0,0625 \]
Finalmente la stima dell'errore è accettabile perché \( 0,0625<0,1 \).
Ho raggiunto la precisione richiesta.
Nota. Non è necessario calcolare \(f(1,1875)\), perché so già che la radice è contenuta nell'intervallo \([1,125;1,25]\) e che il suo punto medio dista dalla radice al massimo \(0,0625\).
Quindi, la soluzione approssimata è
\[ x\approx1,1875 \]
L'errore massimo garantito è \( 0,0625 \) ed è inferiore all'errore \( 0,1 \) che ritenevo accettabile.
Ecco la tabella riassuntiva dei passaggi:
| Iterazione | Intervallo utilizzato | Punto medio | Segno di \(f(m_n)\) | Errore massimo |
|---|---|---|---|---|
| 0 | \([1;2]\) | 1,5 | Positivo | 0,5 |
| 1 | \([1;1,5]\) | 1,25 | Positivo | 0,25 |
| 2 | \([1;1,25]\) | 1,125 | Negativo | 0,125 |
| 3 | \([1,125;1,25]\) | 1,1875 | Non necessario | 0,0625 |
Il risultato conferma che sono sufficienti quattro punti medi, da \(m_0\) a \(m_3\).
Esplorazione del dominio: come individuare gli intervalli contenenti radici
L'esplorazione del dominio di una funzione consiste nel trovare gli intervalli \([a, b]\) dove \( f(a) \cdot f(b) < 0 \), cioè la funzione cambia segno e quindi c'è una radice lì dentro.
E' il passo preliminare fondamentale per individuare gli intervalli in cui applicare il metodo di bisezione.
In pratica, consiste nel valutare la funzione in una sequenza di punti distribuiti nel dominio e cercare coppie di punti consecutivi \( a \) e \( b \) in cui la funzione cambi segno, ossia \( f(a) \cdot f(b) < 0 \).
Per il teorema degli zeri, in questi intervalli \([a, b]\) deve esistere almeno una radice nell’intervallo.
La scelta della distanza tra i punti, detta passo di esplorazione, ed è cruciale perché:
- se troppo grande, rischia di saltare cambi di segno e quindi perdere radici
- se troppo piccolo, garantisce l’individuazione di tutte le radici ma aumenta notevolmente il costo computazionale
Per questo, si cerca un compromesso tra accuratezza ed efficienza, adottando un passo abbastanza fine da catturare i comportamenti significativi della funzione, ma non tanto minuto da rendere l'esplorazione inutilmente pesante.
Solo dopo aver identificato con successo gli intervalli con cambio di segno, si procede ad applicare il metodo di bisezione in ciascuno di essi.
Esempio
Devo trovare tutte le radici reali della funzione
\[ f(x) = x^3 - 2x^2 - x + 1 \]
Inizialmente non so in quale intervallo cercare. Essendo un polinomio di terzo grado, posso dedurre che può avere fino a tre radici reali ma non so dove sono le radici, quante sono e se ci sono.
Non posso nemmeno trovarle a occhio, perché non ci sono numeri interi evidenti, quindi serve un’esplorazione numerica.
Provo ad analizzare la funzione in alcuni punti con un passo di esplorazione pari a 5
\[
\begin{array}{c|c}
x & f(x) \\
\hline
-10 & -1189 \\
-5 & -169 \\
0 & 1 \\
5 & 71 \\
10 & 791 \\
\end{array}
\]
Dalla tabella mi accorgo che deve esserci almeno una radice nell'intervallo (-5,0).
Tuttavia, se mi basassi solo su questa analisi farei un errore perché il passo di esplorazione è troppo grande. Sto sorvolando la funzione da troppo in alto.
Ad esempio, riduco il passo di esplorazione a 1 per scendere più nel dettaglio.
\[
\begin{array}{cc}
x & f(x) \\
\hline
-5 & -169 \\
-4 & -91 \\
-3 & -41 \\
-2 & -13 \\
-1 & -1 \\
0 & 1 \\
1 & -1 \\
2 & -1 \\
3 & 7 \\
4 & 29 \\
5 & 71 \\
\end{array}
\]
Così facendo mi accorgo che nella funzione c'è un primo cambio di segno nell'intervallo (-1,0), un secondo cambio di segno nell'intervallo (0,1) e un terzo cambio di segno nell'intervallo (2,3)
Nota. Questo dimostra che se esploro con balzi troppo grandi, potrei saltare radici tra due valori. Se, invece, esploro con balzi troppo piccoli, trovo tutto ma il costo computazionale aumenta inutilmente. Ad esempio, un passo 0.1 nell'intervallo \([-10, 10]\) implica 200 valutazioni ed è troppo costoso. Come sempre, ... in medio stat virtus. Serve un compromesso intelligente, ad esempio usare un passo di 0.5 o 0.25, a seconda della funzione.
Una volta individuati gli intervalli posso applicare il metodo di bisezione su ciascuno di essi
- Primo intervallo: \([-1, 0]\)
In poche interazioni giungo a una radice approssimata: \[ x_1 \approx -0.8 \] - Secondo intervallo: \([0, 1]\)
Anche in questo caso non occorrono molte iterazioni per arrivare a una radice approssimata \[ x_2 \approx 0.5 \] - Terzo intervallo: \([2, 3]\)
Applico nuovamente il metodo di bisezione in questo intervallo e trovo la terza radice \[ x_3 \approx 2.2 \]
Pertanto, le tre radici approssimate della funzione \( f(x) = x^3 - 2x^2 - x + 1 \) sono \( x_1 \approx -0.8 \) , \( x_2 \approx 0.5, \) e \( x_3 \approx 2.2 \).
In conclusione esplorare il dominio è essenziale per localizzare gli intervalli delle radici prima di usare il metodo di bisezione.
Serve un passo bilanciato, né troppo grande, né troppo piccolo.
Una volta trovati gli intervalli con cambio di segno, si applica il metodo di bisezione localmente, in modo efficiente e sicuro
E così via.
