Вычислительные процедуры для построения обобщенных решений уравнения Беллмана-Айзекса тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

V \ и

\\0tV МИНИСТЕРСТВО ПО ДЕЛАМ НАУКИ, ВЫСШЕЙ ШКОЛЫ И ТЕХНИЧЕСКОЙ ПОЛИТИКИ РОССИЙСКОЙ ФЕДЕРАЦИИ УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

УСПЕНСКИЙ Александр Александрович

УДК 519.837.2

ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЛЯ ПОСТРОЕНИЯ ОбОбЩЕННЫХ РЕШЕНИЙ УРАВНЕНИЯ БЕЛЛМАНА-АЙЗЕКСА

Специальность 01.01.02 - дифференциальные уравнения

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

ЕКАТЕРИНБУРГ - 1993

Работа выполнена в Уральском государственном университете имени A.M.Горького на кафедре прикладной математики

Научный руководитель - доктор физико-математических наук,

ведущий научный сотрудник В.Н.Ушаков;

Официальные оппоненты - доктор физико-математических наук, профессор В.И.Благодатских; кандидат физико-математических наук доцент В.И.Ухоботов.

Ведущее учреждение - Институт проблем механики РАН.

Защита диссертации состоится i & К 1993 года в

g I

часов на заседании специализированного совета К С63.78.03 по присуждению ученой степени кандидата физико-математических наук в Уральском государственном университете имени А.М.Горького (620083, г.Екатеринбург, К-83, пр. Ленина, 51, комн. 248)

С диссертацией можно ознакомится в библиотеке Уральского государственного университета.

Автореферат разослан (О 1 1993 г.

Ученый секретарь специализированного совета к.ф.-м.н., доцент УЧ^л^—В.Г.Пименов

Об ШЛЯ ХАРАКТЕРИСТИКА РАбОТЫ

Актуальность проблемы. Данная работа посвящена изучению некоторых вопросов теории дифференциалыпп игр (д.и.) и теории минимаксных решений (ИР) уравнений Гамильтона-Якоби. В работе рассматриваются две задачи:

I. задача о численном построении решений линейных дифференциальных игр;

II. задача о приближенном конструировании функции цены д.и. (MP задачи Коши для уравнения Беллмана-Айзекса).

Одними из первых в теории д.и. были результаты Р.Айзекса и У.Флеминга, опубликованные в конце 50 - начале 60 годов. Независимо исследования в этой области были начаты советскими математиками. Основополагающий вклад в теорию д.и. внесли Н.Н.Красовский, Л.С.Понтрягш, Б.Н.Пшеничный и их последователи.

Н.Н.Красовским и его сотрудниками была создана теория позиционных д.и., объединившая конструктивные методы решения широкого круга проблем от теорем существования ситуаций равновесия до разработки вычислительных методов. В теории д.и. используются результаты и методы различных математических дисциплин. С другой стороны конструкции, разработанные в теории д.и. находят применение в смежных разделах математики. Так, например, на базе конструкций теории позиционных д.и. А.И.Субботиным было введено понятие обобщенного (минимаксного) решения уравнения Гамильтона-Якоби. Первые результаты', относящиеся к этому направлению были связаны с изучением основного уравнения теории дифференциальных

игр - уравнения Беллмана-Айзекса. В дальнейшем этот подход был

2

распространен на уравнения Гамильтона-Якоби общего вида

В последние годы опубликована большая серия работ зарубежных математиков, посвященных исследованию вязкостных решений уравнений в частных производных первого порядка (УЧППП). Понятие вязкостного решения ввели в начале 80-ых годов M.G. Grandall и P.-L. Lions. Отметим, что хотя по происхождению и по форме определения минимаксного и вязкостного решений различны, в конечном итоге они оказываются эквивалентными.

1 Субботин А.И., Субботина H.H. Необходимые и достаточные условия для кусочно-гладкой цены дифференциальной игры // Локл.

АН СССР. 1978. Т.243, IN 4. С.862-865.

2

Субботин А.И. Минимаксные неравенства и уравнения Гамильтона-Якоби.- М.: наука, 1991.- 216 с.

В теории обобщенных ( минимаксных и/или вязкостных) решений доказаны теоремы существования и единственности для широкого круга краевых задач и задач Коши. Отметим также, что этим результатам предшествовали исследования многих математиков, проведенные в 50-70-ых годах. Проблемой построения решений УЧППП занимались И.Н.Гельфанд, С.К.Годунов, С.Н.Кружков, Н.Н.Кузнецов, О.А.Ладыженская, О.А.Олейник, А. А .Самарский, А.Н.Тихонов, P.D.Iax, E.Hopf, W.H.Fleming и другие.

В конце 80-ых годов начаты исследования УЧППП методами идем-потентного анализа. К указанному направлению принадлежат работы

В.П.Маслова, С.Н.Самборского, В.Н.Колоколъцева и других авторов.

Большое внимание уделяется исследованиям, направленным на развитие вычислительных методов решения уравнений Беллмана-Ай-зекса и Гамильтона-Якоби. В теории д.и. известны различные подходы к численному построению стабильных мостов, функции цены

д.и., минимаксных решений уравнений Гамильтона-Якоби. Так, 3

например, известно , что решение регулярных д.и. сводится к решению задач выпуклого и математического программирования. Для решения нерегулярных игровых задач с выпуклой по фазовой переменой функцией цены д.и. Н.Н.Красовским разработан метод стохастического программного максимина. В работах В.С.Пацко и его учеников изложены методы приближенного решения линейных дифференциальных игр с выпуклой терминальной платой. Известен также подход к численному решению игровых задач на основе альтернированного интеграла. Численным аспектам построения решений УЧППП в рамках теории вязкостных решений посвящены работы P.E.Souganidls, S.Osher и других авторов.

Данная работа примыкает к исследованиям 4.5,6,7 ß которых

3

Красовский H.H. Игровые задачи о встрече движений // М.: Наука, 1970. - 420 с.

4

Красовский H.H. К задаче унификации дифференциальных игр // Докл. АН СССР. 1976. Т.226, N 6. С.1260-1263.

5

Красовский H.H. Унификация дифференциальных игр // Игровые

задачи управления / Свердловск. 1977. С.32-34. g

Алексейчик М.И. Дальнейшая формализация основных элементов антагонистической дифференциальной игры // Мат. анализ и его прил. / Ростов, ун.-т. Ростов-на Дону, 1975. Т.7. С.191-193.

7

Ушаков В.Н. К задаче построения стабильных мостов в дифференциальной игре сближения-уклонения // Изв. АН СССР. Техн.кибернетика. 1980. N 4. С.29-36.

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

Основными целями работы являются:

1) исследование аппроксимаций стабильных мостов (множеств уровня минимаксного решения уравнения Беллмана-Айзекса) и управляющих воздействий в линейных конфликтно-управляемых динамических системах;

