|
==Algoritmo==
Data l'equazione <math>\,f(x)=0</math> definita e continua in un intervallo <math>\,[a,b]</math>, tale che <math>\,f(a)\cdot f(b)<0</math>, è allora possibile calcolarne un'approssimazione in <math>\,[a,b]</math> (vedi [[Teorema di Bolzano|teorema degli zeri]]).
Si procede dividendo l'intervallo in due parti eguali e calcolando il valore della funzione nel punto medio di ascissa <math>\,\frac{a+b}{2}.</math>. Se risulta <math>f\left(\frac{a+b}{2}\right)=0</math> allora <math>\frac{a+b}{2}</math> è la radice cercata; altrimenti tra i due intervalli <math>\left[a,\frac{a+b}{2}\right]</math> e <math>\left[\frac{a+b}{2},b\right]</math> si sceglie quello ai cui estremi la funzione assume valori di segno opposto. Si ripete per questo intervallo il procedimento di dimezzamento. e, cosìCosì continuando si ottiene, potenzialmente, una successione di intervalli ''incapsulati'', cioè ognuno incluso nel precedente,<math>\,[a_1,b_1],[a_2,b_2],...\ldots,[a_n,b_n], ...\ldots,</math>; questi''incapsulati'', cioè ognuno incluso nel precedente. Questi intervalli hanno come ampiezze <math>b_n-a_n=\frac{b-a}{2^n}</math> per <math>\,n=1, 2, 3, ...\ldots</math>.
I valori <math>a_i</math> sono valori approssimati per difetto della radice, i valori di <math>b_i</math> sono invece i valori della radice approssimati per eccesso. Gli <math>a_ia_n</math> formano una successione crescente limitata ed i <math>b_ib_n</math> formano una successione decrescente limitata. Le due successioni ammettono lo stesso limite che è la radice dell'equazione esaminata.
Come approssimazione della radice <math>\,\alpha</math> si considera il punto medio degli intervalli, cioè <math>c_n = \frac{a_n+b_n}{2},</math> per <math>n=1,2,\ldots</math>
L'algoritmo viene arrestato quando <math> \,f( c_{i}c_n)</math> è abbastanza vicino a <math>0 </math> e/o quando l'ampiezza dell'intervallo <math> \,[ a_{i}a_n, b_{i}b_n]</math> è inferiore ad una certa tolleranza <math> \,\varepsilon</math>. Dunque come stima di <math> \,\alpha</math> alla fine avremo un certo <math> \,c_{n}c_n.</math> ; siSi provadimostra facilmente che per l'errore commesso <math>e_n</math> vale la seguente relazione: ▼<math>c_{i} = \frac{a_{i}+b_{i}}{2}\;</math> per <math>i=1,2,...</math>
:<math>| e_{n}e_n|=| c_{n}c_n - \alpha| \leq \frac{b-a}{2^{n+1}} .</math> .▼
▲L'algoritmo viene arrestato quando<math>\,f(c_{i})</math> è abbastanza vicino a 0 e/o quando l'ampiezza dell'intervallo<math>\,[a_{i},b_{i}]</math> è inferiore ad una certa tolleranza <math>\,\varepsilon</math>. Dunque come stima di <math>\,\alpha</math> alla fine avremo un certo<math>\,c_{n}</math>; si prova facilmente che per l'errore commesso vale:
▲<math>|e_{n}|=|c_{n} - \alpha| \leq \frac{b-a}{2^{n+1}}</math>.
Un importante corollario è che
:<math>\lim_{n \to \infty}|e_{n}e_n| = 0,</math>
quindi la convergenza del metodo è ''globale''.
Se richiediamo <math>|e_{n}e_n| \leq \varepsilon</math> otteniamo la seguente condizione per <math>n</math>:
:<math>n \geq log_{2}\frac{b-a}{\varepsilon} -1.</math>.
Essendo <math>log_{2}10 \approx 3.,32</math> servono in media più di 3tre 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 <math>|e_{in+1}| < |e_{i}e_n|</math> \;per \forallogni i<math>n=1,2,\ldots</math>. Non si può definire quindi un vero e proprio ''ordine di convergenza'' per questo metodo.
== Voci correlate ==
|
