Biseksjonsmetode – Hva er, algoritme og eksempel

Hva er biseksjonsmetode?

Biseksjonsmetode er en av de grunnleggende numeriske løsningene for å finne roten til en polynomligning. Den har intervallet som roten til ligningen ligger i, og deler dem inn i halvdeler i hver iterasjon til den finner roten. Dermed kalles halveringsmetoden også bracketing-metoden.

Siden arbeidsmekanismen er lik den binære søkealgoritmen, er biseksjonsmetoden også kjent som binær søkemetode, halveringsmetode eller dikotomimetoden. Den er først og fremst basert på teoremet for mellomverdi.

Finne røtter til ligninger

I dette eksemplet tar vi bare for oss ligninger med én uavhengig variabel. Den kan enten være lineær eller ikke-lineær. Lineære ligninger brukes til å representere grafen til en rett linje, mens ikke-lineære ligninger brukes til å representere kurver.

Roten til en ligning betyr verdien av den uavhengige variabelen som tilfredsstiller ligningen. For eksempel: roten av en ligning f(x)= 4-x² = 0 er 2 fordi f(2) = 4-2² = 0.

La oss betrakte f(x) som en reell kontinuerlig funksjon. I følge mellomverditeoremet har ligningen f(x)=0 minst én rot mellom a og b hvis f(a)f(b) < 0. Funksjonen f(x) har en rot, "c," mellom a og b.

Grafisk fremstilling av halveringsmetode

Følgende graf representerer arbeidsmekanismen til halveringsmetoden. Fra grafen kan vi se at roten av ligningen er rødmerket.

Til å begynne med:

Vi tok først to innledende gjetninger, en₁ og b_1, for hvilken f(a₁)f(b₁) < 0. I følge mellomverditeoremet skal roten ligge i [a₁, b₁].
Vi kan finne midtpunktet til a₁ og b_1,som er b₂. Dermed er startintervallet nå redusert til [a₁, b₂] fordi f(a₁)f(b₂) < 0.
På samme måte reduseres intervallet inntil den omtrentlige løsningen er funnet.

Biseksjonsmetodealgoritme

Trinnene for å bruke halveringsmetodealgoritmen for å finne roten til ligningen f(x)=0 er som følger

Trinn 1) Velg innledende gjetninger a, b og toleransegrad e

Trinn 2) Hvis f(a)f(b) >=0, så ligger ikke roten i dette intervallet. Dermed blir det ingen løsning.

Trinn 3) Finn midtpunktet, c = (a+b)/2

(i) Hvis funksjonsverdien til midtpunktet f(c) = 0, så er c roten. Gå til trinn 5.
(ii) Hvis f(a)f(c) < 0 ligger roten mellom a og c. Sett deretter a = a, b = c.
(iii) Ellers sett a = c, b = b.

Trinn 4) Hvis den absolutte feilen er høyere enn toleransegraden eller (ba) > e, gå til trinn 3.

Trinn 5) Vis c som den omtrentlige roten.

La oss se et eksempel på algoritmen for halveringsmetoden.
Vi må finne roten til følgende kontinuerlige funksjon ved å bruke formelen for halveringsmetoden.

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

Eksempel på halveringsmetode

Trinn 1) La oss anta,

         a = -10,
         b = 10, og
         e = 1 % eller 0.01

Trinn 2) Nå skal vi sjekke om f(a)f(b) >= 0 eller ikke.

         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

Derfor ligger roten til funksjonen ovenfor i dette intervallet [-10, 10].

Trinn 3) Da vil midtpunktet c beregnes først.

Nå må følgende forhold kontrolleres:

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

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

Vilkåret er oppfylt. For neste iterasjon vil verdiene være,

a = a = -10
b = c = 0

Trinn 4) Ettersom (ba) = (0-(-10)) = 10>0.05, vil prosessen gjentas. De neste iterasjonene er vist i tabellen.

køyring	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

Trinn 5) I den 11. iterasjonen vil trinn 4-betingelsen være falsk. Dermed er roten til denne ligningen -1.00586.

Biseksjonsmetode logisk diagram

Pseudo-kode

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

Eksempel på halveringsmetode i C/C++

Inngang:

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

Utgang:

The root is :-1.00586

Eksempel på halveringsmetode i Python