2) построение аппроксимирующих операторов, доставляющих приближенные реше!шя задач Коши для нелш1ейных по всем переменным уравнениям Гамильтона-Якоби;

3) разработка и реализация алгоритмов численного решения уравнений Гамильтона-Якоби, использующих идеи сеточных методов.

Метод решения. В работе систематически используются методы теории д.и. и теории МР уравнений Гамильтона-Якоби,привлекаются понятия выпуклого анализа и математического программирования.

Научная новизна. Основные результаты работы являются новыми.

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

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

Результаты работы являются новыми и могут быть использованы для решения задач оптимального управления и построения решений УЧППП.

Апробация работы. По материалам диссертации сделаны сообщения на Международном семинаре "Устойчивость и колебания нелинейных систем управления" (Москва,1992), II Международном семинаре ИФАК "Негладкие и разрывные задачи управления и оптимизации" (Челябинск, 1993), Гагаринских научных чтениях по космонавтике и авиации (Москва, 1988), VII Всесоюзной конференции "Управление в механических системах" (Свердловск, 1990), III Всесоюзной школе "Понтрягинские чтения" (Кемерово, 1990), XI Всесоюзной конференции "Проблемы теоретической кибернетики" (Волгоград, 1990) и докладывались на семинарах отдела динамических систем Института математики и механики УрО РАН и ряде региональных школ и конференций.

Публикации. По теме диссертации опубликованы 10 работ.

Структура и объем. Диссертация состоит из введения, списка обозначений, трех глав и списка литературы. Объем работы составляет 165 страниц машинописного текста. Библиография включает 133 наименований работ российских и зарубежных авторов.

СОДЕРЖАНИЕ РАбОТЫ

Во введении обосновывается актуальность темы исследований, определяется цель работы, дается обзор литературы по исследуемой проблематике.

В первой главе рассматривается игровая задача сближения с выпуклым компактом M с Rn для линейной управляемой системы:

X = A(t)x + B(t)u + C(t)v (1)

