Метод на разполовяване – какво е, алгоритъм и пример

Какво представлява методът на бисекция?

Методът на бисекцията е едно от основните числени решения за намиране на корена на полиномно уравнение. Той поставя в скоби интервала, в който се намира коренът на уравнението, и ги разделя на половини във всяка итерация, докато намери корена. По този начин методът на разполовяване се нарича още метод на поставяне в скоби.

Въпреки това, тъй като работният механизъм е подобен на алгоритъма за двоично търсене, методът на разполовяване е известен също като метод на двоично търсене, метод на разполовяване или метод на дихотомия. Основно се основава на теоремата за междинната стойност.

Намиране на корени на уравнения

В този пример разглеждаме само уравнения с една независима променлива. Тя може да бъде линейна или нелинейна. Линейните уравнения се използват за представяне на графиката на права линия, докато нелинейните уравнения се използват за представяне на криви.

Коренът на уравнение означава стойността на независимата променлива, която удовлетворява уравнението. Например: корен на уравнение f(x)= 4-x² = 0 е 2, защото f(2) = 4-2² = 0.

Нека разгледаме f(x) като реална непрекъсната функция. Съгласно теоремата за междинната стойност, уравнението f(x)=0 има поне един корен между a и b, ако f(a)f(b) < 0. Функцията f(x) има корен, "c," между a и b.

Графично представяне на метода на разполовяването

Следващата графика представя работния механизъм на метода на разполовяване. От графиката можем да видим, че коренът на уравнението е маркиран с червено.

Да започнем с:

Първо направихме две първоначални предположения, a₁ и b_1, за което f(a₁)f(b₁) < 0. Според теоремата за междинната стойност коренът трябва да се намира в [a₁, б₁].
Можем да намерим средата на a₁ и b_1,което е b₂. По този начин първоначалният интервал сега е намален до [a₁, б₂], защото f(a₁)f(b₂) < 0.
По същия начин интервалът се намалява до намиране на приблизителното решение.

Алгоритъм на метода на разполовяване

Стъпките за прилагане на алгоритъма на метода на разполовяване за намиране на корена на уравнението f(x)=0 са както следва

Стъпка 1) Изберете първоначални предположения a, b и степен на толерантност e

Стъпка 2) Ако f(a)f(b) >=0, тогава коренът не лежи в този интервал. Така няма да има решение.

Стъпка 3) Намерете средната точка, c = (a+b)/2

(i) Ако функционалната стойност на средната точка f(c) = 0, тогава c е коренът. Отидете на стъпка 5.
(ii) Ако f(a)f(c) < 0, коренът се намира между a и c. След това задайте a = a, b = c.
(iii) В противен случай задайте a = c, b = b.

Стъпка 4) Ако абсолютната грешка е по-висока от процента на толеранс или (ba) > e, преминете към стъпка 3.

Стъпка 5) Покажете c като приблизителен корен.

Нека видим пример за алгоритъма на метода на разполовяване.
Трябва да намерим корена на следната непрекъсната функция, използвайки формулата на метода на разполовяването.

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

Пример за метод на разполовяване

Стъпка 1) Да предположим,

         a = -10,
         b = 10 и
         e = 1% или 0.01

Стъпка 2) Сега ще проверим дали f(a)f(b) >= 0 или не.

         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

Следователно коренът на горната функция се намира в този интервал [-10, 10].

Стъпка 3) Тогава първо ще се изчисли средната точка c.

Сега трябва да се проверят следните условия:

(i) дали f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) ако f(a)f(c) < 0:
f(c)f(a) = 2*(-1098) < 0

Условието е изпълнено. За следващата итерация стойностите ще бъдат,

а = а = -10
b = c = 0

Стъпка 4) Тъй като (ba) = (0-(-10)) = 10>0.05, процесът ще се повтори. Следващите повторения са показани в таблицата.

Повторение	a	b	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

Стъпка 5) В 11-то повторение условието от стъпка 4 ще бъде невярно. Така коренът на това уравнение е -1.00586.

Логическа диаграма на метода на разполовяване

Псевдо-код

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

Пример за метод на разполовяване в C/C++

Вход:

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

Изход:

The root is :-1.00586

Пример за метод на разполовяване в Python