Полиэдральные аппроксимации в задачах гарантированного управления и оценивания

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

Проблему построения трубок траекторий (многозначных функций, описывающих, например, динамику множеств достижимости, разрешимости, информационных областей) можно назвать одной из фундаментальных задач математической теории управления. К необходимости изучения трубок траекторий (в частности, трубок выживающих траекторий, трубок разрешимости) приводят многие задачи теории управления и оценивания, теории дифференциальных игр, связанные с исследованием сложных реальных систем различной природы (механических, технологических, экономических, экологических, био-медицинских и др.), в которых присутствует недоопределенность в их описании. К недоопределенности могут приводить, например, неполнота информации о начальном состоянии системы, неконтролируемые возмущающие силы, помехи при измерении данных, неточности в задании параметров модели (коэффициентов уравнений) и т. д. При гарантированном подходе, принятом в настоящей работе, предполагается, что описание недоопределенностей имеет вид включений, ограничивающих возможные значения неизвестных величин принадлежностью заданным множествам. При этом решение многих задач управления и оценивания может быть получено, если построено некоторое многозначное отображение (трубка траекторий). Гарантированный подход был инициирован исследованиями Н. Н. Красовского [76−78] и далее систематически развит А. Б. Куржанским [86−93,196,201], Ю. С. Осиповым [81,117,218], А. И. Субботиным [80,140], их сотрудниками и учениками. Принципиальные результаты в области гарантированного управления, оценивания и идентификации, математического программирования в условиях неполной информации для различных классов систем были получены авторами работ [2−5,7,17,24,26−29,33−35,38,51,58,75,82,83,96,97,106,110,115, 120,130,135,136,142,145,148,157,164,167−169,176,180,197,198, 208, 210, 212,224,226,235] и др.

Для нахождения упомянутых многозначных отображений выведены различные динамические уравнения, форма которых соответствует выбранной форме описания множеств X С IRn. При этом использовались следующие формы описания: поточечная (заключающаяся в прямом перечислении точек, которые содержит Х) с помощью неравенства типа X — {хВ{х) < 0}, задающего множество уровня некоторой функции (например, подходящей функции цены, функции Минковского) — с помощью опорных функций (рпорных отображений в невыпуклом случае) — с помощью параметрического описания границы. Для систем с геометрическими ограничениями первой форме соответствует эволюционное уравнение, представляющее собой для многошаговых систем рекуррентные соотношения для пересчета множеств от предыдущего момента к следующему, а для дифференциальных систем — так называемое уравнение интегральной воронки. Последнее есть предельное соотношение, связывающее (в терминах расстояния или «полурасстояния» Хаусдорфа) близкие по времени значения множеств, и является аналогом обыкновенного дифференциального уравнения (ОДУ). Решением уравнения интегральной воронки служит многозначный интеграл, сводящийся в разных задачах к интегралу Аумана [165], альтернированному интегралу Пон-трягина [124,125], конволюционному интегралу [98] или обобщеному интегралу из [95]. При втором описании множества уравнение выписывается в пространстве состояний в терминах функции В (х). В частности, функция цены в дифференциальных системах, имеющая смысл оптимального расстояния до цели, описывается уравнением Гамильтона-Якоби-Беллмана-Айзекса с частными производными. Для опорного отображения получаются уравнения в частных производных в сопряженном пространстве. Известно несколько типов уравнений для параметрического описания границы. Выводу и изучению упомянутых уравнений посвящено большое число теоретических исследований, из которых отметим работы [14,19,32,38,55,79,95,98,108,111,118,123,139,142,144,173,220].

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

Существует много подходов к созданию упомянутых численных методов. Рассматривая их с точки зрения геометрического представления аппроксимирующих множеств, условно можно выделить следующие большие группы методов. В первую отнесем методы, которые основываются на аппроксимации множеств многогранниками (часто внешними и/или внутренними, а иногда и не обладающими указанными свойствами) с большим числом вершин и граней [15,16,18,20,31,44,45,47,50,56,85,103, 109,116,141,143,146,155,158,160,162,170,178,212,231]. Для систем высокой размерности эти методы могут потребовать весьма большого объема вычислений. Для невыпуклого случая разрабатываются методы, основанные на аппроксимации множеств невыпуклыми многогранниками [217], на представлении множеств в виде конечного набора своих выпуклых сечений и аппроксимации последних выпуклыми многогранниками [83,84].