Здесь t - время, изменяющееся на отрезке [t0>i3]; х - п-мерный фазовый вектор системы; и и v - векторы управляющих воздействий первого и второго игроков соответственно, стесненные ограничениями uePcRp,v6Qc R4,P и Q - выпуклые компакты; A(t), B(t), C(t) - непрерывные на отрезке Itg.tfl матрицы-функции.

Первый параграф носит вводный характер: в нем дается постановка задачи и излагается необходимый для решения задачи набор сведений из теории д.и..

Пусть D с (t0>t?]xRn - множество позиций игры. Пусть задано некоторое множество V элементов у/, а также семейство отображений Rn

( F^: D ч 2 >, отвечающее множеству V и удовлетворяющее набору условий (А1,А2,АЗ)Э. Элементы у/ множества у можно тракто-

8 Тарасьев A.M., Успенский A.A., Ушаков В.Н. Построение разрешающих процедур управления в трехмерной линейной игровой задаче с терминальной платой. Свердловск, 1990, 93 с. Деп в ВИНИТИ 20.07.90.// И 4495-В90.

ватъ как некоторые "обобщетше" управления второго игрока, а множества F^(t,x) как вектограммы управляемой системы (1) в точке (t,x), отвечающие "обобщенным" управлениям у.

Rn

В терминах семейства ( F : D -> 2 ) определяется оператор V » • •

стабильного поглощения (ОСП) it(t.;t ,W ) ( t. * t. s t s i) ,

• n 4 5 В 7

W с R ). Понятие ОСП восходит к унифюсационным моделям ' ' ' .

Здесь же отмечается, что форма задания оператора не единственна. Приводятся определения u-стабильного моста и максимального и-стабильного моста, который обозначается символом W0.

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

Во втором параграфе условия А1-АЗ дополняются условием A4 -

условием литшицевости по переменной х многозначного отображения рП

< F : D(t) « 2 , t б (t„,iJl ). Наличие условий А1-А4 позволяет

у/ О

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

'о

(АООТ ji(t.;t ,W ) ( tn s t. < t ï в. W с Rn) и ввести опреде-

ление аппроксимирующей системы множеств (ACM) ( W(t.) с Rn: tj е 3 >. 3 - некоторое разбиение отрезка It^.Jl.

Здесь же дается утверждение о достаточных условиях, налагаемых на различные формы ОСП, при соблюдении которых происходит совпадение аппроксимирующих систем множеств, отвечающих этим формам ОСП и конструируемых на одном и том же разбиении отрезка времени игры.

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

выступающей в роли потенциала аппроксимирующей дифференциальной 9

игры :

g

Ушаков в.Н. К теории минимаксных дифференциальных игр. Часть

I. Свердловск: 1980, 187 с. Леп. в ВИНИТИ 16.10.80.// N 4425-80.

ТЕОРЕМА 1. Для того, чтобы точка xlt.l удовлетворяла

включению xlt.l 6 3W(t.) необходимо, чтобы

max е. (t.,x[t.],l) = max е. (t.,x[t.l,l) = О

А. 11 Q А. 1 i

leS leLu(x(t(>)

и достаточно, чтобы

max г. (t..xlt.l,l) = 0.

л

leL (х(t.)) 1

Здесь

где

1Л (t.,x[t().l) = - < 1, x[t.]> - ^j-pltj.xltjl.l) +

+ V (xlt 1) i+1

S = !P = UeRn: Hill = l),/>(t,x,l) = max min <l,A(t)x+B(t)u+C(t)v>

ueP veQ

X(t. + ^;tj.xltj]) = xltjl + (tJ+ -tjJ-FUj.xttj] ),

Mt ( xlt.l ) = W(t1+1) л X(t. + 1;t..xlt.l), i+1

min <l,z>, если М * а zeM

+оо , если М = и

для конкретного М,

Lgtxlt.l) - замыкание множества векторов 1 е S внутренних

нормалей к множеству М (xlt.l) в точках множества Hgtxlt;]) = i+1 1 1 = int X(t. ;t.,xlt.l) л SM ( xlt.l ). 111 i+1 1 Основные результаты первой главы сосредоточены в третьем

параграфе.

