f (xk )sk f (xk )	(4.6)
относительно sk и положить
xk+1 = xk + sk .	(4.7)

Алгоритм (4.6), (4.7) называется методом Ньютона. Положительной сто-

роной этого метода является то, что если x0 достаточно близко к точке локального минимума функции f(х) с невырожденной матрицей Гессе (матрица

f (x* ) является тогда положительно определенной), то последовательность

{xk }, генерируемая методом Ньютона, будет сходиться к минимуму x* и скорость сходимости будет так называемой q-квадратичной.

Кнедостаткам метода относятся:

1.Метод не сходится глобально, то есть требует достаточно хорошее начальное приближение x0 ;

2.Требует аналитическое задание первых и вторых производных;

3.На каждом шаге необходимо решать систему уравнений (4.7);

4.В методе Ньютона нет ничего, что удерживало бы его от продвижения в сторону максимума или седловой точки, где f тоже равен нулю.

Здесь каждый шаг направляется в сторону стационарной точки локальной квадратичной модели независимо от того, является ли стационарная точка минимумом, максимумом или седловой точкой. Этот шаг оправдан при минимиза-

ции, только когда Гессиан f (xk ) положительно определен.

Вообще говоря, метод Ньютона не обладает высокой надежностью.

4.3. Метод Марквардта

Этот метод является комбинацией методов градиентного спуска и Ньютона, в котором удачно сочетаются положительные свойства обоих методов. Дви-

жение в направлении антиградиента из точки x0 , расположенной на значитель-

ном расстоянии от точки минимума x* , обычно приводит к существенному уменьшению целевой функции. С другой стороны, направление эффективного поиска в окрестности точки минимума определяются по методу Ньютона.

В соответствии с методом Марквардта, направление поиска sk определяется равенством

(H k +λk I )sk = − f (xk ),	(4.8)
а новая точка xk+1 задается формулой
xk+1 = xk + sk .	(4.9)

30

В системе (4.8) I – единичная матрица, H k – матрица Гессе, λk ≥ 0.

Вформуле (4.9) коэффициент перед sk взят равным 1, так как параметр λk

в(4.8) позволяет менять и длину шага, и его направление.

На начальной стадии поиска параметру λ0 приписывается некоторое большое значение, например 104 , так что левая часть равенства Марквардта (4.8) при

больших λ0 примет вид

(H 0 + λ0I)sk ≈ (λ0I)sk = λ0sk .

(4.10)

Таким образом, большим значением λ0 , как видно из (4.8) и (4.10), соответствует направление поиска

sk = −λ10 f (xk ),

то есть направление наискорейшего спуска.

Из формулы (4.8) можно заключить, что при уменьшении λk до нуля век-

тор sk изменяется от направления, противоположного градиенту, до направления, определяемому по Ньютону. Если после первого шага получена точка с

меньшим значением целевой функции, то есть f (x1 )< f (x0 ), следует выбрать

λ1 < λ0 и реализовать еще один шаг. В противном случае нужно положить λ0 =βλ0 , где β >1, и вновь реализовать предыдущий шаг.

Заметим, что недостатком метода Ньютона является то, что если матрица

Гессе H k не является положительно определенной, то Ньютоновский шаг sk не приводит к убыванию функции. Поэтому «исправление» Гессиана в соответ-

ствии с формулой H k + λk I модифицирует матрицу и при соответствующем вы-

боре λk делает ее положительно определенной, так как единичная матрица положительно определена.

Приведем теперь алгоритм метода:

1.Задать x0 – начальное приближение к x* , M – максимально допустимое количество итераций и ε – параметр сходимости.

2.Положить k = 0, λ0 =104 .

3.Вычислить f (xk ).

4.Проверить f (xk ) < ε?

(Можно взять

f (x

k

)

=

∂f (xk )

2

+...... +

∂f (xk )

2

).

∂x

∂x

1

n

Если да, то перейти к п.11.

5. Проверить k ≥ M ? Если да, то перейти к п.11.

31

6.Вычислить шаг sk , решив систему

(H k + λk I ) sk = − f (xk ).

7.Положить xk+1 = xk + sk .

8.Проверить: f (xk+1 )< f (xk )?

Если да, то перейти к п.9, иначе к п.10.

9.Положить λk+1 = 12 λk , k = k +1. Перейти к п.3.

10.Положить λk = 2λk . Перейти к п.7.

11.Вывод результатов:

xk , f (xk ), f (xk ), f (xk ) , k .

Отметим, что в различных модификациях метода Ньютона требуется большое количество вычислений, так как на каждой итерации следует сначала вычислить элементы матрицы n ×n , а затем решать систему линейных уравнений. Применение конечно разностной аппроксимации первых и вторых производных только ухудшит ситуацию.

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

Различные формы таких методов, часто называемые методами секущих, показали неплохие результаты в научных и технических исследованиях.

32