Metodo della bisezione

Da Wikipedia, l'enciclopedia libera.
Alcuni passi del metodo della bisezione, applicato all'intervallo [a1;b1]. 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 | modifica sorgente]

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.

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica