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

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

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

Сходимость метода дихотомии линейная с коэффициентом α=0,5. Покажем это.
Если в качестве x_n брать a_n, то из формулы (6) мы можем записать , . Отсюда следует .
Отметим, что за 10 итераций (n=10) интервал уменьшается в 2¹⁰ = 1024 ≈ 10³ раз. За 20 итераций (n=2) уменьшается в 2²⁰ ≈ 10⁶ раз.

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

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

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

Пример №1. Найти экстремум функции: y=5x²-4x+1 методом дихотомии, если ε=0.1, а исходный интервал [0,10].

• Решение
• Видео решение

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

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

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

Найдем корни уравнения:
Используем для этого Метод половинного деления (метод дихотомии)..
Считаем, что отделение корней произведено и на интервале [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 итераций интервал будет равен:
b_n-a_n=¹/₂ⁿ(b-a)
В качестве корня ξ. возьмем ¹/₂(a_n+b_n). Тогда погрешность определения корня будет равна (b_n – a_n)/2. Если выполняется условие:
(b_n – a_n)/2 < ε
то процесс поиска заканчивается и ξ = ¹/₂(a_n+b_n).
Решение.
Поскольку 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
Остальные расчеты сведем в таблицу.

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