next up previous contents
Next: Metoda iteracije Up: Rješavanje jednadžbi Previous: Rješavanje jednadžbi   Contents


Metoda polovljenja

Metoda polovljenja se sastoji u tome da se segment $ [a,b],$ na kojem je ispunjen uvjet $ f(a)f(b)<0,$ raspolovi, tj. nađe polovište $ c.$ Ako je $ f(c)=0,$ onda je $ s=c.$ U protivnom se ponovi operacija na onom od segmenata $ [a,c]$ ili $ [c,b]$ na kojem je ispunjen uvjet (3.2), itd. Tako imamo sljedeći algoritam.

Algoritam 1   Za $ k=0,1,2,\ldots{}$ računamo

$\displaystyle x_{k+1} = \frac{1}{2}\,(a_{k+1} + b_{k+1}),$

gdje je

$\displaystyle a_{k+1} = a_k,$   i$\displaystyle \hspace{1cm}b_{k+1} = x_k,$    ako je $\displaystyle f(a_k)\,f(x_k) \leqslant{} 0$

$\displaystyle a_{k+1} = x_k,$   i$\displaystyle \hspace{1cm}b_{k+1} = b_k,$    ako je $\displaystyle f(b_k)\,f(x_k) \leqslant{} 0,$

s tim da je

$\displaystyle a_0 = a,\hspace{1cm}b_0 = b.$

slika

Metoda uvijek konvergira, ali vrlo sporo. Očito je

$\displaystyle \vert x_0 - s\vert \leqslant{} \frac{1}{2}\,(b-a),\; \vert x_1 - s\vert \leqslant{}
\frac{1}{2^2}\,(b-a),\; \ldots{}$

Tako za $ k$-tu aproksimaciju imamo ocjenu greške

$\displaystyle \left\vert x_k - s\right\vert \leqslant{} \frac{1}{2^{k+1}}\,(b-a).$

Ova ocjena se zove apriorna, jer se može izračunati prije nego smo postupak iteracije uopće započeli. Naravno, ova ocjena nam ne kaže kolika je greška, već samo to da greška nije veća od tog broja.



Salih Suljagic
1999-01-27