Обратная квадратичная интерполяция

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

Метод

Алгоритм обратной квадратичной интерполяции определяется рекуррентным соотношением

$x_{n+1}={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

${}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},$

где ж _k знак равно ж ( Икс _k ). Как видно из рекуррентного соотношения, этот метод требует трех начальных значений: x ₀ , x ₁ и x ₂ .

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

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

$f^{-1}(y)={\frac {(y-f_{n-1})(y-f_{n})}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {(y-f_{n-2})(y-f_{n})}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}$

$\qquad +{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n}.$

Мы ищем корень 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