Metodo della bisezione

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.

Descrizione 

Data l'equazione  definita e continua in un intervallo , tale che , è allora possibile calcolarne un'approssimazione in  (vedi teorema degli zeri).

Si procede dividendo l'intervallo in due parti uguali e calcolando il valore della funzione nel punto medio di ascissa  Se risulta  allora  è la radice cercata; altrimenti tra i due intervalli  e  si sceglie quello ai cui estremi la funzione assume valori di segno opposto. Si ripete per questo intervallo il procedimento di dimezzamento. Così continuando si ottiene una successione di intervalli  incapsulati, cioè ognuno incluso nel precedente. Questi intervalli hanno come ampiezze  per 

I valori  sono valori approssimati per difetto della radice, i valori di  sono invece i valori della radice approssimati per eccesso. Gli  formano una successione crescente limitata ed i  formano una successione decrescente limitata. Le due successioni ammettono lo stesso limite che è la radice dell'equazione esaminata.

Come approssimazione della radice  si considera il punto medio degli intervalli, cioè  per 

L'algoritmo viene arrestato quando  è abbastanza vicino a  e/o quando l'ampiezza dell'intervallo  è inferiore ad una certa tolleranza . Dunque come stima di  alla fine avremo un certo  Si dimostra facilmente che per l'errore commesso  vale la seguente relazione:

 

Un importante corollario è che

 

quindi la convergenza del metodo è globale.

Se richiediamo  otteniamo la seguente condizione per :

 

Essendo  servono in media più di tre 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  per ogni  Non si può definire quindi un vero e proprio ordine di convergenza per questo metodo.

Algoritmo 
Di seguito si fornisce lo pseudocodice di questo metodo:  
 N ← 1
 While N ≤ NMAX # limite alle iterazioni per impedire loop infiniti
   c ← (a + b)/2 # new midpoint
   If f(c) = 0 or (b – a)/2 < TOL then # soluzione individuata
     Output(c)
     Stop
   EndIf
   N ← N + 1 # incremento del contatore
   If sign(f(c)) = sign(f(a)) then a ← c else b ← c # nuovo intervallo
 EndWhile
 Output("Operazione non riuscita.") # massimo numero di iterazioni superato

Esempio 
È possibile utilizzare il metodo di bisezione per trovare la radice del seguente polinomio:

Innanzitutto bisogna individuare due numeri  e  tali che  e  hanno segno discorde. Per la funzione summenzionata,  e  soddisfano tale criterio, in quanto 

e

Essendo la funzione continua, le ipotesi del teorema di Bolzano sono rispettate e deve esservi una radice compresa tra .

Essendo gli estremi dell'intervallo che abbiamo considerato  e , il punto medio sarà:

Il valore della funzione al punto medio sarà . Essendo  negativa,   viene sostituita con  per la prossima iterazione affinché  e  abbiano segno discorde. Con la continuazione di questo processo l'intervallo fra  e  diverrà drasticamente sempre più piccolo, sino a convergere nella radice ricercata. Si consulti, in tal senso, la tabella successiva:

Dopo tredici iterazioni è evidente che si verifica una convergenza in 1,521 come radice del polinomio.

Note

Bibliografia 
Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (terza edizione), PWS Publishers, ISBN 0-87150-857-5.

Voci correlate 

 Analisi numerica
 Metodi di approssimazione per la soluzione di equazioni
 Metodo dell'interpolazione lineare
 Metodo dell'iterazione diretta
 Teorema di Bolzano

Altri progetti

Collegamenti esterni 
 Applet Geogebra per visualizzare il metodo

Analisi numerica
Algoritmi per il calcolo degli zeri
Calcolo infinitesimale