Puolittamismenetelmä – mikä on, algoritmi ja esimerkki

Mikä on puolitusmenetelmä?

Bisection Method on yksi numeerisista perusratkaisuista polynomiyhtälön juuren löytämiseksi. Se sulkee välin, jossa yhtälön juuri sijaitsee, ja jakaa ne puoliksi kussakin iteraatiossa, kunnes se löytää juuren. Siten puolittamismenetelmää kutsutaan myös haarukointimenetelmäksi.

Koska toimintamekanismi on kuitenkin samanlainen kuin binäärihakualgoritmi, puolittamismenetelmä tunnetaan myös binäärihakumenetelmänä, puolitusmenetelmänä tai dikotomiamenetelmänä. Se perustuu ensisijaisesti väliarvolauseeseen.

Yhtälöiden juurten löytäminen

Tässä esimerkissä tarkastelemme vain yhtälöitä, joissa on yksi riippumaton muuttuja. Se voi olla joko lineaarinen tai epälineaarinen. Lineaarisia yhtälöitä käytetään esittämään suoran viivan kuvaajaa, kun taas epälineaarisia yhtälöitä käytetään kuvaamaan käyriä.

Yhtälön juuri tarkoittaa riippumattoman muuttujan arvoa, joka täyttää yhtälön. Esimerkiksi: yhtälön juuri f(x)= 4-x² = 0 on 2, koska f(2) = 4-2² = 0.

Tarkastellaan f(x):tä todellisena jatkuvana funktiona. Väliarvolauseen mukaan yhtälöllä f(x)=0 on vähintään yksi juuri a:n ja b:n välillä, jos f(a)f(b) < 0. Funktiolla f(x) on juuri, "c", a:n ja b:n välillä.

Bisection-menetelmän graafinen esitys

Seuraava kaavio esittää puolittamismenetelmän toimintamekanismia. Kaaviosta näemme, että yhtälön juuri on merkitty punaisella.

Aivan aluksi:

Teimme ensin kaksi alustavaa arvausta, a₁ ja b_1, jolle f(a₁)f(b₁) < 0. Väliarvolauseen mukaan juuren tulee olla [a₁, b₁].
Voimme löytää a:n keskipisteen₁ ja b_1,joka on b₂. Näin ollen aloitusväli on nyt pienennetty [a₁, b₂] koska f(a₁)f(b₂) <0.
Samalla tavalla väliä pienennetään, kunnes likimääräinen ratkaisu löytyy.

Bisection Method Algorithm

Vaiheet puolittamismenetelmäalgoritmin soveltamiseksi yhtälön f(x)=0 juuren löytämiseksi ovat seuraavat

Vaihe 1) Valitse alustavat arvaukset a, b ja toleranssisuhde e

Vaihe 2) Jos f(a)f(b) >=0, niin juuri ei ole tässä välissä. Siten ratkaisua ei tule.

Vaihe 3) Etsi keskipiste, c = (a+b)/2

(i) Jos keskipisteen f(c) funktion arvo on 0, niin c on juuri. Siirry vaiheeseen 5.
(ii) Jos f(a)f(c) < 0, juuri on a:n ja c:n välillä. Aseta sitten a = a, b = c.
(iii) Muuten aseta a = c, b = b.

Vaihe 4) Jos absoluuttinen virhe on suurempi kuin toleranssiaste tai (ba) > e, siirry vaiheeseen 3.

Vaihe 5) Näytä c likimääräisenä juurena.

Katsotaanpa esimerkki puolittamismenetelmän algoritmista.
Meidän on löydettävä seuraavan jatkuvan funktion juuri käyttämällä puolittamismenetelmän kaavaa.

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

Esimerkki puolittamisesta

Vaihe 1) Oletetaan,

         a = -10,
         b = 10 ja
         e = 1 % tai 0.01

Vaihe 2) Nyt tarkistetaan onko f(a)f(b) >= 0 vai ei.

         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

Yllä olevan funktion juuri on siis tässä välissä [-10, 10].

Vaihe 3) Sitten keskipiste c lasketaan ensin.

Seuraavat ehdot on nyt tarkistettava:

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

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

Ehto täyttyy. Seuraavaa iteraatiota varten arvot ovat

a = a = -10
b = c = 0

Vaihe 4) Koska (ba) = (0-(-10)) = 10>0.05, prosessi toistetaan. Seuraavat iteraatiot näkyvät taulukossa.

iteraatio	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

Vaihe 5) 11. iteraatiossa vaiheen 4 ehto on epätosi. Siten tämän yhtälön juuri on -1.00586.

Puolittamismenetelmän looginen kaavio

Pseudokoodi

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

Esimerkki puolittamisesta C/C++

input:

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

lähtö:

The root is :-1.00586

Esimerkki puolittamisesta menetelmässä Python