§ 4.6. Метод Ньютона

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

1. Метод касательных.

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

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

Напомним, что уравнение касательной, проведенной к графику функции в точке имеет вид

Рис. 4.9

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

Выражая из него получаем расчетную формулу метода Ньютона:

Благодаря такой геометрической интерпретации этот метод часто называют методом касательных.

2. Метод линеаризации.

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

Пусть приближение уже получено. Представим функцию в окрестности точки по формуле Тейлора:

Здесь некоторая точка, расположенная между Заменяя в уравнении функцию главной линейной частью разложений (4.38), получим линейное уравнение

Принимая решение уравнения (4.39) за новое приближение приходим к формуле (4.37).

3. Основная теорема о сходимости метода Ньютона.

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

где означающая, что метод сходится с квадратичной скоростью.

Следствием оценки (4.40) является априорная оценка

в которой

Так как (по определению простого корня), то в силу непрерывности функций найдется -окрестность корня, в которой при некоторых постоянных выполнены неравенства

Пусть где Подставляя в (4.38), получим равенство

в котором Вычитая из него равенство (4.36), имеем

Тогда, приравняв модули обеих частей этого равенства и используя условия ограниченности приходим к неравенству откуда следует справедливость оценки (4.40). Доказательство теоремы завершается применением леммы 4.2.

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

Приведенные в теореме 4.6 оценки погрешности являются априорными (см. § 3.3) и их использование в практике вычислений для количественной оценки погрешности неэффективно или чаще всего невозможно.

4. Критерий окончания.

На практике предпочтительнее использование простой апостериорной оценки

справедливость которой обосновывается следующим утверждением. Теорема 4.7. Пусть выполнены условия теоремы Тогда для всех верна оценка (4.42).

Из оценки (4.41) следует, что Поэтому, применяя неравенство (4.40), получим цепочку неравенств из которой вытекает оценка (4.42).

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

Пример 4.8. Используя метод Ньютона, найдем с точностью положительный корень уравнения

В примере 4.2 корень был локализован на отрезке [0, 1]. Для

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

Результаты первых итераций с 10 знаками мантиссы приведены в табл. 4.4.

Таблица 4.4 (см. скан)

При вычисления следует прекратить и после округления получим

Сравнение результатов итераций со значением х показывает, что приближения содержат 1, 3, 6 верных значащих цифр соответственно. Можно показать, что приближение содержит 10 верных цифр. Это подтверждает отмеченный ранее общий факт: при каждой итерации метода Ньютона число верных значащих цифр примерно удваивается.

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

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

При эта формула уже была получена в примере 3.17.

5. Связь с методом простой итерации.

Метод Ньютона можно рассматривать как один из вариантов метода простой итерации, связанный со специальным преобразованием уравнения к виду

где В самом деле, итерационная формула метода простой итерации совпадает с формулой (4.37).

Исходя из этого с учетом оценки (4.19), можно было бы сделать вывод о том, что метод Ньютона сходится только линейно. Однако заметим, что Так как то и величина определяющая в силу равенства (4.20) коэффициент сжатия ошибки, стремится к нулю при . Скорость сходимости возрастает по мере приближения к корню, отсюда и ее сверхлинейный характер.

В качестве аналога теоремы 4.4 для метода Ньютона приведем следующий результат.

Теорема 4.8. Пусть отрезок локализации простого корня х уравнения (4.1). Предположим, что на этом отрезке функция дважды непрерывно дифференцируема, а ее производные знакопостоянны. Пусть произвольное начальное приближение, и в случае выполнено дополнительное условие (первое приближение не выходит за пределы отрезка локализации).

Тогда начиная с итерационная последовательность метода Ньютона сходится к х монотонно с той стороны отрезка где

Иллюстрацией монотонного характера сходимости может служить рис. 4.9.

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

6. Трудности использования.

Простота, логическая стройность и высокая скорость сходимости делают метод Ньютона чрезвычайно привлекательным. Однако для его практического применения нужно преодолеть две существенные трудности. Одна из них состоит в необходимости вычисления производной Часто бывает невозможно найти аналитическое выражение для определить приближенное значение с высокой точностью очень трудно. Иногда вычисление

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

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

Рис. 4.10

7. Влияние погрешности вычислений.

Пусть простой корень. Если метод Ньютона рассматривать как вариант метода простой итерации, связанный с преобразованием уравнения к виду (4.45), то можно воспользоваться результатами § 4.4 и § 4.5.

Поскольку справедливо неравенство (4.30) и радиус интервала неопределенности корня х равен примерно . В оценках (4.32)-(4.34) можно считать Для того чтобы сделать окончательные выводы, остается оценить

Пусть приближенные значения функций вычисляемые в малой окрестности корня х. Будем считать, что производим вычисляется хотя бы с точностью до 1—2 верных значащих цифр. В противном случае (особенно, если неверно определяется знак из геометрического смысла метода легко понять, что его применять не следует. В силу предложения 2.5 в малой окрестности корня имеем

Так как погрешность , вносимую в вследствие выполнения операции вычитания, получим

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