В численном анализе , обратный квадратичной интерполяции является алгоритмом корневого ознакомительным , а это означает , что алгоритм решения уравнений вида F ( х ) = 0. Идея состоит в том , чтобы использовать квадратичную интерполяцию , чтобы аппроксимировать обратные от е . Этот алгоритм редко используется сам по себе, но он важен, поскольку является частью популярного метода Брента .
Метод
Алгоритм обратной квадратичной интерполяции определяется рекуррентным соотношением
где f k = f ( x k ). Как видно из рекуррентного соотношения, для этого метода требуются три начальных значения: x 0 , x 1 и x 2 .
Объяснение метода
Мы используем три предыдущих итерации, x n −2 , x n −1 и x n , с их значениями функций, f n −2 , f n −1 и f n . Применение формулы интерполяции Лагранжа для выполнения квадратичной интерполяции на обратной величине f дает
Мы ищем корень f , поэтому мы подставляем y = f ( x ) = 0 в приведенное выше уравнение, и это приводит к приведенной выше формуле рекурсии.
Поведение
Асимптотическое поведение очень хорошее: как правило, итерации x n быстро сходятся к корню, как только они приближаются. Однако производительность часто бывает довольно низкой, если начальные значения не близки к фактическому корню. Например, если по какой-либо причине два из значений функции f n −2 , f n −1 и f n совпадают, алгоритм полностью терпит неудачу. Таким образом, обратная квадратичная интерполяция редко используется в качестве автономного алгоритма.
Порядок этой сходимости составляет приблизительно 1,84, что может быть доказано анализом метода Секанта .
Сравнение с другими методами поиска корней
Как отмечалось во введении, в методе Брента используется обратная квадратичная интерполяция .
Обратная квадратичная интерполяция также тесно связана с некоторыми другими методами поиска корней. Использование линейной интерполяции вместо квадратичной интерполяции дает метод секущей . Интерполяция f вместо обратного f дает метод Мюллера .
Смотрите также
- Последовательная параболическая интерполяция - это связанный метод, который использует параболы для поиска экстремумов, а не корней.
Рекомендации
- Джеймс Ф. Эпперсон , Введение в численные методы и анализ , страницы 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1