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

9.3.1. Описание общей схемы метода.

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

по формуле

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

Иными словами, . Несложные выкладки показывают, что для (9.2)

где

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

где выбирается, например, в соответствии со способом 1 из предыдущего параграфа или из условия

Процедура (9.10) оказывается более стабильной по сравнению с (9.9), которая особенно чувствительна к выбору начального приближения и подвержена эффекту «раскачки» при его неудачном выборе.

9.3.2. Скорость сходимости процедуры.

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

где константа С определяется видом функции и не зависит от

При решении практических задач на данное утвешдение (впрочем, как и на аналогичное утверждение из § 9.2; не следует особенно полагаться. Дело в том, что проверка условий, его сопровождающих, за исключением тривиальных случаев, реально невозможна. К тому же большинство из них для «экзотических» выборок (маловероятных выборок) заведома не будут выполняться. Тем не менее подобные утверждения все же имеют смысл, так как позволяют дать оценку той максимальной скорости сходимости, которую можно достигнуть с помощью данного метода. Данное замечание имеет место для всех методов, рассматриваемых в этой главе.

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

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