Алгоритъм за метод на бисекция с примери

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

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

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

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

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

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

Коренът на уравнението е стойността на независимата променлива, която удовлетворява уравнението. Например, коренът на уравнението 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₁, което е б₂Първоначалният интервал сега е намален до [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

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

         а = а = -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

Предимства и ограничения на метода на бисекция

Както всяка числена техника, методът на бисекция има ясни силни страни и няколко практически недостатъка. Таблицата по-долу обобщава най-важните плюсове и минуси.

Приложения на метода на бисекция

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

• Инженерни симулации: Решаване на нелинейни уравнения, които се срещат в топлопреноса, флуидната динамика и структурния анализ.
• Финансово моделиране: Изчисляване на доходност, вътрешни норми на възвръщаемост и точки на рентабилност, където не съществуват решения в затворена форма.
• Машинно обучение и изкуствен интелект: Локализиране на прагове, калибриране на модели и настройване на хиперпараметри в числени решатели, управлявани от изкуствен интелект.
• Компютърна графика: Определяне на пресечните точки на лъч-повърхност и стойности на параметри по криви.
• Вградени системи: Приближаване на корени в контролери с ниски ресурси, където простотата и предвидимостта са по-ценни от скоростта.

Въпроси и Отговори