Внешнее и внутреннее оценивание областей достижимости при помощи параллелотопов

Вычислительные технологии

Том 3, № 2, 1998

ВНЕШНЕЕ И ВНУТРЕННЕЕ ОЦЕНИВАНИЕ ОБЛАСТЕЙ ДОСТИЖИМОСТИ ПРИ ПОМОЩИ ПАРАЛЛЕЛОТОПОВ *

Е. К. КостоусовА Институт математики и механики УрО РАН Екатеринбург, Россия e-mail: kek@oou.imm.intec.ru

The capabilities of two-sided approximations (estimates) of attainability sets for linear dynamic continuous time systems by parallelotopes are considered. The families of parallelotopic estimates that ensure exact representations of the attainability sets (through intersections and unions) are introduced. Estimates that are optimal in some sense are singled out.

1. Введение

Решение многих задач теории управления и оценивания в условиях неопределенности в гарантированной постановке основывается на исследовании трубок траекторий динамических систем [6-9, 13, 17, 18]. Существует несколько подходов к разработке численных методов их аппроксимации. Ряд методов основывается на аппроксимации множеств многогранниками с большим числом вершин и граней (см., например, [13, 15]). Другой подход состоит в построении внешних и внутренних оценок с помощью областей некоторой фиксированной формы. Одним из интенсивно развиваемых является метод аппроксимации при помощи эллипсоидов [13, 18]. К этому же направлению относится и основанный на идеях интервальных вычислений [1, 3] метод покоординатного оценивания [4]. Однако покоординатные оценки могут оказаться слишком грубыми в силу известного в интервальном анализе "эффекта упаковывания" (wrapping effect).

В настоящей работе развивается подход [18], состоящий в аппроксимации искомой трубки целым семейством внешних (внутренних) трубок, образованных параллелепипедами (параллелотопами), грани которых не обязательно параллельны координатным плоскостям. Семейства вводятся таким образом, чтобы, с одной стороны, обеспечить точные представления решений (через пересечение или объединение), а с другой — чтобы каждая конкретная трубка могла быть найдена с помощью эволюционных уравнений независимо от остальных (что открывает возможности для параллельных вычислений). В работе такие семейства вводятся для областей достижимости линейных динамических систем. Выведены обыкновенные дифференциальные уравнения, описывающие эволюцию внешних

* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, гранты №96-01-00050, 97-01-00672.

© Е. К. Костоусова, 1998.

и внутренних оценок. Приведены достаточные условия, при которых внутренние оценки являются невырожденными параллелепипедами. Выделены оценки, оптимальные в некотором смысле. Отметим, что семейство внешних оценок обладает тем свойством, что для каждого параллелепипеда все гиперплоскости, в которых лежат его (п — 1)-мерные грани, являются опорными для области достижимости. Таким образом, отказ от ортогональности параллелепипедов и постоянства их ориентации позволяет избежать "эффекта упаковывания". Работа продолжает исследования [5, 16].

2. Постановка задачи

Пусть состояние х(г) £ К"" объекта описывается системой

х = А

Здесь К" — п-мерное евклидово пространство, А(г) — некоторая известная пхп-матрица, непрерывная по ¿. Начальное состояние х(г0) = х0 £ К" и входное воздействие эд(-), являющееся измеримой (по Лебегу) п-мерной функцией времени ¿, стеснены ограничениями

х0 £ х0, Цг) £Н

где Х0, Н(¿) — заданные выпуклые компакты в К", причем многозначное отображение Н(¿) непрерывно.

Областью достижимости X(¿) = X(¿,г0, Х0) системы (21)-(22) при г > ¿0 называется множество таких точек х £ К", для каждой из которых существуют х0 и эд(-), удовлетворяющие (22) и порождающие решение х(-) системы (21), такое, что х(г) = х. Известно, что области достижимости обладают полугрупповым свойством

X(г,*0, Х0) = X(г,т, X(г,*0, хъ)), Ут,г: *0 < т < г < tf.

