Метод Ньютона

Пусть функция f(x) дважды дифференцируема в Е_п. Тогда для нее можно записать разложение по формуле Тейлора в окрестности точки х:

f(x)=f(x)+<f(x), x-x>+1/2<f"(x)(x-x), x-x>+0(||x-x||)

Отсюда видно, что поведение функции f(x) с точностью до величины порядка 0(||х-x||) может быть описано квадратичной функцией

Ф(k)=1/2<f"(x)(x-x), x-x>+<f(x), x-x>+f(x) (1)

Минимизируем функцию Ф(k) вместо f(x). Найдем ее точку минимума xиз условия Ф'(х)=0:

Ф'(х)=f"(x)(x-x)+f(x)=0 (2)

Пусть матрица Гессе f"(х) положительно определена при всех хЄ Е_п и, следовательно, невырождена (det f "(х)>0). Тогда существует обратная матрица [f"(х)]. Отметим, что квадратичная функция (1) с положительно определенной матрицей f"(x) сильно выпукла и уравнение (2) определяет единственную точку глобального минимума функции Ф(x). Умножим слева обе части равенства (2) на матрицу [f"(х)]и найдем точку минимума xквадратичной функции (1), аппроксимирующей f(x) в окрестности точки х=x:

x=x-[f"(х)]f(x), k=0,1,… (3)

Итерационный процесс (3), начатый из произвольной точки xЄ Е_п, называется методом Ньютона минимизации функции многих переменных и является обобщением метода Ньютона в одномерном случае.

Очевидно, для квадратичной функции с положительно определенной матрицей А применение метода Ньютона обеспечивает получение точки глобального минимума ровно за один шаг из любой точки xЄ Е_п.

Для выпуклой функции, отличной от квадратичной, применение этого метода обеспечивает, как правило, быструю сходимость. Дело в том, что на каждом шаге итерационного процесса (3) используется информация о поведении функции f(x) в окрестности точки x, содержащаяся не только в значениях первых, но и вторых ее частных производных. Поэтому при прочих равных условиях следует ожидать более быструю сходимость метода Ньютона по сравнению с градиентными методами.

При выборе достаточно хорошего начального приближения xЄ Е_п минимизирующая последовательность {x} для сильно выпуклой дважды дифференцируемой функцииm f(х) сходится к точке минимума с квадратичной скоростью р(x, х*)<=сq, qЄ(0;1). Если же точка х⁰ выбрана недостаточно близкой к точке х*, то последовательность (3) может расходиться.

Отметим, что даже сходящаяся последовательность {x} метода Ньютона не всегда обеспечивает монотонное убывание f(х), т.е. неравенство f(x)<f(x) для некоторых k = 0,1,... может нарушаться. Этот недостаток устранен в обобщенном методе Ньютона:

x=x-α[f"(x)]f(x),

где величина α>0 находится на каждом шаге из условия исчерпывающего спуска по направлению р=-[f"(x)]f(x).

Недостатком метода Ньютона является необходимость вычисления и обращения матрицы Гессе на каждой итерации.

Пример 3.13. Найти точку минимума функции f(x)=4x+3x-4xx+xметодом Ньютона из начальной точки х=(0,0).

Градиент f(х°)=(-1,0), матрица Гессе f"(х°)=A=. Найдем обратную матрицу [f"(х°)]=. С помощью формулы (3) получаем х=х°-α[f"(х°)]f(х°)=(-3/16, -1/8). Так как f(х)= (0,0), то задача решена: х*=х. Целевая функция квадратична, поэтому решение задачи получено за одну итерацию.

Дата добавления: 2014-01-07