Численные методы поиска экстремума функций одной переменной: метод золотого сечения

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Тамбовский государственный технический университет

Институт экономики и качества жизни

Кафедра "Коммерция и бизнес-информатика"

Пояснительная записка к курсовой работе

Численные методы поиска экстремума функций одной переменной: метод золотого сечения

Тамбов 2015 г.

Содержание

Введение

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

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

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

. Метод чисел Фибоначчи

.1 Числа Фибоначчи

.2 Понятие метода чисел Фибоначчи

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

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

. Практическая часть

.1 Задача 1

.2 Задача 2

.3 Задача 3

.4 Задача 4

.5 Задача 5

Заключение

Список используемых источников

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Метод чисел Фибоначчи

.1 Числа Фибоначчи

Последовательность чисел Fi задаётся условиями F0=F1=1.

Элементы введённой последовательности называются числами Фибоначчи. Выведем формулу, выражающую числа Фибоначчи в ясном виде. Для этого будем искать решение рекуррентного уравнения

+1=Fi+Fi-1

среди геометрических прогрессий с i-членом ti. Имеем,

+1=ti+ti-1.

Ненулевые корни данного уравнения являются корнями квадратного трёхчлена t2-t-1 и равны (1±√5)/2. Вводим обозначение T=(1+√5)/2=1,618. Тогда

(1+√5)/2=-1/Т.

Таким образом, последовательности Ti и (-1/Т)i удовлетворяют этому рекурентному уравнению. Ему также удовлетворяет любая линейная комбинация последовательностей с1ti+c2(-1/t)i .Возьмём коэффициенты с1 и с2 так, чтобы выполнялись условия F0=F1=1. Имеем с1+с2=1. с1t+c2(-1/t)=-1.

Решая данное уравнение, выводим формулу для чисел Фибоначчи:

Fi=((Ti+1-(-T)-(i+1))/√5)=((1+√5)/2)i+1-((1-√5(/2)i+1)/√5)=(Ti+1-(-T)-(i+1)/√5)=((1+√5/2)i+1-(1-√5/2)i+1)√5)

Из которой следует:

~(Ti+1/√5) при i→∞

.2 Понятие метода чисел Фибоначчи

