Назад Метод простых итераций
 Наверх: Приближённое нахождение корней уравнений
Вперед: Метод простого перебора

Untitled Document

Ядерное оружие | Графика | Математика | Физика | Заказать диплом | Информатика | ТКМ | Электротехника | Атомная энергетика | Лекции

Метод половинного деления

Снова предположим, что корень отделён на отрезке $ [a;b]$ и знаки $ f(a)$ и $ f(b)$ различны (функция $ f(x)$ меняет знак при переходе через корень $ x^*$).

Положим $ a_0=a$ и $ b_0=b$ и вычислим значения функции в левом конце отрезка, $ f(a_0)$, и в его середине $ c_0=\dfrac{a_0+b_0}{2}$: $ f(c_0)$. Сравним знаки чисел $ f(a_0)$ и $ f(c_0)$. Если эти знаки различны, то корень $ x^*$ лежит в интервале $ (a_0;c_0)$; если же одинаковы, то тогда различны знаки $ f(c_0)$ и $ f(b_0)$, и корень лежит в интервале $ (c_0;b_0)$. (Возможен ещё случай $ f(c_0)=0$; тогда корень $ x^*=c_0$ уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке $ [a_0;c_0]$ либо $ [c_0;b_0]$, длина которого ровно в два раза меньше длины исходного отрезка $ [a_0;b_0]=[a;b]$. Обозначим этот отрезок половинной длины через $ [a_1;b_1]$ (то есть положим $ a_1=a_0;b_1=c_0$ в случае, когда $ f(a_0)$ и $ f(c_0)$ разных знаков, и $ a_1=c_0;b_1=b_0$ в случае, когда $ f(a_0)$ и $ f(c_0)$ одного знака).

Далее повторим процесс для отрезка $ [a_1;b_1]$: снова отыщем его середину $ c_1$, найдём значение функции $ f(c_1)$ и сравним знак этого числа со знаком $ f(a_1)$; если знаки разные, то корень отделён на $ [a_2;b_2]=[a_1;c_1]$, если одинаковые, то на $ [a_2;b_2]=[c_1;b_1]$ (или же оказывается, что $ f(c_1)=0$; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рис.9.2.Последовательное деление отрезка пополам и приближение к корню $ x^*$


Поступая тем же образом и далее, получаем, что после $ k$ делений длина отрезка, на котором лежит корень, сокращается в $ 2^k$ раз и становится равной $ {\delta}_k=\dfrac{b-a}{2^k}$ (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с $ c_i$ при некотором $ i$). Пусть $ {\varepsilon}$ -- заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство $ 2{\delta}_k\leqslant {\varepsilon}$. Очевидно, что если при этом положить

$\displaystyle \wt x=c_k=\dfrac{a_k+b_k}{2},$

то расстояние от корня $ x^*$, лежащего где-то в интервале $ (a_k;b_k)$, до середины этого интервала $ \wt x$ будет не больше $ {\varepsilon}$, то есть приближённое равенство $ x^*\approx\wt x$ будет выполнено с нужной точностью.

        Пример 9.5   Снова рассмотрим уравнение $ x^3+2x^2+3x+5=0$. Пусть корень этого уравнения требуется вычислить с точностью $ {\varepsilon}=0.001$. Начинаем решение методом половинного деления с отрезка $ [-2;-1]$, на котором отделён корень $ x^*$.

Последовательно находим значение функции в серединах получающихся отрезков:

\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}.$ При этом середина последнего отрезка -- это точка $ -1.842773$. Получаем, что приближённое значение $ \wt x$ корня $ x^*$ с точностью до $ 0.001$ равно $ \wt x\approx-1.843$.     

Поскольку при каждом делении отрезка приходится ровно один раз вычислять значение функции $ f(x)$ (в том из концов нового отрезка, в котором это значение не было вычислено на предыдущих этапах), то в среднем придётся для нахождения корня с точностью $ {\varepsilon}$ вычислить значение функции $ N=k+1$ раз. Число $ k$ можно определить из неравенства $ \dfrac{b-a}{2^k}\leqslant 2{\varepsilon}$, откуда

$\displaystyle N=k+1=\left\lceil\log_2\dfrac{b-a}{2{\varepsilon}}\right\rceil+1.$

Это значение $ N$ при малых $ {\varepsilon}$ много меньше того значения $ N=\left\lceil\dfrac{b-a}{2{\varepsilon}}\right\rceil+1$, которое мы получили, анализируя метод простого перебора.

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

Далее мы рассмотрим более быстрые методы, в которых наличие производной будет играть существенную роль.
Наверх: Приближённое нахождение корней уравнений

Физика лабы
Элементарная математика Кратные интегралы Математический анализ
Векторный анализ Аналитическая геометрия Пределы функции Изучение функции Конспекты по математике Комплексные числа Дифференциальные уравнения Определенные интегралы Лекции по высшей математике Исследование функций Вычисление объема с помощью интегралов Алгеброические структуры