Составители:
Рубрика:
10
Определение 3.2. Последовательность точек {x
k
}
∞
k=0
в методе
спуска называют траекторией спуска.
3.2. Выбор направления и шага спуска.
Метод наискорейшего спуска
Способ выбора направления спуска p
k
определяет конкретный
численный метод, а различные алгоритмы вычисления шага спу-
ска α
k
задают варианты этого метода.
Рассмотрим, каким образом выбирается направление p
k
, ко-
торое обеспечивает убывание целевой функции на бесконечно
малом положительном шаге α. Предполагая непрерывность пер-
вых частных производных целевой функции, разложим ее в ряд
Тэйлора в точке x
k
: f (x
k
+ αp
k
) = f (x
k
) + α (f
΄ (x
k
), p
k
) + o(α), где
(...) – скалярное произведение. Тогда если
(f ΄ (x
k
), p
k
) < 0 , (3.3)
то f (x
k
+ αp
k
) – f (x
k
) < 0. Таким образом, чтобы p
k
было направ-
лением спуска, необходимо и достаточно, чтобы p
k
составляло
острый угол с антиградиентом.
Определение 3.3. Методы, основанные на выборе в качестве
направления спуска p
k
антиградиента g
k
или – βf ΄(x
k
), β > 0 , на-
зываются градиентными. ♣
Градиент, как правило, меняется при переходе из точки в точ-
ку, следовательно, меняется и направление наискорейшего убы-
вания функции. Антиградиентное направление может не являться
наилучшим из возможных направлений спуска, поскольку всег-
да существует направление из текущей точки непосредственно в
точку минимума (см. рис. 1.3), но мы его не знаем.
Будем рассматривать следующий способ выбора шага. Введем
функцию одной скалярной переменной F
k
(α) = f (x
k
+ αp
k
) и опре-
делим α
k
, решая задачу одномерной минимизации
()
0
min
≥α
→α
k
F
(3.4)
аналитически, например, для квадратичной функции, либо каким-
либо итеративным методом.
Разложим в ряд Тэйлора в точке x
k
функцию
f (x
k +
αp
k
) = f (x
k
) + α (f ' (x
k
), p
k
) +
1
α
2
(f '' (x
k
) p
k
, p
k
) + o (α
2
).
2
27
Выделив диапазон A7:Q7, потянем «крестик» вниз (рис. 7.14)
до тех пор, пока не появится в столбце М запись, запрограммиро-
ванная нами, «корень получен за … шагов», где количество шагов
прописывается из столбца А (рис. 7.15).
Рис. 7.14
Для полноты картины нам требуется построить график пере-
хода от итерации к итерации и в итоге – к искомой точке мини-
мума. Для этого воспользуемся вкладкой «Вставка» – «мастер
диаграмм» – «точечная, на которой значения соединены от-
резками». Заполнив диапазон значений координат x
1
и x
2
, вы-
делив соответственно диапазоны J6:J10 и K6:K10, мы получим
ломаную, изображенную на рис. 7.15. Через каждую вершину от-
резков ломаной можно для наглядности условно провести линии
уровня поверхности, как на рис. 7.16.
Рис. 7.15
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
