Метод Ньютона
25. Анализ §§ 21—23 касался только предельной скорости сходимости, и мы рассмотрели детально только случай корней кратности один и два. Кроме того, мы пренебрегали ошибками округления. Но, вообще говоря, трудно начать итерационный процесс с хороших приближений к корню, а вычисленные значения всегда будут подвержены влиянию ошибок округления. Эти вопросы будут рассмотрены в §§ 59, 60 и §§ 35—47 соответственно после изучения других итерационных методов.
Рассмотрим теперь методы, в которых в дополнение к значениям функций используются значения производных. Наиболее известным является метод Ньютона, в котором
приближение связано с
соотношением
В окрестности простого корня
а
где производные вычислены при
Следовательно, мы имеем
что
Для двойного корня
следовательно, из (25.3) следует
что
Аналогично можно показать, что для корня кратности
так что сходимость становится все медленнее вместе с ростом кратности. Очевидно, что для корня кратности
поправка, сделанная на каждом
шаге, уменьшается на множитель
Поэтому для таких корней (25.1) заменяется на
и (25.9) дает
К сожалению, мы обычно не имеем заранее информации о кратности нулей.