Метод золотого сечения для чайников. Блок-схема метода "золотого сечения". Понятие и определение метода золотого сечения

Метод основан на делении текущего отрезка [а, b ], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего минимум (максимум).

Золотое сечение определяется по правилу: отношение всего отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки c и d , расположенные симметрично относительно середины отрезка.

Путем сравнения R (c ) и R (d ) определяют следующий отрезок, где содержится максимум. Если R (d ) > R (c ), то в качестве следующего отрезка выбирается отрезок [с, b ], в противном случае – отрезок [a , d ].

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [с, b ], т.е.

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

Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение R (x ), которую нетрудно получить:

Условие окончания поиска – величина отрезка, содержащего максимум, меньше заданной погрешности.

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

На рис. 3 приведены два этапа поиска максимума функции методом золотого сечения.

Рис. 3. Иллюстрация метода золотого сечения: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого золотого сечения в точках c и d ); 2 – то же, после второго этапа (новая точка е и старая точка d )

Алгоритм метода золотого сечения для минимизации функции.

Начальный этап. Выбрать допустимую конечную длину интервала неопределённости l > 0. Пусть [а , b ] – начальный интервал неопределённости. Положить
и
. Вычислить R (c ) и R (d ), положить k = 1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если b k – a k < l , то остановиться; точка минимума принадлежит интервалу [а k , b k ]. В противном случае если R (c k ) > R (d k ), то перейти к шагу 2, а если R (c k ) ≤ R (d k ), то к шагу 3.

Шаг 2. Положить a k +1 = c k и b k +1 = b k ,
. Вычислить R (d k +1) и перейти к шагу 4.

Шаг 3. Положить a k +1 = a k и b k +1 = d k ,
. Вычислить R (c k +1) и перейти к шагу 4.

Шаг 4. Заменить k на k + 1 и перейти к шагу 1.

Пример.

Дана функция R (x ) = D sin(Ах B + С), где коэффициенты имеют следующие значения: А = 1,0, В = 1,0, С = 1,0, D = 1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: ε =0,05.

Результаты расчетов. Для "запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]:

x 1 =0,145898, х 2 =0,85410197.

Значения критериев в этих точках соответственно R(x 1) = 0,911080, R (x 2) = 0,960136. Следовательно, новым отрезком является , внутри которого находится максимальное из найденных значений R . Точка золотого сечения для нового отрезка будет x 3 =0,58359214, a R (x 3) =0,99991813. Далее приведены только координаты лучших точек при очередном шаге, номер шага и значения критерия в этих точках.

х 3 = 0,58359214; R 3 = 0,99991813;

х 4 =0,58359214; R 4 = 0,99991813

х 5 = 0,58359214; R 5 = 0,99991813;

х 6 = 0,58359214; R 6 = 0,99991813

х 7 = 0,58359214; R 7 = 0,99991813;

х 8 = 0,55920028; R 8 = 0,99993277;

х 9 = 0,55920028; R 9 = 0,99993277.

Всего было проведено 10 вычислений критерия оптимальности.

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

Предположим, что имеется интервал неопределенности (x 1 ,x 3) и известно значение функции f(x 2) внутри этого интервала (см. рис. 9.3). Если можно вычислить функцию всего один раз в точке х 4 , то где следует поместить точку х 4 , для того чтобы получить наименьший возможный интервал неопределенности ?

Рис. 9.3.

Положим х 2 –х 1 =L и х 3 –х 2 =R , причем L > R , как показано на рис. 9.3 , и эти значения будут фиксированы, если известны x 1 , x 2 и х 3 . Если х 4 находится в интервале (х 1 ; х 2) , то:

если f(x 4) < f(x 2) , то новым интервалом неопределенности будет (x 1 ,x 2) длиной х 2 –х 1 =L ;
если f(х 4)>f(x 2) , то новым интервалом неопределенности будет (х 4 ,х 3) длиной х 3 –х 4 .

Поскольку не известно, какая из этих ситуаций будет иметь место, выберем х 4 таким образом, чтобы минимизировать наибольшую из длин х 3 -х 4 и х 2 -х 1 . Достигнуть этого можно, сделав длины х 3 – х 4 и х 2 – х 1 равными т.е. поместив х 4 внутри интервала симметрично относительно точки х 2 , уже лежащей внутри интервала. Любое другое положение точки х 4 может привести к тому, что полученный интервал будет больше L . Помещая х 4 симметрично относительно х 2 , мы ничем не рискуем в любом случае. Если окажется, что можно выполнить еще одно вычисление функции, то следует применить описанную процедуру к интервалу (х 1 , х 2) , в котором уже есть значение функции, вычисленное в точке х 4 , или к интервалу (х 4 ,х 3) , в котором уже есть значение функции, вычисленное в точке х 2 .

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

