Составители:
Рубрика:
24
Затем создадим «заготовки» для вычислений в виде коммента-
риев «№», «x
k
», «g
k
», «α
k
», «x
k+1
», «||g
k
||» и «z» (рис. 7.4, где «№» –
номер итерации; «||g
k
||» – евклидова норма антиградиента; «z» –
значение квадратичной функции в точке минимума, а «g
k
», «α
k
»,
«x
k+1
» вычисляются по соответствующим формулам: антигради-
ента и (3.6), (3.2)).
Рис. 7.4
Заполним ячейки A6, B6 и C6 (рис. 5): номер итерации – 1, на-
чальное приближение – (0, 0).
Рис. 7.5
Выделим ячейки E6:F6, в поле ввода формулы (рис. 7.6) поста-
вим знак «равно»
1
и воспользуемся «мастером функций» (слева
вверху на рис. 7.6). Поскольку выделен диапазон по горизонтали,
а антиградиент – это вектор-столбец, то вызываем функцию транс-
понирования «трансп». В нее записываем знак «–» из формулы
антиградиента, открываем и закрываем скобки, в которых запи-
сываем функцию перемножения матриц «мумнож», воспользо-
вавшись снова «мастером функций», к ней прибавляем диапазон
Рис. 7.6
1
Со знака «=» начинается ввод любой вычислительной формулы.
13
но, луч L
0
являются касательными к линии уровня Г
1
= { x | f (x) =
= f (x
1
)} в точке x
1
. Из точки x
1
проводят спуск в перпендикуляр-
ном линии уровня Г
1
направлении g
1
, пока соответствующий луч
L
1
не коснется в точке x
2
линии уровня, проходящей через эту точ-
ку, и т. д.
В градиентных методах спуск происходит по нормали к линии
уровня, траектория спуска носит зигзагообразный характер и гра-
диенты в любых двух последовательных точках ортогональны.
3.6. Сходимость и проблема «оврагов»
Градиентный метод сходится достаточно быстро, если для ми-
нимизируемой функции f (x) поверхности уровня близки к сфе-
рам (при n = 2 – к окружностям – см. рис. 3.1). Если же линии
уровня сильно вытянуты в каком-то направлении, то по нормали
к этому направлению целевая функция меняется значительно бы-
стрее, чем вдоль направления. Такой характер целевой функции
называется овражным (рис. 3.2). «Дно оврага» к тому же может
быть искривлено.
Если начальная точка x
0
попадает на «склон оврага», то на-
правление градиентного спуска из этой и последующих точек
будет почти перпендикулярным ко «дну оврага», хотя надо бы
двигаться вдоль «дна оврага». Из-за малых шагов процесс прак-
тически останавливается вдали от точки минимума x
*
, поэтому
сходимость градиентного метода может быть очень медленной.
Рис. 3.2
Поверхностями уровня квадратичной функции (в случае ПО)
служат n-мерные эллипсоиды с центром в точке x
*
. В двумерном
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
