2015-01-30
483
Градиентные методы, базирующиеся только на вычислении градиента R(x), являются методами первого порядка, так как на интервале шага они заменяют нелинейную функцию R(x) линейной.
Более эффективными могут быть методы второго порядка, которые используют при вычислении не только первые, но и вторые производные от R(x) в текущей точке. Однако у этих методов есть свои труднорешаемые проблемы — вычисление вторых производных в точке, к тому же вдали от оптимума матрица вторых производных может быть плохо обусловлена.
Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядка с исключением их недостатков. На начальных этапах (вдали от оптимума) метод ведет себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.
Первый шаг аналогичен первому шагу метода наискорейшего спуска, второй и следующий шаги выбираются каждый раз в направлении, образуемом в виде линейной комбинации векторов градиента в данной точке и предшествующего направления.
|
|
|
Алгоритм метода можно записать следующим образом (в векторной форме):
Величина a может быть приближенно найдена из выражения
Алгоритм работает следующим образом. Из начальной точки х 0 ищут min R(x) в направлении градиента (методом наискорейшего спуска), затем, начиная с найденной точки и далее, направление поиска min определяется по второму выражению. Поиск минимума по направлению может осуществляться любым способом: можно использовать метод последовательного сканирования без коррекции шага сканирования при переходе минимума, поэтому точность достижения минимума по направлению зависит от величины шага h.
Для квадратичной функции R(x) решение может быть найдено за п шагов (п — размерность задачи). Для других функций поиск будет медленнее, а в ряде случаев может вообще не достигнуть оптимума вследствие сильного влияния вычислительных ошибок.
Одна из возможных траекторий поиска минимума двумерной функции методом сопряженных градиентов приведена на рис. 17.
