Metodo della bisezione

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

In analisi numerica il metodo di bisezione (o 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.

Algoritmo [modifica]

Data l'equazione $\,f(x)=0$ definita e continua in un intervallo $\,[a,b]$ , tale che $\,f(a)\cdot f(b)<0$ , è allora possibile calcolarne un'approssimazione in $\,[a,b]$ (vedi teorema degli zeri).

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{b-a}{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 crescente limitata ed i $b_i$ formano una successione decrescente limitata. Le due successioni ammettono lo stesso limite che è la radice dell'equazione esaminata.

Come approssimazione della radice $\,\alpha$ si considera il punto medio degli intervalli,

$c_{i} = \frac{a_{i}+b_{i}}{2}\;$ per $i=1,2,...$

L'algoritmo viene arrestato quando $\,f(c_{i})$ è abbastanza vicino a 0 e/o quando l'ampiezza dell'intervallo $\,[a_{i},b_{i}]$ è inferiore ad una certa tolleranza $\,\varepsilon$ . Dunque come stima di $\,\alpha$ alla fine avremo un certo $\,c_{n}$ ; si prova facilmente che per l'errore commesso vale

$|e_{n}|=|c_{n} - \alpha| \leq \frac{b-a}{2^{n+1}}$ .

Un importante corollario è che

$\lim_{n \to \infty}|e_{n}| = 0$

quindi la convergenza del metodo è globale.

Se richiediamo $|e_{n}| \leq \varepsilon$ otteniamo la seguente condizione per n:

$n \geq log_{2}\frac{b-a}{\varepsilon} -1$ .

Essendo $log_{2}10 \approx 3.32$ servono in media più di 3 bisezioni per migliorare di una cifra significativa l'accuratezza della radice, quindi la convergenza è lenta. Inoltre la riduzione dell'errore a ogni passaggio non è monotona, cioè non è detto che $|e_{i+1}| < |e_{i}| \; \forall i$ . Non si può definire quindi un vero e proprio ordine di convergenza per questo metodo.