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

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

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

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

Недостатки

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

Улучшения

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

См. также

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

Ссылки

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