Bisektionsmetod – vad är, algoritm och exempel

Vad är bisektionsmetod?

Bisektionsmetoden är en av de grundläggande numeriska lösningarna för att hitta roten till en polynomekvation. Den placerar inom intervallet som ekvationens rot ligger inom parentes och delar upp dem i halvor i varje iteration tills den hittar roten. Sålunda kallas bisektionsmetoden även bracketingmetoden.

Men eftersom arbetsmekanismen liknar den binära sökalgoritmen, är bisektionsmetoden även känd som binär sökmetod, halveringsmetod eller dikotomimetoden. Den bygger i första hand på satsen mellanvärde.

Hitta rötter till ekvationer

I det här exemplet betraktar vi bara ekvationer med en oberoende variabel. Det kan vara antingen linjärt eller olinjärt. Linjära ekvationer används för att representera grafen för en rät linje, medan icke-linjära ekvationer används för att representera kurvor.

Roten till en ekvation betyder värdet på den oberoende variabeln som uppfyller ekvationen. Till exempel: roten till en ekvation f(x)= 4-x² = 0 är 2 eftersom f(2) = 4-2² = 0.

Låt oss betrakta f(x) som en reell kontinuerlig funktion. Enligt mellanvärdessatsen har ekvationen f(x)=0 minst en rot mellan a och b om f(a)f(b) < 0. Funktionen f(x) har en rot, "c", mellan a och b.

Grafisk representation av bisektionsmetoden

Följande graf representerar arbetsmekanismen för halveringsmetoden. Från grafen kan vi se att roten av ekvationen är rödmarkerad.

Till att börja med:

Vi tog först två inledande gissningar, en₁ och b_1, för vilken f(a₁)f(b₁) < 0. Enligt mellanvärdessatsen ska roten ligga i [a₁, b₁].
Vi kan hitta mittpunkten av a₁ och b_1,vilket är b₂. Således är det initiala intervallet nu reducerat till [a₁, b₂] eftersom f(a₁)f(b₂) < 0.
På samma sätt reduceras intervallet tills den ungefärliga lösningen hittas.

Bisektionsmetodalgoritm

Stegen för att tillämpa tvåsektionsmetodens algoritm för att hitta roten till ekvationen f(x)=0 är som följer

Steg 1) Välj inledande gissningar a, b och toleransgrad e

Steg 2) Om f(a)f(b) >=0, så ligger inte roten i detta intervall. Det blir alltså ingen lösning.

Steg 3) Hitta mittpunkten, c = (a+b)/2

(i) Om funktionsvärdet för mittpunkten f(c) = 0, så är c roten. Gå till steg 5.
(ii) Om f(a)f(c) < 0 ligger roten mellan a och c. Ange sedan a = a, b = c.
(iii) Annat set a = c, b = b.

Steg 4) Om det absoluta felet är högre än toleransgraden eller (ba) > e, gå till steg 3.

Steg 5) Visa c som den ungefärliga roten.

Låt oss se ett exempel på algoritmen för tvåsektionsmetoden.
Vi måste hitta roten till följande kontinuerliga funktion med hjälp av tvåsektionsmetodens formel.

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

Exempel på tvåsektionsmetod

Steg 1) Låt oss anta,

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

Steg 2) Nu ska vi kontrollera om f(a)f(b) >= 0 eller inte.

         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

Därför ligger roten till ovanstående funktion i detta intervall [-10, 10].

Steg 3) Då kommer mittpunkten c att beräknas först.

Nu måste följande villkor kontrolleras:

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

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

Villkoret är uppfyllt. För nästa iteration kommer värdena att vara,

a = a = -10
b = c = 0

Steg 4) Eftersom (ba) = (0-(-10)) = 10>0.05, kommer processen att upprepas. Nästa iterationer visas i tabellen.

iteration	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

Steg 5) I den 11:e iterationen kommer steg 4-villkoret att vara falskt. Roten till denna ekvation är alltså -1.00586.

Bisektionsmetod logiskt diagram

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

Exempel på tvåsektionsmetod i C/C++

Ingång:

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

Produktion:

The root is :-1.00586

Bisektionsmetod Exempel i Python