В другую группу можно отнести методы, основанные на аппроксимации множеств объединением точек («пикселов») [37,107,119,223,227]. Они применимы и для невыпуклого случая, но тоже могут потребовать большого объема вычислений и памяти. Существует и явление «расширяющейся сетки» (чем больше множество, тем больше точек необходимо для его аппроксимации).

Еще один подход состоит в аппроксимации множеств классом более простых областей некоторой фиксированной формы (например, эллипсоидами, параллелепипедами). В настоящее время достаточно хорошо развит метод эллипсоидов, позволяющий строить внешние и внутренние оценки выпуклых множеств, в том числе оптимальные и локально-оптимальные в некотором смысле. Его разработке посвящены работы [6,9,21,43, 52−54,112−114,121,133,153,155,156,161,169,175,177,184,206, 215,216,219,221,224,226,228,229,232,234,235] и др.

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

Вопросы оценивания искомых множеств с помощью параллелепипедов рассматривались также в работах [22, 42, 88, 91,166,171,172,174,.

185,209,211,212,230−233] и некоторых других. Здесь значительные усилия уделены нахождению внешних и внутренних оценок, являющихся оптимальными (в статической постановке) или «последовательно» -оптимальными (в динамической постановке) в каком-либо смысле, например, в смысле объема или радиуса [22,42,166,171,172,185,212,232, 233], а также построению внешних оценок в виде ортогональных параллелепипедов, преимущественно с гранями, параллельными координатным плоскостям («боксов») [88,91,166,174,209,211,212,230,231]. При этом решение задачи часто предлагается не в аналитическом виде, а в виде решения одной или 2п статических оптимизационных задач. В некоторых случаях (например, для нахождения внешней оптимальной по объему оценки пересечения невырожденного параллелепипеда с гиперполосой и суммы невырожденного параллелепипеда с отрезком) решение было найдено в явном виде [172,233]. Строились также [194,195] внешние оценки в виде зонотопов [225] — политопов, представляющих собой сумму q (q > п) отрезков.

Покоординатные оценки («боксы», в русскоязычной литературе называемые также брусами или интервальными векторами) получают также с помощью интервальных операций, используемых в интервальном анализе. Интервальный анализ [1,49] — это самостоятельно развивающаяся область математики, имеющая в настоящее время очень обширную библиографию, а первой монографией на эту тему была книга R.E.Moore [213], вышедшая в 1966 г. Ряд авторов использовал методы интервального анализа для решения задач управления, оценивания и идентификации [36,41,46,48,57,152,159,183,204,207].

Следует однако отметить, что в динамических задачах оценивания трубок траекторий оценки, построенные с помощью интервальных вычислений, могут оказаться слишком грубыми в силу известного в интервальном анализе «эффекта обертывания» (wrapping effect) (см., например, [179], [49, с.177], [214]), и такие оценки наиболее полезны для систем, обладающих сильными свойствами устойчивости [57]. Другое применение интервального анализа состоит в построении для искомых множеств внешних и внутренних оценок в виде подпокрытий («замощений», дословно, «subpavings») — объединений неперекрывающихся «боксов». При этом для достижения заданной точности аппроксимации для систем большой размерности может потребоваться очень много вычислений и памяти. Поэтому, как признают сами авторы [183], такие методы подходят больше для систем невысокой размерности.

Обращаясь к теме диссертации, подчеркнем, что рассматриваемые в ней трубки траекторий обладают полу групповым свойством, входящим в определение обобщенной динамической системы в смысле Е. А. Барбашина и E. Roxin [8,222]. Поэтому естественно требовать выполнения аналогичного свойства для оценок. Таким образом, постановка задачи исключает использование стандартных процедур оптимизации ввиду требований динамики и многозначности. Упомянутая постановка является решающей при рассмотрении задач оценивания и синтеза управлений в условиях неопределенности [88,201].

