Метод розрізу навпіл – що таке, алгоритм і приклад

Що таке метод бісекції?

Метод ділення навпіл є одним із основних чисельних розв’язків для знаходження кореня многочленного рівняння. Він бере в дужки інтервал, у якому лежить корінь рівняння, і ділить його на половини в кожній ітерації, доки не знайде корінь. Таким чином, метод поділу навпіл ще називають методом брекетингу.

Однак, оскільки робочий механізм подібний до алгоритму бінарного пошуку, метод розділення навпіл також відомий як метод бінарного пошуку, метод розведення навпіл або метод дихотомії. Основним чином він базується на теоремі проміжного значення.

Знаходження коренів рівнянь

У цьому прикладі ми розглядаємо лише рівняння з однією незалежною змінною. Він може бути як лінійним, так і нелінійним. Лінійні рівняння використовуються для представлення графіка прямої лінії, тоді як нелінійні рівняння використовуються для представлення кривих.

Корінь рівняння означає значення незалежної змінної, яке задовольняє рівняння. Наприклад: корінь рівняння 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

Умова виконана. Для наступної ітерації значення будуть такими:

a = a = -10
b = c = 0

Крок 4) Оскільки (ba) = (0-(-10)) = 10>0.05, процес буде повторюватися. Наступні ітерації наведені в таблиці.

Ітерація	a	b	c	ба	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

Крок 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