‹-- Назад
Метод половинного деления
Снова предположим, что корень отделён на отрезке 
и знаки 
и 
различны (функция 
меняет знак при переходе через корень 
).
Положим 
и 
и вычислим значения функции в левом конце отрезка, 
, и в его середине 
: 
. Сравним знаки чисел и . Если эти знаки различны, то корень лежит в интервале 
; если же одинаковы, то тогда различны знаки и 
, и корень лежит в интервале 
. (Возможен ещё случай 
; тогда корень 
уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке 
либо 
, длина которого ровно в два раза меньше длины исходного отрезка 
. Обозначим этот отрезок половинной длины через 
(то есть положим 
в случае, когда и разных знаков, и 
в случае, когда и одного знака).
Далее повторим процесс для отрезка : снова отыщем его середину 
, найдём значение функции 
и сравним знак этого числа со знаком 
; если знаки разные, то корень отделён на 
, если одинаковые, то на 
(или же оказывается, что 
; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.
Поступая тем же образом и далее, получаем, что после 
делений длина отрезка, на котором лежит корень, сокращается в 
раз и становится равной 
(если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с 
при некотором 
). Пусть 
-- заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство 
. Очевидно, что если при этом положить
, лежащего где-то в интервале 
, до середины этого интервала 
будет не больше , то есть приближённое равенство 
будет выполнено с нужной точностью.
. Пусть корень этого уравнения требуется вычислить с точностью 
. Начинаем решение методом половинного деления с отрезка 
, на котором отделён корень . Последовательно находим значение функции в серединах получающихся отрезков:
после чего вычисления прекращаются на девятом шаге, так как очередной отрезок имеет длину
При этом середина последнего отрезка -- это точка 
. Получаем, что приближённое значение корня с точностью до 
равно 
. Поскольку при каждом делении отрезка приходится ровно один раз вычислять значение функции (в том из концов нового отрезка, в котором это значение не было вычислено на предыдущих этапах), то в среднем придётся для нахождения корня с точностью вычислить значение функции 
раз. Число можно определить из неравенства 
, откуда
при малых много меньше того значения 
, которое мы получили, анализируя метод простого перебора. Заметим, что метод деления отрезка пополам, как и метод простого перебора, не предъявляет никаких требований к гладкости функции (то есть к существованию её производной): достаточно, чтобы функция была непрерывной.
Далее мы рассмотрим более быстрые методы, в которых наличие производной будет играть существенную роль.
