Что такое метод бисекции?
Метод бисекции (он же метод половинного деления, или дихотомии) — один из самых старых и надёжных способов найти корень непрерывной функции \(f(x)\), то есть такое значение \(x\), при котором \(f(x) = 0\). Идея проста: берём отрезок \([a, b]\), на концах которого функция меняет знак, и раз за разом делим его пополам, оставляя ту половину, где знак по-прежнему меняется. Поскольку смена знака сохраняется на каждом шаге, метод гарантированно сходится — при условии, что функция \(f\) непрерывна, а значения \(f(a)\) и \(f(b)\) имеют противоположные знаки. Калькулятор работает с любой безразмерной вещественной функцией, а в тригонометрии использует радианы.
Как пользоваться калькулятором
Введите функцию в поле f(x), используя \(x\) как переменную (например, x-cos(x), x^2-2 или exp(x)-3). Задайте левую границу a и правую границу b так, чтобы корень оказался между ними: произведение \(f(a)\cdot f(b)\) должно быть меньше или равно нулю. Укажите максимальное число итераций n и количество знаков digits для вывода результата. В ответе вы получите приближённое значение корня, значение функции в этой точке (оно должно быть близко к нулю) и количество реально выполненных итераций.
Формула
На каждом шаге за приближение берётся середина отрезка \(x_n = (a_n + b_n) / 2\). Если \(|f(x_n)|\) меньше заданной точности, значение \(x_n\) принимается за ответ. Иначе алгоритм оставляет ту половину, где сохраняется смена знака: если \(f(a_n)\cdot f(x_n) > 0\), корень находится правее (полагаем \(a = x_n\)), в противном случае — левее (полагаем \(b = x_n\)). Ширина отрезка уменьшается как \((b-a)/2^n\), поэтому сходимость линейная — примерно один новый верный двоичный разряд за каждый шаг.
$$ \begin{gathered} c = \frac{\text{a} + \text{b}}{2} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} &\text{if } f(a)\cdot f(c) < 0 \Rightarrow b \leftarrow c \\ &\text{else} \Rightarrow a \leftarrow c \\ &\text{repeat up to } n \text{ times} \end{aligned} \right. \end{gathered} $$
Разбор примера
Возьмём \(f(x) = x - \cos(x)\) на отрезке \([-10, 10]\): \(f(-10) \approx -10{,}84\) (отрицательное), а \(f(10) \approx 10{,}84\) (положительное), значит, корень заключён внутри отрезка. Повторное деление пополам сходится к \(x \approx 0{,}7390851332151607\) — это знаменитое число Дотти, при котором \(x = \cos x\), а значение \(f(x)\) фактически равно нулю.
Частые вопросы
Почему появляется ошибка «нет смены знака»? Для метода бисекции значения \(f(a)\) и \(f(b)\) должны иметь противоположные знаки. Подберите \(a\) и \(b\) так, чтобы корень оказался между ними.
Можно ли найти сразу несколько корней? Нет — метод возвращает только один корень внутри заданного отрезка и не находит корни, где график лишь касается оси, не пересекая её.
Почему он медленнее метода Ньютона? Бисекция сходится линейно, добавляя около одного двоичного разряда за шаг, тогда как метод Ньютона сходится квадратично. Часто бисекцию используют, чтобы получить надёжное начальное приближение, которое затем уточняют более быстрыми методами.
Как выполнить метод бисекции вручную
Метод бисекции находит корень \(f(x)=0\), многократно деля пополам интервал, который, как известно, содержит корень. Он основан на теореме о промежуточном значении: если \(f\) непрерывна на \([a,b]\) и \(f(a)\) и \(f(b)\) имеют противоположные знаки, то корень должен находиться между ними.
- Проверьте скобки. Подтвердите, что \(f(a)\cdot f(b)<0\). Если произведение положительно, интервал не гарантированно содержит корень — выберите другой \([a,b]\).
- Вычислите середину. \(m=\dfrac{a+b}{2}\).
- Вычислите функцию. Найдите \(f(m)\). Если \(f(m)=0\) (или находится в пределах допуска), \(m\) — корень и вы останавливаетесь.
- Замените конечную точку по знаку. Если \(f(a)\cdot f(m)<0\), корень находится в \([a,m]\), поэтому установите \(b\leftarrow m\). В противном случае корень находится в \([m,b]\), поэтому установите \(a\leftarrow m\).
- Повторяйте шаги 2–4 до тех пор, пока \(|b-a|<\text{допуск}\) или \(|f(m)|<\text{допуск}\), или пока не достигнете максимального количества итераций.
Пример: \(f(x)=x^{3}-x-2\) на \([1,2]\). Проверка: \(f(1)=-2\), \(f(2)=4\), произведение \(<0\) — скобки действительны.
| Итер. | a | b | m=(a+b)/2 | f(m) | Новый интервал |
|---|---|---|---|---|---|
| 1 | 1.0000 | 2.0000 | 1.5000 | −0.125 | [1.5, 2] |
| 2 | 1.5000 | 2.0000 | 1.7500 | 1.6094 | [1.5, 1.75] |
| 3 | 1.5000 | 1.7500 | 1.6250 | 0.6660 | [1.5, 1.625] |
| 4 | 1.5000 | 1.6250 | 1.5625 | 0.2522 | [1.5, 1.5625] |
| 5 | 1.5000 | 1.5625 | 1.5313 | 0.0591 | [1.5, 1.5313] |
| 6 | 1.5000 | 1.5313 | 1.5156 | −0.0340 | [1.5156, 1.5313] |
После дополнительных итераций интервал закрывается на истинном корне 1.521380, который является также единственным действительным корнем кубического уравнения \(x^{3}-x-2=0\), найденным с помощью прямого решателя.
Итерации в сравнении с допуском и шириной скобок
Каждый шаг бисекции делит интервал пополам, поэтому после \(n\) итераций ширина скобок составляет \((b-a)/2^{\,n}\). Чтобы достичь допуска \(\text{допуск}\) на местоположение корня, вам примерно нужно
$$n \approx \log_2\!\left(\frac{b-a}{\text{допуск}}\right).$$Количество растёт только с логарифмом точности, поэтому даже очень строгие допуски требуют относительно немного шагов. В таблице показано округлённое в большую сторону количество итераций для нескольких комбинаций.
| Начальная ширина \(b-a\) | Целевой допуск | \(\log_2((b-a)/\text{допуск})\) | Требуемые итерации |
|---|---|---|---|
| 1 | \(10^{-3}\) | 9.97 | 10 |
| 1 | \(10^{-6}\) | 19.93 | 20 |
| 1 | \(10^{-10}\) | 33.22 | 34 |
| 10 | \(10^{-6}\) | 23.25 | 24 |
| 20 | \(10^{-6}\) | 24.25 | 25 |
| 100 | \(10^{-8}\) | 33.22 | 34 |
| 0.5 | \(10^{-12}\) | 38.86 | 39 |
Например, скобки шириной 20, уточнённые до \(10^{-6}\), требуют \(\lceil\log_2(20/10^{-6})\rceil=\lceil 24.25\rceil=\) 25 итераций, а скобки шириной 1, уточнённые до \(10^{-10}\), требуют \(\lceil 33.22\rceil=\) 34. Сокращение вдвое начальной ширины экономит ровно одну итерацию; возведение в квадрат точности (одна дополнительная цифра) стоит примерно 3.3 итерации.
Ключевые термины
- Корень. Значение \(x^{*}\), где функция равна нулю, \(f(x^{*})=0\); также называется нулём или решением уравнения.
- Скобки / интервал \([a,b]\). Пара конечных точек, которые, как предполагается, содержат корень. Для бисекции должны удовлетворять условию изменения знака.
- Изменение знака. Условие \(f(a)\cdot f(b)<0\), означающее, что \(f\) принимает противоположные знаки в конечных точках. Для непрерывной \(f\) это гарантирует по крайней мере один корень между ними (теорема о промежуточном значении).
- Середина. Центр текущего интервала, \(m=(a+b)/2\); каждый шаг проверяет эту точку и отбрасывает половину, которая не может содержать корень.
- Допуск. Цель точности, которая останавливает итерацию, применяется либо к ширине интервала \(|b-a|\), либо к остатку \(|f(m)|\).
- Сходимость (линейная). Бисекция сходится линейно: ошибка примерно вдвое уменьшается на каждом шаге (ошибка \(\le (b-a)/2^{n}\)), что даёт устойчивый, но не ускоряющийся прогресс — примерно одна дополнительная правильная двоичная цифра на итерацию.
- Итерация. Один полный цикл вычисления середины, вычисления функции и обновления конечной точки. Количество итераций ограничено параметром максимального количества итераций.
