Метод квадратичной интерполяции

Этот метод может непосредственно применяться к унимодальным функциям одной переменной. Он может быть очень полезным для поиска частного оптимума по отдельным направлениям при решении задач многомерной оптимизации.

В предыдущих двух методах была сделана попытка найти малый интервал, в котором находятся оптимум функции I(x). В рассматриваемом методе применяется иной подход. Он заключается в построении аппроксимирующей модели оптимизируемой функции I(x). Функция I(y) может быть аппроксимирована полиномом второго порядка

(1.5)

по крайней мере, в небольшой области значений, в том числе в области оптимума. При этом положение экстремума I(x) определяется положением экстремума полинома (1.5), поскольку последний вычислить проще.

Экстремум функции I_a(x), как известно, расположен в точке

(1.6)

Положим, что окрестность некоторой исходной точки x=x₁ на области определения I(x) аппроксимирована полиномом (1.5). Задача поиска заключается в определении смещения

(1.7)

которое приводит из исходного состояния x=x₁ в экстремальное x=x*. Если I(x) строго квадратичная функция, то смещение Dx после первого шага сразу приведет к x*. В противном случае достижение x* требует выполнения итерационной процедуры.

Для определения смещения Dx нужно определить коэффициенты параболы (4.5). Эта задача легко решается, если известны значения I(x) в трех точках. Пусть вычисление I(x) производилось в районе исходного состояния x=x₁ в точках x₁, x₀=x₁-h, x₂=x₁+h и при этом получено три значения этой функции:

(1.8)

где h – полуинтервал интерполяции, малая постоянная положительная величина.

Подставляя эти значения в уравнение (1.5), получаем систему из трех линейных уравнений с тремя неизвестными a, b и с:

(1.9)

Для того, чтобы эта система имела решение, необходимо, чтобы ее определитель не был равен нулю, то есть

(1.10)

Раскрывая этот определитель, находим

,

что всегда выполняется, поскольку h¹0.

Разрешая систему уравнений (1.9), получаем интересующие нас значения параметров a, b, cи, подставляя их в формулу (1.6), находим положение экстремума параболы

(1.11)

Величина рабочего смещения Dx равна

(1.12)

Зная коэффициенты a, b, с можно определить и экстремальное значение функции (1.5) по формуле

(1.13)

которое является оценкой экстремума критерия I(x).

После выполнения рабочего шага Dx следует проверить, действительно ли найден экстремум. Для этого достаточно вычислить значение функции цели I(x) в предполагаемом экстремуме и сопоставить его с оценкой (1.13). Если эти величины отличаются не более чем на e, то есть

(1.14)

где e – заданная погрешность определения экстремума, то задачу отыскания экстремума можно считать выполненной. При этом x*=x₁+Δx.

Если же условие (1.11) не соблюдается, то это означает, что исходное предположение о квадратичности целевой функции не выполняется и следует продолжать процесс поиска, то есть выполнить следующий цикл, но построение модели производить в окрестности точки x*=x₁. Эта процедура повторяется до тех пор, пока не выполнится условие (1.11).

Вполне очевидно, что критерием окончания процесса поиска экстремума может служить выполнение условия

(1.15)

Таким образом, с помощью итерационной процедуры значение x^*уточняется до получения его с заданной погрешностью e.