Здесь отмечается, что выражение тах е. (t.,xlt. 1,11=0,

о \ 1

IEL (х(tj)) 1

фигурирующее в теореме 1, не очень удобно для построения границы

3W(t.) множества W(t.), ибо в это соотношение входит опорная

функция а., , ,, ,, (1) множества М. (xlt.J), зависящего от М (xlt.l) t i

i+I

искомой ТОЧКИ xlt.l 6 3W(t.). Это обстоятельство, в частности, I 1

осложняет построение вычислительных процедур.

Для того, чтобы преодолеть эту трудность, осуществляется переход от "плавающего" локального целевого множества М (x(t.l) к локальному целевому множеству М^ (x[t.|),

i+l 1 Vi 1

"закрепленному" за некоторой граничной точкой х Е t. + ^ 1 множества w(V[).

Итак, пусть xlt.+1l е

- 1+1

О (x[t. .]) = < x: И x - xlt. 1 И г I, г г O. r 1+1 1+1

Число r выбирается исходя in динамических свойств системы

(1) и геометрических характеристик множества W(t.+!).

Вводится в рассмотрение функция

г1] (t.,x[t.],l) = - < 1, xlt.]> - ¿1.-p{t..xlt.l, 1) + A. 1 l l i

+ 4>i+i>>(U 1+1

Символом Lr(xlt[+1l) обозначается замыкание множества всех

векторов 1 е S внутренних нормалей к множеству М^ (x[t.+ 1l) в

¡+1 1

точках множества A (xlt. ,])= ЗмГ (x[t. .]) n im О (xlt. ,1).

r i+l t. , 1+1 Г 1+1

i+l

Функция е^ (t.,x[t.],l) более регулярна, чем функция i

г. (t.,x[t.l,l) в том смысле, что последнее слагаемое, входящее J. 1 1 1

в выражение для этой функции, есть опорная функция множества, не зависящего от точки xft.l, подлежащей вычислению.

Показывается, что замена в теореме 1 функции г^ (•) на е^ (•) эквивалентна.

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

Указанный подход при построении АСМ развивался также в работе1".

■

На прямой с направляющим вектором 1 и проходящей через

_• _

точку x[t.+ 1], рассмотрим точки xlt. 1 = xlt.+j] + yl ( у е. R ), для которых выполняется неравенство

dist ( xlt. .] + yl*. 3W(t. .) ) s KA. (2)

l+l ' i+l l

Обозначим у = max ( у: dist ( xlt. , ] + yl , 3W(t. ,) ) i KA. ).

' i+l ' i+l l

Выберем г = ( 1 + у )'KA..

ТЕОРЕМА 2. Пусть x[t.+11 € 3W(t.+1), 1 e S и удовлетворяют

условию (2). Пусть xlt.) удовлетворяет соотношениям

Л0(хи.])'* И> xlt.] е ОуКЛ (x[t.+1l).

Тарасьев A.M., Ушаков В.Н. Алгоритм построения стабильного моста в линейной задаче сближения с выпуклой целью // Исследования задач минимаксного управления. Свердловск. 1985. С.82-90.

а также равенству

xtt.l = x[t.+IJ + у -1

где

у" = тах ( еГ. (t„xlt. ,1.1) / <1,(Е + ¿.A(t.)) 1*> >,

"j.ii+1 11

l6Lr(x[t.+1]) 1 Е - единичная матрица.

Тогда xlt.l б 3W(t.).

При этом предполагается, что вектор 1 е S выбрал из условия <1,(Е + JjAlt^) 1*> > О для всех 1 б Lr(x[t[+In (3)

В работе рассмотрен и самый общий случай, когда условие (3) не выполняется.

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

х = f(t,x,u,v) в f'lt.x.u) + f2(t,x,v) (4)

где t e [tQ,i31, х - n-мерный фазовый вектор системы, и и v -векторы управляющих воздействий первого и второго игроков соответственно, стесненные ограничениями

u е Р с Rp , v е Q с R4, Р и Q - компакты. Функционал в игре терминальный, функция платы сг( •): Rn => R - локально липшшевая функция.

Функция цены V(-):[t0>i3]xRn в R указанной д.и., у которой правая часть (4) удовлетворяет традиционным условиям теории позиционных д.и., совпадает с МР задачи Коши для уравнения Гамильтона-Якоби:

—(t.x) + h(t,x,VV(t,x)) = О

3t (5)

V(i>,x) = о(х)

Здесь

av av

VV(t,x) = (— (t,x).....— (t,x)) - градиент функции,

3xl 3xn

h(t,x,s) = min max < s, f(t,x,u,v)> - гамильтониан системы , uep veQ

s 6 Rn.

В первом параграфе главы приводятся необходимые для дальнейшей работы сведения и формулировки утверждений из теории д.и. и теории МР уравнений Гамильтона-Якоби. Здесь же указывается подход в решении проблемы численного конструирования МР. Проблема решается за счет повышения размерности динамической системы (4)

ход в решении проблемы численного конструирования МР. Проблема решается за счет повышения размерности динамической системы (4) и рассмотрения соответствующим образом подобранной д.и. сближения для расширенной системы

х = f(t,x,u,v) (6)

, X = О

Максимальный стабильный мост в задаче сближения с tpi а (с hypo а) для системы (6) совпадает с надграфнхом (с подграфи-ком) МР.

Конструкция решения проблемы предполагает построение сужения минимаксного решения V на множество ß = < (t,x) е [t0>13] х Rn: t е ltgg.il. x « (x + (t - t0Q)-F >,

где x e Rn - произвольно взятая, фиксированная точка; г > О; F - шар достаточно большего радиуса, равного К, с центром в начале координат пространства Rn; t^ = тах ( tQ, в - г/К >. По построению ß - сильно инвариантное множество относительно дифференциального включения x s F, а сечение ß(t) множества ß в каждый момент t есть шар с центром в точке х и радиусом г = r(t) = = г - (Л - t

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

Во втором параграфе формируются операторы стабильного поглощения, доставляющие решение задачам I и II соотвегствонно. Для решения каждой из задач вводится в рассмотрение совокупность семейств многозначных отображений, зависящая от числового параметра С. Показывается, что ' семейство, отвечающее конкретному значению параметра С, порождает 001 для соответствующей задачи. Приводится определение аппроксимирующих форм ОСП (ЛТОСП) для расширетгой системы.

В третьем параграфе изучаются свойства ЛФОСП, при этом рассматривается действие АФОСП на одном шаге разбиения отрезка [t^,«?] длиной А. Обсуждается проблема выбора аппроксимирующих форм ОСП, удобных при реализации вычислительных процедур. Имеет место утверждение, обосновывающее корректность операции овыпукления локальных целевых множеств в рассматриваемых злда-чах.

ТЕОРЕМА 3. Пусть ¿:ß(t ♦ J) =» R - липшицева функция с константой Д. Тогда для любого С г 2ХК, для любого достаточно

малого числа Л > 0 справедливо равенство

С С

"в,a' ip/ ' = яв,л( ер1 с0

из которого следует, что

ll/j(x) = ^(х) х е Ö(t).

Здесь

г

1) лв - аппроксимирующая форма ОСП в задаче I, действующая на шаге разбиения отрезка и выделяемая в рамках семейства аппроксимирующих форм ОСП значением параметра С;

2) со ф - выпуклая оболочка сужения функции ф на зам-

Vх'

кнутый шар О^(х) радиуса КЛ с центром в точке х;

3) »/j(x) = Inf { *:(х, х) « «в jt <Pi Ф) >;

"С С

4) = tof { д;:(х, д;) 6 яв if" СО ^ '

Аналогичный результат справедлив для задачи И.

ТЕОРЕМА 3 . Пусть ÖCt + Л) •> R - лгашицева функция с

константой Д. Тогда для любого С s 2ХК, для любого достаточно

малого числа Л > 0 справедливо равенство

к ( hypo ф ) = ,( hypo сопс ф ),

Н, ¿1 — н, ^ —

<Wx) °каш

из которого следует, что

{^(х) = {^(х) х е ß(t),

Здесь

С

1) я аппроксимирующая форма ОСП в задаче II, действующая

н, ¿J

на шаге А разбиения отрезка ltQ,i>l и выделяемая в рамках семейства аппроксимирующих форм ОСП значением параметра С;

2) сопс ф - вогнутая оболочка сужения функции ф на зам-

_VX)

кнутый шар О^(х) радиуса КЛ с центром в точке х;

С С

3) { Лх) = sup { у) € к Л hypo ф) };

