Алгоритм построения оптимальной стратегии в нелинейной дифференциальной игре c нефиксированным временем окончания

Основы теории дифференциальных игр с нулевой суммой заложены в работах Р. Айзекса. [1], Л.С. Понтрягина. [2], Н.Н. Красовского [3] и др. В настоящее время разработаны различные алгоритмы, вычисляющие цену игры и оптимальные стратегии управления [4] - [6]. Для линейных дифференциальных игр с выпуклым целевым множеством современные методы используют алгоритмы вычисления игровых множеств достижимости через опорные функции этих множеств. Если дифференциальная игра нелинейна, то игровые множества, достижимости становятся невыпуклыми и аппарат опорных функций неприменим.

В настоящей работе предлагается алгоритм построения квазиоптимальной (или е- оптимальной) стратегии управления для нелинейной дифференциальной игры на нефиксированном отрезке времени с целевым множеством. Алгоритм использует конструкцию игровых множеств достижимости, похожую на. конструкцию, используемую в [7]. В двумерном случае эти множества, могут быть построены с помощью алгоритма, близкого к алгоритму построения суммы Минковского двух многоугольников с использованием конволюты [9] - [10]. Настоящая работа, продолжает работу [8], в которой этот подход применяется для построения е-оптимальной стратегии управления для игры на фиксированном интервале времени.

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

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

Рассмотрим динамическую систему, описываемую дифференциальным уравнением

x(t) = a(x(t), u(t)) + b(x(t), v(t)),                                    (1)

где t E [0, P] - время, число P определяет максимальную продолжительность игры, x(t) E R” - фазовый вектор системы, управление первого игрока u(t) и второго игрока v(t) подчинены ограничениям

u(t) E Р, x(t) E Q.                                        (2)

Предполагается, что заданы компактные множества Р С R^p, Q С R^p и непрерывные функции a : Rⁿ хР ^ Rⁿ и b : Rⁿ xQ ^ Rⁿ. Кроме того, вектограммы a(x, Р ) = {a(x, и) : и E Р },

b(ж,Q) = {Ь(ж, v) : v G Q} выпуклы при всех ж G R”. Пусть также задано компактное множество М С R”, которое будем называть целевым или терминальным.

Пусть задан отрезок [tg, ti] С [0, Р] и пусть для какой-то начальной позиции ж(ф) = жо G R” и каких-то измеримых управлений n : [ф,Ц] ^ Р, v : [ф,Ц] ^ Q абсолютно непрерывная функция ж : [ф,Ц] ^ R” почти всюду на отрезке [tg, ti] удовлетворяет уравнению (1). Если существует момент времени t G [to, ti] такой, что ж(t) G М, то будем говорить, что на отрезке [Д,Ц] имеет место поимка. Иначе, то есть если ж(t) G М при всех t G [to,ti], то будем говорить, что на отрезке [Д,Ц] имеет место уклонение. Цель первого игрока состоит в минимизации числа Ро G [0, Р] такого, что на отрезке [0, Ро] обеспечена поимка. Цель второго игрока — обеспечить уклонение на отрезке [0, Р] или, если это невозможно, максимизировать время Ро G [0,Р] такое, что на отрезке [0, Ро] обеспечено уклонение.

Расстоянием от точки ж G R” до множества Y С R” называется величина

р(ж,У) = inf ||ж - у^ .                                      (3)

y e v

