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

Рисунок 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