Пусть Х=[0;1].Это не ограничивает общности рассмотрений, так как заменой переменной x`=a+x(b-a),Î[a,b].

Первые вычисления проводятся в точках х1=FN-2/FN, x2= FN-1/FN, которые расположены симметрично относительно середины отрезка[0,1].

Если f(x1)<f(x2),то отрезком локализации минимума является отрезок [0,х2].

В случае f(x1)>f(x2)-отрезок [х1,1].Если f(x1)=f(x2),то отрезок [х1,х2].В последнем случае будем рассматривать в качестве отрезка локализации, например [0,х2].

Точка х3 выбирается симметрично относительно середины отрезка локализации к лежащей внутри этого отрезка уже проведённого вычисления (х1 или х2).

Взаимное расположение точек х1,х2,х3 в случае f (x1)≤ f (x2) показано на рисунке 2.

Рисунок 2- График, изображающий взаимное расположение

вычислений по методу Фибоначчи

Алгоритм определяется следующим образом: на каждом шаге точка очередного вычисления выбирается симметрично относительно середины отрезка локализации к лежащей внутри этого отрезка точке уже сделанного вычисления. Взаимное расположение генерируемых алгоритмом точек показывает таблица 1,в которой через r1,r2 обозначены расстояния точки сделанного вычисления, лежащей внутри текущего отрезка локализации, до дальнего и ближнего концов этого отрезка. После (N-1) шага точка проведённого вычисления оказывается в середине отрезка локализации.

Точка хN выбирается на расстоянии δ от середины этого отрезка, где δ - заранее фиксированное малое положительное число.

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

В случае Х=[a,b] длина отрезка локализации минимума после N вычислений не превосходит (b-a)/FN+δ

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

Для начала приведём алгоритм поиска экстремумы методом золотого сечения.

Пусть функция одной переменной y = f (x) может быть вычислена в любой точке отрезка [a, b] и имеет на нем локальный экстремум. Поскольку задача о нахождении минимума f (x) сводится к нахождению максимума функции - f(x), ограничимся рассмотрением первого случая. Построим алгоритм нахождения сложения минимума с заданной точностью s [4]. Если искать решение задачи простым перебором внутренних точек отрезка с шагом s, то потребуется большое число вычислений функции. Рассмотрим более эффективный метод золотого сечения.

Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей (см. рисунок 1)

[ab]/[x1b]= [x1b]/ [ax1] (1)

Соотношение (1) перепишем в виде

-3ll1+l2=0, (2)

золотой сечение фибоначчи программирование

где l1 =[a1x], l = [ab] и для l1 получаем

=(3√5/2)l (3)

Поскольку для корня, соответствующего знаку +, имеем l1 > l, то нас устраивает только знак − и окончательно имеем

=0.3819661 (4)

или

=a+0.3819661(b-a) (5)

Золотое сечение отрезка [a, b] производится двумя симметрично рас- положенными точками x1 и x2 и совершенно аналогично для точки x2 можно записать

= a + b - x1 = ((a +√5 - 1)/2)(b-a)= + 0.618034(b − a). (6)

Замечательно то, что в свою очередь точка x1 производит золотое сечение отрезка [a, x2], а x2 - золотое сечение отрезка [x1, b] [1].

Рисунок 3 - График, изображающий применение метода золотого сечения

Вычислим функцию f (x) в точках a, b, x1, x2. Пусть f (x1) < f (x2), тогда отбрасываем точку x = b. Если f (x1) > f (x2), то отбрасываем точку x = a [3]. Итерация закончена, но длина отрезка, на котором локализован минимум [a, x2] или [x1, b], стала в 1.62 раза короче. Итерационный процесс можно повторять, пока длина полученного отрезка не окажется меньше s. После n итераций отрезок, содержащий минимум, уменьшается в 1.62n раза и из условия

b - a/1.62n = s (7)

n=ln((b-a)/∑)/ln1.62=2ln((b-a)/∑) (8)

Таким образом, в методе золотого сечения функция f (x) рассчитывается

=3+2ln((b-a)/∑) (9)

Если начальный отрезок [a, b] содержит несколько локальных минимумов, то процесс сойдется к одному из них, но необязательно к наименьшему. Немаловажно, что данный метод применим к любым, в том числе разрывным, недифференциируемым функциям [4].

4. Практическая часть

В качестве примера найдем экстремум функции f (x) = arctan x cos x + 1 на [0, 2] с помощью метода золотого сечения.

Результат выполнения программы:

Рисунок 4 - Результат выполнения заданной задачи - программой

Строим график нашей функции, который выглядит следующим образом:

Рисунок 5 - График функции f(x)

Метод Фибоначчи и метод золотого сечения основываются на одном и тоже алгоритме перехода к следующей пробной точке и отличаются лишь способом выбора первой точки. В результате каждого шага (добавления одной пробной точки) мы получаем отрезок Ln = [an, bn] с одной "старой" пробной точкой xn ∈ (an, bn). "Новая" пробная точка yn определяется как точка симметричная xn относительно центра отрезка Ln:

yn=((an+bn)/2)+ ((an+bn)-xn)= an+bn-xn (10)

Затем, в зависимости от того, какое из неравенств f(xn) ≤ f(yn) или f(xn) > f(yn) выполняется, в качестве Ln+1 выбирается или отрезок [an, yn], или [xn, bn] (здесь мы считаем для определенности, что xn < yn), а в качестве старой пробной точки xn+1 выбирается либо xn, либо yn.

.1 Задача 1

Докажите, что ln-1 = ln + ln+1, где ln - длина отрезка Ln.

В методе золотого сечения x0 делит отрезок [a, b] по правилу золотого сечения:

(b - a)/ (x0 - a)= τ, (11)

где τ - положительный корень уравнения

τ2 = τ + 1 (12)

(золотое сечение): τ = (1 + √5)/2 ≈ 1.618). Таким образом, l0 = l1τ. Но тогда

= l0 - l1 = l1(τ- 1) = l1/τ, т. е. l1 = l2τ. (13)

.2 Задача 2

Докажите, что ln+1 = lnn/τ.

Поэтому после n + 1 эксперимента

ln=1/τn (14)

В частности, для уменьшения отрезка неопределенности в 106 раз нужно провести 29 вычислений функции.

В методе Фибоначчи сначала задается число n вычислений функции, и затем первая пробная точка подбирается таким образом, чтобы последняя пара экспериментов давала отрезок неопределенности наименьшей длины, т. е. чтобы последние две точки составляли симметричную относительно центра отрезка пару, расстояние между которыми равно ∑.

Таким образом,

= 2ln - ∑. (15)

Учитывая, что

= ln-1 + ln, (16)

получаем ln-2 = 3ln - ε, ln-3 = 5ln- 2ε, ln-4 = 8ln - 3ε, ln-5 = 13ln -5ε и т. д. Индукцией по i легко доказывается, что

ln-i=Fi+1ln- Fi-1∑ (17)

где Fi - так называемые числа Фибоначчи, определяемые соотношениями F0 = F0 = 1, Fi = Fn-1 + Fn-2, i = 2,3, ..., введенные в XIII веке Леонардом Пизанским (Фибоначчи) совсем по другому поводу. Из (17) мы получаем, во-первых, длину ln отрезка неопределенности, получающегося в результате вычисления f в n + 1 точках:

= l0 = Fn+1ln - Fn-1∑, (18)

откуда

ln = (1/Fn+1)+(Fn-1/Fn+1)∑ (19)

и, во-вторых, длину отрезка l1, задающего положение первой (стартовой) точки:

= Fnln - Fn-2ε = (Fn/Fn+1)l+((FnFn-1- Fn-2Fn+1)/Fn+1) (20)

.3 Задача 3

Докажите, что (Fi)2 = Fi-1Fn+1 + (-1)i.

Используя это тождество, получите из (20) более простое соотношение, определяющее ln:

=((Fn/Fn+1)l+((-1)n/Fn+1) ∑ (21)

Таким образом, чтобы запустить метод Фибоначчи необходимо заранее знать количество точек, в которых будет вычисляться функция f. В то же время метод Фибоначчи является наилучшим алгоритмом в таком классе методов, в частности, по сравнению с методом золотого сечения, за одно и то же число шагов он дает отрезок неопределенности в τ2/√5 ≈ 1.17 раз меньший. На практике чаще используют первый из них, поскольку выигрыш в методе Фибоначчи не велик, а необходимость заранее знать число n вычислений функции зачастую обременительна.

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

4.4 Задача 4

Требуется минимизировать: f(x)=(100-x)2 в интервале 60<=x<=150.

Решение:

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

минимизировать f(Z) = (40-90Z)2;

при ограничении 0<=Z<=1.

Итерация 1.

Интервал  I1=(0,1); L1=1.

Проведем два первых вычислений функции:

=q=0.618, f(Z1)=244.0=1-q=q2=0.382, f(Z2)=31.6

Т.к. f(Z2)<f(Z1) и Z2<Z1, интервал Z2>=Z1 исключается.

Итерация 2.

=(0, 0.618); L=0.618=q.

Следующее вычисление значения функции проводится в точке.

=q-q2=q(1-q)=q3=0.236, f(Z3)=352.

Т.к. f(Z3)>f(Z3) и Z3<Z2, интервал Z2<=Z2 исключается.

Итерация 3.

=(0.236, 0.618); L=0.382=q2.

Следующее вычисление функции проводится в точке, расположенной на расстоянии q*(длина полученного интервала), или на расстоянии (1-q)*(длина интервала) от правой граничной точки.

Таким образом:

=0.618 - (1-q)L3=0.618 - q2 L3=0.618 -q2(q2)=0.618 - q4=0.472;f(Z4)=6.15.

Т.к. f(Z4)<f(Z2) и Z4>Z2, интервал Z4<=Z2 исключается.

В результате получен следующий интервал неопределенности:

.382<=Z<=0.618 для переменной Z, или 94.4<=x<=115.6 для переменной x.

.5 Задача 5

Найти минимум функции f(x)=(100-x)2 в интервале 60£ x £150 методом золотого сечения.

Здесь a=60, b=150 и L=150-60=90, L1=12.

Итерация 1.

=>

=>

Итерация 2.

,

=>

=>

Итерация 3.

,

=>

=>

Итерация 4.

,

=>

=>

Итерация 5.

,

=>

=>

Итерация 6.

,

=>

=>=>

точка золотого сечения и есть точка минимума.

Заключение

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

Метод золотого сечения также применяется в экономике. Метод золотого сечения (метод золотой пропорции) (golden section method) -применительно к оценке бизнеса, метод определения ставки дисконтирования, когда основная часть ставки (примерно 62%) вычисляется как обычно, напр., по модели САРМ, и к ней прибавляется дополнительная часть (примерно 38%), отражающая неидентифицируемые факторы риска. Математически метод золотого сечения (МЗС) обосновывался в работах акад. И.В. Прангишвили. Этот метод эффективен при использовании в условиях экономических кризисов, причем сначала рассчитывают долю идентифицируемых воздействий, затем - неидентифицируемых. При углублении кризиса (движение "ко дну") эта доля постепенно возрастает. При выходе из кризиса (движение "ото дна") она постепенно снижается и сходит на нет по мере преодоления аномальных кризисных явлений, перехода к условиям стабильного экономического развития. Т.о. соотношение между долями считается подвижным, что реалистично. Пропорции 0,62: 0,38 оно достигает "на дне" кризиса.

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

Список используемых источников

1.      Поляк Б.Т. Введение в оптимизацию. М.: Наука. 2003. С. 301

2.      Бояршинов М.Г.Численные методы оптимизации. Пермь: ПГТУ. 2008. С. 42

3.      URL: http://mathfunc.narod.ru/met_zol.html (2011.12 янв.)

4.      Сухарев А.Г. Курс методов оптимизации. М.: Физмалит. 2005. С. 45

5.      URL: http://webmath.exponenta.ru/dnu/lc/kiselev1/node88.html (2012.15 мая)

7.      URL: http://vsem-dm.narod.ru/27.html(2010.10 фев.)

8.      URL: http://www.ict.nsc.ru/books/textbooks/akhmerov/mo_unicode/5.html (2009. 5 янв.)

9.      URL: http://dic.academic.ru/dic.nsf/ruwiki/1034656 (2013.5 июн.)

10.    Харчистов Б.Ф. Методы оптимизации: Учебное пособие. Таганрог: ТРТУ. 2004. С. 41