Будем говорить, что на отрезке [tg, ti] С [0, Р] имеет место е-поимка, если существует такой момент времени t G [tg, ti], что р(ж(Ц,М) < е.

Будем предполагать, что функции а : R” х Р ^ R” и b : R” х Q ^ R” удовлетворяют следующим условиям Липшица:

||а(жі, ni) - а(ж2, П2)| 6 ^£||жі -Ж2І + L“|ni - «2||

(4) ;

;                  (5)

V ж1, ж₂ G R”, n1, n₂ G Р

||b(Ж1,V1) - Ь(ж2, V2)| 6 L^|ж1 - Ж2І + L^ |vi - V2|

V ж1,ж2 G R”, v1,v2 G Q

||а(ж,п)|| 6 С_а V ж G R”, n GP; |b(ж,v)| 6 С_ъ V ж G R”, v G Q.

Обозначим

С = С_а + Съ, L = L^ + L£.

2.    Стратегии и законы управления

Пусть задан отрезок [Д,Ц] С [0, Р]. Множеством Ы[ф,Ц] допустимых реализаций управления первого игрока называется множество всех измеримых функций n : [tо,t1] ^ Р. Множеством У[tо,t1] допустимых реализаций управления второго игрока называется множество всех измеримых функций v : [tо,t1] ^ Q.

Позиционной стратегией первого игрока называется произвольная функция nstr   : R”   ^ Р. Пусть   Т =   {тЦ^о - разбиение отрезка

[t0,t1] С [0,Р] : t0 = то < т1 < ••• < ti = t1. Пгipa. (nstr,T). составленная из позици онной стратегии первого игрока nstr и разбиения Т отрезка [tо,t1], называется законом управления первого игрока на отрезке [Д,Ц]. Движением, соответствующим начальному состоянию ж(tо) = жо, закону у правления (nstr,T) и допустимой реализации управления v G У[tо,t1]. будем называть абсолютію непрерывную функцию ж : [tо, ti] ^ R”. определяемую из пошагового уравнения cr(t) = а(ж(t), nstr (ж(ті))) + b(ж(t), v(t)),                                (9)

которое должно выполняться при почти всех t G [тдТі+і] и всех г G 0,1 - 1. При этом начальная позиция для отрезка [то,ті] равна жо, а начальная позиция ж(т,) для отрезка [тг,Тг+1] совпадает с копенной позицией ж(т,) отрезка [ т і - і ,т і ].

В силу принятых предположений при заданных начальной позиции ж(to) = жо, разбиении Т, позиционной стратегии первого игрока ustr и допустимой реализации управления v € У [to, ti] движение ж(-) существует и единственно. Обозначим его следующим образом:

$m^ot(t, t₀, ж_о, Т, ustr, v) = x(t) V t € [t₀,t_i]. (10)

Аналогично определяются позиционная стратегия второго игрока vstr и движение жm^ot(t, t₀, ж_о, Т, u, vstr), соответствующее начальной позиции x(t0) = ж_о, разбиению Т, допустимой реализации управления первого игрока u € U [to, ti] и стратегии второго игрока vstr.

Будем говорить, что закон управления (ustr, Т ) гарантирует Е-поимку на отрезке [to, ti] для начального состояния жо, если для любой реализации управления v € У[to,t_i] существует момент времени t € [Д,П] такой, что выполняется

6 ^m^ot(t, t₀, ж_о, Т, u^stT,v),M ) <  е. (11)

Закон управления (vstr^) гарантирует уклонение на отрезке [to,ti] для начального состояния жо- если для любой реализации управления u € U[to,ti] выполняется жmot(t, t0,ж0,Т,u, vstr) € M V t E [t0,ti]. (12)

Пусть задано число е >  0 и законы управления (ustr,^), (v^str ,Т„ ) первого и второго игроков на отрезке [0,У]. Пара законов ((ustr,^), (vstr,^,)) называется Е-оптимальной, если для любого начального положения жо € R” такого, что у(жо,М ) >  е, выполняется альтернатива:

• 1)    существует момент времени Уо € [0, У] такой, что закон управления (u^str, Т_и) гарантирует Е-поимку на отрезке [0,Уо], а закон управления (vstr,!,) гарантирует уклонение на отрезке [0, Уо]. либо

• 2)    закон управления (vstr,!,) гарантирует уклонение на отрезке [0,У]

3.    Алгоритм вычисления стратегии управления

