Построение аппроксимирующих моделей минимизируемой функции

Рассмотрим класс алгоритмов, поиск глобального минимума по которым сводится к следующей последовательности действий:

1) проводятся испытания в точках xi, i = 1, 2,…, N, расположенных определенным образом на интервале [a, b];

2) по полученным значениям (xi, Q (xi)), i = 1,2,…, N, строится математическая модель, аппроксимирующая функцию Q (х) на интервале [a, b];

3) оценивается точность приближения построенной модели к функции Q (х);

4) если точность аппроксимации недостаточна, то проводятся дополнительные испытания и процедура поиска повторяется с п. 2; в противном случае при помощи полученной математической модели принимается решение о расположении на интервале [а, b] точки глобального минимума х* функции Q (х).

Будем считать, что минимизируемые кривые Q (х) являются непрерывными функциями, удовлетворяющими условию (4.1), в котором количественное значение константы Липшица L в общем случае может быть неизвестно.

Согласно теореме Вейерштрасса, любая непрерывная функция Q (х) может быть аппроксимирована равномерно сходящейся последовательностью алгебраических полиномов PN(х)=∑akxk, т. е. для
любого числа ε > 0 найдется такой полином PN (х), что для всех х∈[a, b] будет справедливо неравенство

|Q(x) — PN(х)| ≤ ε.

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

min max |Q(x)—PN(х)|.

Для непрерывных функций Q (х) оптимальное решение задачи (4.25) существует и является единственным многочленом степени не выше N, который в аналитическом виде может быть представлен при помощи интерполяционного полинома Лагранжа

PN(x) = ∑Q(xiN+1 (x)/[(x-xiN+1(xi)], (4.26)

Точность приближения функции Q (x) полиномом (4.26) будет тем выше, чем меньше многочлен ωN+1(х) будет отклоняться от нуля. Поэтому точки испытаний xi, i = 1, 2,…, N, которые в (4.26) являются узлами интерполяции, необходимо выбирать таким образом, чтобы при увеличении числа испытаний N, С одной стороны, обеспечить равномерную сходимость последовательности полиномов PN (х) к функции Q (х), а с другой — наибольшую скорость уменьшения многочлена ωN+1(х). Для рассматриваемого класса минимизируемых функций Q (х) сформулированные требования выполняются, если в качестве точек испытаний xi выбирать нули многочлена Чебыщева TN(х) = cos (N arccos (x)), которые являются вещественными, простыми и лежат в интервале [-1, 1]:

xi = cos[(2i-1)/2N — π], i=1,2,…,V, (4.27)

Использование в качестве математической модели интерполяционного полинома Лагранжа (4.26), а в качестве точек испытаний — нулей многочлена Чебышева (4.27) приводит к алгоритму F13, реализующему пассивную стратегию поиска точки глобального минимума х* произвольной кривой Q (х):

1. Определяется расположение точек испытаний на интервале [а, b]

xi = |(b — а)ξi + (а + b)|/2, i = 1, 2, …, N + 1, где
ξi = cos[(2i-1)/2(N+1) — π]

2. По информации о проведенных испытаниях (xi, Q (xi)), i = 1, 2, …, N + 1, строится математическая модель функции Q (х) в виде интерполяционного полинома Лагранжа.

3. Находится первая производная от полинома РN (х) и путем решения уравнения:

РN(x) = 0

(например, с помощью метода Мюллера вычисляются корни алгебраического полинома (N — 1)-й степени, среди которых выбирается значение x*, удовлетворяющее условию

РN(х) = min РN(х).

4. В качестве апостериорного интервала неопределенности [aN, bN], в котором предполагается наличие точки минимума х*, выбирается отрезок между точками испытаний xш и xi+1 удовлетворяющих условию:

xi ≤ x* ≤ хi+1.

При малом числе испытаний алгоритм F13 может не локализовать точку минимума х* (т. е. интервал [xi, xi+1] не будет содержать точку x*). Однако в силу равномерной сходимости полиномов РN(х) к функции Q(x) с ростом числа испытаний N вероятность потери точки глобального минимума х* будет убывать. Недостатком рассмотренного алгоритма является то, что при изменении числа проводимых испытаний хотя бы на одно (так как многочлены Чебышева TN (х) и TN+1 (х) не имеют общих корней), для сохранения свойства равномерной сходимости полиномов PN(х) к функции Q (х), необходимо узлы интерполяции {xi} вычислять заново, что приводит к потере всей информации о предыдущих испытаниях. В связи с этим рассмотрим последовательную стратегию поиска точки глобального минимума x* с помощью интерполяционных полиномов Лагранжа (4.26), в которых система узлов интерполяции {xi} обладает следующими свойствами:
— при увеличении числа испытаний N новые узлы лишь добавляются между старыми узлами, которые сохраняются неизменными;
— построенные по этим узлам интерполяционные полиномы PN(х) обладают свойством равномерной сходимости к функции Q (х).

Для удовлетворения сформулированных требований, предъявляемых к узлам интерполяции {хi}, необходимо, чтобы они вычислялись о помощью полиномов, корни которых не меняются при изменении числа N, но в то же время эти полиномы должны обладать свойствами многочленов, наименее отклоняющихся от нуля на интервале [-1,1].


Оставить комментарий





Статистика

Рейтинг@Mail.ru