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

Введение

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

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

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

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

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

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

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

Тесты

Алгоритм

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

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. Повторяем до тех пор, пока не будет достигнута заданная точность.

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

Тема 1.6. Одномерная оптимизация

Постановка задачи

Метод дихотомии

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

Сравнение методов

Тестовые задания по теме «Одномерная оптимизация»

Постановка задачи

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

По количеству независимых переменных различают задачи одномерной оптимизации (n=1 ) и многомерной оптимизации (n ³ 2 ). При этом задача нахождения максимума целевой функции сводится к задаче нахождения минимума путем замены функции f(x) на -f(x) , поэтому в дальнейшем будем говорить только о поиске минимума функции, то есть такого x*Î, при котором f(x*) = min f(x).

В области допустимых значений функция f(x) может иметь несколько экстремумов (минимумов или максимумов - рис. 4.6.1). Говорят, что функция f(x) имеет в точке x* локальный минимум, если существует некоторая положительная величина d , такая, что если ½х – х*½< d, то f(x)³ f(x*), т.е. существует d - окрестность точки х*, такая, что для всех значений х в этой окрестности f(x)³ f(x*). Функция f(x) имеет глобальный минимум в точке x*, если для всех х справедливо неравенство f(x)³ f(x*) . Таким образом, глобальный минимум является наименьшим из локальных.

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

Интервал, на котором локализован единственный минимум, называется отрезком неопределенности.

Известно, что необходимым условием существования экстремума дифференцируемой функции f(x) является выполнение равенства f¢(х) = 0 . Точка х , удовлетворяющая данному условию, называется точкой стационарности . Достаточным условием существования минимума в точке стационарности является выполнение неравенства f¢¢(х)>0 , а максимума - f¢¢(х)<0 .

Задача одномерной оптимизации имеет единственное решение в том случае, если функция f(x) на отрезке имеет только один экстремум. Тогда говорят, что функция унимодальная на отрезке .

Достаточными условиями унимодальности функции на отрезке являются:

1. Длядифференцируемой функции f(x) ее производная f¢(х) - неубывающая.

2. Для дважды дифференцируемой функции f(x) выполняется неравенство f¢¢(х)³0 .

Все численные методы одномерной оптимизации применяются только для унимодальных на определенном интервале функций.

Пример 1.6.1-1. Провести исследование функции f(x) = x 3 – x + e - x на предмет существования экстремумов.

Вначале проведем графическое исследование. Построим график функции f(x) (рис. 1.6.1-2). Из графика видно, что f(x) имеет две точки минимума: х 1 и х 2 , причем точка х 1 – точка глобального минимума. Исходя из графика, можно принять следующие отрезки неопределенности: для точких 1 - [-4;-3], а для точки х 2 - .

Проверим достаточное условие существования минимума на выбранных отрезках:

f¢(x) = 3x 2 – 1 – e -x ; f¢¢ (x) = 6x + e -x ,

f¢(0) < 0, f¢(1) > 0, f¢¢ (x) > 0 для хÎ,

f¢(-4) < 0, f¢(-3) > 0, f¢¢ (x) > 0 для хÎ[-4;-3].

Условия существования минимума выполнены, поскольку f¢¢(x) > 0 для всех хÎ и хÎ[-4;-3]. Следовательно, функция f(x) является унимодальной на выбранных отрезках.

На практике численные методы одномерной оптимизации применяют в следующих случаях:

· значения функции f(x) определены в ходе эксперимента;

· целевая функция очень сложна или не имеет непрерывных производных;

· классические методы поиска оптимального значения не применимы.

Суть методоводномерного поиска заключается в том, что на каждой итерации интервал неопределенности уменьшается и стягивается к точке минимума. Уменьшение отрезка происходит до тех пор, пока на некоторой n- й итерации отрезок неопределенности не станет соизмеримым с заданной погрешностью e , то есть будет выполняться условие |b n -a n | < e. Тогда за точку минимума можно принять любую точку, принадлежащую этому отрезку, в частности, его середину.

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

Рассмотрим, в частности, метод дихотомии и метод золотого сечения .

Метод дихотомии

Пусть дана функция f(x), унимодальная на отрезке . Обозначим a 0 = a и
b 0 = b . Поиск минимума начинают с выбора на отрезке неопределенности двух симметричных относительно середины точек: