Metodo della bisezione

Da Wikipedia, l'enciclopedia libera.

Alcuni passi del metodo della bisezione, applicato all'intervallo [a₁;b₁]. Il punto rosso è la radice della funzione.

Il metodo della bisezione (detto anche algoritmo dicotomico) è il metodo numerico più semplice per trovare le radici di una funzione. La sua efficienza è scarsa e presenta lo svantaggio di richiedere ipotesi particolarmente restrittive. Ha però il notevole pregio di essere stabile in ogni occasione e quindi di garantire sempre la buona riuscita dell'operazione.

[modifica] Esempio

Data l'equazione $\,f(x)=0\,$ ed un intervallo $\,[a,b]\,$ che si ha ragione di credere contenga una radice è possibile ottenere un'approssimazione di questa radice nel caso che agli estremi dell'intervallo si abbia $\,f(a)\cdot f(b)<0\,$ e la $\,f(x)\,$ sia continua in $\,[a,b]\,$ .

Si procede dividendo l'intervallo in due parti eguali e calcolando il valore della funzione nel punto medio di ascissa $\,\frac{a+b}{2}\,$ . Se risulta $f\left(\frac{a+b}{2}\right)=0$ allora $\frac{a+b}{2}$ è la radice cercata; altrimenti tra i due intervalli $\left[a,\frac{a+b}{2}\right]$ e $\left[\frac{a+b}{2},b\right]$ si sceglie quello ai cui estremi la funzione assume valori di segno opposto. Si ripete per questo intervallo il procedimento di dimezzamento e, così continuando si ottiene, potenzialmente, una successione di intervalli incapsulati, cioè ognuno incluso nel precedente, $\,[a_1,b_1],[a_2,b_2],...,[a_n,b_n], ...\,$ ; questi hanno come ampiezze $b_n-a_n=\frac{a+b}{2^n}$ per $\,n=1, 2, 3, ...$ .

I valori $a i$ sono valori approssimati per difetto della radice, i valori di $b i$ sono invece i valori della radice approssimati per eccesso. Gli $a i$ formano una successione non decrescente limitata ed i $b i$ formano una successione non crescente limitata. Le due successioni ammettono lo stesso limite che è la radice dell'equazione esaminata. Fissata l'approssimazione $τ$ richiesta, si può ricavare il numero di dimezzamenti necessari, dalla condizione $b_n-a_n=\frac{a+b}{2^n}<\tau$ dalla quale $n> \log_2\frac{b-a}{\tau}$ .

Con abuso di linguaggio (vedi osservazione seguente) possiamo dire che il metodo della bisezione è del primo ordine, ciò significa che l'errore della stima al ciclo n+1 (ε_n+1) è proporzionale all'errore al ciclo n (ε_n), dunque la convergenza è lineare. Poiché l'intervallo viene dimezzato a ogni ciclo si può sinteticamente esprimere quanto detto con la relazione

ε_n+1 = 1/2ε_n

Osservazione: è uno dei pochi algoritmi in cui la decrescenza dell'errore non è monotona!