Метод бисекции – что такое, алгоритм и пример

Что такое метод бисекции?

Метод бисекции является одним из основных численных решений для поиска корня полиномиального уравнения. Он заключает в скобки интервал, в котором находится корень уравнения, и делит его пополам на каждой итерации, пока не найдет корень. Таким образом, метод деления пополам также называют методом брекетинга.

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

Поиск корней уравнений

В этом примере мы рассматриваем только уравнения с одной независимой переменной. Оно может быть как линейным, так и нелинейным. Линейные уравнения используются для представления графика прямой линии, тогда как нелинейные уравнения используются для представления кривых.

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

Рассмотрим f(x) как действительную непрерывную функцию. Согласно теореме о промежуточном значении, уравнение f(x)=0 имеет хотя бы один корень между a и b, если f(a)f(b) < 0. Функция f(x) имеет корень «c», между а и б.

Поиск корней уравнений

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

На следующем графике представлен рабочий механизм метода деления пополам. На графике мы видим, что корень уравнения отмечен красным.

Начать с:

  • Сначала мы сделали два первоначальных предположения:1 и б1, для которого f(a1)f(б1) < 0. Согласно теореме о промежуточном значении корень должен лежать в [a1, б1].
  • Мы можем найти середину1 и б1, что такое б2. Таким образом, начальный интервал теперь сокращается до [a1, б2] потому что f(a1)f(б2) < 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 (х) = х3 - Икс2 + 2

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

Шаг 1) Давайте предположим,

         а = -10,
         б = 10, и
         е = 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
         б = с = 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

Входной сигнал:

def value(x):
	return x*x*x - x*x + 2
def bisection_method(a,b):
	if (value(a) * value(b) >= 0):
		return
	c = a
	while ((b-a) >= 0.01):
		c = (a+b)/2
		if (value(c) == 0.0):
			break
		if (value(c)*value(a) < 0):
			b = c
		else:
			a = c			
	print("The root is : ","%.4f"%c)	
a =-10
b = 10
bisection_method(a, b)

Вывод:

The root is :  -1.0059

Преимущества и ограничения метода пополам

Вот плюсы и минусы метода пополам:

Плюсы Минусы
Легкий и простой в реализации метод поиска корней. Сходимость происходит медленно, поскольку она просто основана на уменьшении интервала вдвое.
Поскольку он заключает в скобки корень, он всегда сходится. Если одно из начальных предположений близко к корню, достижение корня потребует большего количества итераций.
Частоту ошибок можно контролировать, увеличивая или уменьшая количество итераций.