ВУЗ:
Составители:
Рубрика:
то можно выбрать так, чтобы
В частности, выбрав для определенности положительный корень для
получим
Полезность сопряженных систем для оптмизации связана с тем, что в систе-
ме координат, построенной на сопряженных векторах, задача оптимизации
квадратичной функции выглядит обобенно просто.
Действительно, пусть — некоторая нормированая сопряжен-
ная система из векторов -мерного пространства переменных. В силу
своей линейной независимости эта система образует базис исходного прост-
ранства и, следовательно, любой вектор может быть представлен в виде
линейной комбинации
В системе координат, связанной с сопряженными векторами, квадратичная
функция принимает исключительно простой вид
где и задача минимизации имеет простое решение
Применить этот подход на практике мешает отсутствие сопряженной сис-
темы векторов. Такую ситему можно было бы построить, взяв за исходный
материал произвольную ( например, ортонормированую ) систему линейно
независимых векторов, однако, при этом необходимо вычислять призведен-
ия матрицы на некоторые векторы, что на первый взгляд требует знания
этой матрицы. Однако, если — известна, что мешает нам применить мет-
од Ньютона и решить задачу минимизации за один шаг ?
Так вот метод сопряженных градиентов умудряется совместить пост-
роение системы сопряженных векторов с поэтапным ремением
задачи минимизации и все это без явного использования матрицы !
Рассмотрим теперь собственно алгоритм. Пусть решается задача мини-
мизации
(31)
21
то можно выбрать так, чтобы
;7*
В частности, выбрав для определенности положительный корень для
"
получим
Полезность сопряженных систем для оптмизации связана с тем, что в систе-
ме координат, построенной на сопряженных векторах, задача оптимизации
квадратичной функции выглядит обобенно просто.
//0
Действительно, пусть — некоторая нормированая сопряжен-
ная система из векторов -мерного пространства переменных. В силу
своей линейной независимости эта система образует базис исходного прост-
ранства и, следовательно, любой вектор может быть представлен в виде
линейной комбинации
В системе координат, связанной с сопряженными векторами, квадратичная
функция принимает исключительно простой вид
;
Z5
где
и задача минимизации имеет простое решение
= D
-*
; -*
; ! -*
Применить этот подход на практике мешает отсутствие сопряженной сис-
темы векторов. Такую ситему можно было бы построить, взяв за исходный
материал произвольную ( например, ортонормированую ) систему линейно
независимых векторов, однако, при этом необходимо вычислять призведен-
ия матрицы на некоторые векторы, что на первый взгляд требует знания
этой матрицы. Однако, если — известна, что мешает нам применить мет-
од Ньютона и решить задачу минимизации за один шаг ?
Так вот метод сопряженных градиентов умудряется совместить пост- //0
роение системы сопряженных векторов с поэтапным ремением
задачи минимизации и все это без явного использования матрицы !
Рассмотрим теперь собственно алгоритм. Пусть решается задача мини-
мизации
= -*
= <
; -*
(31)
21