¿л Н, /л

""с С

4) { Лх) = sup { х'Лх, г) € л^ hypo сопс ф )

J н, д —

°клм

Следствием теорем 3 и 3 и теоремы об отделимости выпуклых множеств является

ТЕОРЕМА 4. Пусть <j:6(t + А) ■> R - липшицева с константой А функция, А - достаточно малое положительное число, х е Sit). С ^ 2ХК . Тогда

я? Л epi со ф ) = тР Л tp\ со ф ),

в — в, J —

°к/х) °кам

с о

А hypo сопс ф ) - л Л hypo сопс ф )

н, л — н, л —

°КАЫ

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

В четвертом параграфе выписываются формулы для построения функций, порождаемых АФОСП на шаге длиной а. В частности, в предположениях теоремы 4 показывается, что

Q

^е.(х) = у.(х) = тах т'п со ф (х + А'П (7)

л а seS feF (t.x.s) " , .

п в 0/гл(х)

( ix) = £.(х) = min тах сопс ф (х + J*f), (8)

й а seS feF Ct.x.s) ~ , ,

п н 0_.(х)

КА

а также С

гдМ = = га" ( J-Mt.x.p) +

уб0£(хМ(х) ресо ф{у'х) + < р, х-у> + со ф{у-,х) >, (9)

С

i^j(x) = {j(x) = min min { A 'hlt.x.p) +

у6°Я(хЫ(х) P*conc <Му;Х) + < p, x-y> + сопс ф(у;х) ), (10)

S = <seRn: IIsII = 1>; F (t,x,s) = If e F: <s,f> г h(t,x,s) ); n в

F^t.x.s) = (f e F: <s,f> s h(t,x,s) );

со ф(';х) = со ф (•) - локально выпуклая оболочка (ЛВО)

°КАЫ -

функции ф, построенная на шаре 0„ (х);

КА

со_ф(у;х) = ( р е R : со фЫ;х) - со ф(у;х) г < р, w - у> V w е 0^. (х) ) - субдифференциал ЛВО функции ф, построенный в точке у, здесь у е константа АГ(х) выбрана in условия

Х(х) s K/Z;

сопс <#( • ;х) = сопс ф (•) - локально вогнутая оболочка

(ЛВГО) функции ф, построенная на шаре О (х);

КА

сопс ф{у;х) = { р е Rn: сопс фЬч-,х) - сопс ф{у;х) s

i < р, w - у> V w б О (х) > - супердифференциал ЛВГО функции

ф, построенный в точке у, здесь v е 0_, . ,(х). константа АГ(х)

KlxlA

выбрана из условия К{х) з К/2.

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

h(t,x,s) = min <s,f(1)(t,x,u)>, U€P

имеют место формулы

V .(х) » min со ф (х + 4'Г) =

Г«о Fs(t.x) -

KA

= max max < J'lhlt.x.p) -

teco F(t,x) peco «(х+Ж;х)

- < p, Ol + со ¿(x+dr;x) ),

í ,(х) = min . сопс ф (х + ¿l'f)

fee« F(t.x) -

ka

- min min ( ¿'(htt.x.p) -

teco F(t,x) peconc ¿(y;x)

- < p, D] + conc tf(x+dr¡x) >,

где со F(t,x) = со ( f: f = f(11(t,x,u), u e P>.

В § 5 формируются операторы, апппроксимируюшие функцию цены д.и., и показывается, что в качестве таковых могут применяться

1) оператор последовательного максимина от локально выпуклых оболочек (базовая формула (7));

2) оператор последовательного минимакса от локально вогнутых оболочек (базовая формула (8)).

Для примера приведем определение одной из возможных аппроксимаций. Зафиксируем произвольно взятое разбиение . ¡J = ( t^g, tj, ..., ) отрезка ( tQ, i». Зададим функцию

N

V (•): и ( t.,ß(t.)) » R: В 1=1 1 1

Vb(IJ,x) = с(х),

V (t.,x) = max min со V (t. ,,х; х + ¿J.-f);

в i . г _ , в 1+1 1

seS feF (t.,x,s) п в i

где со V (t. ,,х; •): 0_.(х) ■» R - JIBO функции V(t. ,,•), по-в 1+1 kó 1+1

строенная на шаре О (х).

кд

Отметим ' возможность построения односторонних аппроксимаций. Так, например, функция

N

(V (•)- pUiam 3) ): и ( t., ß(t.)) 4 R, t. е ¡J B i=l 1 1 1

аппроксимирует снизу функцию цены V на множестве б. Здесь <Нат 3 - диаметр разбиения 3, ¡1 - функция, обладающая тем свойством, что /|(<$) 1 О при <5 А О. Аналогичным образом строится мажорирующая аппроксимация функции.

В заключение параграфа показывается, что основные результаты первой и второй глав могут быть получены в рамках единого подхода. Так, соотношения (9), (10) выводятся по рецептам первой главы на основе построения потенциала дифференциальной игры для расширенной системы (6) и знания формул сдвижек.

Третья глава включает пять параграфов и целиком посвящена анализу вычислительных проблем, возникающих при реализации идей, изложенных в первых двух главах. При этом в первых трех параграфах речь идет об алгоритмах, относящихся к численному решению линейной игровой задачи управления, в четвертом параграфе - о сеточном методе конструирования МР уравнения Айзекса-Беллмана.

В первом параграфе показывается, что при построении системы

множеств, аппроксимирующей максимальный стабильный мост в игре

(1) в виде совокупности ( № П.): 1. е 3 ' выпуклых многогран-

а 1 1

ников, вычисление коэффициента сдвижки у сводится к конечной задаче математического программирования:

у = тах тах

кеК. (у.о>) 1е1_;

тах к

V ,а>

<1,хИ. , )> - л.<1,ла.)х[ 1. , )> 1+1 I I 1+1

