Последовательная параболическая интерполяция - Successive parabolic interpolation

Последовательная параболическая интерполяция это метод нахождения экстремум (минимум или максимум) непрерывного унимодальная функция путем последовательной установки параболы (многочлены степени два) к функции одной переменной в трех уникальных точках или, в общем, к функции п переменные на 1 + п (п + 3) / 2 точек, и на каждой итерации заменяя «самую старую» точку на экстремум подобранной параболы.

Преимущества

Используются только значения функций, и когда этот метод сходится к экстремуму, он делает это с порядок сходимости примерно 1.325. Сверхлинейная скорость сходимости превосходит другие методы с линейной сходимостью (например, линейный поиск ). Более того, не требуя вычисления или приближения функции производные делает последовательную параболическую интерполяцию популярной альтернативой другим методам, которые действительно требуют их (например, градиентный спуск и Метод Ньютона ).

Недостатки

С другой стороны, сходимость (даже к локальному экстремуму) не гарантируется при изолированном использовании этого метода. Например, если три точки коллинеарен, результирующая парабола выродиться и, таким образом, не дает нового кандидата. Более того, если доступны производные функций, применим метод Ньютона, который демонстрирует квадратичную сходимость.

Улучшения

Чередование параболических итераций более надежным методом (поиск золотого сечения - популярный выбор) выбор кандидатов может значительно увеличить вероятность сходимости без снижения скорости сходимости.

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

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

использованная литература

Майкл Хит (2002). Научные вычисления: вводный обзор (2-е изд.). Нью-Йорк: Макгроу-Хилл. ISBN  0-07-239910-4.