2.1 Algoritmo di bisezione
L’algoritmo di bisezione è un metodo semplice per trovare le radici di funzioni unidimensionali. L’obiettivo è trovare una radice \(x_0\in\) tale che \(f(x_0)=0\). L’algoritmo inizia con un grande intervallo, noto per contenere \(x_0\), e poi riduce successivamente la dimensione dell’intervallo fino a quando non si trova la radice. Il fondamento teorico dell’algoritmo è il teorema dei valori intermedi che afferma che se una funzione continua \(f(a)\ prende i valori \(f(a)\ e \(f(b)\ nei punti finali dell’intervallo \(\), allora \(f)\ deve prendere tutti i valori tra \(f(a)\ e \(f(b)\ in qualche punto dell’intervallo. Quindi se \(f(a) < \gamma < f(b)\), allora esiste un \(c\in\) tale che \(f(c)=\gamma\).
Con queste informazioni, possiamo presentare l’algoritmo di bisezione. Prima dobbiamo verificare che \(\testo{segno}(f(a)) \ne \testo{segno}(f(b))\). Altrimenti, l’intervallo non contiene la radice e potrebbe essere necessario allargarlo. Allora possiamo procedere:
-
Lascia che \(c = \frac{a + b}{2}\).
-
Se \(f(c) = 0\), fermati e ritorna \(c\).
-
Se \(\testo{segno}(f(a))\ne{segno}(f(c))\), allora impostate \(freccia a sinistra c\). Altrimenti se \(\testo{segno}(f(b))\ne\testo{segno}(f(c))\), allora impostate \(a\freccia sinistra c\).
-
Prendete il via e ripetete fino alla convergenza (vedi sotto).
Dopo \(n)iterazioni, la dimensione dell’intervallo che racchiude la radice sarà \(2^{-n}(b-a)\).
L’algoritmo di bisezione è utile, concettualmente semplice, ed è facile da implementare. In particolare, non hai bisogno di alcuna informazione speciale sulla funzione \(f\) tranne la capacità di valutarla in vari punti dell’intervallo. Gli svantaggi sono che è utile solo in una dimensione e la sua convergenza è lineare, che è il tasso di convergenza più lento per gli algoritmi che discuteremo (più avanti).
L’algoritmo di bisezione può incontrare problemi in situazioni in cui la funzione \(f\) non si comporta bene. La situazione ideale per l’algoritmo di bisezione assomiglia a questa.
Sistemazione ideale per l’algoritmo di bisezione.
Qui, \(f(a)\) e \(f(b)\) sono di segno opposto e la radice è chiaramente tra \(a\) e \(b\).
Nello scenario seguente, l’algoritmo non parte perché \(f(a)>0\) e \(f(b)>0\).
Derivata di \(f\) alla radice è \(0\).
In questo prossimo scenario, ci sono due radici tra \(a\) e \(b\), oltre ad avere \(f(a)>0\) e \(f(b)>0\). Si dovrebbe ridurre la lunghezza dell’intervallo di partenza per trovare una delle due radici.
Due radici all’interno dell’intervallo.
Nello scenario seguente, l’algoritmo partirà perché \(f(a)\) e \(f(b)\) sono di segno opposto, ma non c’è una radice.
L’intervallo contiene un asintoto ma nessuna radice.
La convergenza dell’algoritmo di bisezione può essere determinata dall’avere \(|b-a|< \varepsilon\) per qualche piccolo \(\varepsilon\) o dall’avere \(|f(b)-f(a)|< \varepsilon\). Quale criterio si usa dipende dall’applicazione specifica e da quali tipi di tolleranze sono richieste.
2.1.1 Esempio: Quantili
Data una funzione di distribuzione cumulativa \(F(x)\) e un numero \(p\ in (0, 1)\), un quantile di \(F\) è un numero \(x\) tale che \(F(x) = p\). L’algoritmo di bisezione può essere usato per trovare un quantile \(x) per un dato \(p) definendo la funzione \(g(x) = F(x) – p\) e risolvendo il valore di \(x) che ottiene \(g(x) = 0\).
Un altro modo per mettere questo è che stiamo invertendo la CDF per calcolare \(x = F^{-1}(p)\). Quindi l’algoritmo di bisezione può essere usato per invertire le funzioni in queste situazioni.