Метод золотого сечения пример решения экстремум функции. Блок-схема метода "золотого сечения"

О методе Золотого Сечения:

Безусловно, простой и быстрый метод. И как водится, скорость не способствует аккуратности. Это я о том, что если на заданном интервале поиска будут находиться несколько минимумов (максимумов), то данный алгоритм легко может вернуть локальный (не самый большой, не абсолютный) экстремум.

Задание:

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

В программе есть смысл оформить следующие классы и модули :

1. Модуль листа Excel (SheetGoldCutting), на котором как на форме будут располагаться необходимые органы управления ходом тестирования;
2. Форма для ввода данных FormDann;
3. Класс ExtremGC, вычисляющий координаты точки экстремума с заданной точностью, а также массив точек графика функции на заданном интервале (для отображения на диаграмме);
4. Стандартный модуль GoldCutting для описания глобальных констант, переменных и функций.

Например, так...

Рис.1 Рабочий лист Excel с диаграммой, двумя командными кнопками и кнопками выбора функции

Рис.2 Форма для ввода исходных данных

Данная форма вызывается явно при щелчке по первой командной кнопке (расположенной на листе Excel) или косвенно, если в момент нажатия на вторую командную кнопку (расположенную на листе Excel), исходные данные не обеспечивают необходимых условий начала выполнения алгоритма.
Для удобства пользователя, все элементы TextBox допускают ввод только числовых значений.
При щелчке по кнопке «Отмена» все переменные получат значения, которые существовали на момент открытия формы.

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

Private Sub Workbook_Open()
" радиокнопки нумеруются в этой книге от 5 до 9.
" Поэтому по умолчанию выделяю первую кнопку.
Sheets(1).Shapes("Option Button 5").ControlFormat.Value = 1
SheetGoldCutting.OptBut1_Click
End Sub

Метод theAlgoritm класса ExtremGC , который, собственно, и выполняет определение координат точки экстремума выглядит приблизительно так:

"Нахождение экстремума функции на отрезке. Метод золотого сечения
Public Sub theAlgoritm(v1 As Double, v2 As Double, v3 As Double, v4 As Double, findMax As Boolean)
Dim x1 As Double, x2 As Double, y1 As Double, y2 As Double, sme As Double
FullArrayOnly v1, v2, v3, v4 "для проверки допустимости аргумента

If Not BadDann Then

Zc = (1 + Sqr(5)) / 2
n = 0 "количество разбиений (переменная модуля класса)
Do While b - a > ep
sme = (b - a) / zc
x1 = b - sme: x2 = a + sme
y1 = theFunc(x1): y2 = theFunc(x2)
If findMax Then
"поиск максимума
If y1 a = x1
Else
b = x2
End If
Else
"поиск минимума
If y1 >= y2 Then
a = x1
Else
b = x2
End If
End If
n = n + 1 "количество разбиений (переменная модуля класса)
Loop
dxk = Abs(b - a) " конечное значение шага
xe = (a + b) / 2: ye = theFunc(xe) " результат: координаты точки экстремума

End If
End Sub

Где
FullArrayOnly - закрытый метод класса для проверки допустимости аргумента и заполнения массива точек графика;
BadDann – флаг допустимости аргумента;
zc – константа золотого сечения;
a, b – границы интервала;
ep – заданная точность поиска ε ;
findMax – параметр, характеризующий режим поиска (при true ищется максимум, при false – минимум);
theFunc(x As Double) As Double – метод класса, возвращающий значение тестируемой функции в зависимости от значение аргумента.

Кому интересен остальной код – обращайтесь…
Если нужно что-то изменить в проекте под Ваши требования (например, заменить функции) – пожалуйста, проблем не будет!

исходный код уже открыт. Используйте !

Если у Вас не появляется форма ввода данных, значит вы забыли включить макросы…

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

Чтобы увидеть, как ошибается алгоритм и находит локальный экстремум вместо абсолютного, задайте достаточно большой интервал (например: от 0 до 25) для 4 или 5 функций, имеющих явную периодичность…

Основная идея данного метода – сокращение числа n ш вычислений функции на каждом шаге (кроме первого)до 1 (минимально возможного значения) с дальнейшим использованием при поиске минимума второй пробной точки каждого шага, которая попадает внутрь нового доверительного интервала. Несмотря на то, что доверительный интервал сокращается при этом существенно менее, чем в два раза (в отличие от дихотомии), данный метод за счёт уменьшения n ш работает в общем значительно быстрее.

Золотым сечением отрезка [a,b ]называется такое его деление промежуточной точкой с , при котором выполняется соотношение (рис 10.12 а), где ξ – коэффициент золотого сечения.

Рис 10.12. Прямое и обратное золотые сечения отрезка

