Главная > Математика > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

Он называется также методом касательных или методом линеаризации. Если есть некоторое приближение к корню имеет непрерывную производную, то уравнение (22) можно преобразовать следующим образом:

Приближенно заменяя на значение в известной точке получим такой итерационный процесс:

Рис. 28.

Геометрически этот процесс означает замену на каждой итерации графика касательной к нему (рис. 28).

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

Тогда

Если есть -кратный корень уравнения (22), то вблизи него отсюда нетрудно получить . Для простого корня и . Используя результаты п. 4, можно сформулировать следующие условия сходимости итераций (28). Если нулевое приближение выбрано достаточно близко к корню, ньютоновские итерации сходятся; скорость сходимости велика для простого корня и соответствует скорости геометрической прогрессии для кратного корня. При произвольном нулевом приближении итерации сходятся, если всюду в противном случае сходимость будет не при любом нулевом приближении, а только в некоторой окрестности корня.

Сходимость вблизи любого корня монотонна, что легко видеть из рис. 28; но вдали от корня возможна немонотонность итераций.

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

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

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

6 верных знаков, а — примерно 12 знаков. Это иллюстрирует быструю сходимость вблизи корня. Разумеется, вдали от корня подобные соображения неприменимы.

Таблица 16

Если вычисляется корень высокой кратности, то в знаменателе формулы (28) становится малой вблизи корня. Чтобы не было потери точности, отношение надо вычислять достаточно аккуратно. К остальным погрешностям расчета метод Ньютона хорошо устойчив.

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

Пример. Рассмотрим решение уравнения Тогда общая формула метода Ньютона (28) принимает вид

Мы получили вторую формулу (25), которая, как отмечалось раньше, позволяет очень быстро находить квадратный корень с помощью только сложения и деления. Для иллюстрации в таблице 16 приведен ход итераций при извлечении квадратного корня из Видно, что сходимость очень быстрая; несмотря на неважное нулевое приближение, уже третья итерация дает точность 0,005%. Попутно можно заметить, что вблизи корня итерации сходятся с одной стороны, т. е. монотонно, хотя первая итерация дает переброс на другую сторону корня.

<< Предыдущий параграф Следующий параграф >>
Оглавление