Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка nxn, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.
Алгорим метода Дэвидона - Флетчера - Пауэлла
Начальный этап. Пусть eps >0 - константа для остановки. Выбрать точку x1 и начальную симметрическую положительно определенную матрицу D1 . Положить y1 = x1, k=j=1 и перейти к основному этапу.
Основной этап. Шаг 1. Если ||grad(f(x))|| < eps , то остановиться; в противном случае положить dj = -Dj*grad(f(yj)) и взять в качестве lymj - оптимальное решение задачи минимизации f(yj + lym*dj) при lym >= 0. Положить y[j+1] = yj + lymj*dj. Если j < n, то перейти к шагу 2. Если j=n, то положить y1=x[k+1]=y[n+1], заменить k на k+1, положить j=1 и повторить шаг 1.
Шаг 2. Построить Dj+1 следующим образом:
pjpj(t) ...........Djqjqj(t)Dj
Dj+1 = Dj +...------------.... -...-------------- ,
pj(t)qj............. qj(t)Djqj
где
pj = lymj*dj,
qj = grad(f(y[j+1])) - grad(f(yj)).
Заменить j на j+1 и перети к шагу 1.
