Алгоритм методу бісекції з прикладами

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

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

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

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

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

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

Коренем рівняння є значення незалежної змінної, яка задовольняє рівняння. Наприклад, корінь рівняння 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₁, для якого f(a₁)f(b₁) < 0. Згідно з теоремою про проміжні значення, корінь повинен лежати в [a₁, б₁].
• Потім ми обчислюємо середину a₁ і b₁, що є b₂Початковий інтервал тепер зменшується до [a₁, б₂] тому що f(a₁)f(b₂) < 0.
• Таким же чином інтервал знову і знову зменшується вдвічі, доки не буде знайдено наближене рішення в межах потрібного допуску.

Зрозумівши геометричну інтуїцію, ми можемо формалізувати процедуру як покроковий алгоритм.

Алгоритм методу бісекції

Кроки застосування алгоритму методу бісекції для знаходження кореня рівняння f(x) = 0 такі.

Крок 1) Виберіть початкові припущення a, b та коефіцієнт допуску e.

Крок 2) Якщо f(a)f(b) >= 0, то корінь не лежить у цьому інтервалі. У такому випадку розв'язку в межах [a, b] немає.

Крок 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) Якщо абсолютна похибка вища за допустиму похибку, тобто (b – a) > 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)³ – (-10)² + 2 = -1098
         f(b) = f(10) = (10)³ - (10)² + 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)³ - (0)² + 2 = 2, що не дорівнює 0.

(ii) Чи f(a)f(c) < 0:
         f(c)f(a) = 2 * (-1098) < 0

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

         a = a = -10
         b = c = 0

Крок 4) Оскільки (b – a) = (0 – (-10)) = 10 > 0.01, процес повторюється. Наступні ітерації показано в таблиці нижче.

Крок 5) На 11-й ітерації умова на кроці 4 стає хибною. Таким чином, наближений корінь цього рівняння дорівнює -1.00586.

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

Логічна схема методу розрізу

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

Псевдо-Code

Наведений нижче псевдокод відображає алгоритм і служить планом для реалізації методу бісекції будь-якою мовою програмування.

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

Наступний C/C++ Програма реалізує метод розбиття на дві частини для знаходження кореня функції f(x) = x³ - х² + 2 в інтервалі [-10, 10].

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

#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

Команда 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

Переваги та обмеження методу бісекції

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

Застосування методу бісекції

Метод бісекції використовується в багатьох практичних та сучасних обчислювальних сценаріях, де потрібен надійний крок пошуку коренів.

• Інженерне моделювання: Розв'язання нелінійних рівнянь, що зустрічаються в теплопередачі, гідродинаміці та структурному аналізі.
• Фінансове моделювання: Обчислення дохідності, внутрішніх норм рентабельності та точок беззбитковості там, де не існує рішень замкнутої форми.
• Машинне навчання та штучний інтелект: Визначення порогових значень, калібрування моделей та налаштування гіперпараметрів у числових розв'язувачах на основі штучного інтелекту.
• Комп'ютерна графіка: Визначення перетинів променів з поверхнями та значень параметрів вздовж кривих.
• Вбудовані системи: Апроксимація коренів у контролерах з низьким рівнем ресурсів, де простота та передбачуваність цінніші за швидкість.

Поширені запитання