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

Матрица Гессе функции это матрица вторых частных производных, т. е.

Пусть матрица Гессе функции вычисленная при Рассмотрим функцию

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

Если не вырождена, то уравнение имеет решение:

Соотношение определяет итерацию метода Ньютона (его также иногда называют методом Ньютона — Рафсона). Оно вполне согласуется с общей формулой градиентных методов, задаваемой равенством (5 3-7) при

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

В тех случаях, когда неквадратическая функция, точка вообще говоря, не будет стационарной, и потому метод не сойдется за одну итерацию. Однако метод останется допустимым до тех пор, пока матрица будет положительно-определенной. Это условие должно выполняться по крайней мере в некоторой окрестности точки минимума. В этой окрестности сходимость является квадратичной, а это означает, что число верных знаков в значении 0 на каждой итерации приблизительно удваивается, и так будет до тех пор, пока дальнейшее уточнение не будет ограничено ошибками округления при вычислениях. Вне такой окрестности сходимость не может быть гарантирована. Следует отметить, что шаг где положительноопределенная матрица, является решением задачи минимизации функции Чем более приближается матрица тем ближе оказывается эта модифицированная задача к исходной.

Возвращаясь к случаю квадратической функции с положительноопределенной матрицей Гессе Н, отметим, что шаг — в методе Ньютона является единственным, приводящим к минимуму за одну итерацию. Любой другой шаг не приведет в точку минимума. Если определить эффективность метода как отношение уменьшения значения функции, полученного за одну итерацию, к максимально возможному уменьшению, то эффективность метода Ньютона здесь окажется равной 1. В [93] было показано, что эффективность метода, использующего направление ограничивается значениями

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

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

Пусть разложение по собственным значениям (см. раздел А.5) и градиент выражается через собственные векторы как Тогда при

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

Несмотря на то что метод Ньютона обладает достоинствами для задач, в которых он работает, он непрактичен по следующим двум причинам:

1) во многих случаях он не работает, ибо не обязательно положительно определена, исключая окрестность точки минимума;

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

Разработаны различные приемы преодоления этих сложностей при сохранении преимуществ данного метода. Методы Марквардта и выбора направления решают проблему положительной определенности, в то время как методы Гаусса и переменной метрики устраняют

необходимость расчета вторых производных. Все эти методы будут описаны в последующих разделах.

Заметим, что первый из двух недостатков (расходимость) должен быть устранен, если этот метод предстоит применять Вторая трудность (необходимость расчета вторых производных) — просто элемент неудобства. Следует оценить, является ли метод Ньютона (модифицированный, чтобы обеспечить сходимость) настолько более эффективным, чем методы, не требующие знания вторых производных, чтобы вычисление этих производных было оправдано. У нас нет определенного ответа на этот вопрос, но некоторый опыт позволяет нам сделать следующие предварительные заключения:

1) если модель хорошо описывает данные, метод Гаусса часто требует не большего числа итераций, чем метод Ньютона [11];

2) если модель подобрана плохо, метод Ньютона может потребовать меньшего количества итераций, чем метод Гаусса, но время вычислений для обоих методов ориентировочно одинаково [78].