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

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

. В частности, можно взять x0=a или x0=b.

Действительно, пусть, например, f’(x) > 0 при

, f"(x )>0 и х0 = с, где .

Если f(с) = 0, то корень

= с и задача, таким образом, решена.

Если f(c) > 0, то справедливо приведенное выше рассуждение и процесс Ньютона с начальным значением с сходится к корню

.

Наконец, если f(с) <0, то находим значение

Применяя формулу Тейлора, будем иметь:

где

—некоторое промежуточное значение между с и х1. Таким образом, f(x1)f’’(x1)>0.

Кроме того, из условия f"(x) >0 вытекает, что f’ (х) — возрастающая функция и, значит, f’(x) > f' (а) > 0 при х>а. Следовательно, х1 можно принять за начальное значение для процесса Ньютона, сходящегося к некоторому корню

функции f(x) такому, что > с

а. Так как в силу положительности производной f' (х) при х > а функция f(x) имеет единственный корень на интервале (а, + ), то = .

Аналогичное рассмотрение можно провести для других комбинаций знаков производных f’(x)и f"(x).

Замечание 2. Из формулы (3) видно, что чем больше численное значение производной f’(x) в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить (n+l)-e приближение. Поэтому метод Ньютона особенно удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение производной f’(x) близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным. Следовательно, если кривая y=f(x) вблизи точки пересечения с осью Ох почти горизонтальна, то применять метод Ньютона для решения уравнения f(x) = 0 не рекомендуется.

Оценка погрешности

Для оценки погрешности n-го приближения хn можно воспользоваться общей формулой.

(6)

где m1 — наименьшее значение |f’(x)|на отрезке [а, b].

Выведем еще одну формулу для оценки точности приближения xn. Применяя формулу Тейлора, имеем:

(7)

где

.Так как в силу определения приближения хп имеем

то из (7) находим:

где М2 — наибольшее значение |f" (х)|на отрезке [а, b].Следовательно, на основании формулы (6) окончательно получаем:

Если процесс Ньютона сходится, то хп- хп-1 0 при п—►

. Поэтому при п

имеем:

т.е. «установившиеся» начальные десятичные знаки приближений xn-1 иxnначиная с некоторого приближения, являются верными.

Заметим, что в общем случае совпадение с точностью до е двух последовательных приближений хп-1 и хп вовсе не гарантирует, что с той же точностью совпадает значение хп и точный корень | (рис. 19).

Установим также формулу, связывающую абсолютные погрешности двух последовательных приближений хп и xn+1. Из формулы (5) получаем:

где

. Отсюда, учитывая формулу (3), будем иметь:

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

(9)

Формула (9) обеспечивает быструю сходимость процесса Ньютона, если начальное приближение х0 таково, что

В частности, если

то из формулы (9) получаем:

т.е. в этом случае, если приближение хп имело mверных десятичных знаков после запятой, то следующее приближение хп+1 будет иметь по меньшей мере 2т верных знаков; иными словами, если

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

Метод хорд (линейной аппроксимации)

Информация о предыдущих приближениях корня используется для нахождения последующих приближений не только в методе касательных. В качестве примера другого такого метода мы приведём метод, основанный на нахождении xi + 1 по двум предыдущим приближениям xi и xi − 1 с помощью линейной интерполяции, называемый методом хорд.

Идея метода состоит в том, что по двум точкам Mi − 1(xi − 1;f(xi − 1)) и Mi(xi;f(xi)) построить прямую Mi − 1Mi (то есть хорду, соединяющую две точки графика y = f(x)) и взять в качестве следующего приближения xi + 1 абсциссу точки пересечения этой прямой с осью Ox. Иными словами, приближённо заменить на этом шаге функцию f(x) её линейной интерполяцией, найденной по двум значениям : x и xi − 1. (Линейной интерполяцией функции f(x) назовём такую линейную функцию

, значения которой совпадают со значениями f(x) в двух фиксированных точках, в данном случае -- в точках xi − 1 и xi.)

Уравнение хорды - это уравнение прямой, проходящей через две точки (a, f(a)) и (b, f(b)).

В зависимости от того, лежат ли точки xi − 1 и xi по разные стороны от корня x * или же по одну и ту же сторону, получаем такие чертежи:

Рис 3. Построение последовательного приближения по методу хорд: два случая.

Итак, очередное последовательное приближение будет зависеть от двух предыдущих:

. Найдём выражение для функции .

Интерполяционную линейную функцию

будем искать как функцию с угловым коэффициентом, равным разностному отношению

построенному для отрезка между xi − 1 и xi, график которой проходит через точку Mi:

Решая уравнение

, находим

то есть

(1)

Заметим, что величина ki может рассматриваться как разностное приближение для производной f'(x) в точке xi. Тем самым полученная формула (1) -- это разностный аналог итерационной формулы метода Ньютона. Вычисление по формуле (1) гораздо предпочтительнее вычисления по другой полученной нами формуле

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