Перейдем к изложению содержания работы. Она состоит из введения, шести глав, разбитых на 22 раздела (параграфа), заключения, трех приложений и списка литературы.

Первая глава посвящена «полиэдральному исчислению». Этим термином мы называем аппарат для работы с множествами в рамках выбранного класса областей — параллелепипедов (и иногда более широкого класса — параллелотопов). Упомянутый аппарат разрабатывается с целью последующего использования для построения полиэдральных аппроксимаций трубок траекторий в задачах гарантированного управления и оценивания и в этом смысле в некоторой степени подобен развитому в [201] эллипсоидальному исчислению (чем и объясняется выбранный термин). Разрабатываемое «полиэдральное исчисление» может рассматриваться и как некоторое развитие интервального анализа, при котором базовыми множествами служат не интервальные векторы, а произвольные параллелепипеды. Представляется, что оно может оказаться полезным для решения более широкого круга задач, чем те, которые рассмотрены в последующих главах (в частности, в областях, относящихся к оптимизации, аппроксимации, идентификации и др.).

Для пояснения мотивации вводимых конструкций в главу I включен § 1, где на примере многошаговых систем даны постановки некоторых задач управления и оценивания, решения которых связаны с построением трубок траекторий. Здесь приведены определения некоторых многозначных функций %[¦]. Так, трубка траекторий или трубка достижимости описывает эволюцию во времени множеств достижимости (МД) Х[к] множеств тех состояний системы, которые могут быть достигнуты в момент к 6 {1,., N} из заданного начального множества с помощью входных воздействий (управлений или возмущений), подчиненных заданным ограничениям. Если на траектории системы наложено дополнительное ограничение на координаты — фазовое ограничение (ФО), то то трубка достижимости известна также как трубка выживающих траекторий (траекторий, не нарушающих ФО). Для задач гарантированного оценивания состояния такое многозначное отображение возникает естественным образом. Оно описывает динамику информационных областей множеств состояний, совместимых с данными измерений и априорными ограничениями [88].

Далее предполагается, что множество начальных состояний и множества входных воздействий в каждый момент времени (геометрические «жесткие» ограничения на управления/возмущения) являются параллелепипедами, а ФО в каждый момент времени представляют собой параллелепипеды или полосы. Параллелепипедом V (p, Р, тг) в Л" с центром р 6 IRn, неособой матрицей ориентации Р = {р1 • • •рп} 6 Rnxn и величинами «полуосей» щ > 0 называем множество V = V (p, Р, 7г) = {хх =.

ТЬ р + Ёрг7г< 1, г—1,., тг}. Полосой S называем пересечение m т < п) гиперполос с линейно независимыми нормалями (при т, — п полоса превращается в параллелепипед). Ставится задача о нахождении внешних V+[-] и внутренних V~[-] параллелепипедозначных оценок для Х[-]: V~[k] С Х[к] С Т+[к], обладающих обобщенным полугрупповым [201] и эволюционным [155] свойствами (являющимися аналогами полугруппового свойства для МД), и, более того, о введении некоторых семейств таких трубок, обеспечивающих точные представления посредством пересечения внешних и объединения внутренних оценок. Иногда внутренние оценки удобнее искать в виде параллелотопов — зоно-топов с числом слагаемых отрезков q = п. Для формализации естественного желания строить оценки так, чтобы они были «как можно ближе» к искомым множествам, вводятся понятия тугих [202,203], касающихся и неулучшаемых по включению [201] оценок. В частности, внешнюю (внутреннюю) оценку V множества Q Е conv 1R" называем тугой (в направлении I), если значения опорной функции множеств V и Q на векторах ±Z совпадают. Внешнюю оценку называем касающейся, если она является тугой в направлении п векторов, биортогональных к {рг}" =1. Если число элементов в семействах оценок оказывается довольно большим или даже бесконечным, то, ограничиваясь каким-либо конечным подмножеством элементов, можно получить внешние и внутренние аппроксимации искомых множеств. Задавшись каким-либо критерием оптимальности, можно искать оптимальную оценку искомого множества.

