3.5. Продолжение обсуждения метода Ньютона.

Из доказанной теоремы следует, что чем меньше константа Липшица отображения x  f (x), т. е. чем ближе это отображение к константе, и, следовательно, чем ближе функция f к квадратичной, тем быстрее сходится метод Ньютона. В частности, если f квадратична: f(x) = (Ax, x)/2 + (b, x) + c, то метод Ньютона конечен, а именно, сходится за один шаг, причем из любой начальной точки.

Если снизить требования гладкости на функцию f, например, отказаться от условия Липшица для f , то скорость сходимости, вообще говоря, падает.

Как позволяет думать теорема 4.4, метод Ньютона даже для сильно выпуклых функций в общем случае сходится лишь локально. В следующем пункте мы описываем модификации этого метода, которые могут обладать свойством глобальной сходимости.

3.6. Методы Ньютона с регулировкой шага.

Эти методы еще называют методами Ньютона — Рафсона, или демпфированными методами Ньютона. Они строятся по аналогии с градиентными методами с переменным шагом. Общий вид их таков

xn+1 = xn  n[f (xn)]1f (xn).

Длина шага может выбираться с помощью алгоритма дробления шага (см. п. 2.9), требуя, например, выполнения неравенства

f(xn+1) = f(xn n[f (xn)]1f (xn))   f(xn)  n(f (xn), [f (xn)]1f (xn)),

или, как в методе наискорейшего спуска полагая

n = argmin0{f(xn  [f (xn)]1f (xn))}.

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

3.7. Метод Левенберга — Маркардта.

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

xn+1 = argmin (x) = argmin {f(xn) + (f (xn), x  xn) +

+  1 2 (f (xn)(x  xn), x  xn) +  ln 2 ||x  xn||2},

где lⁿ — некоторый параметр (вообще говоря, свой на каждом шаге). Первые три слагаемых в определении функции  представляют собой квадратичную аппроксимацию функции f, а последнее слагаемое — "штраф", не позволяющий точке xⁿ⁺¹ уходить далеко от точки xⁿ (с идеями метода штрафов мы еще столкнемся ниже). Минимум (по крайней мере, стационарная точка) функции  вычисляется в явном виде из следующего уравнения (относительно x)

Q = (x) = f (xn) + f (xn)(x xn) + ln(x xn).

Как легко видеть,

xn+1 = argmin (x) = xn  [f (xn) + lnI]1f (xn).

(13)

Последняя формула и есть метод Левенберга — Маркардта.

Очевидно, что если lⁿ = 0, то (13) представляет собой метод Ньютона, а если lⁿ велико, то (поскольку [f (xⁿ) + lⁿI]^1  (lⁿ)^1I при больших lⁿ) формула (13)близка к градиентному методу. Поэтому, подбирая значения параметра lⁿ, можно добиться, чтобы метод (13), во-первых, сходился глобально, и во-вторых,квадратично. Можно, например, выбирать lⁿ из следующих соображений: угол между направлениями шага и антиградиента должен быть острым, а значение функции на каждом шаге должно квалифицировано убывать. В этом случае lⁿ должно удовлетворять следующим условиям (здесь мы обозначаем "антинаправление" шага [f (xⁿ) + lⁿI]^1f (xⁿ) через yⁿ)

(yn, f (xn)) ||yn|| · || f (xn)||   1,

f(xn+1)  f(xn)  2(yn, f (xn)),

где ₁  (0, 1) и ₂  (0, 1/2) — параметры.