Metodo di bisezione

Analisi numerica > Metodo di bisezione

lezione Metodo di bisezione
	Tipo: lezione
	Materia: Analisi numerica

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'(x)>0\;\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 \mathbb {R}$ una funzione continua tale che $f(a)\cdot f(b)<0.$

Allora esiste almeno un punto $x$ nell'intervallo aperto $\displaystyle (a,b)$ tale che $\displaystyle 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 $\epsilon$

$x_{k}={\frac {a+b}{2}},\qquad k\geq 1$ ;
se $\displaystyle e_{k}=|b-x_{k}|\leq \epsilon :\qquad \qquad \qquad$ esci;
se $\displaystyle f(x_{k})=0:\qquad \qquad$ esci;
altrimenti se $\displaystyle f(a)f(x_{k})>0:$ $\displaystyle a=x_{k}$ ;

altrimenti $:\displaystyle b=x_{k}$ ;
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 ${\mathcal {I}}_{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\geq 0$ . Ovviamente ${\mathcal {I}}_{0}=[a,b]$ . Indichiamo con $|{\mathcal {I}}_{k}|=meas({\mathcal {I}}_{k})$ la lunghezza dell'intervallo ${\mathcal {I}}_{k}$ . In particolare si ha

|{\mathcal {I}}_{k}|={\frac {|{\mathcal {I}}_{k-1}|}{2}}={\frac {|{\mathcal {I}}_{k-2}|}{2^{2}}}=...={\frac {|{\mathcal {I}}_{0}|}{2^{k}}}={\frac {b-a}{2^{k}}}.

Si noti che $\alpha \in {\mathcal {I}}_{k}\;,\forall k\geq 0$ , e quindi

e_{k}\leq |{\mathcal {I}}_{k}|

.

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

\displaystyle \lim _{k\to \infty }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\geq 0$ invece che per $k\geq 1$ .

Esempio

Si consideri la funzione $\displaystyle f(x)=\cos x$ in $\displaystyle [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 $\displaystyle \alpha _{2}$ . Nella pratica, tuttavia, il metodo converge o $\displaystyle \alpha _{1}$ o a $\displaystyle \alpha _{3}$ . Infatti, dato che le operazioni vengono fatte in aritmetica finita, $x_{1}\neq {\frac {3\pi }{2}}$ e a seconda delle approssimazioni del calcolatore $\displaystyle f(x_{1})$ potrà essere positivo o negativo, ma mai nullo. Così l'algoritmo di bisezione in questo caso escluderà automaticamente la radice $\displaystyle \alpha _{2}$ alla prima iterazione, in quanto l'errore sarà ancora molto grande ( $\displaystyle e_{1}=\alpha _{2}$ ).

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