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

Выбор длины шага из условия минимизации функции вдоль заданного направления

Коэффициенты a_k в методе (2.3) можно оп­ределять из условия

, (2.15)

где для методов спуска, т. е. при h^kÎ U(х^k, f), минимум берется по a ³ 0. Такой способ выбора a_k является в некотором смысле наилучшим, ибо он обеспечивает достижение наименьшего значения функции вдоль заданного направления. Однако он требует решения на каждом шаге одномерной задачи минимизации. Эти задачи ре­шаются, как правило, приближенно с помощью численных методов, что приводит к значительному объему вычис­лений.

В простейших случаях величины a_k, удается найти в явном виде.

Адаптивный способ отыскания коэффициентовa_k, не требую­щий дополнительных вычислений характеристик целевой функции

Ранее рассмотрен способ выбора коэф­фициентов a_k, требующий решения вспомогательных одномерных задач. В процессе их решения приходится, как правило, произво­дить дополнительные вычисления характеристик целевой функции f в точках, отличных от x⁰, х¹,..., x^k.

Ниже приводятся явные формулы для a_k. В них используются лишь значения f'(x^k) и некоторые константы, характеризующие глобальные свойства функции f. Эти формулы выбраны с целью обеспечить при соответствующих предположениях о f выполнение неравенства

, (2.17)

где e Î (0, 1), направление h^k таково, что áf'(x^k), h^kñ < 0 и, стало быть, h^kÎ U(х^k, f). Неравенство (2.17) необходимо для обоснования сходимости многих методов минимизации. Из него, в частности, сле­дует, что f(x^k+1) < f(х^k), и соответствующий метод минимизации является, таким образом, методом спуска.

Лемма 2.2. Пусть функция f дифференцируема наRⁿ, а ее градиент удовлетворяет условию Липшица

||f'(x) – f'(x')|| ³ M||x – x'||, x, x' ÎRⁿ, (2.18)

где М > 0.

Тогда для произвольных x^k ÎRⁿ, eÎ (0, 1) и x^k, удовлетворяю­щего неравенству áf'(x^k), h^kñ < 0, условие (2.17) выполнено при

. (2.19)

В этом ме­тоде точки располагаются близко к середине очередного отрез­ка [а; b] ,т.е.

(2)

где — малое число.

При этом отношение длин нового и исходного отрезков близко к 1/2, этим и объясняется название метода.

Отметим, что для любых точек величина , поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каж­дой итерации поиска . В конце вычислений по методу дихотомии в качестве приближенного значения берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство —— .

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить по формулам (2). Вычислить

Ш а г 2. Сравнить , если , то перейти к отрезку , иначе — к отрезку .

Ш а г 3. Найти достигнутую точность . Если , то перейти к следующей итерации, вернувшись к шагу 1. Если , то за­вершить поиск, перейдя к шагу 4.

Шаг 4. Положить .