Сравнение метода Ньютона с методом интерполяции

26. Вычисление первой производной для каждой из специальных форм матриц требует почти такого же объема работы, как и вычисление значений самой функции. Более того, если матрица достаточно высокого порядка, можем считать, что работа, связанная с одним шагом линейной или квадратичной интерполяции или метода Ньютона, мала по сравнению с вычислением значения функции или ее производной.

Поэтому естественно сравнивать два шага линейной или квадратичной интерполяции с одним шагом метода Ньютона. Для двух шагов линейной интерполяции в окрестности простого корня из (21.15) имеем

а для метода Ньютона

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

В окрестности двойного корня для двух шагов линейной интерполяции

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

Последовательная квадратичная интерполяция выглядит еще лучше при таком сравнении. Для простого корня два шага квадратичной интерполяции дают

а для двойного корня

Эти сравнения основаны на предположении, что вычисление значений производной сравнимо с вычислением значений функции. Для матриц общего вида, т. е. для функции это наверняка неверно; вычисление значений производной требует значительно большей работы, чем вычисление значений самой функции. Контраст еще более

заметен для обобщенной проблемы собственных значений, где соответствующая функция имеет вид

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