Metodo di bisezione

Il metodo di bisezione si basa sul teorema di esistenza degli zeri per una funzione continua, il quale garantisce l'esistenza di almeno una radice $\alpha$ della funzione $f$ su un intervallo $[a,b]$ se $f(a)$ e $f(b)$ hanno segno opposto. Se su $[a,b]$ la funzione $f$ è anche monotona, ovvero se $f^{\prime }(x)>0\mathrm{\forall }x\in [a,b]$, allora lo zero della funzione è unico. Stabilita l'esistenza della soluzione, l'algoritmo definisce la successione $x_k$ come la successione dei punti medi degli intervalli di larghezza decrescente che soddisfano le ipotesi del teorema degli zeri. In pratica, dato un intervallo di partenza con all'interno una radice, si continua a dividere a metà gli intervalli finché l'ultimo è sufficientemente piccolo da assicurarci un buona approssimazione dello zero.

Teorema degli zeri

L'enunciato del teorema di esistenza degli zeri per le funzioni continue (o Teorema di Bolzano) dice

Sia $f:[a,b]\to ℝ$ una funzione continua tale che $f(a)\cdot f(b)<0.$

Allora esiste almeno un punto $x$ nell'intervallo aperto $(a,b)$ tale che $f(x)=0$.

La dimostrazione può essere trovata qui.

Algoritmo di bisezione

Data $f\in C^0([a,b])$ che soddisfi le ipotesi del teorema degli zeri e data una tolleranza $ϵ$

1. $x_k=\frac{a+b}{2},k\ge 1$;
2. se $e_k=|b-x_k|\le ϵ:$esci;
3. se $f(x_k)=0:$ esci;

   altrimenti se $f(a)f(x_k)>0:$ $a=x_k$;

   altrimenti $:b=x_k$;

4. torna al passo 1;

Nel primo passo viene definito il nuovo valore della successione: il nuovo punto medio. Nel secondo passo viene effettuato il controllo sulla tolleranza: se l'errore commesso è inferiore alla tolleranza prestabilita accettiamo $x_k$ come radice di $f$. Il terzo passo consiste nel valutare la funzione in $x_k$: se $f(x_k)=0$ abbiamo trovato la soluzione; altrimenti, avendo diviso l'intervallo in due, dobbiamo capire da che parte è rimasto lo zero. Per fare ciò utilizziamo le ipotesi del teorema degli zeri, cerchiamo, cioè, il nuovo intervallo tale per cui la funzione agli estremi è di segno opposto e ridefiniamo quindi l'intervallo, spostando $a$ o $b$ in $x_k$. Infine, se non abbiamo ancora trovato una buona approssimazione per la soluzione, torniamo al punto di partenza.

Analisi di convergenza

Ad ogni iterazione l'intervallo ${ℐ}_k=[a_k,b_k]$ viene diviso a metà, dove abbiamo indicato con $a_k$ e $b_k$ gli estremi dell'intervallo alla iterazione $k\ge 0$. Ovviamente ${ℐ}_0=[a,b]$. Indichiamo con $|{ℐ}_k|=meas({ℐ}_k)$ la lunghezza dell'intervallo ${ℐ}_k$. In particolare si ha

$|{ℐ}_k|=\frac{|{ℐ}_{k-1}|}{2}=\frac{|{ℐ}_{k-2}|}{2^2}=...=\frac{|{ℐ}_0|}{2^k}=\frac{b-a}{2^k}.$

Si noti che $\alpha \in {ℐ}_k,\mathrm{\forall }k\ge 0$, e quindi

$e_k\le |{ℐ}_k|$.

Da questo si ha che $\underset{k\to \mathrm{\infty }}{\lim }{e}_k=0$, poiché $\underset{k\to \mathrm{\infty }}{\lim }\frac{1}{2^k}=0$. Quindi si ha

$\underset{k\to \mathrm{\infty }}{\lim }{x}_k=\alpha$,

che dimostra la convergenza globale del metodo.

La convergenza del metodo di bisezione è molto lenta. Sebbene l'errore, in generale, non diminuisca in maniera monotona, la velocità media di convergenza è 1/2 e quindi, modificando leggermente la definizione di ordine di convergenza, è possibile dire che il metodo di bisezione converge linearmente con fattore di convergenza 1/2. Non crei confusione il fatto che, su alcuni testi o in altre fonti, talvolta, l'errore venga dato dalla relazione $e_k=\frac{b-a}{2^{k+1}}$. Questo è dovuto al fatto che la successione viene definita per $k\ge 0$ invece che per $k\ge 1$.

Esempio

Si consideri la funzione $f(x)=\cos x$ in $[0,3\pi ]$. In questo intervallo la funzione ha 3 zeri: ${\alpha }_1=\frac{\pi }{2}$, ${\alpha }_2=\frac{3\pi }{2}$ e ${\alpha }_3=\frac{5\pi }{2}$.

Teoricamente il metodo di bisezione converge in un'iterazione a ${\alpha }_2$. Nella pratica, tuttavia, il metodo converge o ${\alpha }_1$ o a ${\alpha }_3$. Infatti, dato che le operazioni vengono fatte in aritmetica finita, $x_1\ne \frac{3\pi }{2}$ e a seconda delle approssimazioni del calcolatore $f(x_1)$ potrà essere positivo o negativo, ma mai nullo. Così l'algoritmo di bisezione in questo caso escluderà automaticamente la radice ${\alpha }_2$ alla prima iterazione, in quanto l'errore sarà ancora molto grande ($e_1={\alpha }_2$).

Supponiamo che l'algoritmo converga a ${\alpha }_1$ e vediamo quante iterazioni sono richieste affinché l'errore sia minore di $10^{-10}$. Bisogna quindi richiedere che

$e_k\le \frac{3\pi }{2^k}\le 10^{-10}$,

e quindi, risolvendo la disequazione, che

$k\ge {\log }_2(3\cdot 10^{10}\pi )\approx 36.46$,

e quindi, poiché $k$ è un numero naturale, si ha $k\ge 37$.

Riferimenti

• Template:Cita libro

• Template:Cita libro

• Template:Cita libro

Altre risorse sul metodo di bisezione

Guarda la pagina altre risorse sulla risoluzione di equazioni non lineari. Template:Ip