Загребаев Методы матпрограммирования 2007
.pdfа)
б)
Рис. 3.23. Типы линий уровня: а – линии уровня близкие к окружности,
б– линии уровня «овражного типа»
Суменьшением отношения Mm линии уровня становятся все
более вытянутыми, и направление вектора градиента в большинстве точек все более существенно отклоняется от направления в точку минимума. Это приводит к замедлению скорости сходимости
(рис. 3.23, б).
Особенно медленно градиентные методы сходятся, когда функция имеет «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции – эта группа характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно. Если линии уровня у такой функции сильно вытянуты, то градиентные методы сходятся медленно.
205
Рис. 3.25. Блок-схема градиентного метода, где x0 – аргумент в начале итерации;
|
– текущее значение аргумента; |
f0 |
– функция в точке x0 ; f – функция в точке |
||
x |
|||||
|
; f0′ – производная в точке |
|
; |
λ0 |
– начальное λ для каждой итерации |
x |
x |
В данном методе окончание итерационного процесса осуществляется по условию – || f ′(xk ) ||≤ ε .
207
Задача. Найти методом наискорейшего спуска минимум функции f (x) = 2x12 + x22 + x1 x2 + x1 + x2 с точностью ε = 0,05 (по норме градиента). В качестве начальной точки принять точку x 0 = (0,0) . Значения функции и градиента в этой точке, соответственно, будут:
|
|
|
|
f (x 0 ) = 0 ; |
|
|
||
|
|
∂f |
|
|
|
|
||
|
|
= 4x1 + x2 |
|
|
1 |
|
||
|
|
|
|
+1 |
|
|||
|
|
|
|
|||||
f (x |
|
∂x1 |
|
|
|
|||
0 |
) = |
|
|
|
= |
. |
||
|
|
∂f |
= 2x2 + x1 |
|
|
1 |
|
|
|
|
|
|
+1 |
|
|||
|
|
|
||||||
|
|
|
∂x2 |
|
|
x=x |
|
|
|
|
|
|
|
0 |
|
|
Очевидно, нетрудно найти точное решение данной задачи:
x * = − |
1 |
; |
x* = − |
3 |
; |
f * = − |
2 |
≈ −0,2857 . |
|
|
|
||||||
1 |
7 |
|
2 |
7 |
|
7 |
|
|
|
|
|
|
|
Решим задачу с использованием градиентного метода. В результате получим следующую последовательность действий.
1-я итерация:
|
0 |
1 |
|
|
1 |
|
0 |
|
0 |
|
0 |
|
|
λ |
|
− λ |
|
f (x |
|
; |
x |
= x |
− λf (x |
|
|
|
|
, |
|||||||
|
) = |
|
|
|
) = |
− |
= |
|
|||||||||
|
|
1 |
|
|
|
|
|
|
|
|
0 |
|
|
λ |
|
− λ |
|
f (x0 ) ≈1,4 > ε.
Так как x1 = −λ и x1 = −λ, |
то |
f (x1 (λ)) = f (λ) = 4λ2 − 2λ . |
||||||||||||
1 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
Таким образом, |
значение |
λ , обеспечивающее минимум функ- |
||||||||||||
|
|
|
|
0 |
|
|
1 |
|
|
0 |
|
|
1 |
|
ции по направлению f (x |
) |
= |
|
из точки x |
, будет |
λ = |
|
. |
||||||
|
|
|
4 |
|||||||||||
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
Окончательно получаем для первой итерации: |
|
|
|
|||||||||||
|
1 |
|
−1 4 |
|
|
|
1 |
|
|
|
|
|
|
|
x |
|
|
|
; |
|
f (x |
) = −1 4 = −0,25 . |
|
|
|
||||
|
= |
|
|
|
|
|
|
|
||||||
|
|
|
−1 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
208 |
|
|
|
|
|
|