Метод Розенброка
Представляет усовершенствование метода покоординатного спуска.
Понятие сопряжённости векторов В методе сопряженных градиентов используется понятие сопряжённости векторов. < A, Q× B > = 0 Q – квадратная матрица того же порядка, что и вектора. В этом случае вектора А и В будут Q сопряжёнными. Q = [1]
Сходимость метода сопряжённых градиентов строго обоснована для квадратичных целевых функций. F(X) = A* X + X TЮ Х /2, где Ю – матрица Гессе. Минимизация такой функции осуществляется не более чем за n одномерных минимизаций вдоль определённым образом выбираемых сопряжённых направлений.
Метод сопряжённых градиентов (Флетчера – Ривса) 1) Задается начальная точка поиска Х: = Х 0 2) Рассчитывается grad F(X) 3) Определяется первое направление для поиска P: = -grad F(X) 4) Производится одномерная минимизация на направлении P F (X `) = min F(X +h P) Получаем новую отображающую точку - X: = X ` 5) Рассчитывается градиент в этой точке - grad F(X `) 6) Вычисляется коэффициент β, определяющий новое направление поиска. 7) Определяется новое сопряжённое направление P: = - grad F(X`) +β P 8) Проверяется условие прекращения поиска, например, на близость grad F(X`) к 0 - grad F(X`) ≤ δ. Если они не выполнены, то переход к оператору 4) 9) Через n шагов поиска по сопряжённым направлениям осуществляется обновление метода, т.е. переход к оператору 2). Предложены различные формулы для вычисления β. приведем одну из них:
grad F(Xi)* grad F(Xi)
grad F(Xi-1)* grad F(Xi-1)
|
< A * B > = 0
βi-1 =