Выразим через xи отрезок ab отрезки ас и cb : аc = x ab; cb= x ac = x 2 ab .

Из условия аc + cb = ab после подстановки данных выражений и сокращения на аb получим следующее квадратное уравнение относительно x:

x 2 + x - 1 = 0 .

Решая его, находим корни:

Отбрасывая отрицательный корень, получим искомую величину отношения:

Разбивать отрезок [a,b ]можно не только в прямом, но и в обратном направлении – от b к a . Аналогичная точка d лежит симметрично с относительно средней точки интервала (a+b )/2(рис.10.12 б).

Величину отношения ad/ab получим, вычитая x из 1:

Точки d , с , задающие обратное и прямое разбиение отрезка в золотом сечении, обладают следующими свойствами.

1. Если отбросить часть отрезка [а,d ], то с d, b ].

2. Если отбросить часть отрезка [с, b ], то d – золотое сечение оставшейся части [a, с ].

Данные свойства можно доказать непосредственной подстановкой значений

Допустим, необходимо с точностью e найти минимум унимодальной функции F (x ) на [a,b ].

Предварительные действия (Шаг 0) .

Доверительный отрезок принимаем равным заданному: а 0 = а, b 0 = b .

Шаги i (i>0) выполняются в цикле при выполнении условия (b i - a i > e).

Шаг 1 . 1. Расчет положения двух пробных точек:

х 2 =а 0 + x(b 0 - а 0)» а 0 + 0,618 (b 0 - а 0);

х 1 = ( b 0 + а 0) - x 2 » а 0 + 0,382(b 0 - а 0).

2. Расчет значений функций F (x 1) и F (x 2).

3. Анализ значений функции в точках х 1 , х 2 и изменение доверительного отрезка по аналогии с дихотомией:

а) при F (x 1) ³ F (x 2) принимаем: a 1 = х 1 , х 1 = х 2 , b 1 = b 0 ,

б) при F (x 1) < F (x 2) принимаем: a 1 = а 0 , х 2 = х 1 , b 1 = х 2 .

4. Проверка окончания цикла: если (b 1 - a 1) > e -продолжение цикла, иначе - выход.

Шаги i (i>1) . Из предыдущей итерации (i -1) известно одно значение функции F (x ) во внутренней точке х доверительного отрезка [a i - 1 ; x i - 1 ]. Поэтому для сокращения достаточно ввести только одну новую пробную точку.

1. Расчет положения новой пробной точки: х¢ = (b i - 1 + а i - 1) - х , расчет значения функции F (x¢ ).

2. Упорядочение пробных точек х , х¢ и значений функции в них:

если (х < х¢ ), то { х 1 = х ; F (x 1)=F (x ); х 2 = х¢ ; F (x 2)=F (x¢ ) };

иначе { х 1 = х¢ ; F (x 1)=F (x¢ ) ; х 2 = х ; F (x 2)=F (x ) }.

Пункты 3 и 4 совпадают с шагом 1.

Скорость сходимости и точность метода. Так как на каждом шаге длина доверительного отрезка сокращается в t = 1/x » 1,618 раз, то длина[a 1 ,b 1 ] связана с длиной [a, b ] следующим образом: b 1 - a 1 = x (b 0 - a 0) =x (b - a ).

По аналогии для произвольного шага k длина доверительного отрезка: b k - a k = x k (b - a ).

Процесс заканчивается, когда выполняется неравенство b k - a k = x k (b - a ) £ e.

