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

Опять рассмотрим задачу из примера 2.6, в которой требуется

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

минимизировать f(w)=(40—90w)²

при ограничении 0£ w £1.

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

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

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

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

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

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

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

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

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

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

w= XR—tⁿ или w= XL + tⁿ

в зависимости от того, какой подынтервал был исключен на предыдущей итерации — левый или правый. В приведенных выше формулах через tⁿ обозначена п-ястепень t, где п — количество вычислений значений функции.

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

Сравнение методов исключения интервалов

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

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

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

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

FR(N)=2/(N +l).

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

Таблица 2.1. Величины относительного уменьшения интервала.

Метод поиска	Количество вычислений значений функции
Метод поиска	N = 2	N = 5	N=10	N=15	N = 20
Метод деления интервала пополам	0,5	0,177	0,031	0,006	0,0009
Метод золотого сечения	0,618	0,146	0,013	0,001	0,0001
Метод равномерного поиска	0,667	0,333	0,182	0,125	0,095

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

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

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

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

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

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

N=(2/E)— 1.

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

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

Метод поиска	Заданная точность
Метод поиска	E = 0,1	E = 0,05	E=0,01	E = 0,001
Метод деления интервала пополам	7	9	14	20
Метод золотого сечения	6	8	11	16
Метод равномерного поиска	19	39	199	1999

Дата добавления: 2018-06-01; просмотров: 299; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 5 Следующая ⇒

Мы поможем в написании ваших работ!