Зафиксируем натуральное число I и рассмотрим равномерное разбиение Т = {тД{=о отрезка [0,У], где т і = гт, г € 0,1. Шаг т = У/I разбиения Т будем также называть параметром дискретизации по времени.

Для любого множества S С R” определим множества

AS = {ж € Rⁿ : 3 u € Р : ж + та(ж, u) € S},                   (13)

BS = {ж € Rⁿ : V v € Q : ж + тЬ(ж, v) € S }.                   (14)

Таким образом, определены операторы A и B, которые будем называть одношаговыми операторами достиэюимости.

Суммой и разностью Минковского множеств X С R” и У С R” называются соответственно множества

X + У = {ж + у :ж € X, у €У},    X -У = {ж € Rⁿ :ж + У СХ}.      (15)

Для любого числа R > 0 через Вд обозначим замкнутый шар с центром в нуле и радиусом R; Вд = {ж € Rⁿ : 11*11 6R}

Пусть X - класс аппроксимируюш,их міюжсств. то ость подмножеств R”. с которыми работают алгоритмы и которые с достаточной точностью аппроксимируют игровые множества достижимости (о них речь пойдет ниже). Примером класса X может служить класс многоугольников в R².

Предположим, что построены алгоритмы, которые для каждого множества S € X с некоторыми погрешностями вычисляют множества AS, BS. Учитывая эти погрешности, будем предполагать, что реально для каждого множества S Е У вычисляются множества AS, BS класса У, удовлетворяющие условиям

A(S - B_£A ) с AS с A(S + B_£A ),                       (16)

B(S - B_£B ) с BS с B(S + B_£B ),                       (17)

где числа Е д, Е в определяют погрешности этих алгоритмов. В случае, если класс У состоит из многоугольников в R² с длиной сторон, не превосходящей Һ, в качестве алгоритмов вычисления множеств AS, BS для S Е У могут быть использованы алгоритмы, построенные в [8]. При этом оценки их погрешностей Ед = 4Һ + L^: ^ C_aт 2, Е в = 4Һ + ^С ь т ² останутся справедливыми для рассматриваемой здесь задачи.

Предположим, что построен алгоритм, который для любых множества S С У и вектора ж Е AS позволяет определить вектор й = й(ж, S) Е Р такой, что ж + та(ж,й) Е S + В£и.                               (18)

Также предположим, что построен алгоритм, который для любых множества S С У и вектора ж Е Rn \ (BS) позволяет определить вектор г = г(ж, S) Е Q такой, что ж + тЬ(ж,и) Е (Rn \ S) + B£i.                             (19)

Здесь числа Е_и и е _о определяют погрешности соответствующих алгоритмов. Для класса У, состоящего из многоугольников в R² с длиной сторон, не превосходящей Һ, такие алгоритмы также построены в [8].

Зафиксируем некоторые векторы й* Е Р, г* Е Q и положим й(ж, S) = й* при ж Е AS, v(ж,S) = г* при ж Е BS . Тем самым определены функции й : Rn х У ^ Р,    г : Rn х У ^ Q.(20)

Обозначим

ДО = т2 (LC + U^Ca),   ,\ = т2 ^ PL^ ,(21)

Ди = Ди + ЕВ + (l+тLь)Еи,    До = ДО + ЕД + (1 + тLa)Еo.(22)

Пусть имеются алгоритмы, которые для любого множества S Е У вычисляют множества D_US Е У. D_VS Е У такие, что

S - B Д . С DuS С S - Вдц,    S + BД„ С DoS С S + BД„ +£в,(23)

где число Е в определяет погрешность этих алгоритмов. Будем также предполагать монотонность по включению операторов D_U и D_o, то есть

DuSi С DuS2,     DoSi С DoS2    V Si, S2 Е У : Si С S2.(24)

Зафиксируем положительное число е.

Определим множества М0 Е У, М0 Е У так, что

М + B£-£M СМ0^ СМ + B£,(25)

М + ВтС С М^ СМ + BtC+£m .(26)

Здесь число Е м Е (0, е) определяет погрешность начальной аппроксимации.

Двигаясь в сторону увеличения индекса г и используя описанные выше алгоритмы, вычислим наборы игровых мноэюеств достиэюимости {М_г^и}1=0, {М^ }{=0:

МД1 = (АІЗDиМ^U) иМи,    г Е 0,1 - 1,(27)

МД1 = (BADoМ?) U МО,    г Е 0,1 - 1.(28)

Отметим, что из этих определений следуют включения

М" С М^,    М^ С МД1   V г G 0,7 - 1.(29)

Используя функции (20) и игровые множества достижимости, определим позиционные стратегии управления. Для любого вектора ж G R” \ MQ" положим

г(ж) = тах{г G 0,I — 1 : ж G М"},(30)

а для любого ж G Rn \ М' обозначим

j(ж) = max{j G 0,I — 1 : ж G М^+1}.(31)

Теперь для любого ж G R” определим

и81г(ж)	( и*, = 1 .. , B D"M"(,)) ,	ж ж	G G	Мд", Rn \ М",	(32)
г81г(ж)	Г о*, = Ф(ж, .4», М;Д .	ж ж	G G	М' , Rn \М'.	(33)

Определим числа

Ад = Аи + А- + 2(ед + eg + Ed ),(34)

eq = т(С + Съ) + 2ем + Аи + ed + (тСъ + Ао(1 — 1))e(S т)L •(35)

Теорема 3.1. Пусть г G 0Д, жд G М'", стратегия n^str определена соотношением (32). Тогда закон управления (n^str,T) гарантирует е-поимку на отрезке [0, т_:] для начального состояния ж(0) = жд.

Теорема 3.2. Пусть г G 0,1 — 1, жд G М' стратегия v^str определена соотношением (33). Тогда закон управления (v^str,T) гарантирует уклонение на отрезке [0,т,₊₁] для начального состояния ж(0) = жд.

Теорема 3.3. Пусть е >  Ед, число т выбрано так, что тЕ^ < ^. Тогда

М? СМ V г € 0,1 — 1.                          (36)

Теорема 3.4. Пусть стратегии и⁸Д v^str определены соотношениями (32), (33). Пусть число е > тС + 2 е м выбрано так, что выполняется условие (36). Тогда пара законов управления ((и⁸ДТ_и), (v^str, Т")) является е-оптимальной.

• 4.    Доказательство теорем 3.1-3.4

Лемма 4.1. Для любых мномсества S С R” и числа 5 > 0 операторы (13), (14) удовлетворяют соотношениям

AS + Bs С A(S + B(i+tL5)5),(37)

BS + B5 CB(S + B(i+tL^)5).(38)

Доказательство. Пусть ж G AS + B§. Тогда сущеетвует вектор у G AS такой, что \\у — ж\ 6 5. В силу равенства. (13) существует вектор и G Р такой, что у + та(у,и)G

Отсюда в силу соотношения (4) получаем включение ж + та(ж,и) G S + B (₁+ _tl ^ ) з-

Следовательно, ж G A(S + B(i+t^^)^), что доказывает включение (37). Включение (38) доказывается аналогично.□

Лемма 4.2. Пусти tL ^ <  1. Тогда для любих мноэюества S С Rⁿ и числа 5 >  0 оператор (14) удовлетворяет включению

BS - В ^/д - т^) С B(S - В₅ ).

Доказательство. Пусть х Е BS — B ₅/ (_{1 - tL} ^ ). Тогда для любых v Е Q, z Е B ₅/ (_{1 - tL} ^ ) имеем х + z + тЬ(х + z,v) Е S. Зафиксируем произвольные v ЕQ,у Е B§. Рассмотрим отображение F (z) = тЬ(х, v)+y — Tb(x+z, v). Так как tL ^ <  1, то это отображение является сжимающим. Следовательно, существует его неподвижная точка zo = тb(x,v) + у — тЬ(х + zo,v). При этом ||zo| = ||тb(x,v) + у — тЬ(х + zo,v)| <  5 + tL ^ ||zo|, откуда получаем, что z_o Е Вб/(_1-ть^ )• Таким образом, получаем, что х + тЬ(х, v) + у = х + z_o + тЬ(х + z_o, v) Е S. Отсюда, в силу произвольности выбора v Е Q и у Е Bs, следует, что х Е B(S — В д).    □

Для любых t_o Е [0, Р],Н Е [to, ^], хо Е Rⁿ,u Е Ы [to, t1], v Е У [to, t1] обозначим

x(t, t0,x0,u,v) = x(t) V t Е [to,t1], где х : [to, ti] ^ Rn - решение задачи Коши:

х(і) = a(x(t), u(t)) + b(x(t), v(t)), с начальным условием x(to) = xo•

Проводя рассуждения, близкие к доказательству леммы 5.1 из [7], получаем следующую лемму.

Лемма 4.3. Пусти задачи числа т Е (0, ^), to Е [0,Р — т], вектор xo Е Rn и функции и Е Ы [to, to + т ], v Е У [to, to + т ]. Пусти to+т хи = xo +      a(xo, u(t))dt,(39)

to хі = x(to + т,to,xo,u,v).(40)

Тогда существует вектор vo Е Q такой, что вектор xuv = хи + тЬ(хи, vo)(41)

удовлетворяет неравенству Іхиу — хі| < AU,(42)

где число AU определено равенством (21).

Аналогичная лемма верна для векторов х^,х_уи, определенных аналогично.

Лемма 4.4. Пусти xo Е M'U+1 \ М'и, стратегия u^str определяется соотношением (32), г Е 0,1 - 1. v ЕУ [0, т ]. хі =хи^то1(т, 0, xo, Т, u^str,v). Тогда хі Е М^и.

Доказательство. Определим функцию u Е Ы [0, т] формулой

u(t) = u^str(x₀) V t Е [0, т].                                    (43)

Тогда справедливо равенство (40), где to = 0. Из включения xo Е МгД1 \ М“ и равенства (27) получаем xo Е ABduM'u. В силу равенства. (30) 11 включений (29) имеем г(xo) = г. Отсюда и из соотношений (18), (32) следует включение x0+тa(x0, ustr(x0)) Е BduM'u+ВЕи. Поэтому согласно равенству (43) получаем, что вектор хи, определяемый формулой (39), удовлетворяет включению хи ЕBDиМ'и + В£и. (44)

В силу леммы 4.3 существует вектор во Е Q такой, что для вектора х_и- — х_и + тЬ(х_и,во) справедливо неравенство (42). Согласно включениям (17) и (38) имеем BD_UM^ + В С B(DuM“ + В_£в ) + В С B(DuM" + В_£в + В^ (і+ tL ^ Y Отсюда, из определения (14) оператора B и (41), (44) получаем

^U- — ^хи + тЬ(хи, во) Е DuMf + B£B + B£ _u (1+ tL ^ ).

Далее, учитывая (42), (22), (23), получаем хі Е DuM™ + В£в + В .- + В до С MU - В£в+£„(i+tL^)+ao + В£в+£Ц(і+^)+до С Md

□

Проводя рассуждения, аналогичные доказателвству леммы 4.4, получаем следующую лемму.

Лемма 4.5. Пусть хо Е M ™+2 \ M ™+_і, j Е 0, I — 2 в ли j — I — 1, хо Е Rⁿ \ M— Пусть стратегия в^str определяется соотпошсписм (33). и Е U [0,т]. хі — xm^ot(т, 0, хо, Т, и, в^str). Тогда х_і Е M^-

Лемма 4.6. Пусть х_о Е M^ \ M“, стратегия u^str определяется соотношением (32), г Е 0,I — 1, в Е У[0,Tj+1]. Тогда сущеетвует индекс j Е 0, г + 1 такой, что xU^not (т, , 0, хо, Т, u^str , в) ЕМ™.

Доказательство. Будем доказывать утверждение по индукции. При г — 0 утверждение верно по лемме 4.4. Зафиксируем т Е 0, I — 1. По предположению индукции утверждение верно для всех г Е 0,т — 1. Нужно доказать, что о но будет верным и для г — т. Пусть хо Е Mf +1 \ Mf, в Е У [0,т_т+1]. Требуется доказать, что

3 j Е 0, т + 1 : хт^т,, 0, х_о,Т, ustr, в) Е Md.                     (45)

хт^т/г+ь 0, хо, Т, ustr, в) Е Md, и соотношение (45) выполнено при j — к + 1.                                         □

Лемма 4.7. Пусть г Е 0, I — 1, хо / Md+і- Пусть стратегия в^str определяется соотношением (33). Тогда для любой функции и Е U [0, т] выполнено соотношение x^mot(т, O,xo,Т,u,в^str) Е M^-

Доказательство. Из условия хо / M^+і и включений (29) следует, что либо существует такой номер j Е г, I — 2, что хо Е M6+2 \ M6+U либо хо / MJ (в этом случае положим j — I — 1). Тогда по лемме 4.5 получаем, что xmot(т, 0, хо, Т, и, в^г) Е M™ V и Е U[0, т].

Это в совокупности с (29) дает доказываемое утверждение.                          □

Лемма 4.8. Для любого S С Rⁿ выполнены включения

S С В(S + ВтСь),(46)

BS С S + ВтСь.(47)

Доказательство. Докажем включение (46). Пусть у Е S . Из соотношения (7) следует, что для любого и Е Q справедливо включение у + тЬ(у, и) Е S + В_т с _ь- Отсюда по определению (14) оператора В следует, что у Е В (S + В_тс_ь )•

Докажем включение (47). Пусть у Е BS . По определению (14) оператора В это означает, что для любого и Е Q выполнено включение у + тЬ(у,и) Е S . Отсюда и из соотношения (7) получаем у Е S + Втсь-□

Проводя рассуждения, близкие к доказательству леммы 5.9 из [7], получаем следующую лемму.

Лемма 4.9. Для любого S С Rⁿ выполнено включение

BD_US - В тс ь С S.

Для любого индекса г Е 0,7 — 1 определим число г = (тСь + (1 — г — 1)Ао)е(/-і-1)т£.                          (48)

Лемма 4.10. Пусть выполнены неравенства тВ^ <  |, е >  Ео, г де Ео определено равенством (35). Тогда для любого j Е 0,1 — 1 выполнено включение

М " + В_г. СBD_UМ^-^.                             (49)

Доказательство. Будем доказывать утверждение по индукции. Из включений (25),    (26) получаем следующую цепочку включений:

М0 + В е - тС -2 е м СМ + В тС _+ем + В е - тС -2 е м = М + В_е—_ем С М0¹. Отсюда, используя соотношения (23), получим включения

М0 + В е - тС -2 е м -Д.-ео С (М0 + В е - тС -2 е м) - В Ди■   С М^ — В д ,^ С D М .

Используя (46) для S = М0 + В_е-т С _-2ем-Д_и-ео- тС _ь, получаем включение

М^ + В е - тС -2 е мД- тС ь С В(М0 + В е - тС -2 е мД ) С BD_uМ'0.     (50)

Из равенств (35) и (48) следует, что г₀ + т(С + С_ь) + 2 е м + А_и + е п = е₀ 6 е. Отсюда и из включения (50) получаем, что доказываемое включение (49) справедливо при j = 0.

Пусть теперь включение (49) справедливо при j = г Е 0,1 — 2, то есть

М ^ + В_тч СBD_UМ Д                        (51)

Требуется доказать, что включение (49) выполняется и при j = г + 1. Используя (51), с учетом леммы 4.2 и включения (17) получаем

М ^ + В_тч- е _в Кі - тЬ^^ С BD_uМr — В е _{в К}1 - т^ ^ С В^_иМ? — В е _в ) С ВD_UМ Д

Отсюда с учетом (23) имеем

ПиМ, + ВГі-Д„-ео-ев/(1-тЬ^) С Мг + Вг^-ев/(І-тК^ С ВИиМі , то есть DuМі + ВРі С ВПиМД где

Р г = ^гг ^{— А}и ^{— е} в ^{— е} в ^{/(1 — тВ} ь ).

Учитывая включение (16), получаем

A(D u М' “ + B . -_ЕА ) с A(BD_UM' ^ — B e a ) с АВЕ_иМД            (53)

Из включений (16) и (37) следует, что т

^AD u М ^ + ^В(р^-2еА)/(1+т£^) ^{с A(D} u ^М г ⁺ B e a ^{) + В} ( р ; - 2 е а) / (1+ tL 5) ^{с A(D} u ^М г ⁺ Bp^-EA)•

Из включений (53), (27) получаем AD_uМ г + B(_Pi-2eA)/(_1+TL^) с ABD y M i ¹ с М^+р Введя обозначение

•г = 'іе TLa — Аг — Ed — 2ед — ев/(1 — тіңД(54)

из равенства (52) получаем неравенство 'г <  (р г — 2е д )/(1 + тЕ ^ ). Следовательно, AD_uМ г + В_£і с М^р Используя соотношения (23), из последнего включения получаем

ADuмг + B д с М^ — -Вд . с Dn М^.(55)

Введем обозначение

• г = ^(т г ^{— А}и ^{— E} d ^{— е} в ^{)/(1 + тЬ} ь )•(об)

Используя соотношения (17), (38) и (55), получаем включения

BADyМ + В = с В(ADгMi + Вев) + B   д-вв)/(i+tL^ с BD^^.(57)

Так как • _г <  гд то из включений (24), (29), (51) получаем

М? + Вт. с МІ + BTl с BD^ с BD^^.(58)

Из соотношений (27), (57) и (58) имеем

М+ + B^ = ((BAD u М ? ) U М” ) + B =. = (BAD u М ” + B =) U (М ^ + B =) с BD^. (59)

Из (48) следует неравенство •+ < r_iе^-тL — Ад. В силу равенств (34), (54), (56) и неравенства. тЬ ^ <  2 справедливо неравенство r_iе^-тL — Ад <  т_г. Позтому •+ <  т_г. Отсюда и из соотношений (59) получаем, что включение (49) выполнено для j = г + 1.              □

Доказательство теоремы 3.1. Если жд € Мд1, то утверждение теоремы следует из соотношений (25). Если жд / М^, то в силу включения жд € М“ получаем неравенство г > 0 п существование такого номера m € 0, г — 1. что жд € М^+i \ М^. Пусть задана, функция в € У[0,тт+1]. Тогда по лемме 4.6 (где положим г = т) существует такой номер j € 0, m + 1. что ж^Хт, 0,жд,Т,и8Ь:,в) € Мд.                            (60)

Это означает, что гарантируется е-поимка на отрезке [0,Tm+i] с [0,тг].                   □

Доказательство теоремы 3.2. Зафиксируем произвольную функцию u € U [0,т_г+1]. Обозначим ж(і) = xi^iot(t, 0, жд, Т, u, v^str), t € [0, тг+i]. Применяя лемму 4.7, по индукции получаем, что ж(т ^ ) € Мі^, _- ^ п ри j € 0, г. Отсюда и из включений (29) следует, что ж(т ^ ) € Мд для любого j € 0,г. Предположим, что утверждение теоремы неверно. Тогда существует такой момент времени t € [0,тг+1], что ж(t) € М. Выберем индекс j € 0,г из условия |t — т ^ | <  т. Тогда в силу (1). (6). (7) справедливо неравенство ||ж(т^) — ж(t) ^ <  тС. Отетода и из включений (26) следует, что ж(т₎-) ЕМ + В_т с с М^ ^. Противоречие.               □

Доказательство теоремы 3.3. Пусть выполнено неравенство е > Ед. Зафиксируем произвольное г € 0,1 — 1. По лемме 4.10 выполнено включение М г + В_тч с BD_uM i ^l. Из равенств (48) следует неравенство г_г >  тСь- Поэтому М ^ + В_т с _ь с BD_uM i ¹. Отсюда получаем, что М г с BD_uMг■ — В_т с _ь, и ^с учетом леммы 4.9 справедливо включение М г с М“. □

Доказательство теоремы 3.4. Пусть задан вектор жо G R” такой, что р(жо,М) >  е. Тогда в силу (25) имеем жо / Мд. Если жо G МДр то существует номер г G 0, I — 2 такой, что жо G МД1 \ М“. Так как жо G МДг, то по теореме 3.1 закон управления (ustr, Т) гарантирует е-поимку на отрезке [0, т+г] для начально го состояния ж(0) = жо. Так как жо G Ми и, согласно соотношению (36), М^ С МД то жо G МУ и по теореме 3.2 закон управления (vstr,T) гарантирует уклонение на отрезке [0, т+1] для начального состояния ж(0) = жо. Таким образом, выполняется первы!І пункт альтернативы в определении е-оптимальной пары стратегий.

Пусть теперь жо G МДр Тогда согласно (36) имеем жо G МДр Отсюда по теореме 3.2 закон управления (vstr, Т ) гарантирует уклонение на отрезке [0, Р] для начального состояния ж(0) = жо, то есть реализуется второй пункт альтерпатпвы. □

5.    Примеры классов аппроксимирующих множеств

Покажем, что теоремы 3.1-3.4 могут быть использованы для получения оценок погрешностей алгоритма, изложенного в работе [7]. Поскольку при доказательстве теорем 3.1-3.4 не использовался конкретный вид нормы, то, в частности, так же как и в работе [7], в качестве нормы в R” можно раосмотреть max-нор му: ||ж|| = max_jGi^ |ж«|. При этом шаром Вд будет куб с центром в ііуле и с ребрами длиной 2R. Пусть C - кубическая сетка в R” с шагом Һ. Каждому сеточному множеству S С C сопоставим телесное множество 8 (S ) С Rⁿ, равное объединению кубов в R” с ребрам и длины Һ и центрами в точках множества S. Будем рассматривать класс аппроксимирующих множеств Д = {8 (S) : S - ограниченное подмножество C}. Используя обозначения [7], введем для любого S G Д множества

AS = 8(F_U(S П C)),    ВS = 8 (F(S П C)).

Легко получить (в обозначениях [7]), что ед = тК_и5 + (1 + тЬ_и)Һ/2, е в = тК'5 + (1 + тҒ у )Һ/2. Для погрешностей расчета управлений выполняются оценки е_и = (1 + тҒ_и)Һ/2,е_у = (1 + tL _v )Һ/2. При е в = 3Һ/2 выпо.тпепятотея включения (23) для операторов

D u S = 8 (S П C — B^C, ),    D_vS = 8 (S П C + В^ _+ев ).

Для е м = Һ выполняются включения (25), (26) для множеств МДМ' определенных следующим образом:

Мо и = 8 ((М + B_e-_h/2) П C),    М = 8 ((М + В_тС+ һ/ 2) П C).

Подставляя эти оценки в формулу (35), получим, что при стремлении т, Һ, 5 к нулю погрешность ео по порядку величины совпадает с результатом работы [7]. Из полученной оценки, так же как и в [7], следует, что для получения достаточно малой погрешности необходимо выбирать достаточно малыми параметры Һ, т, 5, причем так, чтобы отношение Һ/т было достаточно малым.

Для класса аппроксимирующих множеств Д состоящего из многоугольников в R² с длиной сторон, не превосходящей Һ, при реализации операторов А, В можно исплользо-вать алгоритмы, построенные в [8]. При этом в случае евклидовой нормы для погрешностей е м , е в ,е_и,е_у,е д ,е в вспомогательных алгоритмов, использующих конволюту, будут справедливы следующие оценки:

ем = Һ,

ев = max <     , I, в        (8Аи ’ 8А' J ’

ед = 4Һ + т 28 С_а,    е в = 4Һ + т ²ЦС_Ь,

е и = V (ед + Һ/2)² + Һ2/4,     е, = _х в ■ ^ 2 ² + һ ² ,.

Работа выполнена при поддержке РФФИ, грант 10-01-00139 и ФЦП «Научные и научнопедагогические кадры инновационной России».