Оценка погрешности метода Ньютона

Для характеристики приближенных методов решения уравнений вводится понятие порядка сходимости метода.

Определение 2.7. Говорят, что метод имеет k -ый порядок сходимости, если существуют , такие, что при условии .

Очевидно, что чем больше k, тем быстрее сходится процесс итераций. В вычислительной практике широко распространены методы второго порядка.

Теорема 2.5. Для метода Ньютона имеет место следующая оценка:

, где , .

Доказательство.

По формуле конечных приращений Лагранжа для некоторого найдется точка (или ) такая, что . Учитывая, что , получим . Выразим из последней формулы модуль разности между n -ым приближением и истинным корнем: .

Запишем формулу Тейлора в окрестности точки .

.

Тогда

,

где – остаточный член формулы Тейлора, (или ).

В силу самого метода Ньютона . Тогда . Используя полученное неравенство и выведенное ранее , можно записать .

Теорема 2.6. Метод Ньютона является методом второго порядка сходимости.

Доказательство.

Полученную выше оценку погрешности метода Ньютона запишем в виде: .

По неравенству треугольника имеем . Так как , то . Возвращаясь к первоначальной оценке метода Ньютона имеем

.

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

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

,

если , то есть, если .

Дата добавления: 2014-01-14