Пример метода золотого сечения

Опять рассмотрим задачу из примера 2.6, в которой требуется минимизировать f(х)=(100-х)² в интервале 60£х£150. Для того чтобы перейти к интервалу единичной длины, проведем замену переменной, положив w=(х - 60)/90. Таким образом, задача принимает следующий вид: минимизировать f(w) = (40 – 90w)² при ограничении 0£w£1.

Итерация 1. I₁ = (0, 1); L₁ = l. Проведем два первых вы­числения значений функции:

w₁ = t = 0,618, f(w₁) = 244,0

w₂ = 1-t = t² = 0,382, f(w₂) = 31,6

Так как f(w₂) < f(w₁) и w₂ < w₁, интервал w ³ w₁ исключается.

Итерация 2. I₂ =(0. 0,618); L₂ = 0,618 = t. Следующее вы­числение значения функции проводится в точке

w₃ = t-t² = t(1-t) = t³ = 0,236, f(w₃) = 352.

Так как f(w₃) > f (w₂) и w₃ < w₂, интервал w £ w₃, исключается.

Итерация 3. I₃ =(0,236, 0,618); L₃ = 0,382 = t². Следующее вычисление значения функции проводится в точке, расположенной на расстоянии t ´ (длина полученного интервала) от левой гра­ничной точки интервала, или на расстоянии (1-t) ´ (длина ин­тервала) от правой граничной точки. Таким образом,

w₄ =0,618 – (1-t)L₃ = 0.618 - t² L₃ 0.618 - t²(t²) = 0.618 - t⁴ = 0,472, f(w₄) = 6,15.

Так как f(w₄) < f (w₂) и w₄ > w₂, интервал w £ w₂ исключается.

В результате получен следующий интервал неопределенности: 0,382 £ w £ 0,618 для переменной w, или 94,4£х£115,6 для перемен­ной х.

Если в процессе поиска проведено шесть вычислений значений функции, то длина результирующего интервала для переменной w равна

t_N-1 = t₅ = 0,09,

что соответствует интервалу длины 8,1 для переменной х. Для срав­нения напомним, что в аналогичной ситуации метод деления интер­вала пополам привел к получению интервала длины 11,25.

В общем случае если правая и левая граничные точки интервала неопределенности (обозначим их через XR и XL) известны, то ко­ординаты всех последующих пробных точек, получаемых в соответ­ствии с методом золотого сечения, можно вычислить по формулам

w = XR - tⁿ или w = XL + tⁿ, в зависимости от того, какой подынтервал был исключен на преды­дущей итерации – левый или правый. В приведенных выше форму­лах через tⁿ обозначена n-я степень t, где п – количество вычисле­ний значений функции.

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

Сравнение методов исключения интервалов. Ниже проводится сравнение относительных эффективностей рас­смотренных методов исключения интервалов. Обозначим длину неходкого интервала неопределенности через L₁, а длину интервала, получаемого в результате N вычислений значений функции, - через L_N. В качестве показателя эффективности того или иного метода исключения интервалов введем в рассмотрение характеристику относительного уменьшения исходного интервала FR(N)=L_N/L₁

Напомним, что при использовании метода деления интервала пополам и метода золотого сечения длина получаемого интервала составляет L₁(0,5)^N/2 и L₁(0.618)^N-1 соответственно. Следовательно, относительное уменьшение интервала после N вычислений значений функции равно

FR(N) = (0,5)^N/2 для метода деления интервала пополам;

FR(N) = (0,618) ^N-1 для метода золотого сечения.

Для сравнения рассмотрим также метод равномерного поиска, в соответствии с которым оценивание функции проводится в N равноотстоящих друг от друга точках (при этом интервал L₁ де­лится на (N+1) равных интервалов длины L₁/(N+l)). Пусть х* – точка, в которой наблюдается минимум функции f(х). Тогда точка истинного минимума f(x) оказывается заключенной в интервале

,

откуда L_N = 2L₁/(N+l). Следовательно, для метода равномерного поиска FR(N)=2/(N+1).

В табл. 6.2 представлены значения FR(N), соответствующие выбранным N, для трех методов поиска. Из таблицы следует, что поиск величины относительного уменьшения интервала с помощью метода золотого сечения

Таблица 6.2

обеспечивает наибольшее от­носительное уменьшение исходного интервала при одном и том же количестве вычислений значений функции. С другой стороны, можно также сравнить количества вычислений значения функции, требуе­мые для достижения заданной величины относительного уменьшения интервала или заданной степени точности. Если величина FR(N) = E задана, то значение N вычисляется по следующим формулам:

для метода деления интервала пополам

N=2 ln(E)/ln(0,5),

для метода золотого сечения

N=1+[ln(E)/ln(0,618)],

для метода равномерного поиска

N=(2/E)-1

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

Требуемые количества вычислений значений функции

Таблица 6.3