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

Рассмотрим такое симметричное расположение точек x 1 и х 2 на отрезке [а ; b ], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x ), так как другое значение уже найдено на одной из предыдущих итераций.

Рассмотрим сначала отрезок и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х 2 = , тогда симметрично расположенная точка х 1 = 1- (рис.2.2).

Рис. 2.2.

Пробная точка х 1 отрезка перейдет в пробную точку х 2 = 1- нового отрезка . Чтобы точки х 2 = , и х 2 = 1- делили отрезки и в одном и том же отношении, должно выполняться равенство или, откуда находим положительное значение … Таким образом, х 1 = 1- = , .

Для произвольного отрезка [а ; b ] выражения для пробных точек примут вид

1. Точки x 1 и х 2 обладают следующим свойством: каждая из них делит отрезок [а ; b ] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а ; b ].

2. На каждой итерации исключения отрезков с пробными точками одна из них переходит на следующий отрезок и значение f (x ) в этой точке вычислять не следует. Если новым отрезком становится [а ; х 2 ], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х 2 "= х 1) (рис. 2.2). В случае перехода к отрезку [х 1 ; b ] пробная точка исходного отрезка становится первой пробной точкой отрезка [х 1 ; b ].

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

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

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

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

Дана функция, где d=2, e=1

Необходимо найти минимум на отрезке , где, т.е. на отрезке

Составить программу, которая выдаст число итераций при точности е=0,001

Решить двумя методами: дихотомии и золотого сечения

Решение методом дихотомии:

Так как f1

Так как f1

Решение методом золотого сечения:

Так как f1

Так как f1

Так как f1

Листинг программы реализующей методы дихотомии и золотого сечения представлен в приложении А

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

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

Задание:

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

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

Введение

Метод золотого сечения имеет достаточно большое применение во многих сферах. Так как всё в мире имеет какую-либо форму: предметы, растения, животные, люди - всё. Что представляют собой эти формы? Любое целое обязательно разделено на части разных размеров. Эти части имеют отношения между собой и ко всему миру, имеют формы. А строение любой формы образуется при помощи симметрии и золотого сечения.

Метод золотого сечения применяют в фотографии, живописи. Для фотографа метод золотого сечения - один из самых простых способов выделить главное на картинке. Применяется этот метод и в web-дизайне. В живописи же примером может послужить картина И.И. Шишкина "Сосновая роща". На этой знаменитой картине И.И. Шишкина с очевидностью просматриваются мотивы золотого сечения. Ярко освещенная солнцем сосна (стоящая на первом плане) делит длину картины по золотому сечению. Справа от сосны - освещенный солнцем пригорок. Он делит по золотому сечению правую часть картины по горизонтали. Слева от главной сосны находится множество сосен - при желании можно с успехом продолжить деление картины по золотому сечению и дальше.

В архитектуре метод золотого сечения также нашёл своё применение. По законам золотого сечения были построены наиболее известные нам сооружения, такие как Парфенон (V в. до н.э.), собор Парижской Богоматери (Нотр-дам де Пари). Яркими примерами в русской архитектуре станут Смольный собор в Санкт-Петербурге и храм Василия Блаженного, в котором, если взять высоту собора за единицу, то основные пропорции, определяющие членение целого на части, образуют ряд золотого сечения.

В основном же, метод золотого сечения применяют в программировании. Он является одним из простейших вычислительных методов решения задач оптимизации.

Цель курсовой работы - рассмотреть численные методы поиска экстремума функций одной переменной, а именно метод золотого сечения.

Исходя из поставленной цели, необходимо решить следующие задачи:

Рассмотреть метод золотого сечения, его алгоритм выполнения;

Рассмотреть метод чисел Фибоначчи и его алгоритм выполнения;

Показать реализацию метода золотого сечения в программировании.

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

История появления метода золотого сечения

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -- симплекс-метод, ставший основным при решении задач линейного программирования.

Присутствие в названии дисциплины термина "программирование" объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово "programming" означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин "линейное программирование" был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях.

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 1930-м годам. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман - математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Канторович - советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 году венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название "проблема выбора", метод решения получил название "венгерского метода".

Канторовичем совместно с М.К. Гавуриным в 1949 году разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Канторовича, Немчинова, В.В. Новожилова, А.Л. Лурье, А. Брудно, Аганбегяна, Д.Б. Юдина, Е.Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем.

Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф.Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования -- симплекс-метод -- был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (англ.), А. Таккера (англ.), Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E.M.) и др.

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

Начиная с 1955 году опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.

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

Пусть Х=. Положим х1=1/T. Так как Т2=Т+1,то 1-1/Т=1/Т2.

Итак,отношение длины всего отрезка,к длине большей из его частей равно отношению длины большей части к длине меньшей части:

1/(1/Т)=(1/Т)/(1/Т2)

Деление отрезка в таком отношении называется золотое сечение.

Точку x2 выберем симметрично точке x1 относительно середины отрезка X:x2=1/T2. Сравнив значения f(x1) и f(x2),находим отрезок локализации минимума ( или ).Нетрудно увидеть, что лежащая внутри локализации точка, где вычисление проведено, делит отрезок в отношении золотого сечения.

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

Рисунок 1 - График взаимного расположения первых 2 вычислений по методу золотого сечения

Таблица 1 ? Взаимное расположение генерируемых алгоритмом точек

Очевидно, что в случае X=, длина отрезка локализации минимума после N вычислений равна (b-a)/(TN-1).