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

Пусть корень уравнения f(x)=0 отделен на отрезке [a;b], причем первая и вторая производные f’(x) и f''(x) непрерывны и знакопостоянны при хÎ [a;b].

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

x = х_n + h_n. (1.2.3-6)

Считаяh_n малой величиной, представим f(х_n+ h_n) в виде ряда Тейлора, ограничиваясь линейными слагаемыми

f(х_n + h_n) »f(х_n) + h_nf’(х_n). (1.2.3-7)

Учитывая, что f(x) = f(х_n + h_n) = 0, получим f(х_n) + h_nf ’(х_n) » 0.

Отсюда h_n» - f(х_n)/ f’(х_n). Подставим значение h_n в (1.2.3-6) и вместо точного значения корня xполучим очередное приближение

(1.2.3-8)

Формула (1.2.3-8) позволяет получить последовательность приближенийх₁,х₂, х₃…, которая при определенных условиях сходится к точному значению корняx, то есть

Геометрическая интерпретация метода Ньютона состоит в следующем
(рис.1.2.3-6). Примем за начальное приближение x₀ правый конец отрезка b и в соответствующей точке В₀ на графике функции y = f(x) построим касательную. Точка пересечения касательной с осью абсцисс принимается за новое более точное приближение х₁. Многократное повторение этой процедуры позволяет получить последовательность приближений х₀, х₁, х_{2 , . . .,} которая стремится к точному значению корня x.

Рис. 1.2.3-6

Расчетная формула метода Ньютона (1.2.3-8) может быть получена из геометрического построения. Так в прямоугольном треугольнике х₀В₀х₁катет
х₀х₁ = х₀В₀/tga. Учитывая, что точка В₀находится на графике функции f(x), а гипотенуза образована касательной к графику f(x) в точке В₀, получим

(1.2.3-9)

(1.2.3-10)

Эта формула совпадает с (1.2.3-8) для n-го приближения.

Из рис.1.2.3-6 видно, что выбор в качестве начального приближения точки а может привести к тому, что следующее приближение х₁окажется вне отрезка [a;b], на котором отделен корень x. В этом случае сходимость процесса не гарантирована. В общем случае выбор начального приближения производится в соответствии со следующим правилом: за начальное приближение следует принять такую точку х₀Î[a;b],в которой f(х₀)×f’’(х₀)>0, то есть знаки функции и ее второй производной совпадают.

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

Если корень уравнения отделен на отрезке[a;b], причем f’(х₀)и f’’(х) отличны от нуля и сохраняют свои знаки прихÎ[a;b], то, если выбрать в качестве начального приближения такую точку х₀Î[a;b], чтоf(х₀).f¢¢(х₀)>0, то корень уравнения f(x)=0может быть вычислен с любой степенью точности.

Оценка погрешности метода Ньютона определяется следующим выражением:

(1.2.3-11)

где -- наименьшее значение при

-- наибольшее значение при

Процесс вычислений прекращается, если ,

где -- заданная точность.

Кроме того, условием достижения заданной точности при уточнении корня методом Ньютона могут служить следующие выражения:

(1.2.3-12)

Схема алгоритма метода Ньютона приведена на рис. 1.2.3-7.

Левая часть исходного уравнения f(x) и ее производная f’(x)в алгоритме оформлены в виде отдельных программных модулей.

Рис. 1.2.3-7. Схема алгоритма метода Ньютона

Пример 1.2.3-3.Уточнить методом Ньютона корни уравнения x-ln(x+2) = 0при условии, что корни этого уравнения отделены на отрезках x₁Î[-1.9;-1.1] и x₂Î [-0.9;2].

Первая производная f’(x) = 1 – 1/(x+2) сохраняет свой знак на каждом из отрезков:

f’(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 при хÎ [-0.9; 2].

Вторая производная f'(x) = 1/(x+2)²> 0 при любых х.

Таким образом, условия сходимости выполняются. Поскольку f''(x)>0на всей области допустимых значений, то для уточнения корня за начальное приближение x₁выберем х₀=-1,9(так какf(-1,9)×f”(-1.9)>0). Получим последовательность приближений:

Продолжая вычисления, получим следующую последовательность первых четырех приближений: -1.9; –1.8552, -1.8421; -1.8414.Значение функции f(x) в точке x=-1.8414 равно f(-1.8414)=-0.00003.

Для уточнения корня x₂Î[-0.9;2] выберем в качестве начального приближениях₀=2 (f(2)×f”(2)>0). Исходя из х₀ = 2, получим последовательность приближений: 2.0;1.1817; 1.1462; 1.1461. Значение функции f(x) в точке x=1.1461 равно f(1.1461)= -0.00006.

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

Метод хорд

Геометрическая интерпретация метода хорд состоит в следующем
(рис.1.2.3-8).

Рис.1.2.3-8

Проведем отрезок прямой через точки A и B. Очередное приближение x₁ является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой:

Положим y=0и найдем значение х=х₁ (очередное приближение):

Повторим процесс вычислений для получения очередного приближения к корню - х₂:

В нашем случае (рис.1.2.11) и расчетная формула метода хорд будет иметь вид

(1.2.3-13)

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

Рассмотрим другой случай (рис. 1.2.3-9), когда .

Рис.1.2.3-9

Уравнение прямой для этого случая имеет вид

Очередное приближение х₁ при y = 0

Тогда рекуррентная формула метода хорд для этого случая имеет вид

(1.2.3-14)

Следует отметить, что за неподвижную точку в методе хорд выбирают тот конец отрезка [a;b], для которого выполняется условие f (x)∙f¢¢ (x)>0.

Таким образом, если за неподвижную точку приняли точку а,то в качестве начального приближения выступает х₀ = b, и наоборот.

Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х,а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон.

Оценка погрешности метода хорд определяется выражением

(1.2.3-15)

Условие окончания процесса итераций по методу хорд

(1.2.3-16)

В случае, если M₁<2m₁, то для оценки погрешности метода может быть использована формула | x_n-x_n-1|£e.

Пример 1.2.3-4. Уточнить корень уравнения e^x – 3x = 0, отделенный на отрезке [0;1] с точностью 10^-4.

Проверим условие сходимости:

Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х₀=1, поскольку f(0)=1>0 и f(0)*f"(0)>0.

Результатырасчета, полученные с использованием формулы
1.2.3-14, представлены в таблице 1.2.3-4.

Таблица 1.2.3-4

Требуемая точность достигается на 8-й итерации. Следовательно, за приближенное значение корня можно принять х = 0.6191.

Схема алгоритма метода хорд приведена на рис. 1.2.3-10.

Выбор неподвижной точки, определяющей вид расчетной формулы, производится путем сравнения одного из концов отрезка [a;b] с начальным приближением (x₀=a). В качестве неподвижного конца отрезка (точка с) выбирается тот, который не совпадает с начальным приближением.

Рис. 1.2.3-10. Схема алгоритма метода хорд