Далее будем предполагать, что множества X0 и Н(г) являются параллелепипедами, и искать внешние (внутренние) оценки областей достижимости в виде параллелепипедов (соответственно параллелотопов).

Параллелепипедом Р(р,Р,п) в К" будем называть множество

гпг&, &|<1, г = 1, • • • , п | •

Здесь р £ К"; Р = {рг} — неособая пхп-матрица со столбцами рг единичной длины (множество всех матриц с условиями Р = 0, ||рг|| = 1, г = 1, •••, п, обозначим М"х"); п £ К", пг > 0. Можно сказать, что р задает центр параллелепипеда, рг — "направления", а пг — величины его "полуосей".

Параллелотопом Р [р, Р] в К" будем называть множество

Ы<1, г = 1, ..., п

где вектор р £ К" играет ту же роль, что и р, а пхп-матрица Р = {рг} может быть особой и ее столбцы р иметь неединичную длину.

Р = Р (р, Р,п )=< х | х = р + ^р

г=1

Р = Р[р, Р] = х | х = р + Ер^

г=1

Очевидно, что любой параллелепипед является параллелотопом:

Р(р,Р,п) = Р[р, Р], где р = р, Р = Р•diagп.

Символ diag п (или diag {п^}) обозначает диагональную матрицу, элементы диагонали которой совпадают с компонентами п вектора п. И наоборот, невырожденный параллелотоп ^е! Р = 0) является параллелепипедом с параметрами Р = Pdiag {||рг||-1}, п = ||рг||. Итак, мы предполагаем, что

Хо = Р

причем г(*), Л(*), р(*) непрерывно зависят от При этом области X(*) параллелепипедами, вообще говоря, не будут. Найдем внешние Р + () и внутренние Р-(-) оценки для X():

Р±(*) = Р (р±(^),Р±(^),п±(^)) или Р±(*) = Р [р±(*),Р±(*)],

удовлетворяющие обобщенному полугрупповому свойству

X

Р-

Соотношения (24), (25) гарантируют включения

Р-

Более того, в соответствии с подходом [18], нашей целью будет ввести некоторые семейства таких трубок Р±(-), которые при каждом * е Т обеспечивают точные представления

Х

Х

внешние — через пересечение, внутренние — через объединение.

Оценки желательно строить таким образом, чтобы они были как можно ближе к областям достижимости, например, "касались" их. Назовем Р внешним касающимся параллелепипедом для выпуклого компактного множества Х, если Х С Р и

р(±р^|Р)= р(±р^|Х), г =1, ...,п.

