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

Метод хорд

Пусть f(a)f(b)<0. Сущность метода (его еще называют методом ложного положения) состоит в замене кривой y=f(x) хордами, проходящими через концы отрезков, в которых f(x) имеет противоположные знаки. Метод хорд требует, чтобы один конец отрезка, на котором ищется корень, был неподвижен. В качестве неподвижного конца х₀ выбирают тот конец отрезка, для которого знак f(x) совпадает со знаком второй производной . Расчетная формула имеет вид

Метод хорд является двухточечным, его сходимость монотонная и односторонняя.

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

Пусть корень ξ уравнения f(x)=0 отделен на отрезке [a,b]. Предположим мы нашли (n-1)-ое приближение корня x_n-1. Тогда n-ое приближение x_n мы можем получить следующим образом. Положим
x_n = x_n-1 + h_n-1 . (3.15)
Раскладывая в ряд f(x=ξ) в точке x_n-1, получим
f(x_n) = f(x_n-1+h_n-1) = f(x_n-1) + f’(x_n-1)h_n-1=0
Отсюда следует
. (3.16)
Подставим (3.16) в формулу (3.15), получим
(3.17)

Рис.1. Геометрическая интерпретация метода Ньютона

Геометрически метод Ньютона эквивалентен замене дуги кривой y=f(x) касательной, проведенной в некоторой точке кривой (см. рис.1).
В точке B имеем f(x₀)f’’(x₀)>0. Здесь x₀=b. Проведем касательную в точке B, получим на пересечении касательной осью OX точку x₁. Далее проводим касательную в точке B₁, получим точку x₂ и т.д.
Если положить x₀=a, то в точке x₀ будем иметь f(x₀)f’’(x₀)<0. Тогда касательная в точке A пересекла бы ось OX в точке x’₁, лежащей вне отрезка [a,b], то есть при таком выборе начальной точки, метод Ньютона оказывается расходящимся. Достаточные условия сходимости метода Ньютона определяются следующей теоремой.

Теорема 5. Если f(a)f(b)<0, причем f’(x) и f’’(x) отличны от нуля и сохраняют определенные знаки при a≤x≤b, то исходя из начального приближения , удовлетворяющего неравенству
f(x₀)f’’(x₀)>0 (3.18)
можно вычислить методом Ньютона (3.17) единственный корень ξ уравнения f(x)=0 с любой степенью точности.
Доказательство: Пусть . Согласно неравенству (3.18) в качестве точки x₀ мы должны взять ту границу отрезка, для которой f(x₀)>0, т.е. в данном случае т. b.
Итак, имеем x₀>ξ. Докажем, что все приближения x_n> ξ и следовательно все f(x_n)>0. Пусть теперь x_n-1> ξ. Положим
ξ = x_n-1 + (ξ-x_n-1).
Применяя формулу Тейлора, получим
,
где ξ <c_n-1<x_n-1.
Так как f’’(x)>0, то имеем
и, следовательно
ч.т.д. (3.19)
Из (3.19) учитывая знаки и имеем x_n<x_n-1, то есть получаем ограниченную монотонную убывающую последовательность . Следовательно, существует .
Переходя к пределу в формуле (3.17) получим
, то есть f(ξ)=0, и следовательно, ξ- корень ,ч.т.д.
Оценим скорость сходимости метода Ньютона. Из (3.17) следует
. (3.20)
Представим f(ξ) в виде
, откуда
. (3.21)
Подставим (3.21) в (3.20), получим

Отсюда
. (3.22)
Здесь ,

Таким образом, скорость сходимости метода Ньютона квадратичная.
Рис.2

Критерий завершения итерационного процесса имеет вид

|x_n – x_n-1|<ε.

Замечание. В общем случае совпадение с точностью до ε двух последовательных приближений x_n-1 и x_n не гарантирует, что с той же точностью совпадет x_n и ξ (см. рис. 2). Поэтому целесообразно проверять кроме разности |x_n – x_n-1|<ε также значение функции f(x_n): |f(x_n)|< ε₁.

Пример. f(x) = x⁴-3x³+75x-10000=0.
Найти отрицательный корень с пятью верными знаками.
Решение: Полагая x=0, -10, -100, получим f(0)=-10⁴, f(-10) = -150, f(-100) ≈ 10⁸. Таким образом -100<ξ<-10. Сузим интервал, так как f(-11)=3433, то -11< ξ <-10.
В интервале [-11, -10] f(x)<0, f’’(x)>0. Так как f(-11)f’’(-11)>0, то x₀=-11.
Последовательные приближения даны в таблице.

Получим -10.261<ξ<-10.260.