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

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

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

Рис. 2.8

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

y – f (x ₀) = f '(x ₀)(x – x ₀). (2.11)

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

x ₁ = x ₀ – . (2.12)

Аналогично поступим с точкой B ₁(x ₁, f (x ₁)), затем с точкой B ₂(x ₂, f (x ₂)), и т. д. в результате получим последовательность приближений x ₁, x ₂, …, x _n , …,причем

x _{n +1} = x _n – . (2.13)

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

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

j (x) = x - . (2.14)

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

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

| x_{n + 1} – x^* | £ C | x_n – x^* |², n 0, (2.15)

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

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

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

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

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

| x_n – x^* | £ | x_n – x_{n – 1}|. (2.17)

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

| x_n – x_{n – 1}| < e. (2.18)

Пример 2.3.

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

x _{n +1} = x _n – = x _n + . (2.19)

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

x _{n +1} = x _n + .

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

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

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

Таблица 2.3

n	xn
	0.8415 0.8861 0.8742 0.8774 0.8765

Дата добавления: 2014-01-05