Как следует из известных рекуррентных формул [51], построение оценок для введенных трубок основывается на выполнении элементарных операций над параллелепипедами: афинного преобразования, геометрической суммы, пересечения. Результат такой операции может не быть параллелепипедом и в этом случае аппроксимируется параллелепипедами снаружи и изнутри. Остальные пять параграфов главы I посвящены х[к} = П-Р+Щ.

Xlk] = JV~lk].

0.1) (0.2) разработке техники аппроксимации множеств (в частности, полученных в результате использования упомянутых и некоторых других операций) с помощью областей выбранного класса. Далее, если не оговорено противное, под оценками будем понимать параллелепипедозначные оценки. Все предлагаемые ниже оценки зависят от некоторых параметров и могут быть легко вычислены по явным формулам (за исключением специально оговариваемых случаев).

В § 2 рассмотрены способы построения и некоторые свойства оценок для выпуклых компактных множеств Q Е conv]Rn. Для произвольного Q Е convIR" (выпуклого политопа Q) введены семейства внешних (внутренних) оценок V+ (V~), обеспечивающие представления.

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

§ 3 посвящен аппроксимации множества Q, являющегося суммой нескольких параллелепипедов. Введено несколько семейств внешних и внутренних оценок, обеспечивающих (0.3), (0.4). Рассмотрена задача о нахождении для суммы двух параллелепипедов внешней оценки наименьшего объема. В случае, когда один из слагаемых параллелепипедов невырожден, а другой мал, ее решение найдено в явном виде.

Q = f]'P+, Q = JV~.

0.3) (0.4).

В § 4 строятся оценки для множеств, полученных в результате использования операции — геометрической разности. Отмечено, что геометрическая разность параллелепипеда и произвольного множества У 6 convHn есть либо параллелепипед, либо пустое множество. Введены семейства внешних и внутренних оценок для множества («pM-fpC2)) — где V^ ~ параллелепипеды, и приведен пример, показывающий, что представление (0.4) при этом, вообще говоря, не гарантировано. Для случая, когда V^ невырожден, a V^ и V^ «малы», в явном виде найдена внешняя оценка, имеющая наименьший объем.

§ 5 посвящен построению оценок для пересечения параллелепипеда и полосы. Для случая, когда S^ есть параллелепипед, рассмотрены два способа построения семейств внешних оценок, обеспечивающих (0.3). Первый основывается на сведении (путем введения матричных параметров [75,201]) операции пересечения к изученной ранее операции сложения параллелепипедов, второй — на том факте, что пересечение параллелепипедов с одинаковыми матрицами ориентации снова есть параллелепипед. Далее рассмотрен случай, когда S^ — гиперполоса. Отмечается, что внешняя оценка с произвольной матрицей ориентации может быть несложно найдена с помощью алгоритмав явном виде найдено несколько касающихся оценок, соответствующих специально выбранным матрицам ориентацииуказаны оценки, имеющие наименьший объем. Последние два утверждения обобщают результаты [233] на случай int Q = 0. Описаны способы нахождения в аналитическом виде точки, принадлежащей Q, что позволяет строить внутренние оценки, введенные в § 5, в явном виде.

В § 6 строятся «элементарные» оценки для множеств, возникающих в гл. VI. Сначала рассматриваются аппроксимации выпуклой оболочки объединения двух параллелотопов и вводятся семейства оценок, обеспечивающие (0.3), (0.4). Затем рассматриваются множества Z в пространстве Rn+1, заданные своими сечениями по последней координате. Введены четыре операции с такими множеством. Первые три: AQZ, Z@a и Z®y (умножение на матрицу A G Нпхп, сложение с вектором, а € Нп, пересечение с множеством У С ]Rn) действуют независимо на каждое сечение, а последняя — Z 1±1 71, 71 С Жп, — комбинирует операции суммы Минковского и объединения по сечениям. В качестве внешних оценок множеств в IRn+1 берутся политопы П, определяемые своими «нижним» и «верхним» сечениями посредством операции выпуклой оболочки, причем сечения эти — параллелепипеды с одинаковыми матрицами ориентации. При этом «промежуточные» сечения П тоже оказываются параллелепипедами. Построены семейства внешних оценок для множеств вида П ЫР, где V — параллелотоп, и ПО<5, где S — параллелепипед либо гиперполоса в lRn. Параметрами оценок выступают матрицы ориентации сечений и 2п векторов, определяющих «боковые грани» .

