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.

Descrizione

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 uguali 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 $[a,\frac{a+b}{2}]$ e $[\frac{a+b}{2},b]$ 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 $[a_1,b_1],[a_2,b_2],\dots ,[a_n,b_n],\dots ,$ incapsulati, cioè ognuno incluso nel precedente. Questi intervalli hanno come ampiezze $b_n-a_n=\frac{b-a}{2^n}$ per $n=1,2,3,\dots$

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_n$ formano una successione crescente limitata ed i $b_n$ 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, cioè $c_n=\frac{a_n+b_n}{2},$ per $n=1,2,\dots$

L'algoritmo viene arrestato quando $f(c_n)$ è abbastanza vicino a $0$ e/o quando l'ampiezza dell'intervallo $[a_n,b_n]$ è inferiore ad una certa tolleranza $\epsilon$. Dunque come stima di $\alpha$ alla fine avremo un certo $c_n.$ Si dimostra facilmente che per l'errore commesso $e_n$ vale la seguente relazione:

$|e_n|=|c_n-\alpha |\le \frac{b-a}{2^{n+1}}.$

Un importante corollario è che

$\underset{n\to \mathrm{\infty }}{\lim }|e_n|=0,$

quindi la convergenza del metodo è globale.

Se richiediamo $|e_n|\le \epsilon$ otteniamo la seguente condizione per $n$:

$n\ge lo{g}_2\frac{b-a}{\epsilon }-1.$

Essendo $lo{g}_{2}10\approx 3,32$ 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 $|e_{n+1}|<|e_n|$ per ogni $n=1,2,\dots$ 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:

$f(x)=x^3-x-2.$

Innanzitutto bisogna individuare due numeri $a$ e $b$ tali che $f(a)$ e $f(b)$ hanno segno discorde. Per la funzione summenzionata, $a=1$ e $b=2$ soddisfano tale criterio, in quanto

$f(1)=(1{)}^3-(1)-2=-2$

e

$f(2)=(2{)}^3-(2)-2=+4.$

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

Essendo gli estremi dell'intervallo che abbiamo considerato $a_1=1$ e $b_1=2$, il punto medio sarà:

$c_1=\frac{2+1}{2}=1,5$

Il valore della funzione al punto medio sarà $f(c_1)=(1,5{)}^3-(1,5)-2=-0,125$. Essendo $f(c_1)$ negativa, $a=1$ viene sostituita con $a=1,5$ per la prossima iterazione affinché $f(a)$ e $f(b)$ abbiano segno discorde. Con la continuazione di questo processo l'intervallo fra $a$ e $b$ diverrà drasticamente sempre più piccolo, sino a convergere nella radice ricercata. Si consulti, in tal senso, la tabella successiva:

Iterazione	$a_n$	$b_n$	$c_n$	$f(c_n)$
1	1	2	1.5	−0.125
2	1,5	2	1,75	1,6093750
3	1,5	1,75	1,625	0,6660156
4	1,5	1,625	1,5625	0,2521973
5	1,5	1,5625	1,5312500	0,0591125
6	1,5	1,5312500	1,5156250	−0,0340538
7	1,5156250	1,5312500	1,5234375	0,0122504
8	1,5156250	1,5234375	1,5195313	−0,0109712
9	1,5195313	1,5234375	1,5214844	0,0006222
10	1,5195313	1,5214844	1,5205078	−0,0051789
11	1,5205078	1,5214844	1,5209961	−0,0022794
12	1,5209961	1,5214844	1,5212402	−0,0008289
13	1,5212402	1,5214844	1,5213623	−0,0001034
14	1,5213623	1,5214844	1,5214233	0,0002594
15	1,5213623	1,5214233	1,5213928	0,0000780

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

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

Collegamenti esterni

• Applet Geogebra per visualizzare il metodo