Итерационные методы, основанные на интерполяции

20. Рассмотрим теперь методы, используемые для дахождения нулей. Сначала рассмотрим методы, основанные только на вычисленных значениях а не на значениях ее производных. Эти методы являются в основном методами последовательной интерполяции. (Мы сейчас не делаем различия между интерполяцией и экстраполяцией.) В наиболее важной группе методов этого класса следующее приближение к нулю определяется по предыдущим приближениям как нуль полинома степени проходящего через точки Из таких нулей в качестве берется тот, который лежит ближе всего к равно 1 или 2, соответствующие полиномы линейные или квадратичные, и нахождение нулей тривиально. Удобно обозначить

В случае имеем

В случае Мюллер (1956) предложил очень удобную схему вычислений. Положим

Легко проверить, что требуемое значение удовлетворяет квадратному уравнению

где

Отсюда получаем

Знак в знаменателе выбирается так, чтобы соответствующее (и следовательно, было наименьшим по абсолютной величине.

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

Если больше двух, каждый шаг итерации требует решения полиномиального уравнения степени три или выше. Следовательно, вряд ли можно оправдать использование кубической или более высокой интерполяции, если только они не имеют значительно лучшие свойства сходимости (см. конец § 21).