< 1,(Е + а.АН. ) И >

1 1

-ал <1,В(и )иУ > + < 1, С( 1. ) Vе01 > ) 1 1 1

< 1, (Е + ¿.Аи.))1 > 1 1

< 1, х*[Ч + 11 >

< 1,(Е + Л .А(г.))1 > 1 1

Здесь К,- количество вершин многогранника попавших в

г-ую окрестность вершины х(1

¡+1'

е № и. Л, а и V - номера а 1+1

вершин многогранников Р и 0 соответственно, ^ - многогранный конус суть пересечение конуса линейности гамильтониана н конуса

внутрешшх нормалей к №а(1.+ [) в вершине х

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

моста на сферических сетках направлений. При этом алгоритм А

- это алгоритм представления многогранника W (t.) в виде графа;

а 1

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

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

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

х = f(t,x,u,v) s g(t,x) + B(t,x)u + C(t,x)v Здесь x - n-мерный фазовый вектор системы, и и v - векторы управляющих воздействий первого и второго игроков, соответст-енно, стесненные ограничениями

u е Р с Rp , v е Q с R4, Р и 0 - выпуклые многогранники. Вектор-функция g(t,x) и матрицы-функции B!t,x) и C(t,x) предполагаются непрерывными по (t,x). Количество вершин многогранников Р и 0 равно 1р и соответственно.

Численное построение аппроксимаций функции осуществляется таблично в узлах сеточной области. Выделим некоторые из алпрок-атациокных разностных операторов:

1) V (t.,x) = max max max < A.'

в 1 . — .1

yJe(W.(x) (y,iu) P63coVB(t.+1,x,yJ; у,со) • t <p,g(tj,x)> + <р,вигх)иу> + <p,C(t.,x)vi0 ] +

