23. Теорема методов сопряжённых направлений

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

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

Доказательство. Пусть для матрицы квадратичной функции (3.1) известны сопряженных векторов , , …, . Используем эти векторы как направления в задаче минимизации квадратичной функции из произвольной точки с помощью точных одномерных поисков по формулам (3.6) и (3.10) при следующей схеме метода сопряженных направлений:

, , . (3.13)

Поскольку , то, продолжая эти преобразования, получим:

, . (3.14)

Отсюда и по формуле (3.3) имеем:

,

.

Тогда

, .

В силу условия точного одномерного поиска (3.7) и определения сопряженных векторов (3.11) имеем при . Поскольку (3.7) можно представить в виде , то для метода сопряженных направлений получим:

, . (3.15)

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

.

Умножая это векторное равенство скалярно на вектор и учитывая условия ортогональности (3.15), получим равенство , откуда следует . По свойству квадратичной функции (3.5) для градиента , то есть имеем . Тем самым доказано, что метод сопряженных направлений (3.13) сходится к оптимальному решению задачи минимизации квадратичной функции не более чем за итераций. 

Рис. 3.2. Расширение подпространств

Равенства (3.15) показывают, что вектор градиента в конечной точке любой итерации ортогонален всем предыдущим направлениям поиска. Эти равенства отображают Принцип расширяющихся подпространств, который допускает наглядную геометрическую интерпретацию, представленную на рис. 3.2.

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

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