Основная идея данного метода – сокращение числа 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. За счет чего метод золотого сечения является более быстрым по сравнению с дихотомией?

Введение

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

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

Тема 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 . Поиск минимума начинают с выбора на отрезке неопределенности двух симметричных относительно середины точек:

Где d - параметр метода.

Сравнивая вычисленные в точках a 1 и b 1 значения функций f(a 1) и f(b 1), в силу унимодальности функции можно провести сокращение отрезка неопределенности следующим образом:

1) еслиf(a 1) £ f(b 1), тоx*Î (Рис. 1.6.1-3.а);

2) еслиf(a 1) > f(b 1), тоx*Î (Рис. 1.6.1-3.b).

Если описанную процедуру принять за одну итерацию, то алгоритм поиска минимума можно описать следующим образом. Опишем k+1 итерацию, исходя из того, что k -й отрезок неопределенности найден :

1. Вычисляются

2. Находят значения f(a k +1) и f(b k +1).

3. Находят k+1 -й отрезок неопределенности по правилу:

если f(a k +1) > f(b k +1), то x* Î,

если f(a k +1) £ f(b k +1), тоx*Î).

Вычисления проводятся до тех пор, пока не выполнится неравенство

где D n – длина n -го отрезка неопределенности.

Заметим, что от итерации к итерации D n убывает и при n®¥ стремится к величине 2d, оставаясь больше этой величины. Поэтому добиться при некотором значении n длины отрезка неопределенности | меньше заданной точности можно лишь выбирая 0.

Длину конечного интервала неопределенности, обеспечивающего заданную величину e , можно вычислить по формуле

Положив D n = e, можно определить соответствующее количество итераций:

Схема алгоритма метода дихотомии приведена на рис. 1.6.1-4.

Рис.1.6.1-4. Схема алгоритма поиска минимума методом дихотомии

Пример 1.6.2-1. Найти минимум функции f(x)=x 3 -x+e -х на отрезке c точностью e и вычислить количество итераций, требуемое для обеспечения точности.

Выберем d =0.001 и положим a = 0; b = 1;

n	a	b	a 1	b 1	f(a 1)	f(b 1)	D n
			0.499	0.501	0.23239	0.23067	0.501
	0.499		0.7485	0.7505	0.14392	0.14435	0.2515
	0.499	0.7505	0.62375	0.6257	0.15486	0.15413	0.12675
	0.62375	0.7505	0.68613	0.6881	0.14040	0.14023	0.06437
…	…..	…..	…..	….	…..	…..	….
	0.701719	0.71931	0.70951	0.7115	0.13954	0.13959	0.00979

При e = 0.1 x*=0.7183 f(x*)=0.1399, а при e = 0.01 x*=0.7066 f(x*)=0.13951
.

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

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

l

Положим l =1 , тогда l 2 2 = 1 - l 2 , а l 2 2 + l 2 -1= 0, откуда

где k 1 , k 2 - коэффициенты золотого сечения.

В методе золотого сечения каждая точка (х 1 и х 2 )осуществляет золотое сечение отрезка (рис. 1.6.3-1).

или

Нетрудно проверить, что точка х 1 , но и отрезка . Точно так же точка х 2 осуществляет золотое сечение не только отрезка , но и отрезка [х 1 ;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Длина конечного отрезка неопределенности D n = 0.618 n D 0 , где D 0 = (b-a) – начальная длина отрезка.

Условие окончания процесса итераций D n e. Отсюда можно найти количество итераций, необходимое для достижения точки минимума:

отсюда логарифмируя, получим

Схема алгоритма метода золотого сечения приведена на рис. 1.6.3-2.

Пример 1.6.3-1. Пусть минимум функции f(x) = x 3 – x + e - x отделен на отрезке . Определить количества итераций и конечные длины отрезков неопределенности, необходимые для достижения заданных точностей e=0.1 и e=0.01.

N	a	b	x 1	x 2	f(x 1)	f(x 2)	D n
			0.38196	0.61803	0.35628	0.15704	0.61803
	0.38196		0.61803	0.76393	0.15704	0.14772	0.382
	0.61803		0.76393	0.85410	0.14772	0.19462	0.236
	0.61803	0.85410	0.70820	0.76393	0.13953	0.14772	0.146
	0.61803	0.76393	0.67376	0.70820	0.14188	0.13953	0.090

При e = 0.1 x*=0.718847, f(x*)=0.139925.

При e = 0.01 x*=0.704139, f(x*)=0.139516.

1.6.3-2. Схема алгоритма поиска минимума методом золотого сечения

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

Накаждойитерации при использовании метода дихотомии отрезок неопределенности сокращается практически в два раза, а при использовании метода золотого сечения в 1.618 раз.

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

На каждой итерации в методе дихотомии целевая функция вычисляется два раза, а в методе золотого сечения только один раз, следовательно, метод золотого сечения менее трудоемок с точки зрения вычислений.

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

1. Оптимальное значение функции –это

1) наилучшее

2) наименьшее

3) наибольшее

4)

2. Локальный минимум – это

1)

2)

3)

4) в списке нет правильного ответа

3. Глобальный минимум – это

1) один из минимумов функции в области допустимых значений

2) наименьшее значение функции в некоторой окрестности

3) наименьший из минимумов в области допустимых значений

4) в списке нет правильного ответа

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

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

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

Примеры правильного написания F(x):
1) 10 x e 2x ≡ 10*x*exp(2*x)
2) x e -x +cos(3x) ≡ x*exp(-x)+cos(3*x)
3) x 3 -x 2 +3 ≡ x^3-x^2+3

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

N	a n	b n	b n -a n	λ n	μ n	F(λ n)	F(μ n)
1	-1	0	1	-0.618	-0.382	-0.5623	-0.2149
2	-1	-0.382	0.618	-0.7639	-0.618	-0.548	-0.5623
3	-0.7639	-0.382	0.3819	-0.618	-0.5279	-0.5623	-0.4766
4	-0.7639	-0.5279	0.236	-0.6738	-0.618	-0.5811	-0.5623
5	-0.7639	-0.618	0.1459	-0.7082	-0.6738	-0.5782	-0.5811
6	-0.7082	-0.618	0.09018	-0.6738	-0.6524	-0.5811	-0.5772

Находим x как середину интервала : x=(-0.618-0.70818104)/2 = -0.66309052.
Ответ: x = -0.66309052; F(x) = -0.57965758