Метод кубической интерполяции

Суть алгоритма заключается в том, что на каждой итерации функция f (x) аппроксимируется кубическим полиномом F (x), точка минимума x^(*) которого берется в качестве текущего приближения к искомому минимуму х^*. Алгоритм предполагает вычисления в каждой очередной точке значений функции f (x) и ее производной f '(x).

Начальный этап. Задать, x₁, h₁ — параметры метода, имеющие общепринятый смысл. Методом Свенна установить начальный интервал [a, b]:

(1) изменить направление поиска h₁ = -h₁, если;

• (2) вычислять f_k в точках при до тех пор, пока не продвинемся в точку x_m, такую, что;
• (3) если, то положить, иначе.

Основной этап.

Шаг 1. Найти аппроксимирующий минимум:

(1) вычислить параметр

(2) принять аппроксимирующий минимум.

.

и.

Шаг 2. Проверить критерий окончания поиска: eсли поиск окончить. Иначе вернуться к шагу 1, используя новый интервал если, либо интервал если.

При решении реальных задач редко приходится иметь дело с функциями одной переменной. Однако методы одномерной оптимизации важны при многомерной оптимизации, которая выполняется в основном по следующему правилу: зафиксировать некоторую точку, выбрать подходящее направление, выполнить одномерную оптимизацию из выбранной точки в выбранном направлении. Поэтому методы интерполяции полезны для выполнения линейного поиска при оптимизации функций многих переменных.

Рассмотренный метод кубической интерполяции является одним из интерполяционных методов Эрмита, приспособленным специально для оптимизации. Этот метод требует знания производных функций и используется в основном в так называемых квазиньютоновских методах многомерной оптимизации, которые и сами по себе используют производные.

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

Пример.

Рассмотрим функцию, найдем точку ее минимума x* на отрезке.

1-й шаг:

Вычисляем и по формуле получаем Находим, и.

Так как, то поиск точки x* продолжаем на отрезке, где и, причем.

2-й шаг:

и Теперь искомая точка x* находится в интервале и.

3-й шаг:

Итак, пришли к значению, у которого четыре верных знака после запятой совпадают с точным значением.