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

Метод основан на делении текущего отрезка [а, 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 вычислений критерия оптимальности.

Предположим, что имеется интервал неопределенности (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) , то:

1. если f(x 4) < f(x 2) , то новым интервалом неопределенности будет (x 1 ,x 2) длиной х 2 –х 1 =L ;
2. если 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 , средняя часть).

Замечание . Из рисунка ясно, что на предпоследнем этапе х 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).

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

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

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

Т.е.

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

Этот алгоритм используется для нахождения минимума функции . Если необходимо найти нули функции, то используется другой алгоритм .

Правила ввода функции

Не всегда можно определить заранее, сколько раз придется вычислять функцию. Метод золотого сечения почти столь же эффективен при n-2, что и метод Фибоначчи , однако при этом не требуется знать n – количество вычислений функции.
Сущность этого метода заключается в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большего отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего (рис 3).

где τ - «золотое сечение»


На каждом шаге этой итеративной процедуры, кроме первого, вычисляется только одно значение функции. Однако Химмельблау рекомендовал вычислять на каждом шаге две точки, для того чтобы не накапливалась погрешность, так как τ имеет приближенное значение (рис 4).
Если длина конечного интервала неопределенности равна δ, то для достижения требуемой точности число вычислений значений функции по методу золотого сечения можно найти по условию

Пример . Методом золотого сечения найти точку минимума x * функции f(x) на отрезке с точностью ε и значение целевой функции в этой точке:
f(x)=x 4 +2x 2 +4x+1=0 , [-1;0], ε=0.1
Решение . Положим a 1 = a, b 1 = b. Вычислим λ 1 = a 1 + (1- 0.618)(b 1 - a 1), μ 1 = a 1 + 0.618(b 1 - a 1).
Вычислим f(λ 1) = -0.5623, f(μ 2) = -0.2149
Итерация №1 .
Поскольку f(λ 1) μ 2 = a 2 + 0.618(b 2 - a 2) = -1 + 0.618(-0.382 +1), f(μ 2) = f(-0.618) = -0.2149
Итерация №2 .
Поскольку f(λ 2) > f(μ 2), то a 3 = -0.7639, b 3 = b 2 , λ 3 = -0.618
μ 3 = a 3 + 0.618(b 3 - a 3) = -0.7639 + 0.618(-0.382 +0.7639), f(μ 3) = f(-0.5279) = -0.5623
Итерация №3 .
Поскольку f(λ 3) μ 4 = a 4 + 0.618(b 4 - a 4) = -0.7639 + 0.618(-0.5279 +0.7639), f(μ 4) = f(-0.618) = -0.4766
Итерация №4 .
Поскольку f(λ 4) μ 5 = a 5 + 0.618(b 5 - a 5) = -0.7639 + 0.618(-0.618 +0.7639), f(μ 5) = f(-0.6738) = -0.5623
Остальные расчеты сведем в таблицу.

Опять рассмотрим задачу из примера 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 приведены данные о количествах вычислений значений функции, необходимых для определения координаты точки мини­мума с заданной точностью. Следует еще раз подчеркнуть, что метод золотого сечения оказывается более эффективным по сравнению с остальными двумя методами, поскольку он требует наименьшего числа оцениваний значения функции для достижения одной и той же заданной точности.