Метод кусочно-кубической и кусочно-линейной аппроксимации.


Процедура поиска точки глобального минимума х* аппроксимирующей модели может быть упрощена, если в качестве математической модели использовать кусочно-кубическую кривую SN(х), проходящую через точки испытаний (xi, Q(xi)), i = 1, 2, …, N, и моделирующую поведение функции Q (х) на отдельных отрезках интервала |a, b| полиномами третьей степени Р3(х) = ∑αkixk. В этом случае поиск точки глобального минимума х* произвольной кривой Q (х) может быть осуществлен с помощью метода кусочно-кубической аппроксимации F15, в котором точки испытаний на каждом k-м шаге выбираются независимо от информации о поведении функции Q(x) и равномерно располагаются на интервале [a, b]:

xi(k) = a + i(b-a)/(Nk-1), i = 0, 1, …, Nk — 1.

Общее число точек испытаний Nk, по которым на k-м шаге строится математическая модель SNk (х), аппроксимирующая функцию Q (х), определяется по итерационной формуле:

N1 = 5; Nk+1 = 2Nk — 1, k = 1, 2, 3,…

В новых точках, не совпадающих с уже проведенными испытаниями

xi(k+1) = (xi(k) + xi-1(k))/2,

проводятся дополнительные вычисления функции Q (х). На первом шаге (k = 1) используется информация обиспытаниях в пяти точках, на втором шаге (k = 2) — в девяти точках, среди которых в пяти уже проведены испытания, т. е. дополнительно вычисляется значение функции Q (х) только в четырех новых точках и т. д,

На k-м шаге поиска с помощью метода кубической интерполяции F(6) строится совокупность аппроксимирующих полиномов P3(i)(х), которые используются для описания функции Q (х) не в точках (xi-1(k), xi(k), xi+1(k), xi+2(k)), по которым каждый из них построен, а только на подынтервалах [xi(k), xi+1(k)], кроме концов интервала [a, b], где полиномы Р3(1)(х) и P3Nk-1(х) аппроксимируют функцию Q (х) на подынтервалах [а, х2] и [xNk-3, b] соответственно. При этом на каждом шаге поиска значения коэффициентов совокупности полиномов Р3(i)(х), образующих кусочно-кубическую кривую SNk(х), должны рассчитываться заново. Пример построения кусочно-кубической модели SN2(х) на втором шаге поиска (к = 2) показан на рис. 4.4.



Рис. 4.4. Пример построения кусочно-кубической модели по девяти точкам в алгоритме F15

Здесь подынтервалы l1, l3, l5 являются областями определения кубических парабол P3(1)(x), Р3(2)(х), Р3(3)(х), а подынтервалы l2, l4, l6 — областями, где функция Q (х) = x/10+cos x аппроксимируется каждым из построенных полиномов третьей степени.

Построение кусочно-кубической модели считается законченным на k-м шаге, если относительная ошибка между значениями функции Q(x) и значениями, полученными по математической модели точках испытаний (k + 1)-го шага, меньше некоторого заданного значения ε:

max |[Q(xi) — SNk(xi)]/Q(xi)| ≤ ε

При выполнении неравенства (4.34) в каждой точке xi*∈[хi(k), хi+1(k)], являющейся точкой минимума полинома Р3(i) (х), которая определяется с помощью метода F6 делается дополнительное,испытание. В качестве приближенной точки глобального минимума выбирается точка х, обеспечивающая минимальное значение функции Q (х) по всем проведенным испытаниям N:

Q(x*) = min Q(xi)

Таким образом, алгоритм F15 позволяет построить аппроксимирующую модель SN(х) при помощи совокупности полиномов третьей степени. Однако для запоминания каждого полинома P3(i)(х) требуется дополнительный объем памяти, который быстро растет с увеличением точности ε совпадения математической модели SN (х) с минимизируемой функцией Q (х).

Этого недостатка лишен алгоритм F16 реализующий метод кусочно-линейной аппроксимации, в котором на каждом шаге поиска в качестве аппроксимирующей модели непрерывной функции Q (х) используется кусочно-ломаная кривая LN (х) (полиномиальный сплайн первой степени). При этом точки текущих испытаний xi, i = 1, 2, …, Nk-1, необходимые для построения математической модели LN(х), выбираются таким же образом, как и в алгоритме F15. Основной характеристикой аппроксимирующей модели LNk(х) является число JNk подынтервалов [xi-1, xi+1], в которых обеспечивается выполнение неравенства:

LNk(xi) ≤ LNk (х) для всех х∈[xi-1, xi+1].

Эти подынтервалы называются, подынтервалами, «подозрительными» на существование в них локального минимума функции Q (x). В связи с простотой аппроксимирующей модели LNk(х) поиск точек ее локальных минимумов, определяющих «подозрительные» подынтервалы, не
представляет труда. Процесс последовательного построения ломаны кривых LNk(х) заканчивается, кац только достигается качественное соответствие между структурой кусочно-линейной модели LNk(х), достроенной на k-м шаге поиска, и функцией Q (х). В качестве такого соответствия принимается значение параметра m (JNk), показывающего, сколько раз подряд число «подозрительных» подынтервалов JNk кусочно-линейной модели повторилось при ее уточнении. При повторении структуры кусочно-линейной модели LNk(х) m раз подряд (JNk = JNk+1, , …, JNk+m) считается, что функция Q (х) имеет такое же число и расположение локальных минимумов, как и ее кусочно-линейная модель, полученная на (k + m)-м шаге.

После построения кусочно-линейной модели LNk(х), адекватной минимизируемой функции Q(x), определение приближенного значения точки глобального минимума х сводится к минимизации одномерной унимодальной функции, являющейся частью кривой Q(x*) в каждом из «подозрительных» подынтервалов [xi-1(k), xi+1(k)], к = 1, JNk. При этом может быть использован любой из алгоритмов унимодального поиска. Таким образом, алгоритм F16 позволяет определить все локальные минимумы функции Q (х) и выбрать среди них тот, который обеспечивает наименьшее значение функции Q (х).

В качестве примера на рис. 4.5 показаны две кусочно-линейные модели функции Q (х) = x/10 + cos х (сплошная лривая), полученные при поиске минимума с помощью алгоритма F16. Кусочно-линейная модель L5 (х), полученная на первом шаге, обозначена пунктирной кривой, а модель L9 (х), полученная на втором шаге,— штрихпунктирной кривой. Точками отмечены испытания, проведенные на первом шаге, а крестиками — на втором. При значении m = 2 построение кусочно-линейной модели заканчивается выделением двух (JN = 2) «подозрительных» подынтервалов (заштрихованные участки оси х), в которых в дальнейшем осуществляется поиск локального минимума с помощью одного из методов (F1 — F10) минимизации унимодальных функций.



Рис. 4.5. Стратегия поиска глобального минимума по методу кусочно-линейной аппроксимации


Комментарии запрещены.




Статистика