Метод деления отрезка пополам

Этот алгоритм используется для нахождения минимума функции. Если необходимо найти нули функции, то используется другой алгоритм.

Примеры правильного написания F(x):
1) 10•x•e^2x записываем как: 10*x*exp(2*x)
2) x•e^-x+cos(3x) ≡ x*exp(-x)+cos(3*x)
3) x³-x²+3 ≡ x^3-x^2+3

Скачать пример оформления

Рассмотрим последовательный поиск точки x_ф ∈ [0;1], в которой унимодальная на отрезке [0,1] функция f(x) достигает наименьшего значения f₀=f(x₀).
Метод прямого поиска, основанный на делении пополам отрезка, на котором находится точка x₀, называют методом дихотомии.

Рис.1

Алгоритм метода дихотомии

Пусть известно, что на k-м шаге последовательного поиска x_ф ∈ [a_k;b_k] ⊂ [0;1] (на первом шаге при k=1 имеем a₁=0 и b₁=1). На отрезке [a_k, b_k] длиной l_k выберем две точки x_k₁=(a_k+b_k)/2-δ и x_k₂=(a_k+b_k)/2+δ (рис. 1), где δ>0 — некоторое достаточно малое число. Вычислим значения f(x_k₁) и f(x_k₂) функции f(x) в этих точках и выполним процедуру исключения отрезка.
Если f(x_k₁) < f(x_k₂), то в силу унимодальности функции f(x) имеем x_ф ∈ [a_k;x_k2], а отрезок [x_k₂,b_k] исключаем из дальнейшего рассмотрения.
Наоборот, если f(x_k₁) ≥f(x_k₂), то x_ф ∈ [x_k1;b_k], а отрезок [a_k,x_k₁] не рассматриваем. В результате получим новый отрезок [a_k+l;b_k+l] ⊂ [a_k;b_k].
Если длина l_k₊₁ нового отрезка больше заданной наибольшей допустимой длины ε₀интервала неопределенности, то алгоритм метода дихотомии переходит к (k+1)-му шагу, повторяя все описанные для k-го шага действия. Если же l_k≤ε₀, то вычисления прекращают и полагают x₀=(a_k₊₁+b_k₊₁)/2.
Так как l_k₊₁=l_k/2+δ или l_k₊₁-2δ =(l_k-2δ)/2, то

.
Из этого равенства выводим следующую формулу длины l_k отрезка [a_k,b_k], получаемого на k-м шаге метода дихотомии:

. (1)
Из (1) следует, что l_k₊₁→2δ при k→∞, но при этом l_k₊₁>2δ. Поэтому выполнение неравенства l_k₊₁<ε₀, означающее достижение заданной точности нахождения точки x_ф, возможно лишь при условии выбора 2δ<ε₀. Кроме того, нужно учитывать неизбежную погрешность, возникающую при вычислении приближенных значений

функции f(x). Это приводит к дополнительной погрешности ∆₀ при нахождении точки x₀ (см. 2). Поэтому выбор значения δ ограничен и снизу, т.е.
∆₀< 2δ<ε₀. (2)
Если эти неравенства нарушаются, то знак разности

может не совпадать со знаком разности f(x_k₁)-f(x_k₂), что приводит к ошибочному выполнению процедуры исключения отрезка.
Итак, метод дихотомии — это последовательное построение на каждом k-м шаге поиска точек x_k₁=(a_k+b_k)/2-δ и x_k₂=(a_k+b_k)/2+δ, симметричных относительно середины отрезка [a_k,b_k] длины l_k. После выполнения k-го шага будет выделен отрезок [a_k₊₁,b_k₊₁] длины l_k₊₁ и вычислено N=2k значений функции. Используя формулу (1) для длины отрезка (интервала неопределенности) и полагая l₁=1, получаем

. (3)
Отметим, что после исключения отрезка на k-м шаге описанного алгоритма точки x_k₁ и x_k₂ принадлежат новому отрезку [a_k₊₁,b_k₊₁], причем одна из них является внутренней для этого отрезка. Но вычисленное в этой точке значение функции f(x) в методе дихотомии не используют для исключения отрезка на следующем шаге, а проводят вычисления в двух новых точках. Существуют методы последовательного поиска, в которых на каждом k-м шаге начиная с k=2 вычисляют лишь одно новое значение функции в точке, принадлежащей отрезку [a_k₊₁,b_k₊₁]. Это значение вместе с уже вычисленным на предыдущем шаге значением функции во внутренней точке отрезка [a_k,b_k] используют при выполнении процедуры исключения отрезка на следующем шаге последовательного поиска.

Пример. Пользуясь методом дихотомии (методом одномерного поиска), минимизировать следующую функцию с точностью до одного знака после запятой: f(x)=3x⁴+(x-1)²

Решение.
x = (0+4)/2 = 2
Шаг приращения δ=0.1
Положим a₁ = a, b₁ = b. Вычислим x₁₁=x-δ=2-0.1=1.9, x₁₂=x+δ=2+0.1=2.1.
Вычислим f(x₁₁) = 39.9063, f(x₁₂) = 59.5543
Итерация №1.
Поскольку f(x₁₁) < f(x₁₂), то b₂ = 2.1, a₂ = a₁, x₂₂ = 1.9
f(x₂₁) = 2.446, f(x₂₂) = 39.9063
Итерация №2.
Поскольку f(x₂₁) < f(x₂₂), то b₃ = 1.9, a₃ = a₂, x₃₂ = 0.95
f(x₃₁) = 1.5885, f(x₃₂) = 2.446
Итерация №3.
Поскольку f(x₃₁) < f(x₃₂), то b₄ = 0.95, a₄ = a₃, x₄₂ = 0.85
f(x₄₁) = 0.45, f(x₄₂) = 1.5885
Итерация №4.
Поскольку f(x₄₁) < f(x₄₂), то b₅ = 0.85, a₅ = a₄, x₅₂ = 0.375
f(x₅₁) = 0.4891, f(x₅₂) = 0.45
Остальные расчеты сведем в таблицу.

N	a_n	b_n	b_n-a_n	x_n1	x_n2	F(x_n1)	F(x_n2)
1	0	4	2	1.9	2.1	39.9063	59.5543
2	0	2.1	2.1	0.95	1.9	2.446	39.9063
3	0	1.9	1.9	0.85	0.95	1.5885	2.446
4	0	0.95	0.95	0.375	0.85	0.45	1.5885
5	0	0.85	0.85	0.325	0.375	0.4891	0.45
6	0.325	0.85	0.525	0.375	0.6875	0.45	0.7679
7	0.325	0.6875	0.3625	0.4063	0.375	0.4343	0.45
8	0.325	0.375	0.05	0.25	0.4063	0.5742	0.4343

Находим x как середину интервала [a,b]: x=(0.375+0.325)/2 = 0.35.
Ответ: x = 0.35; F(x) = 0.46751875

Метод деления отрезка пополам

Алгоритм метода дихотомии

Правила ввода данных

Поиск

Процесс

Сообщение