Алгоритм метода бисекции с примерами.

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

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

Поскольку механизм его работы напоминает бинарный поиск, метод бисекций также известен как метод бинарного поиска, метод деления пополам или метод дихотомии. Он основан на прочном теоретическом фундаменте: теореме о промежуточном значении, которая гарантирует, что непрерывная функция, меняющая знак на интервале, должна пересекать нулевое значение где-то внутри этого интервала.

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

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

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

Корень уравнения — это значение независимой переменной, которому удовлетворяет это уравнение. Например, корень уравнения 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.

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

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

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

Процедуру можно кратко описать следующим образом:

• Сначала мы выбираем два начальных предположения, а₁ и б₁, для которого f(a)₁)f(б₁) < 0. Согласно теореме о промежуточном значении, корень должен лежать в [a₁, б₁].
• Затем мы вычисляем середину отрезка₁ и б₁, то есть б₂Начальный интервал теперь сокращается до [a].₁, б₂] потому что f(a₁)f(б₂) < 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 (х) = х³ - Икс² + 2

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

Шаг 1) Предположим,

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

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

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

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

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

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

Часто задаваемые вопросы (FAQ)