Обратная квадратичная интерполяция - Википедия - Inverse quadratic interpolation

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

Метод

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

где жk = ж(Иксk). Как видно из рекуррентного соотношения, для этого метода требуются три начальных значения: Икс0, Икс1 и Икс2.

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

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

Ищем корень ж, поэтому подставляем у = ж(Икс) = 0 в приведенном выше уравнении, и это приводит к приведенной выше формуле рекурсии.

Поведение

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

Порядок этой сходимости составляет приблизительно 1,84, что доказывает Секущий метод анализ.

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

Как отмечалось во введении, обратная квадратичная интерполяция используется в Метод Брента.

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

Смотрите также

Рекомендации

  • Джеймс Ф. Эпперсон, Введение в численные методы и анализ, страницы 182-185, Wiley-Interscience, 2007. ISBN  978-0-470-04963-1