ВУЗ:
Составители:
где
)(k
h – скалярная величина, определяющая шаг изменения х,
)(k
c
– вектор, определяющий направление изменения х.
Методы минимизации функции ошибки отличаются выбором
с и h.
В соответствии с их выбором разные модификации итерационной
процедуры минимизации.
Метод скорейшего спуска
– выбирается с и h так, чтобы на
каждой итерации
f(x) уменьшалось максимально.
1) в качестве направления выбирается такое, которому
соответствует максимальное уменьшение
f(x) из точки
)(k
x , т.е.
(
)
min
0
)()()(
)(
=+
=
k
h
kkk
chxf
dh
d
при одинаковой длине вектора
)(k
c в разных направлениях
2) при выбранном
)(k
c
определяется такое
)(k
h
, которое
обеспечивает минимум функции вдоль
)(k
c , т.е.
()
0
)()()(
=+
kkk
chxf
dh
d
.
Раскрыв выражение функции и выполнив операции нахождения
производных, получим, что направление наибольшего убывания
функции – это направление по антиградиенту, а величина вектора
направления
)()( kk
rc =
- вектор невязки. Шаг изменения функции
получим
(
)
(
)
)()()()()(
,,
kkkkk
Arrrrh = ,
а функция ошибки убывает в соответствии с формулой
(
)
(
)
)()(
2
)()()()1(
,,)()(
kkkkkk
Arrrrxfxf −=
+
.
Отметим, что направление шага в МСС может заметно отклоняться
от направления на минимум. Объясняется это тем, что данное
направление определяется по наибольшему убыванию функции
f(x) в
начальной точке шага, а это не означает, что данному направлению
соответствует наибольшее конечное уменьшение функции. Поэтому
отклонение от этого направления может даже увеличить сходимость.
Если еще учесть, что вычисление скалярного произведения в числителе
и знаменателе на каждом шаге достаточно трудоемко и сложно, то
вполне разумно подумать о другом варианте
нахождения минимума
функции ошибки.
Метод покоординатного спуска
– выбирается такой путь,
чтобы на каждой итерации вычисления максимально просты.
Естественно, проще всего выбрать поочередное изменение каждой из
переменных на шаге, т.е. на первом шаге изменяется только
х
1
, на
втором –
х
2
и т.д.
В этом случае
)0()0()0()1(
chxx += ,
где
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
==
0
...
0
1
1
)0(
ec , тогда
(
)
()
(
)
()
11
)0(
1
11
1
)0(
)0(
)0(
,
,
,
,
a
r
Aee
er
Acc
cr
h ===
.
В результате выполнения этого шага
где h (k ) – скалярная величина, определяющая шаг изменения х, вполне разумно подумать о другом варианте нахождения минимума
функции ошибки.
c ( k ) – вектор, определяющий направление изменения х. Метод покоординатного спуска – выбирается такой путь,
Методы минимизации функции ошибки отличаются выбором с и h. чтобы на каждой итерации вычисления максимально просты.
В соответствии с их выбором разные модификации итерационной Естественно, проще всего выбрать поочередное изменение каждой из
процедуры минимизации. переменных на шаге, т.е. на первом шаге изменяется только х1, на
Метод скорейшего спуска – выбирается с и h так, чтобы на втором – х2 и т.д.
каждой итерации f(x) уменьшалось максимально.
1) в качестве направления выбирается такое, которому В этом случае x (1) = x (0) + h (0) c (0) ,
соответствует максимальное уменьшение f(x) из точки x (k ) , т.е. ( 0)
⎛1⎞
⎜0 ⎟ ( 0) (
r ( 0) , c ) ( )
r (0) , e1 r1(0)
d
dh
(
f x (k ) + h (k ) c (k ) ) = min
где c = e1 = ⎜ ⎟ , тогда h =
⎜ ...⎟
⎝0⎠
=
(c, Ac ) (e1 , Ae1 )
=
a11
.
h (k ) = 0
В результате выполнения этого шага
при одинаковой длине вектора c (k ) в разных направлениях
2) при выбранном c (k ) определяется такое h ( k ) , которое
обеспечивает минимум функции вдоль c (k ) , т.е.
d
dh
( )
f x (k ) + h (k ) c (k ) = 0 .
Раскрыв выражение функции и выполнив операции нахождения
производных, получим, что направление наибольшего убывания
функции – это направление по антиградиенту, а величина вектора
направления c ( k ) = r ( k ) - вектор невязки. Шаг изменения функции
получим
( )( )
h ( k ) = r ( k ) , r ( k ) r ( k ) , Ar ( k ) ,
а функция ошибки убывает в соответствии с формулой
( )2 (
f ( x) ( k +1) = f ( x) ( k ) − r ( k ) , r ( k ) )
r ( k ) , Ar ( k ) .
Отметим, что направление шага в МСС может заметно отклоняться
от направления на минимум. Объясняется это тем, что данное
направление определяется по наибольшему убыванию функции f(x) в
начальной точке шага, а это не означает, что данному направлению
соответствует наибольшее конечное уменьшение функции. Поэтому
отклонение от этого направления может даже увеличить сходимость.
Если еще учесть, что вычисление скалярного произведения в числителе
и знаменателе на каждом шаге достаточно трудоемко и сложно, то
