Метод бисекции

Метод бисекции (метод деления отрезка пополам, метод дихотомии) — это простейший численный метод для решения уравнений вида \( f(x) = 0 \), основанный на теореме Больцано — Коши о промежуточном значении. Метод относится к классу итерационных методов и гарантирует нахождение корня с заданной точностью, если функция непрерывна на заданном отрезке и меняет на его концах знак.

Алгоритм метода

Теоретическая основа

Метод бисекции применяется для нахождения корня непрерывной функции \( f(x) \) на отрезке \([a, b]\), для которого выполняется условие: \[ f(a) \cdot f(b) < 0 \] Это означает, что функция принимает на концах отрезка значения разных знаков, и, согласно теореме Больцано — Коши, существует хотя бы один корень уравнения \( f(x) = 0 \) внутри интервала \((a, b)\).

Последовательность действий

1. Вычисляется середина отрезка \( c = \frac{a + b}{2} \).
2. Вычисляется значение функции в этой точке \( f(c) \).
3. Проверяется условие:

• Если \( f(c) = 0 \) (или \( |f(c)| \) меньше заданной погрешности), то корень найден.
• Если \( f(a) \cdot f(c) < 0 \), то корень находится на отрезке \([a, c]\), и отрезок \([c, b]\) отбрасывается. Новый отрезок становится \([a, c]\).
• Если \( f(c) \cdot f(b) < 0 \), то корень находится на отрезке \([c, b]\), и отрезок \([a, c]\) отбрасывается. Новый отрезок становится \([c, b]\).

1. Процесс повторяется до тех пор, пока длина текущего отрезка не станет меньше заданной погрешности \( \varepsilon \).

Критерий остановки

Итерации прекращаются при выполнении одного из условий:

• Длина отрезка становится меньше заданной точности: \( b - a < \varepsilon \).
• Значение функции в точке \( c \) становится меньше заданной погрешности по функции: \( |f(c)| < \delta \).

Сходимость и точность

Скорость сходимости

Метод бисекции обладает линейной сходимостью. На каждой итерации длина отрезка, содержащего корень, уменьшается ровно в два раза. Если начальный отрезок имел длину \( L = b - a \), то после \( n \) итераций длина отрезка составит \( L_n = \frac{L}{2^n} \).

Для достижения точности \( \varepsilon \) требуется количество итераций: \[ n \ge \log_2 \left( \frac{b - a}{\varepsilon} \right) \]

Например, для отрезка длиной 1 и точности \( 10^{-6} \) потребуется около 20 итераций.

Гарантированная точность

Главное преимущество метода — гарантированное нахождение корня с заданной точностью, если выполнены начальные условия. Погрешность результата не превышает половины длины последнего отрезка.

Преимущества и недостатки

Преимущества

• Простота реализации: алгоритм легко программируется и не требует вычисления производной функции.
• Надёжность: метод всегда сходится, если функция непрерывна и меняет знак на концах отрезка.
• Гарантированная точность: погрешность контролируется непосредственно длиной отрезка.
• Устойчивость: метод нечувствителен к вычислительным погрешностям, так как на каждом шаге отрезок делится пополам.

Недостатки

• Низкая скорость сходимости: для достижения высокой точности требуется много итераций по сравнению с методами Ньютона или секущих.
• Требование к начальным данным: необходимо заранее знать отрезок, на котором функция меняет знак. Для функций с несколькими корнями требуется локализация каждого корня отдельно.
• Неприменимость к корням чётной кратности: если функция касается оси абсцисс, но не пересекает её (например, \( f(x) = x^2 \) в точке \( x = 0 \)), условие смены знака не выполняется, и метод не работает.
• Неприменимость к разрывным функциям: метод основан на непрерывности функции.

Применение

Решение нелинейных уравнений

Метод бисекции широко применяется для решения уравнений вида \( f(x) = 0 \) в тех случаях, когда требуется гарантированное нахождение корня, а скорость вычислений не критична. Он часто используется как предварительный этап для локализации корня перед применением более быстрых методов (например, метода Ньютона).

Инженерные расчёты

В инженерной практике метод применяется для:

• Расчёта параметров механических систем (например, определение критической нагрузки).
• Нахождения корней характеристических уравнений в теории управления.
• Решения задач теплопередачи и гидравлики.

Образовательные цели

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

Пример реализации

Псевдокод

`` function bisection(f, a, b, epsilon): while (b - a) > epsilon: c = (a + b) / 2 if f(c) == 0: return c if f(a) * f(c) < 0: b = c else: a = c return (a + b) / 2 ``

Пример на языке Python

``python def bisection(f, a, b, eps=1e-6): if f(a) f(b) >= 0: raise ValueError("Функция не меняет знак на концах отрезка") while (b - a) > eps: c = (a + b) / 2 if f(c) == 0: return c if f(a) f(c) < 0: b = c else: a = c return (a + b) / 2 ``

Историческая справка

Метод деления отрезка пополам известен с древности. Его математическое обоснование опирается на теорему Больцано — Коши, сформулированную в первой половине XIX века чешским математиком Бернардом Больцано и французским математиком Огюстеном Луи Коши. В вычислительной практике метод получил широкое распространение с развитием электронно-вычислительных машин в середине XX века благодаря своей простоте и надёжности.

Сравнение с другими методами

Ограничения и особенности

Случаи неприменимости

• Функция не меняет знак на концах отрезка (например, чётные корни).
• Функция имеет разрыв на отрезке.
• На отрезке находится несколько корней — метод найдёт только один из них.

Модификации

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

Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Лаборатория знаний, 2015.
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Калиткин Н. Н. Численные методы. — СПб.: БХВ-Петербург, 2011.
• Burden R. L., Faires J. D. Numerical Analysis. — 9th ed. — Brooks/Cole, 2010.