Poolitamise meetod – mis on, algoritm ja näide

Mis on poolitamise meetod?

Poolitusmeetod on üks põhilisi arvulisi lahendusi polünoomvõrrandi juure leidmiseks. See sulgub intervalli, milles asub võrrandi juur, ja jagab need igas iteratsioonis pooleks, kuni see leiab juure. Seega nimetatakse poolitamise meetodit ka sulgumismeetodiks.

Kuna aga töömehhanism on sarnane binaarse otsingu algoritmiga, tuntakse poolitamise meetodit ka kui binaarset otsingumeetodit, poolitamise meetodit või dihhotoomia meetodit. See põhineb peamiselt vaheväärtuste teoreemil.

Võrrandite juurte leidmine

Selles näites käsitleme ainult ühe sõltumatu muutujaga võrrandeid. See võib olla kas lineaarne või mittelineaarne. Sirge graafiku esitamiseks kasutatakse lineaarseid võrrandeid, kõverate esitamiseks aga mittelineaarseid võrrandeid.

Võrrandi juur tähendab võrrandit rahuldava sõltumatu muutuja väärtust. Näiteks: võrrandi juur f(x)= 4-x² = 0 on 2, sest f(2) = 4-2² = 0.

Vaatleme f(x) reaalse pideva funktsioonina. Vaheväärtuste teoreemi kohaselt on võrrandil f(x)=0 vähemalt üks juur a ja b vahel, kui f(a)f(b) < 0. Funktsioonil f(x) on juur "c," a ja b vahel.

Poolitamise meetodi graafiline esitus

Järgmine graafik kujutab poolitamise meetodi töömehhanismi. Graafikult näeme, et võrrandi juur on punaselt märgitud.

Alustuseks:

• Esmalt tegime kaks esialgset oletust, a₁ ja b_1, mille jaoks f(a₁)f(b₁) < 0. Vaheväärtuste teoreemi järgi peaks juur asuma [a₁b₁].
• Leiame a keskpunkti₁ ja b_1, mis on b₂. Seega on esialgne intervall nüüd vähendatud [a₁b₂], sest f(a₁)f(b₂) < 0.
• Samal viisil vähendatakse intervalli kuni ligikaudse lahenduse leidmiseni.

Poolitamise meetodi algoritm

Poolitamise meetodi algoritmi rakendamise sammud võrrandi f(x)=0 juure leidmiseks on järgmised

Step 1) Valige esialgsed oletused a, b ja tolerantsimäär e

Step 2) Kui f(a)f(b) >=0, siis juur ei asu selles intervallis. Seega lahendust ei tule.

Step 3) Leidke keskpunkt, c = (a+b)/2

(i) Kui keskpunkti f(c) funktsiooni väärtus on 0, siis c on juur. Minge 5. sammu juurde.
(ii) Kui f(a)f(c) < 0, asub juur a ja c vahel. Seejärel seadke a = a, b = c.
(iii) Muidu seadke a = c, b = b.

Step 4) Kui absoluutne viga on suurem kui tolerantsimäär või (ba) > e, minge 3. sammu juurde.

Step 5) Kuva c ligikaudse juurena.

Vaatame poolitamise meetodi algoritmi näidet.
Peame leidma järgmise pideva funktsiooni juure, kasutades poolitamise meetodi valemit.

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

Poolitamise meetodi näide

Step 1) Oletame,

         a = -10,
         b = 10 ja
         e = 1% või 0.01

Step 2) Nüüd kontrollime, kas f(a)f(b) >= 0 või mitte.

         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

Seega asub ülaltoodud funktsiooni juur selles intervallis [-10, 10].

Step 3) Seejärel arvutatakse kõigepealt keskpunkt c.

Nüüd tuleb kontrollida järgmisi tingimusi:

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

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

Tingimus on täidetud. Järgmise iteratsiooni jaoks on väärtused

         a = a = -10
         b = c = 0

Step 4) Kui (ba) = (0-(-10)) = 10>0.05, korratakse protsessi. Järgmised iteratsioonid on näidatud tabelis.

Kordus	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

Step 5) 11. iteratsioonis on 4. sammu tingimus vale. Seega on selle võrrandi juur -1.00586.

Poolitamise meetodi loogiline diagramm

Pseudokood

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

Poolitamise meetodi näide keeles C/C++

sisend:

#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;
}

Väljund:

The root is :-1.00586

Poolitamise meetodi näide in Python

sisend:

def value(x):
	return x*x*x - x*x + 2
def bisection_method(a,b):
	if (value(a) * value(b) >= 0):
		return
	c = a
	while ((b-a) >= 0.01):
		c = (a+b)/2
		if (value(c) == 0.0):
			break
		if (value(c)*value(a) < 0):
			b = c
		else:
			a = c			
	print("The root is : ","%.4f"%c)	
a =-10
b = 10
bisection_method(a, b)

Väljund:

The root is :  -1.0059

Poolitamise meetodi eelised ja piirangud

Siin on poolitamise meetodi plussid ja miinused:

Plusse	Miinused
Lihtne ja lihtne juurutamise meetod, mida rakendada.	Konvergents on aeglane, kuna see põhineb lihtsalt intervalli poole võrrandamisel.
Kuna see sulgudes on juur, on see alati konvergentne.	Kui üks esialgsetest oletustest on juure lähedal, võtab juureni jõudmine rohkem iteratsioone.
Veamäära saab kontrollida, suurendades või vähendades iteratsioonide arvu.