Вычислительная математика

учебное пособие

2.5 Метод Ньютона (метод касательных)

Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений.

Пусть корень x* [a, b], так, что f(a)f(b) < 0. Предполагаем, что функция f(x) непрерывна на отрезке [a, b] и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b. Проведем касательную к графику функции y = f(x) в точке B0 = (x0, f(x0)) (рис. 2.8).

Рис. 2.8

Уравнение касательной будет иметь вид:

y - f(x0) = f (x0)(x - x0). (2.11)

Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. положив в (2.11) y = 0, x = x1:

x1 = x0 - . (2.12)

Аналогично поступим с точкой B1(x1, f(x1)), затем с точкой B2(x2, f(x2)), и т. д. в результате получим последовательность приближений x1, x2, …, xn , …,причем

xn +1 = xn - . (2.13)

Формула (2.13) является расчетной формулой метода Ньютона.

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

(x) = x - . (2.14)

Сходимость метода. Сходимость метода Ньютона устанавливает следующая теорема.

Теорема 2.3. Пусть x* - простой корень уравнения f(x) = 0, и в некоторой окрестности этого корня функция f дважды непрерывно дифференцируема. Тогда найдется такая малая -окрестность корня x*, что при произвольном выборе начального приближения x0 из этой окрестности итерационная последовательность, определенная по формуле (2.13) не выходит за пределы этой окрестности и справедлива оценка:

|xn + 1 - x*| C |xn - x*|2, n 0, (2.15)

где С = -1. Оценка (2.15) означает, что метод сходится с квадратичной скоростью.

Сходимость метода Ньютона зависит от того, насколько близко к корню выбрано начальное приближение. Неудачный выбор начального приближения может дать расходящуюся последовательность. Полезно иметь в виду следующее достаточное условие сходимости метода. Пусть [a, b] - отрезок, содержащий корень. Если в качестве начального приближения x0 выбрать тот из концов отрезка, для которого

f(x)f"(x) 0, (2.16)

то итерации (2.13) сходятся, причем монотонно. Рис. 2.8 соответствует случаю, когда в качестве начального приближения был выбран правый конец отрезка: x0 = b.

Погрешность метода. Оценка (2.15) является априорной и неудобна для практического использования. На практике удобно пользоваться следующей апостериорной оценкой погрешности:

|xn - x*| |xn - xn - 1|. (2.17)

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

|xn - xn - 1| < . (2.18)

Пример 2.3.

Применим метод Ньютона для вычисления . где a > 0, p - натуральное число. Вычисление эквивалентно решению уравнения xp = a. Таким образом, нужно найти корень уравнения f(x) = 0, f(x) = xp - a, f (x) = pxp - 1. Итерационная формула метода (2.13) примет вид:

xn +1 = xn - = xn + . (2.19)

Используя формулу (2.19), найдем с точностью = 10-3.

xn +1 = xn + .

Простой корень уравнения x3 - 7 = 0 расположен на отрезке [1, 2]. Действительно, на концах отрезка [1, 2] функция f(x) = x3 - 7 принимает разные знаки, f (1) < 0, f (2) > 0. Кроме того, при x = 2 выполнено достаточное условие сходимости (2.16): f (2)f" (2) 0.

Поэтому в качестве начального приближения можно взять x0 = 2.

Результаты приведены в табл. 2.3.

Таблица 2.3

n

xn

0

1

2

3

4

5

2

0.8415

0.8861

0.8742

0.8774

0.8765

Делись добром ;)