Методы полиномиальной аппроксимации

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

М е т о д к в а д р а т и ч н о й а п п р о к с и м а ц и и

Метод основан на аппроксимации целевой функции по трем опорным точкам - a₀, a₁, a₂ полиномом второй степени:

Y(a)=a₀+a₁×(a-a₀)+a₂ (a-a₀)×(a-a₁). (1.2.5)

Для определения коэффициентов a_0-2 необходимо решить систему уравнений третьего порядка вида:

(1.2.6)

Решив (1.2.6), получим:

(1.2.7)

Минимуму функции (1.2.5) соответствует точка -

a_min=(a₀+a₁-a₁/a₂)/2. (1.2.8)

Окончательно алгоритм метода будет иметь следующий вид.

{{{ Начало алгоритма

1) Запоминаем центральную опорную точку a_z=a₁.

2) По заданным трем опорным точкам - a₀, a₁, a₂ и значениям целевой функции - J₀, J₁, J₂ вычисляются по формулам (1.2.7) коэффициенты квадратичного полинома (1.2.6) и по формуле (1.2.8) определяем новую минимальную точку a_min и рассчитываем в ней значение целевой функции J_min=J(a_min).

3) Определяем номер опорной точки, соответствующей максимальному значения целевой функции: i_m: max_i(J_i). Эту точку исключаем из дальнейшего рассмотрения, а вместо нее вводим вновь найденную минимальную: a_im=a_min, J_im=J_min.

4) Если разница между старым значением a_z и a_min меньше заданной точности e, т.е. |a_z-a_min|<e, то поиск заканчивается, иначе запоминается новое значение a_z=a_min и переходим к пункту 2).

}}} Конец алгоритма.

Дата добавления: 2015-11-14