Приближённое нахождение корней уравнений

Метод половинного деления
  Пример 9.5 Снова рассмотрим уравнение . Пусть корень этого уравнения требуется вычислить с точностью ${\varepsilon}=0.001$ . Начинаем решение методом половинного деления с отрезка , на котором отделён корень .
Последовательно находим значение функции в серединах получающихся отрезков:
$\begin{multline*} f(-1.5)=1.625;f(-1.75)=0.515625;f(-1.875)=-0.185547;\dots;\\ f(-1.841797)=0.011269, \end{multline*}$

после чего вычисления прекращаются на девятом шаге, так как очередной отрезок имеет длину $\dfrac{1}{2^9}=\dfrac{1}{512}<2{\varepsilon}=\dfrac{1}{500}.$ При этом середина последнего отрезка -- это точка . Получаем, что приближённое значение $\wt x$ корня с точностью до равно $\wt x\approx-1.843$ .
Поскольку при каждом делении отрезка приходится ровно один раз вычислять значение функции (в том из концов нового отрезка, в котором это значение не было вычислено на предыдущих этапах), то в среднем придётся для нахождения корня с точностью ${\varepsilon}$ вычислить значение функции раз. Число можно определить из неравенства $\dfrac{b-a}{2^k}\leqslant 2{\varepsilon}$ , откуда
$\displaystyle N=k+1=\left\lceil\log_2\dfrac{b-a}{2{\varepsilon}}\right\rceil+1.$ Производная функции в точке Примеры решения и оформления задач контрольной работы
Это значение при малых ${\varepsilon}$ много меньше того значения $N=\left\lceil\dfrac{b-a}{2{\varepsilon}}\right\rceil+1$ , которое мы получили, анализируя метод простого перебора.
Заметим, что метод деления отрезка пополам, как и метод простого перебора, не предъявляет никаких требований к гладкости функции (то есть к существованию её производной): достаточно, чтобы функция была непрерывной.
Далее мы рассмотрим более быстрые методы, в которых наличие производной будет играть существенную роль.