Bisectiemethode - Wat is, algoritme en voorbeeld

Wat is bisectiemethode?

Bisection Method is een van de basis numerieke oplossingen voor het vinden van de wortel van een polynoomvergelijking. Het haakt het interval waarin de wortel van de vergelijking ligt in en verdeelt ze in helften in elke iteratie totdat het de wortel vindt. Daarom wordt de bisection-methode ook wel de bracketing-methode genoemd.

Omdat het werkingsmechanisme echter vergelijkbaar is met het binaire zoekalgoritme, staat de bisectiemethode ook bekend als binaire zoekmethode, halveringsmethode of dichotomiemethode. Het is voornamelijk gebaseerd op de tussenwaardestelling.

Wortels van vergelijkingen vinden

In dit voorbeeld beschouwen we alleen vergelijkingen met één onafhankelijke variabele. Het kan lineair of niet-lineair zijn. Lineaire vergelijkingen worden gebruikt om de grafiek van een rechte lijn weer te geven, terwijl niet-lineaire vergelijkingen worden gebruikt om curven weer te geven.

De wortel van een vergelijking betekent de waarde van de onafhankelijke variabele die aan de vergelijking voldoet. Bijvoorbeeld: de wortel van een vergelijking f(x)= 4-x² = 0 is 2 omdat f(2) = 4-2² = 0.

Laten we f(x) beschouwen als een echte continue functie. Volgens de tussenwaardestelling heeft de vergelijking f(x)=0 ten minste één wortel tussen a en b als f(a)f(b) < 0. De functie f(x) heeft een wortel, "c", tussen a en b.

Grafische weergave van de bisectiemethode

De volgende grafiek geeft het werkingsmechanisme van de bisectiemethode weer. Uit de grafiek kunnen we zien dat de wortel van de vergelijking rood gemarkeerd is.

Beginnen met:

We hebben eerst twee initiële gissingen gedaan, a₁ en B_1, waarvoor f(een₁)f(geb₁) < 0. Volgens de tussenwaardestelling zou de wortel in [a moeten liggen₁, b₁].
We kunnen het middelpunt van a vinden₁ en B_1,dat is b₂. Het initiële interval wordt nu dus teruggebracht tot [a₁, b₂] omdat f(a₁)f(geb₂) < 0.
Op dezelfde manier wordt het interval verkleind totdat de geschatte oplossing is gevonden.

Algoritme voor bisectiemethode

De stappen voor het toepassen van het algoritme voor de bisectiemethode om de wortel van vergelijking f(x)=0 te vinden, zijn als volgt

Stap 1) Kies initiële schattingen a, b en tolerantiepercentage e

Stap 2) Als f(a)f(b) >=0, dan ligt de wortel niet in dit interval. Er zal dus geen oplossing zijn.

Stap 3) Zoek het middelpunt, c = (a+b)/2

(i) Als de functiewaarde van het middelpunt f(c) = 0, dan is c de wortel. Ga naar stap 5.
(ii) Als f(a)f(c) < 0 ligt de wortel tussen a en c. Stel vervolgens a = a, b = c in.
(iii) Stel anders a = c, b = b.

Stap 4) Als de absolute fout hoger is dan het tolerantiepercentage of (ba) > e, ga dan naar stap 3.

Stap 5) Geef c weer als de geschatte wortel.

Laten we een voorbeeld bekijken van het algoritme voor de bisectiemethode.
We moeten de wortel van de volgende continue functie vinden met behulp van de formule van de bisectiemethode.

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

Bisectiemethode Voorbeeld

Stap 1) Laten we aannemen,

         een = -10,
         b = 10, en
         e = 1% of 0.01

Stap 2) Nu gaan we na of f(a)f(b) >= 0 of niet.

         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

De wortel van de bovenstaande functie ligt dus in dit interval [-10, 10].

Stap 3) Vervolgens wordt eerst het middelpunt c berekend.

Nu moeten de volgende voorwaarden worden gecontroleerd:

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

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

Er is aan de voorwaarde voldaan. Voor de volgende iteratie zijn de waarden:

een = een = -10
b = c = 0

Stap 4) Als (ba) = (0-(-10)) = 10>0.05, wordt het proces herhaald. De volgende iteraties worden weergegeven in de tabel.

herhaling	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

Stap 5) In de 11e iteratie zal de voorwaarde van stap 4 onwaar zijn. De wortel van deze vergelijking is dus -1.00586.

Bisectiemethode Logisch diagram

Pseudo-code

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

Bisectiemethode Voorbeeld in 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;
}

Output:

The root is :-1.00586

Bisectiemethode Voorbeeld in Python