На n -м вычислении n -ю точку следует поместить симметрично по отношению к (n - 1) -й точке. Положение этой последней точки в принципе зависит от нас. Для того чтобы получить наибольшее уменьшение интервала на данном этапе, следует разделить пополам предыдущий интервал. Тогда точка х будет совпадать с точкой х n-1 . Однако при этом мы не получаем никакой новой информации. Обычно точки х n-1 и х n отстоят друг от друга на достаточном расстоянии, чтобы определить, в какой половине, левой или правой, находится интервал неопределенности . Они помещаются на расстоянии е/2 по обе стороны от середины отрезка L n-1 ; можно самим задать величину е или выбрать эту величину равной минимально возможному расстоянию между двумя точками.

Интервал неопределенности будет иметь длину L n , следовательно, L n-1 = 2L n - е (рис.9.4 , нижняя часть). На предыдущем этапе точки х n-1 и х n-2 должны быть помещены симметрично внутри интервала L n-2 на расстоянии L n-2 от концов этого интервала. Следовательно, L n-2 = L n-1 +L n (pис.9.4 , средняя часть).

Рис. 9.4.

Замечание . Из рисунка ясно, что на предпоследнем этапе х n-2 остается в качестве внутренней точки.

Аналогично L n-3 =L n-2 +L n-1 (pис. 9.4 , верхняя часть)

В общем случае L j-1 =L j + L j+1 при 1

Таким образом,

Если определить последовательность чисел Фибоначчи следующим образом: F 0 =1, F 1 =l , и F k =F k-1 +F k-2 для k = 2, 3,.. ., то

Следовательно, произведя n вычислений функции, мы уменьшим начальный интервал неопределенности в l/F n раз по сравнению с его начальной длиной (пренебрегая е), и это - наилучший результат.

Если поиск начат, то его несложно продолжить, используя описанное выше правило симметрии. Следовательно, необходимо найти положение первой точки, которая помещается на расстоянии L 2 от одного из концов начального интервала, причем не важно, от какого конца, поскольку вторая точкa помещается согласно правилу симметрии на расстоянии L 2 от второго конца интервала:

(2.4)

После того как найдено положение первой точки, числа Фибоначчи больше не нужны. Используемое значение е может определяться из практических соображений. Оно должно быть меньше L 1 \F n+x , в противном случае мы будем напрасно тратить время на вычисление функции.

Таким образом, поиск методом Фибоначчи , названный так ввиду появления при поиске чисел Фибоначчи , является итерационной процедурой. В процессе поиска интервала (x1; x2) с точкой х 2 , уже лежащей в этом интервале, следующая точка х 2 всегда выбирается такой, что х 3 –х 4 = х 2 –х 1 или х 4 -х 1 = х 3 -x 2 , т.е. x 4 =х 1 -х 2 +х 3 .

Если f(x 2) = f 2 и f(x 4) = f 4 , то можно рассмотреть четыре случая (рис. 9.5).

Рис. 9.5.

Следующий из методов одномерной оптимизаци называется методом "золотого сечения" .

Не всегда можно заранее определить, сколько раз придется вычислять функцию. В методе Фибоначчи это нужно знать для определения L 2 , т.е. положения начальной точки (см. уравнение 2.4).

Метод "золотого сечения" почти столь же эффективен, как и метод Фибоначчи , однако при этом не требуется знать n - количество вычислений функции, определяемое вначале. После того как выполнено j вычислений, исходя из тех же соображений, что и ранее (см. уравнение 2.1), записываем

Т.е.

Таким образом, , откуда . Тогда

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

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

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

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

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

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

w 3 = t-t 2 = t(1-t) = t 3 = 0,236, f(w 3) = 352.

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

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

w 4 =0,618 – ( 1-t)L 3 = 0.618 - t 2 L 3 0.618 - t 2 (t 2) = 0.618 - t 4 = 0,472, f(w 4) = 6,15.

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

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

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

t N -1 = t 5 = 0,09,

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

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

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

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

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

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

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

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

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

