Приближенное решение алгебраических и трансцендентных уравнений Метод Ньютона (стр. 2 из 4)

В 1879 годуАртурКэливработе The Newton-Fourier imaginary problem (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

Отделение корней

Во многих приближённых методах нахождения корня уравнения заранее требуется знать какой-либо отрезок, на котором лежит искомый корень, и притом только один этот корень (то есть предъявляемый отрезок не должен содержать других корней уравнения). В этом случае говорят, что корень отделён на отрезке. Отделить корень - значит указать такой отрезок, на котором корень отделён. Заметим, что отделить корень можно не единственным образом: если корень отделён на каком-либо отрезке, то годится и любой меньший отрезок, содержащий этот корень. Вообще говоря, чем меньше отрезок, тем лучше, но при этом не следует забывать о том, что на отделение корня на меньших отрезках также тратятся вычислительные усилия, и, быть может, весьма значительные. Таким образом, часто для начала довольствуются весьма широким отрезком, на котором корень отделён.

Кроме того, часто нужно знать начальное приближениеx0 к корню (который, заметим, неизвестен). В качестве этого начального приближения берут, как правило, любую точку отрезка, на котором отделён корень, например, его середину, если описание метода не предписывает поступить как-нибудь иначе.

Приведём некоторые утверждения, которые могут помочь при отделении корня.

Теорема 1Если функция непрерывна на отрезке, причём значения её в концах отрезка и - это числа разных знаков, то на отрезке лежит по крайней мере один корень уравнения.

Практический смысл теоремы в том, что если мы, вычисляя значения функции в некоторых точках, видим, что вычисление в двух соседних точках даёт значения разных знаков, то на отрезке между этими точками лежит отыскиваемый корень. Если же известно заранее, что корень один, то получаем, что корень отделён на найденном отрезке. Этот же способ, когда мы наугад вычисляем значения функции в каких-то точках, может привести к отделению корней и в случае, когда корней несколько, но заранее известно их число или хотя бы оценка сверху для их количества. Рассмотрим иллюстрирующий сказанное пример.

Теорема 2Если функция строго монотонна на отрезке, то есть возрастает или убывает на, то на этом отрезке уравнение не может иметь более одного корня.

Доказательство сразу следует из того, что строго монотонная функция принимает каждое своё значение ровно один раз. Если 0 является значением функции, то и значение 0 принимается один раз, то есть уравнение имеет один корень.

Тем самым, если отрезок, на котором заведомо имеется хотя бы один корень (например, если и - разного знака), - это отрезок строгой монотонности функции, то на отделён ровно один корень.

Заметим, что интервалы монотонности функции можно отыскивать, решая неравенства (что соответствует возрастанию функции) и (что соответствует убыванию).

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

Пусть корень

уравнения f(x) = 0 отделён на отрезке, причем f’(x) и f’’(x) непрерывны и сохраняют определённые знаки при . Найдя какое-нибудь n-e приближение корня n ( ), мы можем уточнить его по Методу Ньютона следующим образом. Пусть , где hn малая величина. Отсюда, применяя формулу Тейлора, получим:

Следовательно,

Внеся эту поправку в формулу (2), получим следующее по порядку приближение корня:

(n=0,1,2…).

Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y=f(x) касательной, проведенной в некоторой точке кривой. в самом деле, положим для определённости, что f’’(x)>0 при

и f(b)>0 (рис. 1).

Выберем, например, х0=b, для которого f(x)f’’(x)>0. Проведем касательную к кривойy=f(x) в точке B0 (x0, f(x0)).

В качестве 1-го приближения x1 корня

возьмем абсциссу точки пересечения этой касательной с осью Ox. Через точку B1(x1, f(x1)) снова проведем касательную, абсцисса точки пересечения которой с Oxдаст нам 2-е приближениеx2 корня и т.д. (рис. 1). Очевидно, что уравнение касательной в точке Bn (xn, f(xn)) (где n=0,1,2…) есть

Полагая, что у=0, x=xn+1,получим формулу (3):

.

Заметим, что если в нашем случае положить х0=a и, следовательно, f(x)f’’(x)<0, то, проведя касательную к кривой y=f(x)в точкеA(a, f(a)), мы получили бы точку x1’ (рис. 1), лежащую вне отрезка [а, b], т. е. при этом выборе начального значения метод Ньютона оказывается непрактичным. Таким образом, в данном случае «хорошим» начальным приближением х0 является то, для которого выполнено неравенство

(4)

Докажем, что это правило является общим.

Теорема. Если f(a)f(b)<0, причем f'(x) и f" (х) отличны от нуля и сохраняют определенные знаки при

, то, исходя из начального приближения удовлетворяющего неравенству (4), можно вычислить методом Ньютона (формула (3)) единственный корень уравнения (1) с любой степенью точности.

Доказательство. Пусть, например, f(a)< 0, f(b)>0, f'(x) >0, f’’(x)>0 при

(остальные случаи рассматриваются аналогично). Согласно неравенству (4) имеем f(x0) >0 (например, можно принять х0 = b).

Методом математической индукции докажем, что все приближения xn>

(n = 0, 1, 2,...) и, следовательно, f(xn)>0. В самом деле, прежде всего, x0 > .

Пусть теперь xn>

. Положим

Применяя формулу Тейлора, получим:

где

<cn<xn.

Так как f’’(x)>0, то имеем:

и, следовательно,

что и требовалось доказать.

Из формулы (3), учитывая знаки f(xn) и f’(хn), имеем хn+1 < хn (n = 0, 1, ...), т. е. последовательные приближения x0, x1,…, хn, ... образуют ограниченную монотонно убывающую последовательность. Следовательно, существует

.

Переходя к пределу в равенстве (3), будем иметь:

т.е. f(

)=0. Следовательно, = , что и требовалось доказать.

Поэтому, применяя метод Ньютона, следует руководствоваться следующим правилом: в качестве исходной точки х0 выбирается тот конец интервала (а, b), которому отвечает ордината того же знака, что и знак f"(x).

Замечание 1. Если:

1. функция f(x) определена и непрерывна при

;

2. f(a)f(b)<0;

3. f’(x)

при ;