Введение

Метод решения уравнений
В численном анализе обратная квадратичная интерполяция — это алгоритм поиска корней, то есть алгоритм для решения уравнений вида f(x) = 0. Идея заключается в использовании квадратичной интерполяции для приближения обратной функции к f. Этот алгоритм редко применяется самостоятельно, но он важен, поскольку является частью популярного метода Брента.

Объяснение метода

Мы используем три предшествующие итерации, xn−2, xn−1 и xn, с их значениями функций, fn−2, fn−1 и fn. Применение формулы интерполяции Лагранжа для квадратичной интерполяции обратной функции f дает

Мы ищем корень функции f, поэтому подставляем y = f(x) = 0 в приведенное выше уравнение, что приводит к вышеуказанной рекуррентной формуле.

Поведение

Асимптотическое поведение очень хорошее: как правило, итерации xn быстро сходятся к корню, когда они достаточно близки к нему. Однако, производительность часто бывает низкой, если начальные значения далеки от фактического корня. Например, если случайно два из значений функций fn−2, fn−1 и fn совпадают, алгоритм полностью перестает работать. Поэтому обратная квадратичная интерполяция редко используется как самостоятельный алгоритм. Порядок сходимости составляет приблизительно 1,84, что можно доказать анализом метода секущих.

Сравнение с другими методами поиска корней

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