Отсюда следует, что номер шага k , на котором достигается требуемая точность e , равен k (e)= ]log t (b - a )/e [ = ]log t M [.

На первом шаге выполняется два вычисления целевой функции, на всех последующих n ш = 1. Поэтому полное число необходимых вычислений F (х )

п (e) =1+ n ш k (e) = 1+] log t ((b - a )/e)[ .

Зависимость e (п ) находим из равенства (b -a )/e = t ( n -1 ) : e (п ) = (b - a )x (n -1) .

Асимптотические скорости роста зависимостей e(n ) и n (e) для метода золотого сечения:

e (n ) = O[(b-a )x n ];

п(e ) = O =O .

Данный метод является ещё более быстрым по сравнению с дихотомией, так как в формуле для п (e)основание логарифма t » 1,618 < 2. Как и дихотомия, он является регулярным. Также он принадлежит к группе так называемых симметричных методов.

Последовательный метод определения экстремума называют симметричным , если на каждом i –том шаге поиска экстремума на доверительном отрезке [a i ,b i ] уже известна одна пробная точка x 1 и значение целевой функции F (x 1) в ней. Вторая (новая) пробная точка x 2 определяется как симметричная x 1 относительно средней точки (a i +b i )/2 доверительного интервала: x 2 = a i + b i - x 1 .

Метод дихотомии не является симметричным.

Замечание 1. Известная пробная точка x 1 в симметричном методе может быть как меньше, так и больше значения (a i +b i )/2 .

Замечание 2 . Свойство симметрии метода позволяет значительно упростить расчёт новых пробных точек. Формула x 2 = a i + b i - x 1 позволяет рассчитать вторую пробную точку x 2 независимо от того, как первая точка x 1 расположена относительно средней точки доверительного отрезка (до или после).

Замечание 3 . В практических расчетах при большом числе итераций из-за накопления погрешностей вычисления положение пробной точки x 1 на отрезках [a i ,b i ] может значительно отклоняться от золотого сечения. При этом, соответственно, полное число необходимых вычислений целевой функции п (e) будет увеличиваться. Для предотвращения этого явления, положение точки x с известным значением функции можно периодически уточнять по формулам х=a+ x(b-a )либо х=a+ (1-x)(b-a ) в зависимости от того, к какому из данных значений она ближе.

Пример 1 . Найти минимум функции F (х ) = х 2 – 2х на доверительном отрезке по методу золотого сечения при заданной точности e =0,5.

Решение .

Шаг 0. а 0 = а, b 0 = b .

Шаг 1 . Расчет положения двух пробных точек: х 2 =а 0 + x(b 0 – а 0) »1,3124; х 1 = (b 0 +а 0)-х 2) » 0,8876. Значения функции в них: F (x 1 ) = -0,9874; F (x 2) = -0,7768. Так как F (x 1 )<F (x x 2 ;b 0 ].Получаем новый доверительный отрезок [а 1 ;b 1 ] = .

b 1 -а 1 = 1,1124 > e = 0,5;продолжаем поиск.

Шаг 2 . Границы доверительного отрезка а 1 = 0,2; b 1 = 1,3124 . На нем известно значение функции в точке х» 0,8876, F (x ) = -0,9874.

Новая пробная точка: х¢ = ( b 1 +а 1) - 0,8876 » 0,6248. Значение функции в новой точке х¢ : F (x¢ ) = -0,8592.

Поскольку х¢<х, то принимаем х 1 = х¢ ; F (x 1) = F (x¢ ); х 2 = х ; F (x 2) = F (x ).

Так как F (x 1) > F (x 2), то отбрасываем часть доверительного отрезка [a 1 ;x 1 ].Получаем новый отрезок [а 2 ; b 2 ] = .

b 2 -а 2 = 0,6878 > e = 0,5;продолжаем поиск.

Шаг 3 . а 2 = 0,6246; b 2 = 1,3124 . Известно значение функции в точке х» 0,8876, F (x ) = -0,9874.

Новая пробная точка: х¢ = (b 2 +а 2) - 0,8876 » 1,0494.. Значение функции в новой точке х¢ : F (x¢ )= --0,9976.

Поскольку х¢>х, то принимаем х 1 = х ; F (x 1) = F (x ); х 2 =х¢ ; F (x 2) = F (x¢ ).

Так как F (x 1)>F (x 2),то отбрасываем часть доверительного отрезка [a 1 ; x 1 ] и получаем отрезок [а 3 ; b 3 ] = .

b 3 -а 3 =0,4248 < e =0,5;следовательно, поиск завершен.

Ответ. Выполнено3 шага, использовано 4 пробных точки. Найден итоговый доверительный интервал: [а 3 , b 3 ] = длины 0,4248.

Как видно из Примера 1 п.10.3, число необходимых вычислений функции сократилось по сравнению с методом дихотомии с 6 до 4.

Вопросы для проверки знаний.

1. Что называют а) золотым сечением отрезка, б) прямым и обратным золотым сечением отрезка?

3. Какое свойство золотого сечения используется при сокращении доверительного отрезка?

4. Какие методы называют симметричными и как симметричность используется для упрощения расчета пробных точек?

5. Как выполняются первый и последующие шаги в методе золотого сечения?

6. За счет чего метод золотого сечения является более быстрым по сравнению с дихотомией?

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

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

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

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

Код программы:

#include #include using namespace std ; const double goldenRatio = (1 + sqrt (5 ) ) / 2 ; // "Золотое" число // Рассматриваемая нами функция double function (double x ) { return log (1 + x * x - cos (x ) ) - pow (M_E , sin (M_PI * x ) ) ; int main () { double a , b ; // Концы отрезка double accuracy ; // Точность, с которой мы находим локальный максимум double x1 , x2 ; // Точки, делящие текущий отрезок в отношении золотого сечения cin >> a >> b >> accuracy ; while (fabs (b - a ) > accuracy ) { x1 = b - (b - a ) / goldenRatio ; x2 = a + (b - a ) / goldenRatio ;