+ < p, x-yJ> + со VB(t.tl,x; yJ) >.

Здесь

V (•) - аппроксимирующая функция, конструируемая на сеточной в

области, покрывающей множество б;

г., I. .<= 3; А. = I. . - г.; Г 1+1 1 1+1 Г

х - внутренняя точка, находящаяся на расстоянии от границы сеточной области, не меньшем чем К(х)4.;

через у^ обозначены точки сетки, принадлежащие окрестности

узла х;

у и а> - натуральные числа суть номера вершин многогранников Р и Q;

3coVB(t.+j,x,y-';)>,a>) - элемент разбиения субдифференциала

JIBO сеточной функции VQ(t.+1> -), посчитанного в узле у^, конусом линейности гамильтониана.

2) V (t.,x) = max max ( Л,'

в 1 _ 1

(y,<u) peacoVB(t.+1,x,x; у,to)

• [ <p,g(t.,x)> + <p,B(t.,x)uJ'> + ip.Citj.xJv0' ] ).

Здесь обозначения те же, что и в 1).

Выделим различие в операторах I и 2. В операторе 1 шаг по пространственной переменной и шаг по времени - величины независимые. Применение оператора 2 предполагает построение сеток, подчиненных правилу:

J.AT з Н^/2, где Нх - шаг при нанесешш сепси по пространственной переменной.

В пятом параграфе приводятся примеры, посчитанные численно в рамках описанного в работе подхода. Пример 1.

Рассматривается задача Коши

3V(t,x,y)/3t + min max < VV(t.x.y), f(t,x,y,u,v) > = 0 ueP veQ

V(0.5,x,y) = x2+ y2,

здесь

(x,y) e R2, t e [0,0.5],

2 2 T

r(t,x,y,u,v) = t sin(y), u - expi-x -y )-v ) ,

P = [-1,11. Q = (0,1),

T - знак транспонирования. Область фазовой плоскости, на которой осуществлено построение минимаксного решения V - квадрат D = Их,у): О s х s 1, 05J31I

