Метод половинного деления (метод дихотомии или метод бисекции)

Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)<0. Метод дихотомии заключается в следующем. Определяем половину отрезка  и вычисляем f(c). Проверяем следующие условия
1. Если |f(c)| < ε, то c – корень. Здесь ε - заданная точность.
2. Если f(c)f(a)<0, то корень лежит в интервале [a,c].
3. Если f(c)f(b)<0, то корень лежит на отрезке[c,b].
Продолжая процесс половинного деления в выбранных подынтервалов, можно дойти до сколь угодно малого отрезка, содержащего корень ξ.
Так как за каждую итерацию интервал, где расположен корень уменьшается в два раза, то через n итераций интервал будет равен:
при этом an≤ξ≤bn, , .
В качестве корня ξ. возьмем . Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие
(bn – an)/2 < ε
то процесс поиска заканчивается и .
см. более подробный алгоритм метода бисекции.

Теорема 2. Итерационный процесс половинного деления сходится к искомому корню ξ с любой наперед заданной точностью ε.
Доказательство: Рассмотрим последовательность чисел ξi являющихся приближением корня на i-ом шаге.
,
где a0=a; b0=b; ai;bi - границы подынтервалов, в которых f(ai)f(bi)<0. Рассмотрим разности
1- ξ0|, |ξ2- ξ1|, …, |ξn- ξn-1|.
Имеем . Так как всегда имеем либо b1=b0, , либо , поэтому  , если, b1=b0
 либо , если a1=a0.
Повторяя аналогичные рассуждения и учитывая, что всегда выполняется соотношение либо , либо . Получим
;
;
, где .
Отсюда видно, что какое бы малое число ε>0 мы ни задали, всегда можно найти такое n, что  ч.т.д.
Графически метод дихотомии выглядит следующим образом

|f(c)|≤δ f(a)f(c)<0 f(b)f(c)<0

Сходимость метода дихотомии линейная с коэффициентом α=0,5. Покажем это.
Если в качестве xn брать an, то из формулы (6) мы можем записать . Отсюда следует .
Отметим, что за 10 итераций (n=10) интервал уменьшается в 210 = 1024 ≈ 103 раз. За 20 итераций (n=2) уменьшается в 220 ≈ 106 раз.

Перейти к онлайн решению своей задачи

Как легко решить методом дихотомии (методом бисекции)

Скачать решение

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

Пример №1. Найти экстремум функции: y=5x2-4x+1 методом дихотомии, если ε=0.1, а исходный интервал [0,10].
Решение. Находим производную функции: y ' = 10x-4. Найдем нули функции методом дихотомии: y'=0.
Поскольку F(0)*F(10)<0 (т.е. значения функции на его концах имеют противоположные знаки), то корень лежит в пределах [0;10].
Итерация 1.
Находим середину отрезка: c = (0 + 10)/2 = 5
F(x) = 46
F(c) = -4
Поскольку F(c)•F(a) < 0, то b=5
Итерация 2.
Находим середину отрезка: c = (0 + 5)/2 = 2.5
F(x) = 21
F(c) = 46
Поскольку F(c)•F(a) < 0, то b=2.5
Итерация 3.
Находим середину отрезка: c = (0 + 2.5)/2 = 1.25
F(x) = 8.5
F(c) = 21
Поскольку F(c)•F(a) < 0, то b=1.25
Итерация 4.
Находим середину отрезка: c = (0 + 1.25)/2 = 0.625
F(x) = 2.25
F(c) = 8.5
Поскольку F(c)•F(a) < 0, то b=0.625
Остальные расчеты сведем в таблицу.

N c a b f(c) f(x) ε
1 5 10 5 -4 46 5
2 2.5 5 2.5 46 21 2.5
3 1.25 2.5 1.25 21 8.5 1.25
4 0.625 1.25 0.625 8.5 2.25 0.625
5 0.3125 0.625 0.3125 2.25 -0.875 0.3125
6 0.4688 0.625 0.4688 -0.875 0.6875 0.1563


Таким образом, в качестве корня можно принять:
x=(0.3125+0.46875)/2 = 0.3906
Ответ:x=0.3906; F(x) = 0.6875
Количество итераций, N = 6
Параметр сходимости. Сходимость метода дихотомии линейная с коэффициентом α = 0.5.

На отрезке [0,10] функция имеет экстремум x=0.3906.

Пример №2. Методом дихотомического поиска найдите максимумы функций, пологая, что Δ=0,05.
f(x) = x*cos(x), 0 ≤x≤ π

загрузка...