1_theory (732180), страница 4
Текст из файла (страница 4)
8. Одномерная минимизация
Несмотря на кажущуюся простоту, для широкого класса функций решение задачи минимизация функции одного переменного j(х) сопряжено с некоторыми трудностями. С одной стороны, в практических задачах часто неизвестно, является ли функция дифференцируемой. С другой стороны, задача решения уравнения j¢(х)=0 может на практике оказаться весьма сложной. Ввиду этого существенное значение приобретают методы минимизации, не требующие вычисления производной[15].
Поскольку нас интересует приближенное определение точки минимума, то для этого исследуют поведение функции в конечном числе точек, способами выбора которых различаются методы одномерной минимизации.
К методам, в которых при ограничениях на количество вычислений значений j(х) достигается в определенном смысле наилучшая точность, относятся методы Фибоначчи и золотого сечения[17,18]. Оба метода строятся по единой схеме и различаются способом выбора параметра l. Исходными данными для них являются: отрезок [a0,b0] содержащий точку минимума и точность определения точки минимума e.
8.1 Алгоритм методов
-
h0 = b0 - a0 , k = 1 , l Î (0.5,1) , h1 = l×h0 , h2 = h0 - h1 , c1 = a0 + h2 , d2 = b0 - h2
-
Вычислить текущие значения j(ck) и j(dk) и действовать в соответствии с ними:
| j( ck ) £ j( dk ) | j( ck ) > j( dk ) | |
| ak = | ak-1 | ck-1 |
| bk = | dk-1 | bk-1 |
| dk = | ck-1 | |
| ck = | dk-1 | |
| hk+2 = | hk-hk-1 | hk-hk-1 |
| dk = | bk-hk+2 | |
| ck = | ak+hk+2 |
-
Если ( hk £ e ) то xmin=min{ j(ck) , j(dk) } иначе k++ и переход к шагу II
Следует отметить, что на каждом шаге кроме первого, производится только одно вычисление значения функции j(x).
Легко показать, что для получения оптимальной последовательности отрезков, стягивающихся к точке минимума, необходимо положить lk = Fk-1/Fk , где F - число Фибоначчи.
8.2 Метод Фибоначчи
Решая вопрос, при каких значениях параметра l за конечное число итераций N мы получим отрезок минимальной длины, получим l = lN = FN-1/FN. Иначе говоря, для поиска минимума первоначально необходимо найти число Фибоначчи N такое, что FN+1<(b0-a0)/e£FN+2.
8.3 Метод золотого сечения
В реальной ситуации начиная поиск минимума мы не знаем точного числа требуемых итераций. Вместо вычисления l будем выдерживать постоянное отношение длин интервалов hk-2/hk-1 = hk-1/hk = t. При t = (Ö5+1)/2 = 1.618034 получаем метод золотого сечения.
Сравнивая приведенные методы при больших значениях N можно показать, что значение окончательного интервала неопределенности в методе золотого сечения лишь на 17% больше чем в методе Фибоначчи.
22
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