На рисунке 1 представлена аппроксимация на прямоугольной сетке сужения краевого условия на D, на рисунке 2 - аппроксимация на той же сетке в момент t = О решения задачи Коши.

Моделирование осуществлено с применением оператора 2.

Рис. i.

Рис. а

Пример 2.

Рассматривается задача Коши

SV(t,x,y)/at + min тах < 7V(t,x,y), f(t,x,y,u,v) > » О ueP veQ

V(l,x,y) = x + у ,

здесь

(x,y) 6 Rz, t e [0,1],

f(t,x,y,u,v) = ( sin(y), -(Нхг+угГ' + u - txpl-y.2-y2)*v )T, P = [-1,11, Q = t-l.ll.

Область фазовой плоскости, на которой осуществлено построение минимаксного решения V - квадрат D = Цх,у): |х| s 2, |УИ 2 >

На рисунке 3 представлена аппроксимация на прямоугольной сетке сужения краевого условия на D, на рисунке 4 - аппроксимация на той же сетке в момент t = О решения задачи Коши.

Моделирование осуществлено с применением оператора 2.

Публикация по теме диссертации

1. Успенский A.A. Построение множеств разрешимости в линейной дифференциальной игре сближения в трехмерном пространстве // Тез.докл. Гагаринские научные чтения по космонавтике и авиации, Москва, 1988. М.: С.219.

2. Успенский A.A. Алгоритм построения множеств разрешимости в многомерных линейных дифференциальных играх // Проблемы теоретической и прикладной математики. УрО АН СССР. Свердловск, 1989. С.15.

3. Тарасьев A.M., Успенский A.A., Ушаков в.Н. Алгоритмы приближенного построения множества позиционного поглощения в линейной задаче сближения с выпуклой целью // Сборник "Расчет потенциальных и программных управлений", Свердловск, УПН, 1989, С.22-30.

4. Taras'ev A.M., Uspenskii A.A.. Ushakov V.N. Construction of solving procedures in a linear control problem // The Lyapunov functions method and applications. J.C.Daltzer AC, Scientific

9 19

Publishing Co. IMACS, 1990. P.lll-115.

5. Успенский A.A. К вопросу о численном решении дифференциальных игр // Сб. тезисов 3-ей Всесоюзной школы "Понтрягинские чтения", Кемерово, 1990. С.105.

6. Успенский A.A. Алгоритмы построения разрешающих процедур управления и вычисления функции цены для линейных дифференциальных игр // Тезисы докладов И Всесоюзной конференции "Проблемы теоретической кибернетики", Волгоград, 1990, С.108.

7. Тарасьсв A.M., Успенский A.A., Ушаков В.Н. Построение разрешающих процедур управления в трехмерной игровой задаче с терминальной платой. Свердловск, 1990, 93 с. Деп в ВИНИТИ 20.07.90,// N 449S-B90.

8. Вахрушев В.А., Тарасьев A.M., Успенский A.A., Ушаков В.Н., Хрипунов А.П. О численном решении задач оптимального управления нелинейными системами. В кн.: 7 Всесоюзный съезд по теоретической и прикладной механихе. Тезисы докладов. Москва, 15-21 августа 1991 г., С.17.

9. Тарасьев A.M., Успенский A.A., Ушаков В.Н. Алгоритм построения разрешающих позицио1шых процедур управления в трехмерной линейной дифференциальной игре сближения с выпуклой целью // Сборник трудов ИММ УрО АН СССР "Управление в динамических системах", Свердловск, 1992, С.88-104.

10. Тарасьев A.M., Успенский A.A., Ушаков В.Н. Методы построения обобщенных решений основного уравнения теории оптимального управления. В кн.: Устойчивость и колебания нелинейных систем управления. Тезисы докладов. Международный семинар. Москва, июнь 1992 г., С.80.

ЗАКЛЮЧЕНИЕ

В диссертации рассмотрена проблема численного решения уравнений типа Гамильтона-Якоби и получены следующие основные результаты:

1) Изучена структура линейной дифференциальной игры, разработаны алгоритмы приближенного конструирования сечений стабильного моста на сферических сетках направлений, предложена численная реализация одного из алгоритмов для случая игры в трехмерном пространстве.

2) Исследована проблема построения численных процедур для решения уравнений Гамильтона-Якоби, разработаны алгоритмы приближенного конструирования MP уравнений на базе локально выпуклых и локально погнутых оболочек, предложена конктретная вычислительная схема, приведены результаты численного моделирования.