Metoda bisekcije – što je, algoritam i primjer

Što je metoda bisekcije?

Metoda bisekcije jedno je od osnovnih numeričkih rješenja za pronalaženje korijena polinomske jednadžbe. Stavlja u zagrade interval u kojem se nalazi korijen jednadžbe i dijeli ih na polovice u svakoj iteraciji dok ne pronađe korijen. Stoga se metoda bisekcije naziva i metoda stavljanja u zagrade.

Međutim, budući da je radni mehanizam sličan algoritmu binarnog pretraživanja, metoda bisekcije također je poznata kao metoda binarnog pretraživanja, metoda prepolovljenja ili metoda dihotomije. Prvenstveno se temelji na teoremu srednje vrijednosti.

Pronalaženje korijena jednadžbi

U ovom primjeru razmatramo samo jednadžbe s jednom nezavisnom varijablom. Može biti linearan ili nelinearan. Linearne jednadžbe koriste se za predstavljanje grafikona ravne linije, dok se nelinearne jednadžbe koriste za predstavljanje krivulja.

Korijen jednadžbe znači vrijednost nezavisne varijable koja zadovoljava jednadžbu. Na primjer: korijen jednadžbe f(x)= 4-x² = 0 je 2 jer je f(2) = 4-2² = 0.

Promatrajmo f(x) kao realnu kontinuiranu funkciju. Prema teoremu srednje vrijednosti, jednadžba f(x)=0 ima barem jedan korijen između a i b ako je f(a)f(b) < 0. Funkcija f(x) ima korijen, "c," između a i b.

Grafički prikaz metode bisekcije

Sljedeći grafikon predstavlja radni mehanizam metode bisekcije. Iz grafikona vidimo da je korijen jednadžbe označen crvenom bojom.

Početi sa:

Prvo smo uzeli dvije početne pretpostavke, a₁ i b_1, za koje je f(a₁)f(b₁) < 0. Prema teoremu o srednjoj vrijednosti, korijen bi trebao ležati u [a₁, b₁].
Možemo pronaći središte a₁ i b_1,koji je b₂. Dakle, početni interval sada je smanjen na [a₁, b₂] jer f(a₁)f(b₂) < 0.
Na isti način interval se smanjuje dok se ne pronađe približno rješenje.

Algoritam metode bisekcije

Koraci za primjenu algoritma metode bisekcije za pronalaženje korijena jednadžbe f(x)=0 su sljedeći

Korak 1) Odaberite početne pretpostavke a, b i stopu tolerancije e

Korak 2) Ako je f(a)f(b) >=0, tada korijen ne leži u ovom intervalu. Dakle, rješenja neće biti.

Korak 3) Nađite središte, c = (a+b)/2

(i) Ako je vrijednost funkcije sredine f(c) = 0, tada je c korijen. Idite na korak 5.
(ii) Ako je f(a)f(c) < 0, korijen se nalazi između a i c. Zatim postavite a = a, b = c.
(iii) Inače postavite a = c, b = b.

Korak 4) Ako je apsolutna pogreška veća od stope tolerancije ili (ba) > e, prijeđite na korak 3.

Korak 5) Prikaži c kao približan korijen.

Pogledajmo primjer algoritma metode bisekcije.
Moramo pronaći korijen sljedeće kontinuirane funkcije pomoću formule metode bisekcije.

f (x) = x³ - x² + 2

Primjer metode bisekcije

Korak 1) Pretpostavimo,

         a = -10,
         b = 10, i
         e = 1% ili 0.01

Korak 2) Sada ćemo provjeriti je li f(a)f(b) >= 0 ili ne.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Dakle, korijen gornje funkcije leži u ovom intervalu [-10, 10].

Korak 3) Tada će se prvo izračunati središnja točka c.

Sada je potrebno provjeriti sljedeće uvjete:

(i) je li f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) ako je f(a)f(c) < 0:
f(c)f(a) = 2*(-1098) < 0

Uvjet je ispunjen. Za sljedeću iteraciju, vrijednosti će biti,

a = a = -10
b = c = 0

Korak 4) Kako je (ba) = (0-(-10)) = 10>0.05, proces će se ponoviti. Sljedeće iteracije prikazane su u tablici.

ponavljanje	a	b	c	ba	f(c)
1	-10	0	0	10	2
2	-5	0	-5	5	-148
3	-2.5	0	-2.5	2.5	-19.875
4	-1.25	0	-1.25	1.25	-1.52562
5	-1.25	-0.625	-0.625	0.625	1.36523
6	-1.25	-0.9375	-0.9375	0.3125	0.297119
7	-1.09375	-0.9375	-1.09375	0.15625	-0.50473
8	-1.01562	-0.9375	-1.01562	0.078125	-0.0791054
9	-1.01562	-0.976562	-0.976562	0.0390625	0.115003
10	-1.01562	-0.996094	-0.996094	0.0195312	0.0194703
11	-1.00586	-0.996094	-1.00586	0.00976562	-0.0294344

Korak 5) U 11. ponavljanju, uvjet koraka 4 bit će lažan. Dakle, korijen ove jednadžbe je -1.00586.

Logički dijagram metode bisekcije

Pseudo-kod

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

Primjer metode bisekcije u C/C++

Ulazni:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

Izlaz:

The root is :-1.00586

Primjer metode bisekcije u Python