Краткая сводка теоретических сведений, необходимых для выполнения задания 2

Снова предположим, что корень отделён на отрезке [a;b] и знаки f(a) и f(b) различны функция f(x) меняет знак при переходе через корень x*). Положим и и вычислим значения функции в левом конце отрезка, , и в его середине : . Сравним знаки чисел и . Если эти знаки различны, то корень x* лежит в интервале ; если же одинаковы, то тогда различны знаки и , и корень лежит в интервале . (Возможен ещё случай f(c)=0; тогда корень уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке либо , длина которого ровно в два раза меньше длины исходного отрезка . Обозначим этот отрезок половинной длины через (то есть положим в случае, когда f(a) и f(c) разных знаков, и в случае, когда и одного знака). Далее повторим процесс для отрезка : снова отыщем его середину, найдём значение функции f(c) и сравним знак этого числа со знаком f(a); если знаки разные, то корень отделён на , если одинаковые, то на (или же оказывается, что f(c)=0; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

.Последовательное деление отрезка пополам и приближение к корню x* Поступая тем же образом и далее, получаем, что после k делений длина отрезка, на котором лежит корень, сокращается в раз и становится равной (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с при некотором ). Пусть ε - заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство . Очевидно, что если при этом положить то расстояние от корня x*, лежащего где-то в интервале , до середины этого интервала будет не больше ε, то есть приближённое равенство будет выполнено с нужной точностью. Снова рассмотрим уравнение . Пусть корень этого уравнения требуется вычислить с точностью . Начинаем решение методом половинного деления с отрезка [-2;-1], на котором отделён корень x*. Последовательно находим значение функции в серединах получающихся отрезков:

f(-1,5)=1,625

f(-1,75)=0,515625

f(-1,875)=-0,185547

f(-1,841797)=0.011269, после чего вычисления прекращаются на девятом шаге, так как очередной отрезок имеет длину При этом середина последнего отрезка - это точка -1,842773. Получаем, что приближённое значение корня x* с точностью до 0,001 равно . Поскольку при каждом делении отрезка приходится ровно один раз вычислять значение функции f(x) (в том из концов нового отрезка, в котором это значение не было вычислено на предыдущих этапах), то в среднем придётся для нахождения корня с точностью ε вычислить значение функции N=k+1 раз. Число k можно определить из неравенства , откуда N= Это значение N при малых ε много меньше того значения N= , которое мы получили, анализируя метод простого перебора. Заметим, что метод деления отрезка пополам, как и метод простого перебора, не предъявляет никаких требований к гладкости функции (то есть к существованию её производной): достаточно, чтобы функция была непрерывной. Далее мы рассмотрим более быстрые методы, в которых наличие производной будет играть существенную роль.