Во второй главе разрабатываются методы двусторонней аппроксимации МД линейных динамических систем с геометрическими ограничениями на входные воздействия и без ФО. Если не сказано другое, введенные семейства оценок обеспечивают соотношения (0.1), (0.2).

§ 7 посвящен многошаговым системам. Введены три конечных семейства тугих внешних оценок в виде ортогональных или неортогональных параллелепипедовоценки из последнего семейства оказываются касающимися, а при k=N — минимальными по включению. Трубки V+[•] из введенных семейств удовлетворяют эволюционным уравнениям, включающим на каждом шаге изученную ранее операцию вычисления внешней оценки для суммы двух параллелепипедов, и отличаются друг от друга способом построения матриц ориентации. Таким образом, отказ от фиксированных единичных матриц ориентации позволяет ослабить эффект «обертывания» из интервального анализа. Построены касающиеся оценки, применимые и в случае более общих ограничивающих множеств. Далее введено несколько конечных семейств внутренних оценок. Доказано, что оценки одного из семейств являются тугими, а при к = N — и максимальными по включению. Однако в системах, получающихся дискретизацией систем с непрерывным временем, оценки такого типа могут получиться «длинными узкими». Поэтому введено также более широкое семейство внутренних параллелотопозначных оценокв нем выделены тугие.

В § 8 изучены аппроксимации МД X (t) для систем с непрерывным временем. При заданной динамике матриц ориентации выведены ОДУ для центров и величин полуосей параллелепипедов V+(t), являющихся внешними оценками для X (t). В частном случае (матрицы ориентации — единичные, ограничивающие множества — «боксы» с центром в начале координат) оценки превращаются в приведенные в [230]. Показано, что если матрицы ориентации удовлетворяют однородной системе ОДУ с матрицей из исходной системы, то соответствующие оценки оказываются касающимися для X{t) и (0.1) достигается варьированием (бесконечного числа) начальных условий для матриц ориентации. Приводятся ОДУ, описывающие динамику тугих внутренних оценок V~(t) для X (t) при этом X (t) (в случае mtX{t) ф 0) представимо в виде замыкания объединения оценок V~(t), взятого по матричному параметру, определяющему начальные условия V~(0). Введено также семейство внутренних параллелотопозначных оценок для A'(t), параметризованное матричной функцией Г (-), которая входит в правую часть ОДУ, описывающих динамику параметров V~(-). Среди множества оценок выделены тугие, и предложены способы построения кусочно-постоянных функций Г (-), обеспечивающих невырожденность оценок. Рассмотрена задача оптимального управления (роль управления играет Г (-)) о нахождении во введенном семействе трубки V~(-) с наибольшим в смысле объема сечением в конечный момент времени, и для нее выписано необходимое условие оптимальности в форме принципа максимума Понтрягина [126].

