Il metodo di Bisezione

Presentiamo qui il metodo di bisezione che, data una funzione continua

$$f:\mathcal{I}=(a,b)\subseteq \mathbb{R} \to \mathbb{R}$$

e tale che

$$f(a)f(b)<0$$

genera una successione $\{ x_k \}$ che converge verso la soluzione $\overline{x}$. Infatti, sotto le ipotesi fatte prima, sappiamo dal Teorema di esistenza degli zeri che

$$\exists \overline{x} \in (a,b) \mbox{ t.c. } f(\overline{x})=0$$

.

L'algoritmo procede come segue:

$$x=\frac{a+b}{2}$$

1. se $f(x)=0 \Rightarrow \overline{x}=x$
   
2. se $f(a)f(x)<0 \Rightarrow \mbox{ si riapplica nell'intervallo } [a,x]$
   
3. se $f(a)f(x)>0 \Rightarrow \mbox{ si riapplica nell'intervallo } [x,b]$

Difficilmente l'algoritmo potrà convergere dato che, in aritmetica finita, la condizione di uscita $f(x)=0$ non si verificherà mai, se non in casi molto rari. Si devono quindi cercare criteri di arresto alternativi a quello proposto sopra. Ricordiamoci che quello che interessa a noi non è la soluzione esatta, ma una buona approssimazione di essa.

Indicando con $L_k=\vert b_k-a_k\vert$ la larghezza dell'intervallo nel quale attualmente stiamo cercando la soluzione, otteniamo la seguente relazione ricorsiva

$$L_k=\frac{1}{2}L_{k-1}.$$

Sviluppando fino al termine di indice $0$ avremo:

$$L_k =\frac{1}{2}L_{k-1}= \cdots = \frac{1}{2^k}L_0.$$

Allora fissata la nostra tolleranza $\varepsilon$, cioè la bontà con cui cerchiamo la soluzione, basterà arrestarsi quando l'ampiezza dell'intervallo sarà minore di questo valore. Infatti per poter avere $x_k \approx \overline{x}$ deve verificarsi

$$\frac{1}{2^k}L_0 < \varepsilon \quad \Leftrightarrow \quad 2^... ... \Leftrightarrow \quad k \ln 2 \geq \ln L_0 - \ln \varepsilon$$

$$k \geq \left\lceil \frac{\ln L_0 - \ln \varepsilon}{\ln 2} \right\rceil = \nu$$

e questo $\nu$ indica il numero massimo di iterazioni necessarie per ottenere una approssimazione di $\overline{x}$ con la precisione $\varepsilon$ richiesta. Al diminuire di $\varepsilon$, cioè più si avvicina allo zero, e più il metodo di bisezione diventa inefficiente.

Un altro criterio di arresto potrebbe basarsi sul valore che assume la funzione in esame nel punto di approssimazione corrente. Potremmo difatti decidere di arrestare il nostro algoritmo quando $\vert f(x_k)\vert \leq tolf$ ossia quando la funzione è inferiore ad una certa tolleranza. Sviluppando in serie di Taylor la funzione in un intorno di $\overline{x}$ ed arrestandoci al primo ordine si ottiene:

$$f(x_k)=f(\overline{x})+f'(\overline{x})(x_k-\overline{x})$$

e sapendo che per definizione $f(\overline{x})=0$ possiamo riscrivere tutto come:

$$f(x_k)=f'(\overline{x})(x_k-\overline{x}) \longrightarrow (x_k-\overline{x})=\frac{f(x_k)}{f'(\overline{x})}$$

portandoci ai valori assoluti

$$\vert x_k-\overline{x}\vert=\left\vert \frac{f(x_k)}{f'(\ove... ...erline{x})\vert} \leq \frac{tolf}{\vert f'(\overline{x})\vert}$$

Naturalmente vorremmo che, arrestandoci perché il valore della funzione è inferiore alla tolleranza, sia verificato anche che $\vert x_k - \overline{x}\vert \leq \varepsilon$ quindi imponendo:

$$\frac{tolf}{\vert f'(\overline{x})\vert} \approx \varepsilon ... ...ow \quad tolf \approx \varepsilon \vert f'(\overline{x})\vert.$$

La derivata, ovviamente, non la abbiamo a disposizione ed il suo calcolo richiederebbe uno sforzo computazionale superiore allo stesso metodo di bisezione, quello che si può fare è approssimare la derivata con il rapporto incrementale dei punti estremi dell'intervallo attualmente preso in considerazione, alla fine si ottiene:

$$f'(\overline{x}) \approx \frac{f(b_k) - f(a_k)}{b_k - a_k} \q... ...silon \left\vert \frac{f(b_k) - f(a_k)}{b_k - a_k} \right\vert$$

Questo ultimo metodo di arresto è generale e non è stato utilizzato niente che riguardi il metodo di bisezione, possiamo perciò utilizzarlo anche con i metodi che vedremo in seguito avendo l'accortezza di utilizzare la derivata od una sua approssimazione a seconda che sia disponibile oppure no.