Нелинейное программирование
Метод Лагранжа
Метод множителей Лагранжа
Решить онлайн
Примеры решений Метод Зейделя Метод Ньютона Метод хорд Решение уравнений Метод LU-разложения Метод Гаусса Матрица Гессе Градиент функции Экстремум функции

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

Данный метод описывает алгоритм нахождение корней (нулей) функции. Чтобы найти минимум целевой функции методом дихотомии используйте этот калькулятор.
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)<0. Метод дихотомии заключается в следующем. Определяем половину отрезка c=½(a+b) и вычисляем 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). Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие (bn–an)/2<ε, то процесс поиска заканчивается и ε=½(bn+an).
см. более подробный алгоритм метода бисекции.

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

Пример №3. Методом бисекции найти решение нелинейного уравнения на отрезке [a,b] с точностью ε = 10-2. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε = 10-4. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности число итераций.
sqrt(t)+x2 = 10, a = 2.6, b = 3

Найдем корни уравнения:
Используем для этого Метод половинного деления (метод дихотомии)..
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)<0. Метод дихотомии заключается в следующем.
Определяем половину отрезка c=1/2(a+b) и вычисляем f(c). Проверяем следующие условия:
1. Если |f(c)| < ε, то c – корень. Здесь ε - заданная точность.
2. Если f(c)f(a)<0, то корень лежит в интервале [a,c].
3. Если f(c)f(b)<0, то корень лежит на отрезке[c,b].
Продолжая процесс половинного деления в выбранных подынтервалов, можно дойти до сколь угодно малого отрезка, содержащего корень ξ.
Так как за каждую итерацию интервал, где расположен корень уменьшается в два раза, то через n итераций интервал будет равен:
bn-an=1/2n(b-a)
В качестве корня ξ. возьмем 1/2(an+bn). Тогда погрешность определения корня будет равна (bn – an)/2. Если выполняется условие:
(bn – an)/2 < ε
то процесс поиска заканчивается и ξ = 1/2(an+bn).
Решение.
Поскольку F(2.6)*F(3)<0, то корень лежит в пределах [2.6;3].
Итерация 1.
Находим середину отрезка: c = (2.6 + 3)/2 = 2.8
F(x) = -0.487
F(c) = -1.628
Поскольку F(c)•F(x) > 0, то a=2.8
Итерация 2.
Находим середину отрезка: c = (2.8 + 3)/2 = 2.9
F(x) = 0.113
F(c) = -0.487
Поскольку F(c)•F(x) < 0, то b=2.9
Итерация 3.
Находим середину отрезка: c = (2.8 + 2.9)/2 = 2.85
F(x) = -0.189
F(c) = 0.113
Поскольку F(c)•F(x) < 0, то b=2.85
Итерация 4.
Находим середину отрезка: c = (2.8 + 2.85)/2 = 2.825
F(x) = -0.339
F(c) = -0.189
Поскольку F(c)•F(x) > 0, то a=2.825
Остальные расчеты сведем в таблицу.

N c a b f(c) f(x)
1 2.6 3 2.8 -1.6275 -0.4867
2 2.8 3 2.9 -0.4867 0.1129
3 2.8 2.9 2.85 0.1129 -0.1893
4 2.8 2.85 2.825 -0.1893 -0.3386
5 2.825 2.85 2.8375 -0.3386 -0.2641
6 2.8375 2.85 2.8438 -0.2641 -0.2267
Ответ: x = 2.8438; F(x) = -0.2267
Решение было получено и оформлено с помощью сервиса Метод Ньютона онлайн

Пример №2. Локализовать корень нелинейного уравнения f(x) = 0 и найти его методом бисекции с точностью ε1 = 0,01. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации  с точностью ε2 = 0,0001. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности ε2 число итераций.

Аннуитетные платежи онлайн
Расчет аннуитетных платежей по схеме постнумерандо и пренумерандо с помощью удобного калькулятора.
Аннуитетные платежи онлайн
Подробнее
Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Налоговый вычет на обучение
√ 120 тыс. руб. - максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя
Подробнее
Курсовые на заказ