Метод бисекции – что такое, алгоритм и пример
Что такое метод бисекции?
Метод бисекции является одним из основных численных решений для поиска корня полиномиального уравнения. Он заключает в скобки интервал, в котором находится корень уравнения, и делит его пополам на каждой итерации, пока не найдет корень. Таким образом, метод деления пополам также называют методом брекетинга.
Однако, поскольку рабочий механизм аналогичен алгоритму бинарного поиска, метод деления пополам также известен как метод бинарного поиска, метод деления пополам или метод дихотомии. В первую очередь он основан на теореме о промежуточном значении.
Поиск корней уравнений
В этом примере мы рассматриваем только уравнения с одной независимой переменной. Оно может быть как линейным, так и нелинейным. Линейные уравнения используются для представления графика прямой линии, тогда как нелинейные уравнения используются для представления кривых.
Корень уравнения означает значение независимой переменной, которая удовлетворяет уравнению. Например: корень уравнения 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
Преимущества и ограничения метода пополам
Вот плюсы и минусы метода пополам:
Плюсы | Минусы |
---|---|
Легкий и простой в реализации метод поиска корней. | Сходимость происходит медленно, поскольку она просто основана на уменьшении интервала вдвое. |
Поскольку он заключает в скобки корень, он всегда сходится. | Если одно из начальных предположений близко к корню, достижение корня потребует большего количества итераций. |
Частоту ошибок можно контролировать, увеличивая или уменьшая количество итераций. |