откуда L N = 2L 1 /(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+,

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

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

В основе этого метода лежит понятие "золотого сечения", введенного Леонардо да Винчи и используемого, в частности, при построении архитектурных сооружений античности и эпохи Возрождения.

Золотым сечением отрезка называется его разбиение на две неравные части, так, что отношение длины всего отрезка к длине его большей части равно отношению длины большей части к длине меньшей части (рис.1.3, слева)

Золотое сечение осуществляется двумя точками x1 и x2, расположенными симметрично относительно середины отрезка (рис.1.3, справа). Нетрудно проверить, что

Точка x1 осуществляет золотое сечение не только отрезка , но и отрезка , а точка x2 осуществляет золотое сечение не только отрезка , но и отрезка . Действительно,

Из (1.10) и (1.11) получаем:

x1 = a + , x2 = a +. (1.12)

Формулы (1.12) являются основными расчетными формулами метода золотого сечения.

Из (1.12) следует, что x1 + x2 = a + b. Если обозначить r = , то формулы (1.12) можно переписать так:

x1 = b - r(b - a), x2 = a + r(b - a) (1.13)

Процедура деления отрезка такая же, как и для методов дихотомии и Фибоначчи. Вычисляются значения функции в выбранных точках: f(x1) и f(x2). Определяется новый отрезок локализации следующим образом:

если f(x1) f(x2), то a1 = a, b1 = x2;

если f(x1) > f(x2), то a1 = x1, b1 = b.

Так же, как и в методе Фибоначчи, одна из пробных точек x1, x2 станет пробной точкой на новом отрезке локализации. Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.

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

После выполнения n итераций погрешность удовлетворяет следующему неравенству:

Условием окончания вычислений является выполнение неравенства n <.

Алгоритм 1.4 (Алгоритм метода золотого сечения).

Шаг 1. Ввести исходные данные: a, b, . Положить r = , n = .

Шаг 2. Определить x1 и x2 по формулам (1.13).

Шаг 3. Вычислить f(x1) и f(x2).

Шаг 4. Проверить критерий окончания вычислений. Если n <, перейти к шагу 5, иначе - к шагу 6.

Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x1) f(x2), то положить b = x2, x2 = x1, f(x2) = f(x1), x1 = b - r(b - a) и вычислить f(x1). Иначе положить a = x1, x1 = x2, f(x1) = f(x2), x2 = a + r(b - a) и вычислить f(x2).

Положить n = rn и перейти к шагу 4.

Шаг 6. Положить x* . Вычислить f * f(x*).

Реализация в пакете MathCAD 14

Найдем минимум функции f(x), x с точностью до

В итоге получаем f(x*) = -3.749, x*=0.382 с точностью за 18 итераций.

Используйте метод золотого сечения для того, чтобы отыскать с точностью \varepsilon локальный максимум функции на отрезке .

Входные данные

a, b — концы отрезка, на котором требуется найти максимум, и точность \varepsilon.

Выходные данные

Точка локального максимума и локальный максимум в формате (x_{max}, y_{max}).

Тесты

\varepsilon	a	b	(x_{max}, y_{max})
0.001	1.05	2.2	(1.74435, 0.951781)
0.0001	1.05	2.2	(1.74417, 0.951781)
0.0001	5.7	8	(7.57498, 3.68407)
0.0001	3	4	(3.61901, 2.31289)

Алгоритм

Для начала проанализируем данную нам функцию. Найдем ее область определения.

D(f) = x^2 + 1 + \cos x > 0

D(f) = x^2 + 1 + \cos x = x^2 + \frac{1}{2} \cos^2 \frac{x}{2} > 0 \forall x \in \mathbb{R}

Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику).
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывных , унимодальных функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума x_{max}.

x_1 \le x_2 \le x_{max} \Rightarrow f(x_1) \le f(x_2) \lef(x_{max})

X_1 \ge x_2 \ge x_{max} \Rightarrow f(x_1) \le f(x_2) \lef(x_{max})

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

Проведя анализ функции, обратимся к самому методу золотого сечения.

Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки x_1 и x_2 такие, что

\frac{b — a}{b — x_1} = \frac{b — a}{x_2 — a} = \varphi = \frac{1 + \sqrt{5}}{2}

То есть точка x_1 делит отрезок в отношении золотого сечения. Аналогично x_2 делит отрезок в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

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