Методы, использующие производные функции.

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

Метод "золотого сечения" является последовательным методом минимизации. Этот метод использует найденные значения ¦() более рационально, чем метод деления интервала пополам, что позволяет переходить к очередному интервалу, содержащему * после вычисления одного, а не двух значений ¦().

Рассмотрим на исходном отрезке [а;b] точку и вычислим ¦(). Зная значение целевой функции в одной точке, невозможно сузить область поиска точки . Поэтому выберем вто­рую точку так, чтобы a< < <b, и вычислим ¦(). Возможен один из следующих двух случаев ¦() £ ¦() или ¦() ³ ¦().

Согласно свойству унимодальных функций: если ¦() £ ¦(), то *<; если же ¦() ³ ¦(), то x* >; в первом случае искомая точка * не может быть на отрезке [;b], а во втором – на отрезке [a;] (эти отрезки на рисунке 5.3 отмечены штриховкой). Следовательно, теперь область поиска сужается и следующую точку следует брать в одном из укороченных отрезков [a; ] или [;b].

a) б)

Рис. 5.3. Уменьшение интервала поиска точки минимума методом золотого сечения.

Установим где на исходном отрезке лучше всего выбрать точки и . Так как первоначально ничего не известно о положении *, то оба указанных выше случая равновозможные, то есть "лишним" может оказаться любой из отрезков [;b] и [a;]. Отсюда ясно, что точки и должны быть расположены симметрично относительно середины отрезка [a;b]. Чтобы максимально сузить область поиска, эти точки должны быть "поближе" к середине исходного отрезка. Если их взять рядом с серединой исходного отрезка, то на втором этапе сужение области поиска будет незначительным (рис. 5.4).

Риc. 5.4. К выбору пробных точек и .

На втором этапе сужения области поиска потребуется вычислить лишь одно значение ¦(), которое будем сравнивать с уже имеющимся значением ¦() или ¦() в зависимости от того, какой из двух случаев реализовался. Поэтому, с одной стороны, точки и следует выбирать рядом с серединой отрезка, а с другой – слишком близкими их брать нельзя. Для того, чтобы найти “золотую середину”, используется метод "золотого сечения".

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

Рис.5.5. Поиск пробных точек с помощью метода золотого сечения

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

Рис.5.6. Интервалы, полученные методом золотого сечения.

Чтобы точки =1-F и =F делили отрезки [0;F] и [0;1] в одном и том же отношении должно выполнятся равенство или , откуда находим положительное значение . Таким образом, , .Дроби и называются дробями Фибоначчи или числа Фибоначчи (Bonaccio (итал.)), сын Боначчо – добродушный, простодушный, то есть сын добряка, сын удачника. Это название им дал Леонардо Фибоначчи из Пизы, который первым открыл их еще в 1202 году, подсчитывая, сколько пар потомства могут дать в год пара кроликов и их последующее потомство.

Для того чтобы симметрия поискового образа сохранялась, расстояние (1-F) должно составлять F-ю часть длины интервала (которая равна F). При таком выборе F следующая пробная точка размещается на расстоянии, равном F-й части длины интервала, от правой граничной точки интервала (рис. 5.7.).

Риc. 5.7. Симметрия золотого сечения интервала.

Отсюда следует, что при выборе F в соответствии с условием 1-F= симметрия поискового образца (рис.5.5.) сохраняется при переходе к уменьшенному интервалу (рис.5.7.). Схема поиска, при которой пробные точки делят интервал в этом отношении, известна под названием поиска с помощью метода золотого сечения. Для произвольного отрезка [a;b] выражения для пробных точек примут вид

, . (5.3)

Зная одну из точек золотого сечения отрезка [a;b], другую можно найти по одной из формул

, . (5.4)

Пусть ¦()ÎQ[a,b] и требуется найти точку минимума * функции ¦() на [a;b]. Построим последовательности {},{} и {}, n=1,2,..., следующим образом:

, , , если ¦() £ ¦(); (5.5)

, , , если ¦() > ¦(), n=2,3,…,

где , ,и -первая и вторая точки золотого сечения (5.3) отрезка [,].

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

1. найти одну из точек золотого сечения отрезка [,] по известной другой точке , используя формулы (5.4). При определении * с большой точностью, чтобы избежать накопления ошибок округления, обычно точки золотого сечения отрезка [;] находят по формулам (5.3) и в качествеи используют и ту из найденных точек, которая больше отличается от .

2. вычислить значение ¦(х) во вновь найденной точке золотого сечения (значение в другой точке уже вычислено на одном из предыдущих шагов).

3. сравнить значения ¦() и ¦() и найти ,,по формулам (5.5).

Таким образом, на каждом шаге определения ,,, n=2,3... , требуется вычисление одного значения ¦(). Положив * найдем точку минимума * с точностью :

,

откуда следует, что число шагов n метода золотого сечения, обеспечивающее заданную точность e нахождения точки *, должно удовлетворять неравенству

. (5.6)

Пример 5.3. Решить пример 5.2 методом золотого сечения. Вычисления проведем по формулам (5.5), представив результаты в таблице 5.3, где стрелками отмечены сохраняющиеся при переходе к следующему шагу значения.

Таблица 5.3

Значения пробных точек и функции f()

n						¦()	¦()	Примечание
1	0.309	1.5	2.0	1.691	1.809	-92.049	-91.814	¦()<¦(), =
2	0.191	1.5	1.809	1.618	1.691	-91.464	-92.049	¦()>¦(), =
3	0.118	1.618	1.809	1.691	1.736	-92.049	-92.138	¦()>¦(), =
4	0.073	1.691	1.809	1.736	1.764	-92.138	-92.083	¦()<¦(), =
	0.045				1.736		-92.138	точность достигнута.

Из таблицы 5.3 получаем х*»1.736, ¦*»¦(). Если воспользоваться формулой (5.6), то n можно определить заранее. В нашем случае n³4,79, то есть n=5.

Прямые методы используются при минимальных требованиях к целевой функции ¦(x)-она считается унимодальной, и вычислению подлежат значения только самой функции, но не её производных.

Если усилить эти требования, предположив, что ¦(x) является дифференцируемой или дважды дифференцируемой выпуклой функцией, и считать, что возможно вычисление производных ¦(x) в произвольно выбранных точках, то эффективность процедур поиска можно существенно повысить.

Рассмотрим методы минимизации, в которых используются значения производных целевой функции. Напомним, что для выпуклой дифференцируемой функции равенство ¦’(x)=0 является не только необходимым, но и достаточным условием глобального минимума. Поэтому, если известно, что х* является внутренней точкой отрезка [a,b], то приближенное равенство ¦’(x)»0 или |¦’(x)|£e, где e ³0 - достаточно малое число, может служить условием остановки вычислений в рассматриваемых ниже методах.