Методы исключения отрезков

В методе перебора, рассмотренном выше, точки x_i, в которых оп­ределяются значения f (x), выбирают заранее. Если же для выбора очередной точки вычисления (измерения) f (x) использовать информа­цию, содержащуюся в уже найденных значениях f (x), то поиск точки минимума можно сделать более эффективным, т.е. сократить число определяемых для этого значений f (x), как, например, в методе пораз­рядного поиска.

На один из путей такого более эффективного поиска точки х * ука­зывает свойство 3 унимодальных функций (см. формулу (2.3)).

Пусть а < x ₁ <х ₂ <b. Сравнив значения f (x) в точках x ₁ и х ₂ (проб­ных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [ а; х ₂], если или к отрезку m [ x _1; b ] если (рис. 2.6). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку миниму­ма. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить , где — одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков.

Чтобы относительное уменьшение отрезка на каждой итерации не зависело от того, какая из его частей исключается из дальнейшего рассмотрения, пробные точки следует располагать симметрично относительно середины исходного отрезка. В зависимости от способа вы­бора пробных точек получаются различные методы исключения отрез­ков. На практике используются следующие.

Первый метод деления отрезка пополам (дихотомии). В этом методе точки x ₁ и х ₂располагаются близко к середине очередного отрезка [ а; b ], т.е:

, (2.11)

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

Отметим, что для любых точек x ₁ и х ₂ величина t > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каж­дой итерации поиска х*.

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

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

Шаг 1. Определить x ₁ и х ₂ по формулам (2.11). Вычислить f (x ₁) и f (x ₂).

Шаг 2. Сравнить f (x ₁) и f (x ₂). Если , то перейти к отрезку [ а; x ₂], положив b = x ₂ , иначе — к отрезку [ x ₁; b ], положив а = x ₁ .

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

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

Замечания:

1. Число d из (2.11) выбирают на интервале (0;2e) с учетом сле­дующих соображений:

а) чем меньше d, тем больше относительное уменьшение длины отрезка на каждой итерации, т.е. при уменьшении d достигается более высокая скорость сходимости метода дихотомии;

б) при чрезмерно малом d сравнение значений f (x) в точках x ₁ и х _2, отличающихся на величину d, становится затруднительным. Поэтому вы­бор d должен быть согласован с точностью определения f (x) и с количе­ством верных десятичных знаков при задании аргумента х.

2. Число п итераций метода дихотомии, необходимое для опреде­ления точки х * с точностью до e, определяется неравенством

. (2.12)

Обозначим длину исходного отрезка [ а; b ] через D₀. Длина отрезка, полученного после первой итерации, будет D₁ = , после второй итерации , после третьей — , и т.д.

Таким образом, в результате п итераций длина отрезка поиска точки х * станет .

При этом будет достигнута точность определения точки минимума . Находя п из условия

, (2.13)

получаем неравенство (2.12).

3. Величина d может быть выбрана достаточно малой, поэтому, пренебрегая ею в (2.12), получаем: . На каждой итерации метода дихотомии вычисляют два значения f (x). Поэтому после N вы­числений f (x) производят n= N /2 итераций и достигают точность определения х *:

. (2.14)

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

Решить задачу, приведенную в примерах 2.3 и 2.4:

, , e=0,1.

Выберем d=0,02.

Итерация 1.

Шаг 1. x ₁ = 0,49, x ₂ = 0,51. f (x) = 0,670, f (x ₂) = 0,688.

Шаг 2. f (x ₁) > f (x ₂), поэтому полагаем a = x ₁ = 0,49.

Шаг 3. (b-а)/2 = 0,255 > 0,1, т.е. переходим к следующей итерации. Результаты вычислений на остальных итерациях записаны в табл. 2.2.

Таблица 2.2

Номер итерации	а	b	b-a	x 1	x 2	f (x 1)	f (x 2)	Сравнение f (x 1) и f (x 2)
	0,49		0,26	0,735	0,755	0,771	0,792	f (x 1) < f (x 2)
	0,49	0,755	0,13	0,613	0,633	0,683	0,691	f (x 1) < f (x 2)
	0.49	0,633	0,07	0,07 < 0,1 — точность достигнута

Таким образом, , f^*» f (0,56)» 0,67 (сравните с результатами решения примеров 2.3 и 2.4).

Метод золотого сечения. Рассмотрим такое симметричное распо­ложение точек x ₁ и х ₂ на отрезке [ а; b ], при котором одна из них ста­новится пробной точкой и на новом отрезке, полученном после иск­лючения части исходного отрезка. Использование таких точек позво­ляет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x),так как дру­гое значение уже найдено на одной из предыдущих итераций.

Найдем точки x ₁ и х ₂ , обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предпо­ложим, что при его уменьшении исключается правая часть этого от­резка. Пусть х ₂ = t, тогда симметрично расположенная точка х ₁ = 1-t (рис. 2.7).

Рис. 2.7. Определение пробных точек в методе золотого сечения

Пробная точка х ₁ отрезка [0; 1] перейдет в пробную точку х ₂¢ = 1-t нового отрезка [0; т]. Чтобы точки х ₂ = t, и х ₂¢ = 1-t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство или , откуда находим положительное значение … Таким образом, х ₁ = 1-t = , .

Для произвольного отрезка [ а; b ] выражения для пробных точек примут вид

; . (2.15)

Замечания:

1. Точки x ₁ и х ₂ из (2.15) обладают следующим свойством: каждая из них делит отрезок [ а; b ] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [ а; b ]. Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (2.15) одна из них переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [ а; х ₂], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х ₂^’ = х ₁) (рис. 2.7). В случае перехода к отрезку [ х ₁; b ] пробная точка исходного отрезка стано­вится первой пробной точкой отрезка [ х ₁; b ].

3. Легко проверить, что х ₁ =а+b-х ₂ , и x ₂ =а+b-х ₁. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (2.15).

4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков .

На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении , поэтому в результате п итераций его длина становится . Таким образом, точность e _n определения точки х* после п итераций находятиз равенства

, (2.16)

а условием окончания поиска точки х * с точностью e служит неравен­ство e_n £ e.

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

Шаг 1. Найти х ₁ и х ₂ по формулам (2.15). Вычислить f (x ₁) и f (x ₂). Положить , .

Шаг 2. Проверка на окончание поиска: если e _n > e, то перейти к шагу 3, иначе — к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x ₁) £ f (x ₂) то положить b = x ₂ , x ₂ =x ₁, f (x ₂) £ f (x ₁), x ₁= b- t(b-a) и вычислить f (x ₁), иначе — положить a = x ₁, x ₁ = x ₂, f (x ₁) = f (x ₂), x ₂= b+ t(b-a) и вычислить f (x ₂). Положить e _n = te _n и перейти к шагу 2.

Шаг 4. Окончание поиска: положить , .

Пример 2.6. Метод золотого сечения.

Решить задачу, приведенную в примере 2.3: f (x) = x ⁴ + е^-x ®min, x Î [0; I], e=0,l.