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=\frac{a+b}{2}.$ 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

$$x_{k+2} = \frac{1}{2}\,(x_{k+1} + x_{l}),$$

gdje je $l$ najveći od brojeva $0,1,2,\ldots,k$ takav da je $f(x_l)\,f(x_{k+1})\leqslant{} 0,$ s tim da je

$$x_0 = a,\hspace{1cm}x_1 = b.$$

Ovaj algoritam omogućava sljedeći program u programskom paketu Mathematica.

Mathematica program 1   (Metoda polovljenja)

 
f[t_]=; (* funkcija *) 
a=; 
b=;     (* pocetni interval *) 
x=(a+b)/2.; 
n=0; 
Print[{n,a,x,b}]; 
        While[ 
        N[f[x]]!=0., 
                If[ 
                f[b]f[x]<0, 
                a=x;x=(x+b)/2, 
                b=x;x=(a+x)/2 
                ]; 
        n=n+1; 
        If[n>100,Break[]  (* prekid petlje nakon 100 koraka *) 
        ]; 
Print[{n,a,x,b}]]

Metoda uvijek konvergira, ali vrlo sporo.

$$x_0 = a,\quad x_1 = b, \quad x_2 = \frac{a+b}{2},$$

pa je

$$\vert x_2 - s\vert \leqslant{} \frac{1}{2}\,(b-a),\quad \vert x_3 - s\vert \leqslant{} \frac{1}{2^2}\,(b-a),\quad \ldots{}\ .$$

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

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

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.

Primjer 3.1   Riješiti metodom polovljenja jednadžbu

$$x^3 - x + 1 = 0.$$

Rješenje. Računanjem vrijednosti polinoma $f(x)=x^3 - x + 1$ na skupu cijelih brojeva, dobivamo da je $f(-2)=-5,$ a $f(-1)=1.$ Tako na segmentu $[-2,-1]$ postoji bar jedno rješenje. Ako na ovaj problem primijenimo gornji program, dobivamo sljedeću tablicu.

$k$	$x_l$	$x_{k+2}$	$x_{k+1}$
0	$-2$	$-1.5$	$-1$
$1$	$-1.5$	$-1.25$	$-1$
$2$	$-1.5$	$-1.375$	$-1.25$
$3$	$-1.375$	$-1.3125$	$-1.25$
$4$	$-1.375$	$-1.34375$	$-1.3125$
$5$	$-1.34375$	$-1.32813$	$-1.3125$
$6$	$-1.32813$	$-1.32031$	$-1.3125$
$7$	$-1.32813$	$-1.32422$	$-1.32031$
$8$	$-1.32813$	$-1.32617$	$-1.32422$
$9$	$-1.32617$	$-1.3252$	$-1.32422$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$50$	$-1.32472$	$-1.32472$	$-1.32472$

Računalo je tek u pedesetoj aproksimaciji došlo do granica svoje točnosti. Točnost ispisanih rezultata (pet znamanaka) se postiže u devetnajstoj aproksimaciji, što se moglo unaprijed izračunati. Budući da je $b-a=1,$ greška $k$-te aproksimacije nije veća od $\frac{1}{2^{k-1}},$ pa zbog

$$\frac{1}{2^{17}} \approx 7.62939\times 10^{-6}, \qquad \frac{1}{2^{18}} \approx 3.8147\times 10^{-6},$$

rješenje na pet decimala točno se postiže u devetnajstoj aproksimaciji.

Zadatak iz primjera 3.1 se može doduše egzaktno riješiti pomoću Cardanovih formula. Ipak te formule nisu tako jednostavne kao formula za rješenje kvadratne jednadžbe, pa se algebarske jednadžbe trećeg stupnja često rješavaju približnim metodama. U sljedećem primjeru se rješava jednadžba koju ne možemo egzaktno riješiti.

Primjer 3.2   Naći najmanje pozitivno rješenje jednadžbe (v. 2.20)

$${\rm tg}\,\lambda = \frac{1}{\lambda}$$

metodom polovljenja.

Rješenje. Iz slike 2.7 se vidi da se traženo rješenje nalazi u intervalu $\langle{}0,\frac{\pi}{2}\rangle{}.$ Neka je

$$f(\lambda{}) = {\rm tg}\,\lambda - \frac{1}{\lambda}.$$

Imamo

$$f\left(\frac{\pi}{3}\right) = {\sqrt{3}} - {\frac{3}{\pi }} > 0, \quad f\left(\frac{\pi}{4}\right) = {\frac{ \pi- 4}{\pi }} < 0.$$

Prema tome, za početni segment možemo uzeti segment $[\frac{\pi}{4},\frac{\pi}{3}].$

Izračunajmo sada koju aproksimaciju treba naći da bi se dobila točnost na četiri decimale. Iz formule (3.3) slijedi da treba naći $k$ tako da bude

$$\frac{1}{2^{k-1}}\,(b-a) = \frac{1}{2^{k-1}}\,\frac{\pi}{12} \leqslant \frac{1}{2^{k-1}}\,\frac{1}{3} < 0.5\times 10^{-4}.$$

Odatle slijedi $k>13.7027,$ pa treba izračunati četrnaestu aproksimaciju.

$k$	$x_l$	$x_{k+2}$	$x_{k+1}$
0	$0.785398$	$0.916298$	$1.0472$
$1$	$0.785398$	$0.850848$	$0.916298$
$2$	$0.850848$	$0.883573$	$0.916298$
$3$	$0.850848$	$0.86721$	$0.883573$
$4$	$0.850848$	$0.859029$	$0.86721$
$5$	$0.859029$	$0.86312$	$0.86721$
$6$	$0.859029$	$0.861075$	$0.86312$
$7$	$0.859029$	$0.860052$	$0.861075$
$8$	$0.860052$	$0.860563$	$0.861075$
$9$	$0.860052$	$0.860308$	$0.860563$
$10$	$0.860308$	$0.860435$	$0.860563$
$11$	$0.860308$	$0.860371$	$0.860435$
$12$	$0.860308$	$0.86034$	$0.860371$
$13$	$0.860308$	$0.860324$	$0.86034$
$14$	$0.860324$	$0.860332$	$0.86034$

Dakle rješenje, na četiri decimale točno, je

$$\lambda{} = 0.8603.$$