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.

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

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 $\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. Così continuando si ottiene una successione di intervalli $[a_{1},b_{1}],[a_{2},b_{2}],\ldots ,[a_{n},b_{n}],\ldots ,$ 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,\ldots$

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,\ldots$

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 $\varepsilon$. 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 |\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 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,\ldots$ 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 $\left[1,2\right]$.

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

Altri progetti

Altri progetti

• Wikiversità

• Wikiversità contiene risorse su metodo della bisezione

Collegamenti esterni

• Applet Geogebra per visualizzare il metodo