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

Рассмотрим такое симметричное расположение точек 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

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

интервалом неопределенности , но при этом можно выполнить только 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) , то:

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 , средняя часть).

Рис. 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), записываем

Т.е.

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

Введение

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

Метод золотого сечения применяют в фотографии, живописи. Для фотографа метод золотого сечения - один из самых простых способов выделить главное на картинке. Применяется этот метод и в 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).

В этой блок-схеме y, z - точки деления отрезка ,причем y < z .

y = 0.618a + 0.382b

z = 0.382a + 0.618b

Fy = f(y) : Fz = f(z)

b - a < e b - a < e

z = y: Fz = Fy y = z: Fy = Fz

y = 0.618a + 0.382b z = 0.382a + 0.618b

Fy = f(y) Fz = f(z)

Вывод x, f(x)

Пример. Для оценки сопротивления дороги движению автомобиля при скорости v км/ч можно использовать эмпирическую формулу f(v) = 24 - 2/3*v + 1/30*v 2 (для шоссе). Определить скорость, при которой сопротивление будет минимальным.

Решение.

1) Данную задачу легко решить с помощью вычисления производной:

, v = 10 км/ч.

2) Решение с помощью метода "золотого сечения". Начальные границы интервала неопределенности примем равными a = 5, b = 20.

Решение для первого этапа:

y = 0.618*5 + 0.382*20 » 10.7: z = 0.382*5 + 0.618*20 » 14.3

Fy = 24 - 2*10.7/3 + 10.7 2 /30 » 20.7: Fz = 24 - 2*14.3/3 + 14.3 2 /30 » 21.3

Результаты вычислений обычно представляют в виде таблицы. Расчеты проводятся в соответствии с блок-схемой с погрешностью e = 1 км/ч.

После пяти шагов оптимизации искомое значение скорости равно v = (8.6+10.7)/2 = 9.65 км/ч. После еще одного шага этот результат получается с меньшей погрешностью v = (9.4+10.7)/2 = 10.05 км/ч.

Оптимизация функции многих переменных Минимум функции нескольких переменных

Минимум дифференцируемой функции многих переменных u = f(x 1 , x 2 , … , x n) можно найти, исследуя ее значение в критических точках, которые определяются из решения системы дифференциальных уравнений

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

Пример постановки задачи. Пусть требуется спроектировать контейнер в форме прямоугольного параллелипипида объемом V=1 м 3 , причем на его изготовление необходимо израсходовать как можно меньше материала.

При постоянной толщине стенок это условие означает, что площадь полной поверхности контейнера S должна быть минимальной. Если обозначить через x 1 , x 2 и x 3 длины ребер контейнера, то задача сведется к минимизации функции:

S = 2 (x 1 x 2 + x 1 x 3 + x 2 x 3) .

Эта функция в данном случае является целевой, а условие V = 1 м 3 - ограничением-равенством, которое позволяет исключить один параметр:

.

Задача свелась к минимизации функции двух переменных. В результате ее решения будут найдены значения параметров оптимизации x 1 и x 2 , а затем и x 3 . В приведенном примере фактически получилась задача безусловной оптимизации, так как ограничение-равенство было использовано для исключения параметра x 3 .

Решение. После дифференцирования получим

Отсюда находят x 1 = x 2 =1 м, x 3 = 1/(x 1 x 2) = 1 м. Таким образом, оптимальной формой контейнера в данном случае является куб, длина ребра которого равна 1 м.

При таком подходе могут возникнуть серьезные трудности при решении системы нелинейных уравнений.

Вместе с тем, можно эту задачу усложнить. Например, потребуем, чтобы данный контейнер имел длину не менее 2 м. Это условие запишется в виде ограничения-неравенства на один из параметров, например, x 1 ³ 2 .

Таким образом, получили следующую условную задачу оптимизации: минимизировать функцию

учитывая ограничение-неравенство x 1 ³ 2 и найти оптимальные значения факторов x 2 , x 3 (x 2 ³0, x 3 ³0).

Графическое представление функции двух переменных: рассмотреть функцию

f(x 1 , x 2) = x 1 2 + x 2 2 .

Показать линии равного уровня для этой функции.

Дать общий вид трех возможных вариантов линий равного уровня, показать "овражные" функции.

В общем случае для поиска минимального значения целевой функции можно ввести дискретное множество точек (узлов) путем разбиения интервалов изменения параметров x 1 и x 2 на части с шагами h 1 и h 2 . В полученных узлах можно вычислить значения целевой функции и среди них найти наименьшее. Однако в многомерных задачах оптимизации такой подход требует слишком большого объема вычислений.

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

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