Metodo della bisezione
# 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 $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:

## 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.

