Составители:
Рубрика:
20
5. МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ
(МСГ)
5.1. Алгоритм метода
Идея этого метода в том, чтобы на каждом шаге в качестве на-
правления спуска использовать не антиградиент, а его линейную
комбинацию с прежним направлением спуска. Последователь-
ность векторов спуска p
k
строится следующим образом:
1.
00
gp =
, т. е. первый шаг делается по антиградиенту;
2.
k
k
kk
pgp β+=
++ 11
, где
kk
k
gg
1+
=β
;
3.
,
1 k
k
kk
pxx α+=
+
где α
k
находится из формулы (3.5),
2,1,0=k
, ... .
Заметим, что при вычислении β
k
используются только гради-
енты, а для вычисления нового направления нужно помнить и
использовать старое направление, а не старый антиградиент. В
методе сопряженных градиентов новое и старое направления не
ортогональны.
Определение 5.1. Векторы называются сопряженными,
если они удовлетворяют условию (p
i
, Ap
j
) = 0 при любом
ji ≠
,
т. е. являются A-ортогональными. ♣
В случае минимизации положительно определенной квадра-
тичной формы с матрицей A все направления спуска p
i
оказыва-
ются A-ортогональными, из чего и происходит название метода.
Теорема 5.1. Если целевая функция от n переменных пред-
ставляет собой квадратичную форму, то алгоритм сопряженных
градиентов дает точку минимума не более чем за n шагов. ♣
Практически же в «овражных» случаях из-за неточности вы-
числения шага может потребоваться несколько больше шагов, в
некоторых случаях метод может зацикливаться.
5.2. Геометрическая интерпретация
Сделав из начальной точки x
0
шаг по методу наискорейшего
спуска, вычислим антиградиент g
1
в новой точке x
1
(рис. 5.1).
Будем использовать вместо антиградиента g
1
направление
спуска
0
0
11
ggp β+=
, вдоль которого нужно дойти до точки ми-
17
4. МЕТОД ПОКООРДИНАТНОГО СПУСКА
(МПКС)
В этом методе в качестве очередного направления спуска
выбирается направление одной из координатных осей p
k
= e
i
=
= (0, ... , 0,1
i
, 0,...,0)
T
, а шаг спуска – по формуле (3.5).
4.1. Геометрическая интерпретация
Геометрический смысл метода состоит в движении в направле-
ниях, параллельных координатным осям (рис. 4.1, а): точка (x
0
, y
0
)
описывает начальное приближение. Проводя спуск по координа-
те x, попадем в точку (x
1
, y
0
). Двигаясь параллельно оси ординат,
придем в точку (x
1
, y
1
) и т. д. При движении вдоль координатной
оси идем до точки минимума, т. е. касания некоторой линии уров-
ня.
Рис. 4.1
Число шагов зависит от начального приближения и, главное, от
ориентации линий уровня относительно координатных осей. Так,
в задаче минимизации квадратичной функции при ориентации
осей эллипсов вдоль координатных осей достаточно однократ-
ного применения цикла. В овражных случаях при произвольной
ориентации относительно координатных осей даже в квадратич-
ной задаче метод работает плохо (рис. 4.1, б).
а) б)
