Алгоритм поиска минимума методом Ньютона.

1)Задаются . Вычисляются .

Полагается k=1.

2)Определяется матрица вторых производных(матрица Гессе)

3)Определяется обратная матрица

4)Вычисляются ,,,

.

4)Проверяется условие окончания вычислений

Если условие выполняется, то вычисления завершаются. Если нет, то полагается и переход к пункту 2.

2 подход к определению (3.11)

(3.12)

(3.12) – аппроксимирующая функция.

Пусть – выпуклая функция (простейшая ситуация).

Если исходная функция выпуклая, а признак выпуклости проверяется по второй производной.

Следовательно, если вторые производные функции совпадают, то аппроксимирующая функция тоже будет выпуклой. Поэтому аппроксимирующая функция имеет единственную точку минимума.

Решение приведенной системы является решением по (3.11)

Таким образом, мы можем функцию f(x) аппроксимировать в последовательности квадратичных функций.

Так как аппроксимирующая функция имеет минимум, то .

Если функция квадратичная, то для того чтобы дойти из в необходим один шаг.

Достоинства метода Ньютона:

1)Число итераций будет меньше, чем в градиентных методах, а скорость сходимости больше.

2)Для квадратичной функции точка минимума находится за один шаг и значение этой точки точное: ,.

Недостатки метода Ньютона:

1)для «овражной функции» решение получается приближенным

2)высокая сложность вычислений на каждой итерации (на каждой итерации находится матрица Гессе и обратная матрица)

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

При этом очередная точка определяется из соотношения:

Величина параметра выбирается из условия:

Для упрощения сложности метода используются квазиметоды.