Метод Ньютона. Это классический метод второго порядка

Это классический метод второго порядка. Если направление градиента находится из линейного представления функции в окрестности текущей точке, то в методе Ньютона используется квадратичная аппроксимация функции цели. Квадратичная аппроксимация дифферен­цируемой функции f в точке X ^k записывается в виде

, где Н – матрица вторых производных функции f (матрица Гессе). В стационарной точке градиент функции равен нулю, что применительно дает Полагая матрицу H неособенной (существует обратная к ней матрица), получаем рекуррентный способ генерирования последовательности точек

Исходя из вывода формулы ясно, что для квадратичной функции цели X ^{k +1} является точкой минимума. Следовательно, минимум такой функции из любой начальной точки достигается за один шаг. Для нелинейной унимодальной функции, отличной от квадратичной, точки последовательности асимптотически приближаются к минимуму. Условие окончания поиска: . (В случае линейной аппроксимации матрица Н становится единичной и поиск вырождается в градиентный).

Необходимым условием сходимости метода является существование обратной матрицы во всех генерируемых точках. Доказательство сходимости метода получено при условии, что начальная точка достаточно близка к точке минимума. При этом метод имеет высокую скорость сходимости. Если поиск начинается с удаленной точки и функция существенно отличается от квадратичной, метод может не сходиться или давать слабую сходимость. Причина такого поведения в том, что значение функции в точке X ^{k+ 1} не обязательно меньше, чем в точке X ^k. Для устранения отмеченных недостатков предложены модификации метода. Чтобы обеспечить регуляризацию матрицы Н (невырожденность), она деформируется добавлением к ней единичной матрицы с неотрицательным скалярным множителем e: H^¢= Н+ e ×Е. Значение e зависит от X и подбирается так, чтобы все собственные значения матрицы H^¢ были положительными. Тогда эта матрица положительно определена и существует обратная матрица H^¢-1, которая также положительно определена. Возможное ухудшение функции в очередной точке исключается введением в формулу изменяемого параметра h. Модифицированная формула принимает вид

При этом возможен вариант с дискретным шагом h, как в градиентном методе, либо с определением оптимального h^* с помощью одномерной минимизации (наискорейший спуск):

Пример поиска минимума функции
f =(1- x ₁)²+5(x ₁²- x ₂)² методом Ньютона с регулируемым шагом приведен на рис.