Научная литература
booksshare.net -> Добавить материал -> Математика -> Боглаев Ю.П. -> "Вычислительная математика и программирование " -> 116

Вычислительная математика и программирование - Боглаев Ю.П.

Боглаев Ю.П. Вычислительная математика и программирование — Высшая школа, 1990. — 546 c.
ISBN 5-06-00623-9
Скачать (прямая ссылка): vychmatiprog1990.djvu
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 168 >> Следующая

При небольших размерностях п вектора х перебор является наиболее эффективным методом поиска минимума Ф(х) в случае сложного поведения Ф(х) (наличие многих локальных минимумов). Приведем пример программы поиска минимума перебора
пппФ(х1, х2)
в области П = {0^х1<1-, 0<х2<1}:
REAL H,X1,X2,F,FM INTEGER N
С ВВОД ЧИСЛА ТОЧЕК ПЕРЕБОРА N ПО КАЖДОЙ С ПЕРЕМЕННОЙ
READ (5.1) N 1 FORMAT (16)
С ВЫЧИСЛЕНИЕ ШАГА Н ПЕРЕБОРА
Н= 1/N
С АЛГОРИТМ ПЕРЕБОРА
FM = FI(0.,0.)
XI =0.
\
366
Х2=0.
DO 3 1 = 1,N+l DO 3 J=1,N+1 F = FI(H*(I — 1),H*(J — 1))
IF (F.LT.FM) GO TO 2 GO TO 3
2 FM = F X1=H*(I-1)
X2=H*(J— 1)
3 CONTINUE
С ВЫВОД НА ТЕРМИНАЛ МИНИМАЛЬНОГО
С ЗНАЧЕНИЯ ФУНКЦИИ FM;
С ТОЧКИ С КООРДИНАТАМИ XI, Х2, В КОТОРОЙ С ДОСТИГАЕТСЯ FM
WRITE (5.4) FM,X1,X2
4 FORMAT (2X/FM = ',Е 13.6,2Х,2Е13.6)
END
С ФУНКЦИЯ-ПОДПРОГРАММА, ВЫЧИСЛЯЮЩАЯ
С МИНИМИЗИРУЕМУЮ ФУНКЦИЮ
FUNCTION FI(X1,X2)
REAL XI,Х2 FI = ...
RETURN
END
# 9.6. Методы спуска
Идея всех методов спуска состоит в том, чтобы исходя из начального приближения—точки л:(0) = (д:^0), х$\ , д:^0))е/) — пе-
рейти в следующую точку д:(1) = (х(11), х^\ ..., лг^єі) так, чтобы значение Ф(л:^0), ..., лгі,0)) уменьшилось:
Ф(х{1))<Ф{х{0)).
9.6.1. Метод покоординатного спуска. Пусть в области О задано нулевое приближение
*(0>=И», ...,40)).
Рассматриваем функцию Ф(д:(0), хф\ л:^0), ...
..., х5,0)) при фиксированных значениях х<?\ х^\ ...
..., л:^0) как функцию одной переменной хг (рис. 9.16). Находим
ШІП Ф(*1; х^\ ..., дс<®>).
хх ей
Значение х19 доставляющее минимум, обозначаем д;^:
367
• № 4°>............4°')<ф№ xf\
Далее при фиксированных значениях х^\ х^0), ..., х*0) рассматриваем Ф(х(11}, х2, х$\ ..., л^0)) как функцию одной переменной х2. Находим
min Ф(х[1\х2, х$\ ..., х™).
x2eD
Значение х2, доставляющее минимум, обозначаем х^\ получаем
Ф(х{'\ хЧ\ xf\ х<?\ xf\ ...,х<°>)
и т. д., после п шагов получаем
.? Ф(х{'\...,х1")^ф (х[1\хЧ\...,хР).
В результатё одного шага покоординатного спуска происходит переход из начальной точки x(0) = (xi0), ..., х{,0)) в точку x(1) = (xi1}, ..., х{п1)). Если при этом оказывается, что
‘ ^ ф№...5^) = ф(Л...?^),
то начальный элемент х(0)—точка, доставляющая экстремум Ф(х). Если Ф(х(1))<Ф(*(0)), то выполняется следующий шаг покоординатного спуска, в котором за начальную точку принимается х(1), получаем х{2) и т. д. Этот процесс продолжается до тех пор, пока не выполнится какое-либо условие окончания алгоритма, например такое:
| Ф (x(fc+1}) — Ф (x(fc>) | < 8,
(9.6.1)
где в — заданная точность.
Заметим, что центральным звеном рассматриваемого алгоритма является поиск минимума функции одной переменной (см. 9.7).
9.6.2. Метод градиентного спуска. Напомним, что градиент функции Ф(х) определяется формулой
Вектор grac^(x) ортогонален линиям уровня Ф(х) = с=const, его направление совпадает с направлением максимального роста Ф(х) в заданной точке (рис. 9.17). В точке минимума функции grac^ = 0. Определим итерационный процесс:
х(к + 1) _ x(k) _ gra(| ф ^(*)^
(9.6.2)
368
где к>0—шаг спуска, х(0)— заданное начальное приближение к точке минимума.
Заметим, что если gradФ(л;(k))^0, то для достаточно малых значений к
... <Ф(х(к))<... <Ф(х(1))<Ф(х(0)).
Формула (9.6.2) представляет собой метод градиентного спуска с постоянным шагом к спуска. Итерационный процесс (9.6.2) продолжается до выполнения какого-либо условия окончания алгоритма, например (9.6.1), либо следующего:
|| gradФ(x(k+1)) || <е, (9.6.3)
где 8—заданная точность.
Для примера рассмотрим поиск минимума
Ф(х)=^+х| (9.6.4)
методом градиентного спуска. Согласно (9.6.2), имеем
Пусть нулевое приближение х(0)=(х^0)=1, л^0) = 1), шаг спуска к = 0,1. Первые три шага спуска дают следующие приближения
х[х)=0,95; Д2)=0,9025; х[Ъ)=0,8574;
хф = 0,80; хф = 0,6400; хф = 0,5120.
За три шага Ф(х) уменьшилась с 1,25 до 0,446. Естественно поставить вопрос: нельзя ли увеличить шаг спуска так, чтобы быстрее спуститься к точке минимума (в примере—х=(0,0))? Оказывается, что увеличивать к можно только до определенного предела. Слишком большой шаг может Привести к увеличению Ф(х). В рассматриваемом примере к —2 приводит к х^^х^^О, ху)=— 3) и значению Ф(хЦ)) = 9>Ф(х(0)) (рис. 9.18). Таким образом, наиболее важным моментом в методе градиентного спуска оказывается выбор шага. Формула (9.6.2) с постоянным шагом к практически не применяется.
369
Рис. 9.20
Различные стратегии выбора шага к = к(к) определяют разные варианты градиентного спуска.
Далее рассматривается вариант спуска, называемый наискорейшим градиентным спуском.
9.6.3. Метод Ъаискорейшего градиентного спуска. Из (9.6.2) можно определить значение Ф(х) в точке х{к+1):
Если х(к) определено, то значение целевой функции Ф в следующей точке х{к+1) оказывается функцией только шага спуска (рис. 9.19).
Будем выбирать к = к* из условия, чтобы функция Ф за этот шаг максимально уменьшила свое значение:
Выбор шага /г* -сводится к поиску минимума функции одной переменной.
* В примере п. 9.6.2 выбор шага в точке х(0) сводится к следующей Задаче:
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 168 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed