Блок-схема метода квадратичной интерполяции

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

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

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

Пример.

Найти минимум на отрезке c точностью.

Пусть.

1-й шаг:

по трем точкам (-1, 1), (0.5, 0.25), (1, 1) строим параболу и находим ее вершину.

.

Требование по точности не выполнено, поэтому необходимо продолжить вычисления.

.

следовательно, следующую параболу строим по трем точкам: и находим.

.

Вычисления завершены, в качестве приближенного решения получили .

Нетрудно убедится в том, что является точным решением задачи. Это совпадение объясняется тем, что есть многочлен 2-й степени, построенные интерполяционные многочлены, естественно, полностью совпали с .

Замечание.

В описанном алгоритме предполагалось, что унимодальна.

В случае, если этот метод применять для неунимодальной, алгоритм может зациклиться.

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