Здесь р(/|Х) = вир{ (ж,/) | х е Х}, / е К" — опорная функция множества Х С К"; {р±г}П=1 — система векторов, биортогональных к {рг}П=1, т.е. (р±г,р^) = 0, ] = 1, ... , п,

] = г; (рх\р') > 0; Цр^'Ц = 1 (г = 1, ... , п).

Может быть также полезно выделить элементы семейств, оптимальные в некотором смысле. Например, трубку Р+() назовем локально оптимальной в смысле объема внешней оценкой для Х() [13], если при каждом т е Т

5 Р

< 4то1 Р

4=т

для любой трубки P(•) (с дифференцируемыми параметрами p(t),P(t),n(t)), определенной для t > т, обладающей обобщенным полугрупповым свойством (24) и удовлетворяющей начальному условию P (т) = P + (т). Здесь символом vol P обозначен объем параллелепипеда P = P(р, P, п):

n

volP = 2n • | det P| • Д п = 2n • | det P

i=1

Аналогично вводятся внутренние локально-оптимальные оценки.

В качестве другого, нелокального, критерия оптимальности можно рассмотреть, например, объем оценки в конечный момент времени tf, и в семействах внешних и внутренних оценок рассмотреть экстремальные задачи вида

vol P+

vol P-

3. Внешние оценки

Для внешних оценок справедлива

Теорема 31.. Пусть X(t) — области достижимости системы (21)-(23). Пусть P £ МПХП — произвольная матрица. Если параметры параллелепипедов

P+

при t £ T определяются соотношениями

p+ = A(t) p+ + r(t), P+(to) = Po;

P* = A(t) P*, P* (to) = P, P+(t) = P* (t)diag {||p**(t)||}-1;

n * = Abs ((P* )-1R(t)) p(t), n * (to) = Abs (P-1Po) no, n+(t) = diag {||p**(t)||} n* (t),

то P+ (t) удовлетворяют (24) и являются внешними касающимися оценками для областей достижимостиi X(t). Кроме того, при каждом t > to справедливо представление (27), где пересечение взято по всем возможным матрицам P £ МПХП : X(t) = f| {P +(t) | P £ МПХП}. Если начальное множество имеет внутренние точки

int Xo = 0,

то трубка P+(-) является локально-оптимальной в смысле объема внешней оценкой для X(•), причем, если P = Po, то P+(to) = Xo.

Символом Abs B в (31) обозначена матрица абсолютных величин элементов матрицы B = {bj}: Abs B = {|bj|} (верхним индексом нумеруются столбцы, а нижним — строки). Доказательство можно найти в [16].

Замечания. 3.1. Каждая трубка P+(-) описывается своей системой обыкновенных дифференциальных уравнений (31), не зависящей от других. Поэтому конечное число таких оценок можно найти путем параллельных вычислений.

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

3.3. В предположении (32) задача о нахождении локально-оптимальных оценок оказалась решенной. Задача (29) нелокальной оптимизации в рассматриваемом семействе

и и 2

оценок является задачей нелинейного программирования в пространстве размерности n при n ограничениях типа равенств (задающих условие нормирования столбцов P).

3.4. Если параллелепипеды P + (t) рассматривать как параллелотопы P[p+(t),P + (t)], то в предположении (32) несложно выписать дифференциальные уравнения для P + (t). Так как P+=P + diag n+=P* diagп*, то путем прямого дифференцирования находим, что

7+ = A(t) P + + P +  diag ( Abs ((P+)-1 R(t)) p(t) ) , P +(to) = P  diag (Abs (P-1Po) по).

4. Внутренние оценки

Рассмотрим теперь семейство трубок Робразованных параллелотопами, параметры которых удовлетворяют дифференциальным уравнениям

~Р = А(г)р- + г (г), р-(го) = ро;

'р = А

Л 6 G, г(-) G G = { Г(-) | r(t) G G при п. в. t G T};

n

1<г<П^=1

Здесь Л и Г(г) — соответственно пхп-матрица и измеримая п х п-матричная функция — это параметры, определяющие семейство трубок, которые могут варьироваться и которые считаем стесненными ограничениями (42), ||Г|| — матричная норма ||Г||р из [10, с. 198], 0 — множество пхп-матриц, у которых сумма абсолютных величин элементов каждой строки не превышает 1.

Теорема 41.. Пусть X(г) — области достижимости системы (21) - (23). Параллелотопы Р-(г) = Р[р-(г),Р-(г)], параметры которых удовлетворяют соотношениям (41), (42), обладают свойством (25) и являются внутренними оценками для областей достижимости X(г). Более того, при каждом г > г0 справедливо представление (28), где объединение взято по параметрам Л, Г(-), удовлетворяющим (42):

х

Варьирование Г(-) при фиксированном Л = Е обеспечивает представление

х

где ео Я обозначает выпуклую оболочку множества Я, а Е — единичную матрицу.

Доказательство. Проверим (25). Зафиксируем t G T. Если x* G P- (t), то найдутся такие {£г}П=1, |&| < 1, что x* = p-(t) + P%(t)^i. Обозначив правую часть через x*(t), рассмотрим ее как функцию t (зафиксировав £). Тогда, очевидно, x*(9) G P-(в) при произвольном в < t и непосредственным вычислением легко проверить, что при выполнении соотношений (41), (42) x*(t) — А(т)x*(r) G P[г(т),R(t)], т G [в,t]. Таким образом, x* = x*(t) G X(t,e,P-(в)), и, значит, P-(t) С X(t,e,P-(в)). Аналогично, P-(to) С Xo. В силу формулы Коши соотношение x G X(t) для системы (21)-(23) означает, что

x = Ф

J to

при некоторых Z, С('), стесненных условиями

где Ф(t, т) — фундаментальная матрица системы x = A(t) x, удовлетворяющая соотношениям дФ(^т)/dt = A(t)Ф(t, т), Ф(т, т) = E.

Для доказательства (43) достаточно проверить, что для любых Z, £('), стесненных (46), можно найти параметры Л, Г(-) из (42) и a G IRn с условиями |a^ < 1, такие, что

x(t) = Ф(^^)ро + / Ф(£,т)г(т)^т + (ф(мо)Ро аЛ Ф(г,т)r(t)Г(тa,

to to

где через x(t) обозначена правая часть (45). Но этого, очевидно, можно добиться, положив aT = (1,1, ... , 1), Л = diagZ, Г(т) = diagС(т) (Т — символ транспонирования).

Обозначим Xд(t) = X(t,to,dX0), где дXo — граница X0. Тогда X(t) = coXд(t), так как в силу формулы Коши каждая точка первого множества может быть представлена в виде линейной комбинации двух точек второго множества, а обратное включение вытекает из выпуклости X(t). Далее, Xd(t) С co {P-(t) | Л = E, Г(-) G G}, поскольку, если x G

Xд (t), то x имеет вид (45), где у вектора Z хотя бы одна (пусть г*-я) компонента по модулю равна 1, и, следовательно, рассуждая как и выше, достаточно положить a = Z, Л = E,ав качестве Г(т) взять матрицу, у которой г*-й столбец равен sign Zit  С(т), остальные столбцы нулевые. Равенство (44) вытекает теперь из выпуклости X(t).

Отметим, что введенное семейство P-(-) включает семейство внутренних параллеле-пипедозначных оценок для X(), описанное в [16].

Заметим также, что в качестве внешних оценок мы брали параллелепипеды, а в качестве внутренних — параллелотопы, которые могут и не быть параллелепипедами. Однако справедлива

Лемма 41.. Если int Xo = 0 и удовлетворяющие (42) А и Г(-) таковы, что

det P-

tr

то внутренние оценки P-(t) оказываются невырожденными параллелепипедами.

Символом tr в (48) обозначен след матрицы, Bv — матрица, присоединенная к B [10, с.39], а Ф^) = Ф(^о) — фундаментальная матрица. Заметим, что нам важно только

условие intV-(to) = 0, т.е. det P-(to) = 0, поскольку положительности в (47) можно добиться, например, умножением какого-либо столбца матрицы Л или Р0 на -1.

Доказательство. В результате замены переменных x = Ф(£) x приходим к системе с нулевой матрицей A(t) = 0:

X = wf(t), x(to) eXo, wf(t) GV[f(i),JR(i)j,

где f = Ф-1 f, R? = Ф-1 R. Семейство внутренних оценок V- (•) областей достижимости Xf(-) этой системы определяется соотношениями

= f

и (42) и связано с исходным семейством V-(-) формулами pf- = Фp?-, P- = Ф Р-. Для матрицы Pудовлетворяющей (49), имеют место [10, с. 183] равенства

d ,.?- . /,f-w

dt

det P- = tr

4 Р3- = Р- • 1г

а* V /

Соотношения (47), (48) обеспечивают неубывание функции det Р- (*) и ее положительность. Так как det Ф(*) > 0, то и det Р-(*) > 0, V* € Т.

Как видно из доказательства, (48) можно заменить условием

1г

Замечание 4.1. Условие (48) (так же, как и (411)) не очень конструктивно (за исключением тривиального случая Г(*) = 0). Однако на его основе можно предложить следующий способ построения невырожденных внутренних оценок.

Пусть параметр Л € ^ зафиксирован, причем выполнено неравенство (47). Введем множество Т^ точек тк = + k л,, k = 0, ... , N, л, = (tf — . Рассмотрим класс

кусочно-постоянных функций Г(-): = { Г(-) | Г(*) = Г(тк) € 5, * € [тк,Тк+1), к = 0, ... , N—1 } ив нем задачу локальной оптимизации

£ volP-

^ max , Vt G TN.

а — а ~ а ~

Поскольку — det Р3- = — det Ф^ det Р3- + det Ф • — det Р3- и det Ф(*) > 0, получаем, при усло-а* а* а*

вии det Р3-(*) > 0, V* € [*о,т], что задача (412) при фиксированном т € Т^ эквивалентна максимизации по Г правых частей соотношений (410), или, иначе, задаче

1г

г &у

Но при Г 6 G имеем tr (£(т)Г) < max (т) |, причем последнее значение достигается на

k=i1<i<n

матрице Г*(т) = {y*j(т)}, построенной по следующему правилу. Для каждого I = 1, ... , n взять какое-то i*(/) 6 Argmax {|£](т)| | i = 1, ... , n} и положить

y«

Y

где sign z равен -1, 0, 1 для z < 0, z = 0, z > 0 соответственно.

Трубку P-(-) будем строить пошагово. Пусть для т G Tn матрица P_(t) уже определена на промежутке то < t < т. Продолжим ее на (т, т + h]. Если при r(t) = Г *(т), t G [т, т + h), для матрицы P-(t), найденной в силу (41), оказывается

det P-

то удовлетворяемся взятыми T(t) и построенными на этом промежутке P-(t). Иначе полагаем r(t) = 0, t G [т, т + h) и находим в силу (41) соответствующие P- (t). Полученная таким образом трубка P-(-) образована невырожденными параллелепипедами.

Очевидно, что если int X0 = 0 и -R(t) = 0, то, выбирая N достаточно большим, этим способом можно построить r(t), отличные от тождественного нуля. Аналогично можно строить невырожденные внутренние оценки P_(•), если на каждом шаге вместо Г*(т), решающего задачу (413), брать Г*(т) просто из условия tr (£(т)Г *(т)) > 0.

Достаточными условиями для выполнения (415) являются, в силу (410), неравенства

tr(S(t)r*(т)) > 0, Vt G [т,т + h).

d ~ _

Если на промежутке [т, т + h] найти оценку |0(t) — ф(т)| < А, где 0(t) = — det P (t) —

функция, стоящая в правой части формул (410), то еще одно, более грубое, достаточное условие для выполнения (415) можно записать в виде

det ) • tr

При n > 2 в качестве грубой оценки А могут служить, например, величины

Ai = n! n ||P_ Г-1 (h) + n! n (n—1) (CR)2 (||P_|| + CR h)n_2 h,

A2 = det P_ • n exp(nCRh) ||(P_)_1| • (h)+ + (Cr)2 (n + ||(ip_)_1H (1 — Cr ||(P_)_1|h)_2) h), если h < (Cr ||(P_)_1||)_1.

Здесь фигурирует та же матричная норма, что и в (42), аргумент т у всех величин для простоты записи опущен, и использованы следующие обозначения, введенные для произвольной непрерывной матричной функции F(t): (т, h) = max ||F(t) — F(т)||,

т <t<T+h

Cf(т) = max ||F(t)||. Оценку A1 несложно получить, вводя в правую часть первой из

т<t<T+h

формул (410) перекрестные члены, пользуясь формулой Ньютона—Лейбница для P_ и выражением P из (49), а также неравенствами типа

Оценка Д2 получается с использованием правой части второй из формул (410), тождества

d d

Якоби [10, с. 183], соотношения — X-1 = — X-1~гXX-1 для X = Р- и леммы Бихари [2,

dt d t

с. 112] для ||(Р-)- 11|.

Замечание 4.2. Задача (210) является задачей программного управления с терминальным критерием качества, где роль управляющих параметров играют матрица Л и измеримая функция r(t), стесненные ограничениями (42). Предположим, что int X0 = 0, причем det P0 > 0, и положим для простоты Л = E. Задача оптимального управления (210) в классе измеримых функций, удовлетворяющих (42), имеет решение. Необходимое условие оптимальности можно записать в виде принципа максимума Л. С. Понтрягина следующим образом. Если Г(-) — оптимальное управление, а Р-(-) — соответствующее решение системы (41), то при почти всех t G T выполняется соотношение

tr

reG

где матричная функция Ф^) является решением сопряженной системы

Ф = —A(t)T Ф, t G T, Ф(t/) = det Р-(t/) • (P-(t/)-1)т.

Действительно, существование оптимального управления вытекает из линейности системы и компактности множества G [11, с. 178]. Предположение det P0 > 0 обеспечивает, ввиду леммы 41., существование управлений, при которых det Р-(t/) > 0. Условие трансверсальности в соотношениях принципа максимума [12] принимает указанную форму в

д

силу известной [14] формулы — det X = det X • (X-1)т.

Заметим, что при A(t) = 0 соотношение (417) переходит в tr (P-(t/)-1P(t)r(t)) =

max tr (P-(t/)-1iR(t)r), что напоминает условие (413), но отличается от него аргументом reG _

у матрицы Р

Список литературы

[1] Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. Мир, М., 1987.

[2] ДЕмидович Б. П. Лекции по математической теории устойчивости. Наука, М., 1967.

[3] Калмыков С. А., Шокин Ю. И., Юлдашев З. Х. Методы интервального анализа. Наука, Новосибирск, 1986.

[4] КорноушЕнко Е. К. Интервальные покоординатные оценки для множеств достижимых состояний линейной стационарной системы. Автоматика и телемеханика, №5, 1980, 12-22; №12, 1980, 10-17.

[5] КостоусовА Е. К., КуржАнский А. Б. Гарантированные оценки точности вычислений в задачах управления и оценивания. Вычисл. технологии, 2, №1, 1997, 19-27.

[6] КРАСОВСКИй Н. Н., СУББОТИН А. И. Позиционные дифференциальные игры. Наука, М., 1974.

[7] КУРЖАНСКИЙ А. Б. Управление и наблюдение в условиях неопределенности. Наука, М., 1977.

[8] КУРЖАНСКИЙ А. Б., НИКОНОВ O. И. К задаче синтеза стратегий управления. Эволюционные уравнения и многозначное интегрирование. Докл. АН СССР, 311, №4, 1990, 788-793.

[9] КУРЖАНСКИЙ А. Б., Сивергина И.Ф. О необратимых эволюционных системах: гарантированное оценивание и задачи регуляризации. Докл. АН СССР, 314, №2, 1990, 292-296.

[10] Ланкастер П. Теория матриц. Наука, М., 1978.

[11] Ли Э. Б., МАРКУС Л. Основы теории оптимального управления. Наука, М., 1972.

[12] ФЛЕМИНГ У., Ришел Р. Оптимальное управление детерминированными и стохастическими системами. Мир, М., 1978.

[13] ЧЕРНОУСЬКО Ф. Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов. Наука, М., 1988.

[14] ATHANS M. The matrix minimum principle. Information and Control, 11, 1968, 592-606.

[15] BuSHENKOV V., Chernykh O., Kamenev G., Lotov A. Multi-dimensional images given by mappings: construction and visualization. Pattern Recognition and Image Analysis, 5, No. 1, 1995.

[16] KOSTOUSOVA E. K. State estimation for dynamic systems via parallelotopes: optimization and parallel computations. Optimization Methods and Software, 1997 (to appear).

[17] Kurzhanski A. B., FlLIPPOVA T. F. On the theory of trajectory tubes — a mathematical formalism for uncertain dynamics, viability and control. In "Advances in Nonlinear Dynamics and Control: A Report from Russia", Birkhauser, Boston etc., 1993, 122-188.

[18] KURZHANSKI A. B., VAlyi I. Ellipsoidal Calculus for Estimation and Control. Birkhauser, Boston, 1996.

Поступила в редакцию 3 ноября 1997 г., в переработанном виде 16 января 1998 г.