Все формулы РФ

Математика / Начала анализа

Метод бисекции: корень и гарантированная точность

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

Опубликовано: Обновлено:

Математический анализАлгебраСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$c=\frac{a+b}{2},\qquad |c-r|\leq\frac{b-a}{2}$$
Схема Три деления для x²−2
Бисекция: сохраняемый отрезокБисекция: сохраняемый отрезокДеленийОтрезокСерединаОшибка ≤0[1; 2]1,50,51[1; 1,5]1,250,252[1,25; 1,5]1,3750,1253[1,375; 1,5]1,43750,0625Корень √2 остаётся внутри каждого отрезка

Граница ошибки середины уменьшается вдвое после каждого деления.

Обозначения

$a,b$
концы текущего отрезка, a<b, единица аргумента
$c$
середина текущего отрезка, единица аргумента
$r$
хотя бы один корень на текущем отрезке, единица аргумента

Условия применения

Функция должна быть непрерывна на всём исходном отрезке, а значения на его концах — иметь противоположные знаки. Если значение на конце или в середине точно равно нулю, корень уже найден. При нескольких корнях метод сохраняет хотя бы один из них, но не перечисляет все.

Ограничения

Разрыв функции может имитировать смену знака без корня: например, 1/x на [−1;1]. Корень чётной кратности может не менять знак и остаться незамеченным. Нельзя обещать точность меньше разрешения машинной арифметики; вычисление знака очень малого значения тоже требует осторожности.

Подробное объяснение

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

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

После k делений ширина исходного отрезка уменьшается в 2ᵏ раз. Середина нового отрезка удалена от любого его корня не больше чем на половину этой ширины. Именно эта геометрическая оценка позволяет заранее выбрать число шагов для заданной абсолютной погрешности.

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

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

Как пользоваться формулой

  1. Вычислите значения функции на концах и проверьте непрерывность; одинаковые ненулевые знаки не дают гарантии корня.
  2. Найдите середину отрезка и значение функции в ней; при точном нуле завершите расчёт найденным аргументом.
  3. Сохраните половину с разными знаками на концах и повторяйте деление, записывая новую ширину отрезка.
  4. Остановитесь, когда половина ширины не превосходит допуска; ответом возьмите середину последнего отрезка.

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

Деление отрезка пополам относится к элементарным приёмам приближённого вычисления: современную бисекцию не следует без отдельного исторического свидетельства приписывать одному изобретателю. Её строгая гарантия опирается на теорию непрерывных функций, которая получила систематическое развитие в анализе XIX века. История численного решения уравнений значительно старше современной компьютерной реализации, но совпадение идеи с древним поиском приближений ещё не доказывает тождество алгоритмов. В современной классификации NIST DLMF бисекция рассматривается среди методов решения нелинейных уравнений. Её роль отличается от роли касательных и секущих: основной ресурс здесь — отрезок с гарантированным корнем, а не локальная модель производной. В программной записи к математической схеме добавляют контроль округления и предел числа итераций.

Историческая линия формулы

Бисекция здесь представлена как общий алгоритм деления знакопеременного отрезка. Отдельный автор не указан: доказательство относится к теории непрерывности, а современная реализация — к численному анализу. Это не историческое утверждение о первенстве конкретного математика.

Пример

Найдём положительный корень x² − 2 = 0 на [1;2], выполнив три деления. На концах значения − 1 и 2, функция непрерывна. Первая середина 1,5 даёт 0,25, поэтому остаётся [1;1,5]. Вторая середина 1,25 даёт − 0,4375: сохраняем [1,25;1,5]. Третья середина 1,375 даёт − 0,109375, новый отрезок [1,375;1,5]. Его середина равна 1,4375, а половина ширины — 0,0625. Ответ: корень находится не далее 0,0625 от 1,4375. Проверка по √2 ≈ 1,414214 даёт ошибку около 0,023286, которая меньше гарантированной границы. Все числа в этом примере безразмерны. Значение 1,375 было проверенной серединой третьего шага, а 1,4375 — итоговой серединой уже суженного отрезка.

Частая ошибка

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

Практика

Задачи с решением

Два деления

Условие. Для x² − 3 = 0 начните с [1;2] и выполните два деления. Укажите итоговый отрезок.

Решение. Середина 1,5 даёт − 0,75, поэтому остаётся [1,5;2]. Середина 1,75 даёт 0,0625; итог [1,5;1,75]. Его середина 1,625, гарантированная ошибка не более 0,125.

Ответ. [1,5;1,75]; середина 1,625 ±0,125.

Число шагов

Условие. Исходная ширина равна 8. Сколько делений достаточно для ошибки итоговой середины не более 0,01?

Решение. После k делений половина ширины равна 4/2ᵏ. Требуется 2ᵏ≥400. При k = 8 получаем 0,015625, при k = 9 — 0,0078125.

Ответ. 9 делений.

Дополнительные источники

  • https://dlmf.nist.gov/3.8
  • https://fncbook.com/secant/
  • https://mathshistory.st-andrews.ac.uk/Biographies/Bolzano/

Связанные формулы

Математика

Метод Ньютона: приближение корня по касательной

$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$

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

Математика

Метод секущих: поиск корня без вычисления производной

$x_{k+1}=x_k-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$

Метод секущих строит прямую по двум последним точкам графика и использует её пересечение с осью для нового приближения корня. Производная заменяется разностным наклоном.