22. Сопряжённые векторы и их свойства

В эффективных методах оптимизации используется понятие сопряженных направлений.

Пусть – симметрическая и положительно определенная матрица размерности .

Определение 3.1. Ненулевые векторы , , …, пространства при называются -сопряженными или просто сопряженными, если для них

, . (3.11)

Если матрица равна единичной матрице , то и условие сопряженности принимает вид . Это означает, что скалярное произведение векторов равно нулю. В этом случае условие сопряженности векторов эквивалентно условию их ортогональности . В частности, собственные векторы матрицы являются сопряженными.

Лемма 3.1. Если векторы , , …, -сопряженные, то они линейно независимы.

Доказательство. Составим линейную комбинацию векторов и приравняем ее нулю

. (3.12)

Транспонируем это равенство и умножим его справа на , где – произвольный вектор из данной системы векторов. В силу определения сопряженности (3.11) слагаемых левой части обращаются в нуль, и в результате имеем

.

По свойству (3.2) положительно определенной квадратичной функции , поэтому . Итак, равенство (3.12) может выполняться только при нулевых значениях коэффициентов , , …, , откуда и следует линейная независимость сопряженных векторов. 

Количество сопряженных векторов не может быть больше, чем .

Следствие 3.1. Сопряженные векторы , , …, образуют базис в пространстве .

Любой вектор пространства можно разложить по базису из сопряженных векторов. Для положительно определенной квадратичной функции эффективный поиск минимума можно проводить в сопряженных направлениях. Это утверждение основано на свойствах сопряженных направлений.

Теорема 3.1. Пусть – некоторое направление поиска в пространстве , а и – две различные точки минимума квадратичной функции , полученные из двух точек и в направлении . Тогда направление сопряжено к направлению .

Доказательство. Если и – точки минимума квадратичной функции , полученные из двух точек и в направлении , то по свойству (3.7) точного одномерного поиска для квадратичной функции выполняются условия ортогональности:

, .

Но по формуле (3.3) градиента квадратичной функции

, .

Условия ортогональности градиентов направлению примут вид:

, .

Вычитая эти равенства и используя свойства матриц, получим:

.

Обозначая , придем к утверждению теоремы. 

Рис. 3.1. Сопряженные направления

Доказанную теорему называют Свойством параллельного подпространства. По свойству параллельного подпространства выполнение двух одномерных поисков из разных точек в направлении позволяет получить сопряженное к направление (рис. 3.1). Точка минимума квадратичной функции при может быть найдена одномерным поиском из точек или в направлении , то есть в результате проведения трех одномерных поисков.

Гладкие овражные функции вблизи дна оврага можно аппроксимировать квадратичными функциями. Поэтому свойства сопряженных направлений позволяют находить эффективные направления поиска для любых гладких функций.

< Предыдущая		Следующая >