Метод парабол

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

Учесть информацию о значениях функции между точками позволяют методы полиномиальной аппроксимации. Их основная идея заключена в том, что функция Φ(u) аппроксимируется полиномом, а точка его минимума служит приближением к u^*. Разумеется, в этом случае кроме свойства унимодальности (т.е. наличия единственного минимума на рассматриваемом отрезке), необходимо на Φ(u) наложить и требования достаточной гладкости для ее полиномиальной аппроксимации.

Для повышения точности поиска u^* можно как увеличивать степень полинома, так и уменьшать пробный отрезок. Поскольку первый прием приводит к заметному увеличению вычислительной работы и появлению дополнительных экстремумов, обычно пользуются полиномами второй (метод парабол) или третьей (метод кубической интерполяции) степени.

Алгоритм поиска минимума состоит в следующем.

Выбираем на пробном отрезке три точки u₁, u₂, u₃ такие, что u₁ < u₂ < u₃ и.

Построим параболу (квадратичный полином)

Q(u) = a₀ + a₁ (u - u₁) + a₂ (u - u₁)(u - u₂),

график которой проходит через точки (u₁,f(u₁)), (u₂,f(u₂)), (u₃,f(u₃)).

Коэффициенты a_k, k = 1, 2, 3 находим из системы уравнений

Q(u₁) = f(u₁), Q(u₂) = f(u₂), Q(u₃) = f(u₃),

откуда

Точку минимума Q(u) находим, приравнивания его производную к нулю:

Далее полагаем:(очередное приближение точки минимума). Эту процедуру можно продолжить до достижения необходимой точности, выбирая новые точки u_k, k = 1, 2, 3. Для этого можно использовать методы исключения отрезков, используя в качестве двух пробных точек u₂ и, таких, что u₂,

Дата добавления: 2014-01-07