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.^[1]

Data l'equazione ${\displaystyle f(x)=0}$ definita e continua in un intervallo ${\displaystyle [a,b]}$, tale che ${\displaystyle f(a)\cdot f(b)<0}$, è allora possibile calcolarne un'approssimazione in ${\displaystyle [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 ${\displaystyle {\frac {a+b}{2}}.}$ Se risulta ${\displaystyle f\left({\frac {a+b}{2}}\right)=0}$ allora ${\displaystyle {\frac {a+b}{2}}}$ è la radice cercata; altrimenti tra i due intervalli ${\displaystyle \left[a,{\frac {a+b}{2}}\right]}$ e ${\displaystyle \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 ${\displaystyle [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 ${\displaystyle b_{n}-a_{n}={\frac {b-a}{2^{n}}}}$ per ${\displaystyle n=1,2,3,\ldots }$

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

Come approssimazione della radice ${\displaystyle \alpha }$ si considera il punto medio degli intervalli, cioè ${\displaystyle c_{n}={\frac {a_{n}+b_{n}}{2}},}$ per ${\displaystyle n=1,2,\ldots }$

L'algoritmo viene arrestato quando ${\displaystyle f(c_{n})}$ è abbastanza vicino a ${\displaystyle 0}$ e/o quando l'ampiezza dell'intervallo ${\displaystyle [a_{n},b_{n}]}$ è inferiore ad una certa tolleranza ${\displaystyle \varepsilon }$. Dunque come stima di ${\displaystyle \alpha }$ alla fine avremo un certo ${\displaystyle c_{n}.}$ Si dimostra facilmente che per l'errore commesso ${\displaystyle e_{n}}$ vale la seguente relazione:

${\displaystyle |e_{n}|=|c_{n}-\alpha |\leq {\frac {b-a}{2^{n+1}}}.}$

Un importante corollario è che

${\displaystyle \lim _{n\to \infty }|e_{n}|=0,}$

quindi la convergenza del metodo è globale.

Se richiediamo ${\displaystyle |e_{n}|\leq \varepsilon }$ otteniamo la seguente condizione per ${\displaystyle n}$:

${\displaystyle n\geq log_{2}{\frac {b-a}{\varepsilon }}-1.}$

Essendo ${\displaystyle 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 ${\displaystyle |e_{n+1}|<|e_{n}|}$ per ogni ${\displaystyle n=1,2,\ldots }$ Non si può definire quindi un vero e proprio ordine di convergenza per questo metodo.

Di seguito si fornisce lo pseudocodice di questo metodo:^[2]

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

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

${\displaystyle f(x)=x^{3}-x-2\,.}$

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

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

e

${\displaystyle 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 ${\displaystyle \left[1,2\right]}$.

Essendo gli estremi dell'intervallo che abbiamo considerato ${\displaystyle a_{1}=1}$ e ${\displaystyle b_{1}=2}$, il punto medio sarà:

${\displaystyle c_{1}={\frac {2+1}{2}}=1,5}$

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

Iterazione	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle 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.

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

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

• Wikiversità contiene risorse su metodo della bisezione

• Applet Geogebra per visualizzare il metodo

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