§ 9 посвящен вопросам численного построения оценок МД. Вначале предлагаемые численные алгоритмы рассматриваются с точки зрения их эффективности. В частности, приведены оценки числа операций для точного нахождения XN] в виде (0.1) и показано, что при больших N предложенные алгоритмы могут быть более эффективны по числу операций, чем известный алгоритм [103], где МД ищется в виде системы линейных неравенств. Этот выигрыш обусловлен специальным видом ограничивающих множеств (это параллелепипеды, а не произвольные выпуклые политопы, как в [103]). Ряд алгоритмов реализован в виде пакета программ (ToolBox'a) BOXES в системе MATLAB 5 (краткие сведения о нем приведены в Приложении В), а ряд — в виде программы на языке С для многопроцессорного вычислительного комплекса МВС-100. Дается ее краткое описание и обсуждаются вопросы эффективности распараллеливания. Приводятся результаты расчетов для модельных примеров, аналогичных рассмотренным в [155,201].

В третьей главе рассмотрены оценки МД линейных динамических систем с ФО в дискретные моменты времени. Разработанные алгоритмы применимы для аппроксимации информационных областей в задачах гарантированного оценивания при неточных дискретных измерениях. Вводимые семейства оценок опять обеспечивают (0.1), (0.2).

§ 10 посвящен многошаговым системам. При построении первого (бесконечного) семейства внешних трубок V+[- используется подход [75, 201], основывающийся на снятии ФО (путем введения параметров) и последующем использовании конструкций из § 7. При построении двух других семейств внешних оценок (когда ФО имеют вид параллелепипедов и полос) используются оценки из § 5 для пересечения двух параллелепипедов и параллелепипеда с гиперполосой соответственно. При этом пересечение в (0.1) достаточно брать по конечному (но очень большому) множеству последовательностей матриц ориентации. Указано, как в случае int X[N] = 0 можно выбирать матрицы ориентации, чтобы иметь возможность получать оценки в виде вырожденных параллелепипедов. Далее введены семейства внутренних трубок V~[-]. Можно заметить, однако, что при неудачном выборе параметров не исключается и случай, когда, начиная с некоторого шага, оценки могут получиться пустыми, а брать для обеспечения (0.2) объединение по всевозможным центрам не очень конструктивно. В § 11 вводятся семейства оценок Т>±-{-) для трубок достижимости Л'(-) систем с непрерывным временем и ФО в моменты tk, к — 0,., iVc. При t Е параметры V±(t) удовлетворяют ОДУ, описанным в гл. II, § 8, а при t = Ц используются оценки, введенные в гл. I, § 5. В § 12 описаны примеры численного построения оценок МД.

В четвертой главе рассматриваются две задачи нелинейного синтеза управлений в системах с исходной линейной структурой и геометрическими ограничениями: нахождение трубки разрешимости УУ (-) и многозначной позиционной стратегии управления, гарантирующей попадание в конечный момент времени на целевое множество всех траекторий соответствующего дифференциального включения, начинающихся в любой позиции из упомянутой трубки, и та же задача, но для систем, функционирующих в условиях неопределенности. Пути решения данного класса задач указаны в монографиях [80,88]. В [95,111] показано, что искомая трубка W (-) представляет собой единственное максимальное по включению решение некоторого эволюционного уравнения. Решение этого уравнения дается интегралом Аумана (если нет неопределенности в задании правых частей системы) или альтернированным интегралом Понтряги-на. Точное нахождение W (-) представляет собой нетривиальную задачу. Известно, что если построена вся трубка W (-), либо какая-либо другая трубка, удовлетворяющая эволюционному уравнению, то решение задачи синтеза для позиций из этой трубки может быть найдено с помощью экстремальных стратегий Н. Н. Красовского. В [93,94,201] разработана схема «эллипсоидального синтеза». В данной главе разрабатываются конструктивные схемы решения задачи синтеза, при которых вместо трубки W (-) используются семейства параллелепипедозначных оценок. В § 13 дается постановка задачи синтеза. В § 14 введены семейства внешних оценок для трубки разрешимости, дающих внешние оценки множеств тех позиций, для которых задача синтеза разрешима. В § 15 введены семейства внутренних параллелотопозначных оценок — оценок, удовлетворяющих упомянутому уравнению интегральной воронки. Эволюция внешних и внутренних оценок описывается системами ОДУ, где начальные условия или правая часть зависят от параметров (матрица или матричная функция), определяющих семейство. Внутренние оценки, являющиеся парал-лелепипедозначными трубками разрешимости, позволяют находить допустимые синтезирующие стратегии в аналитическом виде на основе решения специфической задачи квадратичного программирования (минимизации квадратичной функции на единичном кубе). Для первой задачи оба семейства обеспечивают точные представления трубки разрешимости (через операции пересечения или объединения оценок), а внешние оценки являются касающимися. Выведено нелинейное дифференциальное включение, все решения которого определяют невырожденные па-раллелепипедозначные внутренние оценки. В § 16 обсуждаются результаты расчетов для модельных примеров, аналогичных рассмотренным в [201].

В пятой главе рассматривается задача гарантированного оценивания состояния параболической системы при «геометрических» ограничениях на неопределенные входные параметры. Задачам оценивания в системах с распределенными параметрами посвящен обширный поток публикаций. Наиболее близким вопросам, связанным с вычислением множеств достижимости и информационных областей параболических систем при «геометрических» ограничениях, посвящены, например, работы [92,105,198]. В § 17 дается постановка задачи и для аппроксимации информационной области, являющейся решением задачи, вводятся (путем дифференциально-разностных или конечно-разностных аппроксимаций) последовательности задач гарантированного оценивания состояния конечномерных систем. В § 18 показано, что при сгущении сетки имеет место сходимость к нулю хаусдорфова полурасстояния между искомым множеством и множеством кусочно-постоянных восполнений решений аппроксимирующих задач. Сходимость к нулю второго полурасстояния доказана при двух дополнительных предположениях. Первое связано с гладкостью функций, задающих ограничения. Второе связано с корректностью задачи. Оно выполняется, например, либо в случае сильной наблюдаемости системы [198] при отсутствии возмущений в правой части уравнения теплопроводности (что эквивалентно [136] так называемой непрерывной наблюдаемости [181]), либо при предположении о регулярности сигнала [198]. Установлена скорость сходимости. Аналогичные результаты справедливы для множества достижимости. В § 19 обсуждаются возможности использования параллелепипедозначных оценок решений аппроксимирующих задач для нахождения внешних и внутренних оценок искомого множества. Отмечается, что формулы для построения семейства внешних касающихся оценок МД многошаговых систем из § 7 приводят в данном случае к неустойчивой разностной схеме. Предлагаются способы построения двух внешних оценок и одной внутренней. Эти способы, ввиду их простоты, позволяют находить параллелепипедо-значные оценки решений аппроксимирующих задач достаточно высокой размерности (в модельном примере п = 199, N = 5(п+1)).

Шестая глава посвящена аппроксимации МД линейных многошаговых систем с интегральными неквадратичными ограничениями на управление и неопределенностью в начальных условиях, включая системы с фазовыми ограничениями. В § 20 дается постановка задачи и вводятся множества достижимости Х[к и Z[k] в исходном и в «расширенном» фазовом пространстве, включающем координату, которая соответствует текущему запасу управления. Отмечается, что множества Z[k] (в отличие от Х[к) обладают полугрупповым свойством. Приведены точные описания МД и, в частности, системы рекуррентных соотношений для нахождения Х[к] (в случае отсутствия ФО) и Z[&]. Статическое описание Х[к из начала координат для автономных многошаговых систем (без ФО) со скалярным управлением известно из [138]. Найдены достаточные условия, гарантирующие для множеств Я[к] невозрастание сечений и выпуклость. В § 21 для множеств Х[к] введены семейства внешних и внутренних параллелепипедо-(иногда параллелотопо-)значных оценок V^k), обеспечивающие точные представления (0.1),(0.2). Для случая без ФО во введенных семействах выделены тугие и касающиеся оценки. Построение внешних (внутренних) оценок при наличии ФО в виде параллелепипедов (соответственно, полос) сводится путем введения параметров к построению оценок МД для вспомогательных систем без ФО (соответственно, с геометрическими ограничениями на управление). В § 22 для МД 2[к], отвечающих, соответственно, исходным системам без ФО, с ФО в виде параллелепипедов и с ФО в виде полос введены три семейства внешних оценок в виде политопов Пвыведены рекуррентные соотношения, описывающие динамику этих оценок. В случае отсутствия ФО в исходной системе доказано точное представление 2[к] в виде пересечения внешних оценок. С использованием оценок такого типа найдены параллелепипедозначные оценки множеств Х[к] и установлено, что при отсутствии ФО получаемое при этом семейство совпадает с введенным в § 21 семейством касающихся оценок. Конструкции, описанные в §§ 21 и 22, проиллюстрированы на модельных примерах.

В Приложении, А приведены некоторые вспомогательные леммы из области линейной алгебры, теории матриц и выпуклого анализа, а также некоторые известные факты, которые используются при доказательстве основных утверждений. В Приложении В приводится список основных функций пакета программ BOXES для системы MATLAB. В Приложении С собраны все рисунки.

Формулы, леммы, теоремы и т. д. имеют в работе двойную нумерацию — параграф и номер внутри параграфа. Такая же нумерация принята для рисунков (где первый номер обозначает параграф, к которому рисунок относится), хотя сами они вынесены в Приложение С.

Разработка методов, описанных в диссертации, была поддержана грантами РФФИ 94−01−803, 96−01−50, 97−01−1 003, 97−01−672, 0001−369 и 03−01−528. Результаты диссертации были представлены в докладах (указано в хронологическом порядке) на V Конференции «Транспьютерные системы и их применение», Домодедово, 1995; II — III International Workshops «Beam Dynamics & Optimization» (BDO-95, BDO-96), С.-Петербург, 1995, 1996; IMACS Multiconference «Computational Engineering in Systems Applications» (CESA'96), Лилль, Франция, 1996; 11 — 12 Международных совещаниях по интервальной математике, Новосибирск, 1996, Красноярск, 1997; 13th International Symposium on the Mathematical Theory of Networks and Systems (MTNS-98), Падуя, Италия, 1998; Международной конференции «Распределенные системы: Оптимизация и приложения в экономике и науках об окружающей среде» (DSO'2000), Екатеринбург, 2000; Международной конференции «Дифференциальные и интегральные уравнения. Математические модели», Челябинск, 2002; юбилейной конференции, посвященной 10-летию РФФИ, Москва, 2002; 4th International Conference «Tools for Mathematical Modelling» (MathTolls'2003), С.-Петербург, 2003, и докладывались на совместных семинарах «Системный анализ и сопряженные уравнения» кафедры системного анализа факультета ВМК МГУ им. Ломоносова и Института вычислительной математики РАН (руководители семинара — академик РАН А. Б. Куржанский и академик РАН Г. И.Марчук), семинарах Института математики и механики УрО РАН. Основные результаты диссертации опубликованы в 20 работах [64−74,149,186−193]. Статьи [61−63] примыкают к вопросам, затронутым в диссертации, но не вошли в нее.

Автор выражает глубокую признательность академику РАН Александру Борисовичу Куржанскому за привлечение ее внимания к теме диссертации, постоянное внимание к работе, ценные советы и поддержку.

Заключение

.

Работа посвящена разработке методов аппроксимации трубок траекторий линейных динамических систем в задачах гарантированного управления и оценивания при помощи параллелепипедов и параллелотопов. Получены следующие основные результаты.

1. Развиты элементы «полиэдрального исчисления» — аппарата работы с множествами в рамках выбранного класса областей — параллелепипедов (и иногда более широкого класса — параллелотопов). Изучены способы построения и свойства внешних и внутренних полиэдральных (параллелепипедои параллелотопозначных) оценок для выпуклых компактных множеств. Изучены операции над параллелепипедами и параллелотопами (геометрические сумма и разность, пересечение с полосой, выпуклая оболочка объединения) и способы построения, а также свойства оценок результирующих множеств.

2. Разработаны алгоритмы построения внешних и внутренних аппроксимаций множеств достижимости линейных динамических систем (многошаговых и описываемых обыкновенными дифференциальными уравнениями, с геометрическими ограничениями на управление) при помощи семейств параллелотопов. Для оценок выведены эволюционные уравнения, независимое интегрирование которых позволяет организовать распараллеливание вычислений. Доказано, что введенные семейства обеспечивают точные представления искомых множеств через операции пересечения и объединения оценок. Изучены свойства оценок, касающиеся неулучшаемости по включению, касания, невырожденности и пр.

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

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

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

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

7. Разработан пакет программ полиэдрального оценивания BOXES в виде набора процедур для системы MATLAB.