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

Данный метод описывает алгоритм нахождение корней (нулей) функции. Чтобы найти минимум целевой функции методом дихотомии используйте этот калькулятор.
Считаем, что отделение корней произведено и на интервале [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≤ π

загрузка...