Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
откуда определяется шаг к наискорейшего спуска А* = 10/9.
Заметим, что методы градиентного спуска, вообще говоря, определяют локальный минимум целевой функции Ф (х). Это связано с зависимостью всего пути спуска х{к) от начального приближения л:(0). Можно привести примеры, когда различные л;(0) дают пути, приводящие к различным точкам локального минимума (рис. 9.20). Поэтому очень важно в задачах минимизации использовать всю имеющуюся информацию о зависимости целевой функции Ф от вектора х для правильного выбора начального приближения х(0).
9.6.4. Применение программы В5А1. Используем программу В5А1 для поиска минимума функции (9.6.4) по заданному начальному Приближению х(0) = (1,1), спуск прекращается по условию
Ф (х(к + х)) = Ф (х(к) — И grad Ф (х(к))).
Ф(х(к+1)) = гтпФ(х{к) —к %га<1 Ф (х(к))).
к
II х{к+1)-х(к) Ке
в евклидовой норме. Программа мо^кет иметь следующий вид: 370 \
REAL X(2),R,G(2),S,E,W(4)
INTEGER N,I,K EXTERNAL F
DATA X/11 ./,N/2/,K/100/,Е/1.Е-4/
С ОБРАЩЕНИЕ К ПРОГРАММЕ В5А1
CALL В5А1 (F,N,X,R,G,S,E,K,I,W)
С ВЫВОД НА ТЕРМИНАЛ ВЕКТОРА X, ДОСТАВЛЯ-
С ЮЩЕГО MIN F,
С ЗНАЧЕНИЯ MIN F, ИНДЕКСА ОШИБОК I
WRITE (5,) X,S,I 1 FORMAT (2Х,2Е13.6,'MINF =El3.6/1=', 12)
END
С ПОДПРОГРАММА, ВЫЧИСЛЯЮЩАЯ F(X), ВЕКТОР
С GRAD F(X)
SUBROUTINE F(N,X,Y,G)
REAL X(2),Y,G(2)
INTEGER N
Y^Xl1)* X(l)/4.+X(2) * X(2)
G(')=x(№-
G(2)=2.*X(2)
RETURN
END
• 9.7. Метод золотого сечения
Выше, рассматривая покоординатный спуск и наискорейший градиентный спуск, мы отметили, что важным элементом этих методов является минимизация функций одной переменной. В настоящем разделе рассматривается метод деления интервала поиска минимума точками (метод золотого сечения), вычисления значения Ф(х) в них, сравнения значений и отбрасывания той части интервала, на которой заведомо отсутствует минимум. Такой подход аналогичен методу бисекции определения корня как по логической схеме, так и по минимальному требованию к гладкости минимизируемой функции Ф(д:). Для метода золотого сечения даже не требуется непрерывности функции, могут существовать разрывы первого рода. Достаточно, чтобы Ф(х) была унимодальной.
9.7.1. Унимодальная функция. Функция ФЫ, заданная на интервале а^х^Ь, называется унимодальной на [а, Ь\ если существует единственная точка х* минимума Ф(х)
Ф(х*)= min Ф(х)
а^х^Ь
и если для любых двух точек хх, х2 е [а, 6] выполняются соотношения: из неравенств х1<х2^х* следует
Ф(х!)>Ф(х2),
371
из неравенств
х2>х1^х+ следует
Ф(х1)<Ф(х2).
Пусть известно, что Ф(л;) унимодальна на [а, о]. Тогда по любым двум значениям Ф^), Ф(^г) можно указать интервал, в котором находится точка х*, минимизирующая Ф(х), причем этот интервал имеет длину, меньшую первоначальной. Пусть для определенности хг<х2, возможны следующие три варианта (рис. 9.21):
a) Ф(дг1)>Ф(х2);
b) Ф(д:1)<Ф(х2);
‘ . с) Ф(х1) = Ф(л:2).
В случае а) следует отбросить интервал [а, лгх], в случае Ь)— [х2, 6], в, случае с)—интервалы [я, л^], [х2, 5], поскольку на этих интервалах не может находиться х*, в противном случае нарушается предположение об унимодальности Ф(х).
В зависимости от стратегии выбора двух точек хг, х2 на интервале имеются различные методы поиска минимума унимодальной функции, отличающиеся скоростью стягивания интервала неопределенности, содержащего х*, к точке х*.
9.7.2. Метод золотого сечения. Золотое сечение, открытое Евклидом, состоит в разбиении интервала [<я, ?] точкой хг на две части таким образом, чтобы отношение длины всего интервала к большей части было равно отношению большей части к меньшей:
Ь—а Ь—хх Ь—х1 х1—а
Легко проверить, что золотое сечение производят две точки:
Х1=а+(1-хЩ-а)} /-
х2 = а + т(Ь — я), т = (1-%/5)/2.
Значение 1^0,618.
Алгоритм метода золотого сечения следующий:
1) вычисляют значения х19 х2;
2) вычисляют Ф (д:!), Ф(х2);
3) если Ф(^с1)<,Ф(^2), то для дальнейшего деления оставляют интервал [я, л:21;
4) если Ф(д:1)>Ф(д:2), то для дальнейшего деления оставляют интервал [*1, Ь1
Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет меньше заданной точности в.
Заметим, что точка хг производит золотое сечение интервала [я, лг2], точка х2—интервала [х19 &]. Поэтому на оставшемся
I
I
М/Л-
9
I
I
а)
9
I
I
Ь)
Рис. 9.21
С)
Рис. 9.22
интервале нужно определить одну точку, производящую золотое сечение. После этого процесс повторяется. На каждом шаге длина нового интервала неопределенности равна ~ 0,618 длины старого интервала.
9.7.3. Схема алгоритма метода золотого сечения. Представим блок-схему алгоритма в следующем виде (рис. 9.22).
9.7.4. Применение программы В5А0. Для минимизации функции одной переменной можно использовать библиотечную программу В5А0. Пусть необходимо найти минимум функции
Ф(х) = л:2 + е*
на интервале [—1, 0] с относительной точностью определения х*, равной 0,001, и абсолютной точностью 0,00001. Программа может иметь следующий вид:
373
REAL E,E1,A,B,X,R INTEGER N,I EXTERNAL F
DATA E,E 1, А,В/1 .E3,1 ,E5,1. ,0./,N/l 00/
DATA I/O/
ОБРАЩЕНИЕ К ПРОГРАММЕ B5A0 CALL B5A0(F,E,E1,A,B,N,X,R,I)
