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

Метод простой итерации

Итерационные методы уточнения корней

Метод простой итерации применяется к решению уравнения (3.1), разрешенному относительно x:

x = j(x). (3.5)

Переход от записи (3.1) к эквивалентной записи (3.5) можно сделать многими способами.

Метод состоит в построении последовательности (3.2) в виде

, n = 0, 1, 2, … .

Если j(x_n) – непрерывная функция, а x_n – сходящаяся последовательность, то искомое значение x^* =x_n и будет решением (3.5), следовательно, и (3.1).

Например, получим (3.5) из (3.1) следующим образом: умножим (3.1) на подобранную функцию y(x) ¹ 0 (в частности можно взять y(x) = const) и сложим с тождеством x = x, тогда (3.5) будет иметь вид, эквивалентный виду (3.3):

. (3.6)

Подбирая y(x), добиваются сходимости решения (3.6). Функция y(x) может быть монотонной, если j'(x) > 0, или колеблющейся, если j'(x) < 0.

Метод является одношаговым (m = 1), и для начала вычислений нужно знать одно начальное приближение: x₀ = a (рис. 3.3, а), или x₀ = b (рис. 3.3, б), или x₀ = (a + b)/2.

В методе простой итерации сходимость гарантирована не всегда, например, если j(x) имеет вид, представленный на рис. 3.4.

Представленная ситуация, при которой мы удаляемся от искомого корня, может быть устранена подбором y(x) в (3.6).

В качестве y(x) можно взять, например, y(x) = const = 1/k. При этом необходимо, чтобы |k| > max| f ¢(x)|/2, а знак k должен совпадать со знаком f ¢(x).

Рис. 3.3

Рис. 3.4

Доказано, что в общем случае расходимость (несходимость) исключается, если подбирается соотношение

| j'(x) | £ q < 1. (3.7)

При этом скорость сходимости увеличивается при уменьшении величины q.

Максимальный интервал (a, b) при выполнении условия (3.7) называется областью сходимости. Для данной оценки (3.7) берется любое значение x Î (a,b); x^* Î (a, b).

Итерационный процесс уточнения корня заканчивается, когда

| x_n – x_n–1| < e, или | f(x_n) – f(x_n–1)| < e.

Данный метод является модификацией метода простой итерации. Если функция f(x) непрерывна и дифференцируема, то, положив в (3.6) , получим эквивалентное уравнение x = x – f(x) / f '(x) = j(x), f '(x) ¹ 0.

Подбором y(x) добиваются, чтобы в (3.7) q = j'(x^*) º 0, что обеспечивает большую скорость сходимости в рекуррентном соотношении метода Ньютона вблизи искомого корня:

, n = 1, 2, … . (3.8)

Это также одношаговый метод.

Геометрическая интерпретация метода представлена на рис. 3.5.

Рис. 3.5

Проблематичным является выбор x₀ ввиду узости области сходимости вычисления производной. Часто при неудачном выборе x₀ нет монотонного убывания последовательности | f(x_n) |, поэтому рекомендуется вычисления проводить по модифицированной схеме:

n = 0, 1, 2, … .

Сомножители a_n Î [0, 1] выбирают так, чтобы выполнялось неравенство

| f(x_n+1)| < | f(x_n)| .

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