Bisektionsmetode - Hvad er, algoritme og eksempel

Hvad er bisektionsmetode?

Bisektionsmetode er en af de grundlæggende numeriske løsninger til at finde roden til en polynomialligning. Den anbringer intervallet, som ligningens rod ligger i, og underinddeler dem i halvdele i hver iteration, indtil den finder roden. Således kaldes halveringsmetoden også for bracketing-metoden.

Men da arbejdsmekanismen ligner den binære søgealgoritme, er bisektionsmetoden også kendt som binær søgemetode, halveringsmetode eller dikotomimetoden. Det er primært baseret på mellemværdisætningen.

Finde ligningers rødder

I dette eksempel betragter vi kun ligninger med én uafhængig variabel. Det kan enten være lineært eller ikke-lineært. Lineære ligninger bruges til at repræsentere grafen for en ret linje, hvorimod ikke-lineære ligninger bruges til at repræsentere kurver.

Roden af en ligning betyder værdien af den uafhængige variabel, der opfylder ligningen. For eksempel: roden af en ligning f(x)= 4-x² = 0 er 2, fordi f(2) = 4-2² = 0.

Lad os betragte f(x) som en reel kontinuerlig funktion. Ifølge mellemværdisætningen har ligningen f(x)=0 mindst én rod mellem a og b, hvis f(a)f(b) < 0. Funktionen f(x) har en rod, "c," mellem a og b.

Grafisk fremstilling af bisektionsmetode

Den følgende graf repræsenterer arbejdsmekanismen for halveringsmetoden. Fra grafen kan vi se, at roden af ligningen er rødmarkeret.

Til at starte med:

Vi tog først to indledende gæt, en₁ og b_1, for hvilken f(a₁)f(b₁) < 0. Ifølge mellemværdisætningen skal roden ligge i [a₁, b₁].
Vi kan finde midtpunktet af a₁ og b_1,som er b₂. Således er det indledende interval nu reduceret til [a₁, b₂] fordi f(a₁)f(b₂) < 0.
På samme måde reduceres intervallet, indtil den omtrentlige løsning er fundet.

Bisektionsmetodealgoritme

Trinnene til at anvende halveringsmetodealgoritmen til at finde roden af ligningen f(x)=0 er som følger

Trin 1) Vælg indledende gæt a, b og tolerancerate e

Trin 2) Hvis f(a)f(b) >=0, så ligger roden ikke i dette interval. Der vil således ikke være nogen løsning.

Trin 3) Find midtpunktet, c = (a+b)/2

(i) Hvis funktionsværdien af midtpunktet f(c) = 0, så er c roden. Gå til trin 5.
(ii) Hvis f(a)f(c) < 0 ligger roden mellem a og c. Indstil derefter a = a, b = c.
(iii) Ellers sæt a = c, b = b.

Trin 4) Hvis den absolutte fejl er højere end toleranceraten eller (ba) > e, skal du gå til trin 3.

Trin 5) Vis c som den omtrentlige rod.

Lad os se et eksempel på bisektionsmetodens algoritme.
Vi er nødt til at finde roden til den følgende kontinuerlige funktion ved hjælp af formlen for halveringsmetoden.

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

Eksempel på halvsektionsmetode

Trin 1) Lad os antage,

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

Trin 2) Nu vil vi kontrollere, om f(a)f(b) >= 0 eller ej.

         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 roden af ovenstående funktion i dette interval [-10, 10].

Trin 3) Herefter beregnes midtpunktet c først.

Nu skal 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

Betingelsen er opfyldt. For den næste iteration vil værdierne være,

a = a = -10
b = c = 0

Trin 4) Da (ba) = (0-(-10)) = 10>0.05, vil processen blive gentaget. De næste iterationer er vist 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

Trin 5) I den 11. iteration vil trin 4-betingelsen være falsk. Således er roden af denne ligning -1.00586.

Bisektionsmetode 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++

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

Eksempel på halveringsmetode i Python