ALGORITHMS OF SYMBOLIC COMPUTATIONS BASED ON ROOT TREES FOR EVALUATING THE CAPABILITY OF THE CONTROL PROCESS

Full Text

Введение. Практическое построение управления объектом выполняется как в детерминированном слу- чае, так и при априорной неопределенности внешних возмущений, а также неопределенности состояния текущего объекта. Появление неопределенности зави- сит от влияния различных неопределенных факторов: возмущающих воздействий, не поддающихся контро- лю погрешностей параметров в определении началь- ных условий, и некоторых других причин. Вероятно- стные (стохастические) характеристики во многих случаях не могут обеспечить эффективную оценку поведения управляемой системы с неопределенными факторами [1-3]. Причины этого заключаются в том, что их использование принципиально не гарантирует результат одного конкретного опыта (испытания) и, кроме того, требует знания статистических харак- теристик, которые не всегда доступны в достаточной пьютеров, поэтому используются структуры данных, составленные из формальных линейных комбинаций корневых помеченных деревьев для эффективных символьных вычислений композиций операторов. Можно напомнить, что дерево - широко распростра- нённая программная единица для хранения и обра- ботки однотипных данных, имитирующая древовид- ную структуру в виде набора связанных узлов [8], являющаяся связным графом, не содержащим циклы. В статье будут использоваться корневые конечные деревья, в которых выделена одна вершина (корень дерева). Формально корневое дерево определяется как ко- нечное множество T одного или более узлов со сле- дующими свойствами: а) существует один корень дерева Т; б) остальные узлы (за исключением корня) расмере [4-6]. пределены среди m ³ 0 непересекающихся множеств В данной статье за основу выбран подход, в кото- ром для оценки возможностей управления строятся формулы решения задачи (в общем случае прибли- женные с контролем их точности), что помогает оце- нить области значений этих формул. Области значе- ний этих формул определяют гарантированные гра- ницы всех возможных фазовых состояний системы T1, ...,Tm , и каждое из множеств является корневым деревом; деревья T1, ...,Tm называются поддеревьями данного корня Т. Постановка задачи оценки множеств достижимости. Структура управляемого объекта описывается системой дифференциальных уравнений управления с учетом влияния всех факторов неопре- деленности. Эти границы являются верхней и нижней dy = f (t, y, u) dt (1) границами множеств достижимости. В статье описы- ваются методы, повышающие эффективность работы с символьными формулами, на которых основан рас- чет включений множеств достижимых множеств. с заданным классом допустимых управлений и началь- ным и конечным состоянием управляемого объекта при условиях, налагаемых на правую часть системы дифференциальных уравнений: Символьные формулы решений лежат в основе этих алгоритмов, их объем может достигать значительной величины. Символьная формула (аналитическое где u(t) ÎU Ì Rr , t Î T = [t0, tF ] , (2) Y0 ,U - выпуклые компактные множества. Полавыражение) определяется как последовательность гаем, что функция f (t, y, u) вместе со своими произимен переменных и знаков операций, которые нужно водными по y, u является непрерывной относительно проделать в определенном порядке над значениями этих переменных, чтобы получить значение выражеаргументов (t, y, u) на произведении T ´ Rn ´U и ния. Поэтому символьный метод (аналитический ме- тод) представляет метод преобразования символьной информации (символьных формул) на языке анализа удовлетворяет условию Липшица по y Î Rn с константой L > 0 " y1, y2 Î Rn на T ´ Rn ´U . Кусочноматематических выражений. В эти формулы могут непрерывная функция u(t), t Î T , - это управляющая включаться числовые константы с отложенным вы- полнением арифметических действий над ними. Можно провести некоторую аналогию с определени- ем из [7], где предлагается разработать аппарат для преобразования уравнений с помощью простых мате- матических приемов, большинство из которых подоб- но обычным алгебраическим алгоритмам. В нашем случае этот аппарат рассчитан на использование комфункция, удовлетворяющая (2) и такая, что при этом управлении существует непрерывная кусочно-диффе- ренцируемая траектория y(t) системы (1) при t Î T и заданном начальном состоянии y0 . Множество до- пустимых управлений обозначается через U . Для описания управляемых систем, описываемых обыкновенными дифференциальными уравнениями [1-3], во многих задачах требуются множества дос- сборки по адресам. Для этого возможно использовать тижимости Y (t) - множества точек в фазовом проj( y0 ) - непрерывное, однозначное отображение странстве Rn , в которые возможно сдвинуться вдоль траектории решения задачи (1), (2) за интервал времени [t0, t] . Из определения множества достижимости ясно, единичного интервала на n-мерный куб, называемое кривой Пеано, заполняющей пространство и пред- ставляющей непрерывную, нигде не дифференцируе- мую кривую, которая проходит через все точки едичто практически необходимо численно приближать ничного гиперкуба в пространстве Rn . Это соответмножества достижимости и вычислять границы областей, содержащих эти множества, т. е. строить внешние оценки множеств достижимости. Более де- тально изучены множества достижимости линейных систем дифференциальных уравнений с выпуклыми ограничениями на управления и состояния системы. В работах [4-6] представлены численные методы, позволяющие вычислять границы множеств дости- жимости для систем такого типа, кроме того, методы нахождения внешних оценок множеств достижимости для линейных систем описаны в работах [3; 9]. Для нелинейных систем эта задача решается зна- чительно более сложно, возможно оценивать множе- ства достижимости, причем предлагаемые методы обычно требуют больших вычислительных затрат. Множества достижимости нелинейных систем в обствие задано отображением элементов конечного множества отрезков из единичного интервала и эле- ментами конечного множества гиперкубов, входящих в Rn. Формула будет представлять рекурсивную структуру, размер которой изменяется. Для записи такой формулы в компьютере используются линей- ные динамические структуры. В рассматриваемых задачах управление является измеримой функцией, что не допускает применения методов рядов Тейлора для построения опорных траекторий. В символьный метод оценки множеств достижи- мости входит запись компонент символьных формул решений как векторных функций, состоящих из символьных компонент s (tk ) , зависящих от символьных щем случае невыпуклые, несвязные. Созданы методы форм начальных данных y0, ..., y0 и описывающих аппроксимации множеств достижимости, исполь- 1 n зующие уравнение Беллмана, а также принцип срав- нения с реализацией метода эллипсоидов, известны схемы [2; 5] аппроксимации множеств достижимости за счет вычисления характерных точек множеств непосредственно через решение серии задач опти- мального управления [10; 11]. Основная задача статьи - применить методы сим- вольных вычислений на основе корневых деревьев для улучшения реализации гарантированных методов решения дифференциальных систем с учетом управ- ляющих воздействий и основанных на символьном представлении решений. Более полное описание этого подхода можно найти в [12-18]. Пусть справедлива равномерная оценка | y(t) |< b для всех решений (1) на интервале t Î[t0,T ], где b = const > 0; множество достижимости Y (t) = f (t, y,U ) для всех у, t Î[s,T ], является компактным и выпуклым множеством. Как было отмечено выше, символьная формула решений определяется сдвигом вдоль траектории ре- шения и получается в процессе последовательного преобразования формул вида Y n = Fn (t0, K, tn,Y 0,Y1, K,Y n ) = сдвиг вдоль кривой, аппроксимирующей траекторию решения системы, на каждом шаге. Сдвиг вдоль тра- ектории решений определяется на основе построен- ных символьных формул решений. Символьные фор- мулы не преобразуются на каждом шаге алгоритма, они хранятся в памяти компьютера, для этого полез- ным являются символьные формулы кусочно- полиномиальных функций. Используя символьную формулу Y, аппроксимирующую оператор сдвига вдоль траектории, в методе определяются прообразы экстремальных значений (верхних и нижних границ для множеств решений) как решения экстремальной задачи. Эти точки определяют границы множеств достижимости. Выполнение преобразований символьных формул - это первый этап гарантированного метода включения решений, за которым следует этап числовых вычис- лений. Символьные преобразования реализуются в системах компьютерной алгебры. Однако такое применение компьютерной алгебры, как правило, яв- ляется крайне затратным по времени исполнения, особенно если вычисления производятся в цикле. Найденные формулы часто являются громоздкими, что и приводит к неэкономным вычислениям, особен- но если речь идет о вычислениях в цикле. Поэтому в = Sn (Y 0) oKo S 2(Y i-1) o S1(Y i ). (3) статье предлагается хранить и обрабатывать форму- лы, хранящиеся в виде помеченных деревьев. Пусть j( y0 ) обозначает однозначное отображе- Преобразования символьных формул. Вычисле- ния, рассматриваемые в статье, представлены как алние единичного интервала из R1 на прямоугольный гебраические выражения над входными данными, параллелепипед из Rn , которое каждой точке t Î R ставит в соответствие некоторую точку y = j(t). 1 2 n Такое отображение определяет процедуру исполне- ния, в которой для каждой точки t Î R определяется формула отображения F (Y 0,Y 0, K,Y 0 ) и процесс ее которые сохраняют важнейшие соотношения между входными данными и результирующей аналитической информацией. В предлагаемых методах символьных вычислений моделируются операторы присваивания, условные операторы, циклы и процедуры. Это помо- гает повысить эффективность и точность при настой- чивом применении процедур упрощения. Определим умножение на укоренившихся поме- ченных деревьях, тем самым создавая набор этих структур данных как ассоциативную алгебру. Алгебра гомоморфизмов задана на исходной алгебре операто- Diff (D1, ..., DN ; R) является алгеброй всех отображе- ний R ® R , порожденных отображениями Dm L(a) , a Î R (отображение L(a), a Î R определяется завиров, отображаемой в данную алгебру деревьев. Если операторы представить на этой структуре данных, то появятся сокращения, связанные с тем, что непере- становочные операторы выражаются через коммутисимостью L(a)(b) = ab Пусть c : k E1, ..., EM для b Î R ). ® Diff ( D1, ..., DN ; R) рующие операторы. Это приводит к алгоритму, при- менение которого для определения формул производ- ных ускорит вычисления оператора экспоненциально. Многие вопросы, описанные в этом разделе, опи- раются на работы [19; 20]. обозначает отображение, которое отображает p Î k E1, ..., EM в линейный дифференциальный оператор c( p) , полученный подстановкой (1) и упро- щением, с использованием того факта, что Dm являются Кратко напомним основные определения, исполь- зуемые в этой работе. производными R. Пусть p Î k E1, ..., EM l имеет вид Алгебра над полем - это векторное пространство, снабженное билинейным произведением. Отсюда p = å pi , где каждый член i=1 pi имеет степень m. Для следует, что алгебра над полем является одновременрасчета значения c( p) будем вычислять c( pi ) . Это но векторным пространством и кольцом, причём эти структуры согласованы. Алгебра Ли - это векторное пространство L над даст значение формулы жим, что Expenditure( p) lm!N m членов. Предполо- - это затраты применения полем k ; на пространстве введено билинейное отображение [-, -] : L ´ L ® L , удовлетворяющее усло- виям: алгоритма A для упрощения p Î k E1,..., EM . Затраты пропорциональны количеству дифференцирований и умножений. [x, y] + [ y, x] = 0 для всех x, y Î L ; Тогда Expenditure( p) = O (lmn!Nm ) . Simple éë x,[ y, z]ùû + éë y,[z, x]ùû + éë z,[x, y]ùû = 0 для всех x, y, z Î L . Так, пример алгебры Ли выглядит следующим об- разом: билинейное отображение [-, -] определено как [x, y] = xy - yx для x, y Î A . Дифференцированием в алгебре U называется линейное отображение d :U ® U , удовлетворяющее правилу Лейбница Проанализируем алгоритм, выполняющий предва- рительную обработку выражения p, целью которой является устранение любых членов, сокращаемых после подстановок (1), из вычислений. Возможно сформулировать следующую теорему. Теорема 1. Предположим: 1) p - это сумма l = 2m-1 членов, каждый из кото- рых является однородным относительно степени m; дифференцирования произведения 2) c( p) - это линейный дифференциальный опеd(ab) = d(a)b + ad(b). Пусть R - это коммутативная алгебра с единичратор степени 1; 3) m, N ®¥ таким образом, что 2m << Nm . ным элементом над полем k характеристики О. Тогда ExpenditureBetter ( p) = O æ 1 ö . (6) Пусть D1, ..., DN - это N перестановочных производ- ExpenditureSimple ( p) ç m × 2m ÷ è ø ных R, т. е. для i, j = 1, ..., N , Di Dja = Dj Dia для всех a Î R . Предположим, что мы также получили M произ- водных Dif1, ..., DifM Î R , которые могут быть выра- Напомним, что скобка Ли [ , ]: g × g → g - это билинейная, кососимметрическая операция, удовле- творяющая тождеству Якоби: [[x, y], z] + [[z, x], y] + + [[y, z], x] = 0. Значение теоремы 1 состоит в том, что алгоритм, жены как R линейных комбинаций производных т. е. для j = 1, ..., M , Di , представленный для упрощения вычисления произ- водных, входящих в формулу c( p) , является мето- Dif = å a D , гдеj m N j j m am Î R. m=1 (4) дом, который часто экспоненциально улучшает эффективность вычислений. Конечно, если мы априорно знаем определенные свойства c( p) , то мы можем Для создания эффективного символьного алгорит- ма необходимо записать производные высокого порядка, порожденные Dif1, ..., DifM , с помощью чле- нов перестановочных производных D1, ..., DN . Обозначим свободную ассоциативную алгебру символом Dif1, ..., DifM , и пусть Diff (D1, ..., DN ; R) - это пространство формальных линейных дифферен- циальных операторов с коэффициентами из R, т. е. использовать эти свойства, чтобы вычисления были эффективнее. Тем не менее, наш алгоритм не требует знания свойств c( p) . Сокращения, которые появляются, когда непере- становочные операторы выражены через коммути- рующие операторы, возникают естественно. Это при- водит к алгоритму, применение которого для опера- торов, таких как производные, ускоряет вычисления экспоненциально. Пусть {E1, ..., EM } - множество символов. Будем называть дерево помеченным метками {E1, ..., EM } , если каждому узлу дерева, отличному от корня, соот- Помеченное упорядоченное дерево является поме- ченным деревом, для которого существует линейное упорядочение потомков каждого узла. Обозначим векторное пространство над k с базисом из множества помеченных упорядоченных деревьев через ветствует элемент {E1, ..., EM } , присвоенный ему. k {LOF (E1, ..., EM )} . Определения операций умноже- Обозначим множество всех деревьев, помеченных ния и ко-умножения для k {LOF (E1, ..., EM )} аналометками {E1, ..., EM }, через Forest {E1, ..., EM } . гичны определениям, приведенным выше. Следующая теорема доказана в работе [20]. Пусть k {Forest {E1, ..., EM }} обозначает векторное Теорема 2. Набор помеченных деревьев t , корень пространство над полем k с базисом Forest {E1, ..., EM } . которых имеет ровно одного потомка, является бази- сом для P (k {Forest {E1, ..., EМ }}) . Определим умножение в k {Forest {E1, ..., EM }} Доказательство. Непосредственно получим, что любое дерево, корень которого имеет только одного следующим образом. Поскольку набор помеченных деревьев образует базис для k {Forest {E1, ..., EM }} потомка k, охватывает примитивные элементы. Пусть O = k {Forest {E1, ..., EМ }}, и определим линейное векторного пространства, достаточно описать произ- ведение двух помеченных деревьев. Пусть t1, t2 - два помеченных дерева. Пусть s , s , ..., s - дети корня t . Если t имеет n +1 узлов отображение p : O Ä O ® O следующим образом: если t1 и t2 - помеченные деревья, то p(t1 Ä t2 ) - это помеченное дерево, образованное путем идентифика- ции корней t1 и t2 . Другими словами, p(t1 Ä t2 ) яв- 1 2 r 1 2 (считая корень), существуют (n +1)r способов приляется помеченным деревом, для которого поддеревья корня образуют все поддеревья корней t1 и t2 . Легко соединения r поддеревьев t1 , для которых s1, ..., sr видеть, что если t - помеченное дерево, корень котоиспользуются как корни помеченного дерева t2 . При- соединим каждый si как потомок некоторого узла t2 , рого имеет r потомков, то p o D(t ) = 2r t . С другой стороны, если a = å a t Î P(O) , мы получаем, что сохраняющий исходные метки. Произведение деревь- i 1 2 ев t t определяется как сумма этих (n +1)r помеченp o D(a) = 2a . Так как деревья t являются линейно независимыми, следует, что a = 0 , если корень t имеет ных деревьев. Можно показать, что это произведение ассоциативно и что дерево, состоящее только из кор- ня, является мультипликативным тождеством (эле- ментом, являющимся единичным для мультиплика- тивной операции) (cм. [19; 20] для доказательства). Определим ко-умножение над k {Forest {E , ..., E }} i более одного потомка. Это завершает доказательство теоремы. Далее опишем, как помеченные деревья могут быть использованы для упрощения вычислений диф- ференциальных операторов. Начнем с определения следующим образом. 1 М отображения y : k {Forest {E1, ..., EМ }} ® Diff ( D1, ..., DN ; R) Пусть t - помеченное дерево, и пусть s1, ..., sr дети корня t. Если P - подмножество Ct = {s1, ..., sr} , полагаем, что t p - помеченное дерево, образованное путем создания (размещения) элементов из P как по- томков нового корня. При этом сохраняются исход- ные метки. Определим ко-умножение как операцию D(t) = å t p ÄtCt \ P , где X \ Y обозначает операцию следующим образом. Шаг 1. Задав помеченное дерево t Î LFm ( E1, ..., EM ) , ставим в соответствие корню число 0 и назначаем остальным узлам числа 1, ..., m . Мы в дальнейшем идентифицируем узел с числом, назначенным узлу. Чтобы определить отображение, мы просуммируем индексы m1, ..., mm , связанные с PÍCt теоретико-множественного относительного дополне- ния Y в X. Определим ко-единицу измерения, полагая каждым узлом дерева, кроме корня. Закрепим узел k дерева t, и пусть l, ..., l¢ обозначают детей этого узла. Пусть e(t ) равным 1, если t имеет только один узел (его ìD ...D aml , если k - не корень, корень), и равным 0 в противном случае. Можно показать, R(k;m , ..., m ) = ï ml mr gk что это делает k {Forest(E1, ..., EM )} ко-коммутативной l r í ïîDml ...Dmr , если k - корень. ко-алгеброй. Возможно определить шкалу градации Обозначим эту величину R(k) . Заметим, что на k {Forest(E1, ..., EM )} , полагая k{Forest(E1, ..., EM )} R(k) Î R при k > 0 . N подпространством k {Forest(E1, ..., EM )}, натянутым Шаг 2. Определим на деревья с n +1 узлами и обозначенным через y(t) = å R(m)...R(1)R(0) k {Forestn (E1, ..., EM )}. m1, ...,mm =1 и расширим ψ на все k {Forest {E1, ..., EМ }} в силу его линейности. Следующие три предложения описывают основные свойства отображения ψ. Первое предложение является примером упрощения факторизации χ с по- мощью множества помеченных деревьев. Легко полу- чить, что часто менее затратно вычислять ψ и φ содует рассматривать только деревья, корень которых содержит только один узел - потомка. Предложение 3 а) пусть L ( E1, ..., EM ) обозначает алгебру Ли, по- рожденную производными E1, ..., EM , тогда j(L ( E1, ..., EM )) Í P (k {LF ( E1, ..., EM )}), вместно, чем вычислять χ. Предложение 1 y (P (k {LF ( E1, ..., EM )})) Í Der R; а) отображение ψ является гомоморфизмом алгебры; б) c= y o j. Доказательство. Доказательство (а) получено не- посредственным вычислением по правилу Лейбница и содержится в работе [19]. Так как χ и y o j согласованы (располагаются) на генерируемом множестве E1, ..., EM , то часть (б) предложения 1 следует из часб) элементы L ( E1, ..., EM ) отображаются под дей- ствием φ в суммы деревьев, корень которых имеет только одного потомка. Завершим этот раздел простым примером вычисления производной третьего порядка с использованием деревьев. Фиксируем производные ти (а). Это завершает доказательство предложения. N m На самом деле верно более сильное утверждение: отображение ψ соблюдает взаимодействие ко- умножения на k {Forest {E1, ..., EМ }}-ассоциативной Ej = å a j Dm , 1 £ j £ 3, m=1 и рассмотрим производные высшего порядка алгебре символов над помеченными деревьями и ум- ножение в R в следующем смысле. Предложение 2 p = E3E2 E1 - E3E1E2 - E2 E1E3 + E1E2 E3. Вычисление c( p) «в лоб» включает в себя вычис- Для всех a, b Î R и для всех t Î k {LF (E1, ..., EM )} ление 24N 3 членов: 8N 3 - члены-сомножители Dm1 , ((yÄ y) o D(t))(a Ä b) = y(t) (ab). 2N 3 из них сокращаются, 12N 3 членов, содержащих Для многих приложений важно знать, ограничимножители D , все из них сокращаются, и m m 2 1 4N 3 ваются ли действия этих гомоморфизмов областью алгебры Ли, порожденной производными E1, ..., EM . Следующее ниже утверждение показывает, что если известны вычисленные элементы алгебры Ли, то слечленов, включающих множители сокращаются. Вычисляя j( p) , получим Dm3m2m1 , все из них - - + - + 3 E1 E2 E3 E E3 E2 E3 E1 E2 E1 E1 E2 E3 E3 E2 E1 Все сокращения членов при вычислениях Используя теорему 3, можно построить еще более c( p) = y(j( p)) происходят при вычислении j( p) . Сделаем следующие предположения: p Î k E1, ..., Em эффективные алгоритмы для вычисления результата воздействия элементов k E1, ..., EM , которые, как (элемент ассоциативной алгебры символов) есть сумl известно, являются дифференциальными оператора- ми. В этом случае деревья, для которых корень имеет ма p = å pi , i=1 где каждый член pi имеет степень m; более одного потомка, даже не нужно строить. Приложения затраты на умножение составляют одну единицу; за- траты на дифференцирование - одна единица; затраты на сложение равны нулю; затраты добавления узла к дереву - одна единица, так что стоимость построе- ния дерева t Î LFm ( E1, ..., Em ) равна m единиц. Предложение 1 1. Рассмотрим движение управляемого объекта на плоскости, описываемого следующей системой диф- ференциальных уравнений: dy1 = V cos j, dt dy2 = V sin j, Вычислительные затраты на вычисление c( p ) равны величине 2lmm!Nm. dt d j = k u, u £ 1, (7) Доказательство. Предположим, что pi имеет вид E ... E для некоторых индексов 1 £ g , ..., g £ M . dt V V = const, k = const > 0. gm g1 Тогда c( p ) равно 1 m Значения угла φ рассматриваются на интервале (-p, p). Здесь y1, y2 - координаты объекта, отожде- çç å a Dm ÷÷...çç å a Dm ÷÷. æ N ö æ N ö ствляемого с точкой на плоскости; φ - угол между mm gm m =1 m1 m g1 1 m =1 вектором скорости объекта и осью x; u - управляю- щий параметр, удовлетворяющий указанному ограни- è m ø è 1 ø После разложения появляются m!Nm членов, каждый из которых включает в себя m дифференци- рований и m умножений (включая умножения и диф- ференцирования, связанные с применением оператора c( p)) . Предложение 2 Затраты на вычисление j( p ) равны lmm! . чению и характеризующий скорость изменения угла φ; k - максимальное боковое ускорение; V - величина скорости; a = k . V Неравенство в (7) ограничивает радиус кривизны траектории объекта, а именно, радиус кривизны не может больше единицы. Рассматриваемая система использовалась Р. Айзексом при постановке задачи Доказательство. Моному степени m отображение φ «шофер-убийца» (рис. 1). Состояние z0 = ( y1(t0 ), ставит в соответствие сумму (объединение) m! поме- ченных деревьев. Этот факт легко доказать по индук- ции (доказательство в [19]). По предположениям, представленным выше, затраты на построение поме- ченного дерева с m узлами (в дополнение к корню) составляют m единиц. Поэтому общие затраты равны lmm! . Предложение 3 Пусть s= j( p) обозначим через s число помеy2 (t0 ), j(t0 )) объекта в начальный момент времени предполагается заданным. Множество достижимости G(T ) в момент време- ни T ³ 0 есть совокупность всех точек фазового про- странства, в каждую из которых возможен перевод системы (7) в момент времени T ³ 0 при помощи некоторого допустимого управления на промежутке T = [0, t*] из начальной точки z0. ченных деревьев с ненулевыми коэффициентами σ. Тогда затраты на вычисление y (s) равны 2m s Nm . 2. Рассмотрим систему обыкновенных дифферен- циальных уравнений, в правую часть которой входит управляющее воздействие: Доказательство. Фиксируем помеченное дерево t Î LFm ( E1, ..., EM ) . Из определения отображения ψ dy1 = 2 y dt 2 + y4 , мы видим, что затраты на вычисление y(t) равны dy2 = -2 y + y + u(t), 2mN m , и, следовательно, полные затраты равны 2m s Nm. Объединяя эти три утверждения, получим теорему. Теорема 3. В соответствии с принятыми выше dt dy3 = y dt dy4 = 2 y 1 3 2 +10 y4 , - 2 y + u (t). (8) предположениями затраты Cost Simple ( p) вычисления dt 1 3 2 l c( p) = åc( pi ) составляют 2lmm!Nm , тогда как Система (8) - это гамильтонова система, имеющая гамильтониан i=1 H = y2 + y y + 5 y + y2 - y y + y2 - u (t) y - u (t) y . 1 2 4 4 1 1 3 3 1 1 2 3 CostBETTER ( p) lmm!+ 2m s Nm . вычисления L =y o j( p ) равны В этой формуле y1, y2 - обобщенные координаты, y2 , y4 - обобщенные импульсы. На возмущающие силы системы жены ограничения { u1 £ 1, u2 £ 1}. u1(t), u2 (t) налопредложить гарантированные оценки множеств дос- тижимости, качественно совпадающие с результатами [1], показывающими отсутствие экспоненциального роста границ эллипсоидов. В [1] графики построены В [1] для этой системы были выбраны начальные данные в виде параллелепипедов размерности 4. Динамические оценки множеств достижимости были построены в виде эллипсоидов [1]. Поэтому полезно в логарифмической шкале с несколькими числовыми метками. Других числовых данных для этой системы в [1] не приводится (рис. 2, 3). Рис. 1. Гарантированные границы множества достижимости задачи (7) - проекция на оси t-y1-y2 задачи «шофер-убийца» Fig. 1. Guaranteed set boundaries of tasks (7) - projection on an axis t-y1-y2 “driver-killer” tasks Рис. 2. Гарантированные границы множества достижимости задачи (8) - проекция на оси t-y1: 1 - верхняя граница проекции множества достижимости; 2 - нижняя граница проекции множеств достижимости Fig. 2. Guaranteed set boundaries of tasks (8) - projection on an axis t-y1: 1 - upper limit of set projection of reachability; 2 - lower limit of set projection of reachability Рис. 3. Гарантированные границы множества достижимости задачи (8) - проекция на оси t-y2: 1 - верхняя граница проекции множества достижимости; 2 - нижняя граница проекции множеств достижимости Fig. 3. Guaranteed set boundaries of tasks (8) - projection on an axis t-y2: 1 - upper limit of set projection of reachability; 2 - lower limit of set projection of reachability Заключение. В статье описаны символьные алго- ритмы, улучшающие применение гарантированных методов оценки решений дифференциальных уравне- ний для вычисления включений множеств достижи- мости управляемых систем. В статье применяется операция умножения на укоренившихся помеченных деревьях, что создает набор этих структур данных как ассоциативную алгебру. Затем определяется алгебра гомоморфизма из исходной алгебры операторов в данную алгебре деревьев. Сокращения, которые появляются, когда неперестановочные операторы вы- ражены через коммутирующие операторы, возникают естественно, когда операторы представлены с исполь- зованием этой структуры данных. Это приводит к алгоритму, применение которого для операторов, таких как производные, ускоряет вычисления опера- тора, что повышает эффективность применения гарантированных методов.

About the authors

A. A. Rogalev

Siberian Federal University, Institute of Space and Information Technologies

Email: a.rogalyov@yahoo.com
26, Academica Kirenskogo Str., Krasnoyarsk, 660074, Russian Federation

References

Supplementary files