Интервальные алгебраические задачи и их численное решение

Содержание
Введение 5
1 Постановки интервальных задач 17
1.1 Анализ интервально заданных систем ..................................... 17
1.1а Описание практической ситуации..................................... 17
1.16 Предварительная постановка задачи.................................. 20
1.2 Обобщённые множества решений интервальных уравнений...................... 22
1.2 а Кванторный формализм .............................................. 22
1.26 Интерпретация...................................................... 27
1.2 в Множества АЕ-решений .............................................. 29
1.3 Детальная постановка задачи ............................................. 34
1.3 а Обсуждение......................................................... 34
1.36 Что такое интервальная “задача оценивания”?........................ 35
1.3в. Задачи, которые будут рассматриваться.............................. 38
2 Характеризации и свойства множеств решений 43
2.1 Интервальные арифметики.................................................. 43
2.1а Классическая интервальная арифметика............................... 43
2.16 Интервальная арифметика Кахана .................................... 44
2.1 в Неформальное обсуждение............................................ 44
2.1 г Полная интервальная арифметика . ................................. 47
2.1 д Интервальные векторы и матрицы..................................... 51
2.1с Арифметика Каухера— минимаксная интервальная арифметика ... 53
2.2 Характеризации множеств АЕ-решений....................................... 54
2.3 Множества АЕ-решений интервальных линейных уравнений .................... 61
2.3 а Кванторный формализм в линейном случае............................. 61
2.36 Характеризация и постановки задач ................................. 68
2.4 Управляемое множество решений интервальных линейных систем............... 74
3 Внешнее оценивание множеств решений 81
3.1 Основы алгебраического подхода .......................................... 82
3.2 Оптимальность внешнего оценивания........................................ 84
3.3 Интервальный метод Гаусса-Зейделя для обобщённых множеств решений . . 90
3.4 Исследование обобщённого метода Гаусса-Зейделя .......................... 92
3.5 Предобуславливание....................................................... 97
3.6 Внешнее оценивание для нелинейных систем.................................103
3.7 Обсуждение и численные эксперименты .....................................106
СОДЕРЖАНИЕ 3
4 Оптимальное внешнее оценивание множеств решений 114
4.1 Оптимальные решения и их цепа...........................................114
4.2 Пассивный переборный алгоритм...........................................116
4.3 Интервальные методы глобальной оптимизации..............................118
4.4 Методы дробления решений................................................125
4.4 а Решение одномерных включений .....................................125
4.46 Основной алгоритм.................................................126
4.4 в Доказательство сходимости ........................................131
4.5 Модификации методов дробления решений .................................136
4.5 а Оценивание но знакоонределённым брусам............................136
4.56 Использование локальных решателей.................................138
4.5 в Новая стратегия дробления.........................................141
4.5 г Итоговая схема....................................................143
4.6 Численные эксперименты с методами дробления решений.....................147
4.7 Методы дробления параметров.............................................152
4.7а Общая схема методов...............................................152
4.76 Решение линейных систем...........................................153
4.8 Модификации методов дробления параметров................................157
4.8 а Тест на монотонность..............................................159
4.86 Стратегия дроблеыия...............................................161
4.8 в Влияние базового алгоритма........................................162
4.8 г Отсев бесперспективных записей....................................163
4.8 д Итоговая схема алгоритма..........................................163
4.9 Численные эксперименты с методами дробления параметров..................165
4.10 Последовательно гарантирующие и финально гарантирующие алгоритмы . . 170
5 Внутреннее оценивание множеств решений 176
5.1 Алгебраический подход...................................................176
5.2 Внутреннее оценивание для интервальных линейных систем..................179
5.3 Максимальность внутренних оценок .......................................181
5.4 Коррекция внутренних оценок.............................................183
5.5 Интервальные линейные системы с неотрицательными матрицами..............187
5.5 а Теоретическая основа..............................................188
5.56 Алгоритм..........................................................192
5.5 в Выбор начальной точки.............................................194
5.5 г Численные эксперименты............................................196
6 Численное нахождение алгебраических решений 199
6.1 Погружение в линейное пространство......................................199
6.1 а Зачем погружать?..................................................199
6.16 Определение и основные свойства.................................. 200
6.1 в Стандартное погружение............................................204
6.1 г Сопутствующие матрицы........................................... 206
6.1 д Вполне невырожденные матрицы......................................208
6.2 Исследование индуцированных уравнений...................................210
6.2 а Порядковая выпуклость и субдифференцируемость.....................212
6.26 Полиэдр ал ьность ................................................215
СОДЕРЖАНИЕ
4
6.2 в Оценки субдифференциалов .....................................218
6.3 Существование и единственность алгебраических решений..................220
6.4 Субдифференциальный метод Ньютона......................................223
6.4 а Алгоритм.........................................................223
6.4 б Доказательство сходимости .......................................223
6.4 в Вычисление субдифференциала......................................228
6.5 Численные эксперименты с субдифференциальным методом Ньютона .... 232
6.6 Стационарные одношаговыс итерационные методы...........................234
6.6 а Общий подход: расщепление матрицы ИСЛАУ..........................234
6.66 Отщепление вещественного слагаемого-.............................236
6.6 в Треугольное расщепление матрицы системы..........................241
6.7 Численные эксперименты со стационарными итерационными методами . . . 243
5 Библиография 247
Введение
Интервальный анализ — это сравнительно молодая и интенсивно развивающаяся область знаний на стыке информатики, кибернетики и вычислительной математики, предметом которой является решение задач с интервальными неопределенностями и неоднозначностями в данных. Её основная идея очень кратко может быть выражена следующим образом: интервалы (или, более общо, некоторые другие ‘‘простые” множества) рассматриваются как самостоятельные целостные объекты, между которыми, в соответствии со смыслом рассматриваемой задачи, вводятся операции и отношения. И далее, решая задачу, мы оперируем уже в этом новом множестве “интервальных” объектов.
Интервальный анализ, по существу, можно рассматривать как вычислительный отдел хорошо знакомого теоретическим математикам многозначното анализа. Но интервальная идея по самой своей сути алгоритмична, требует реализации на машине, и потому неудивительно, что в докомпьютерную эпоху развитие интервального анализа не состоялось. Но уже в 50-е годы, с появлением и распространением первых ЭВМ, потребность в интервальных методах и оценках стала ощущаться столь остро, что пионерские работы по интервальному анализу появились практически одновременно и независимо в Японии, СССР, США и Польше. Первая русская теоретическая работа по интервальному анализу [43] принадлежит леру академика Л.В. Канторовича и опубликована в одном из первых томов “Сибирского математического журнала”.
Таким образом, интервальный анализ и интервальные методы первоначально возникли как средство автоматического учета ошибок округлений при счете на ЭВМ с конечной точностью представления чисел (конечной разрядной сеткой). На протяжении ряда лет этот акцент в развитии интервального анализа был доминирующим, и именно так представлена новая научная дисциплина, например, в “Математической энциклопедии” [64] и “Математическом энциклопедическом словаре” [65]. В некоторых странах (например, в Германии) это обстоятельство со временем повлекло за собой даже постепенную эволюцию научной терминологии. Выявилась, в частности, отчетливая тенденция к устранению самих слов “интервальный”, “интервальность” и т.п., некогда характеризовавших отдельное и целостное научное направление. Взамен предлагается говорить о надежных/достоверных/ыаучных вычислениях (соответствующие английские термины — reliablc/validated/scientific computation). Под влиянием этих веяний название специализированного научного журнала Interval Computations, возникшего как трибуна специалистов по интервальному анализу и его приложениям, было изменено на Reliable Computing.
Однако идеи, положенные в основу нового научного направления, оказались гораздо шире чисто “округленческих” приложений. Вскоре выяснилось, что нарождающиеся интервальные подходы и модели получают чрезвычайно плодотворное применение как язык описания некоторого особого класса неопределенностей, — так называемых ограниченных по амплитуде неопределенностей (соответствующие английские термины — bounded disturbances, bounded error approach, bounded parameter model и т.п.). А.П.Вощинин
ВВЕДЕНИЕ
6
и Г.Р.Сотиров в учебнике (16) отмечают, что интервальное представление факторов неопределенности “в последнее время привлекает все большее внимание исследователей как наименее ограничительное и отвечающее широкому классу задач.” И далее : “Во многих прикладных задачах часто нет оснований или недостаточно информации для того, чтобы рассматривать факторы неопределенности как случайные Это приводит к необходимости учета неопределенности нсстатистической (или, в общем случае, неизвестной) природы, когда относительно факторов ... ничего неизвестно, кроме их свойства быть ограниченными” [16]. В этом же смысле высказываются А.Б.Куржанский в обзоре [53],
B.А.Грановский и Т.Н.Сирая в монографии [22] и другие авторы. Замечательно, что в упомянутой цервой отечественной интервальной статье Л. В. Канторовича [43], где новое научное направление еще не называется явно, но рельефно очерчивается, акцент в приложениях нового подхода делается как на повышении точности и надежности численных алгоритмов, так и на перспективах развития аппарата для оперирования с ограниченными неопределённостями.
Характерная черта исследований, в которых интервальный анализ используется для получения математически гарантированных результатов (т.е. автоматического учета ошибок округлений) на ЭВМ с конечной разрядной сеткой — допущение о малости интервалов изменений “входных” данных, позволяющее во многих случаях осуществлять асимптотический анализ и т.п. Но погрешности вычислений необходимо учитывать при этом во всех без исключения операциях на ЭВМ, формирующих окончательный результат. Существенное влияние на работы по этой тематике оказывают конкретные особенности вычислительных машин и процессоров, их архитектура, языки программирования и пр. За обзорами результатов и подробной библиографией по “округленческому” направлению мы отсылаем читателя к книгам Р. Е. Мура [202, 204], Г. Алефсльдаи Ю. Хсрцбергера [4],
C. А. Калмыкова, Ю. И. Шокина и 3. X. Юлдашева [42], Р. Б. Кирфотта [174], О. Аберта [118] и другим.
Напротив, в тех работах, где интервальный анализ служит средством для исследования ограниченных но амплитуде неоиределённостей, допущение о малости возмущений не работает, размеры “входных” интервалов могут быть сколь угодно велики, но зато предполагается, что все арифметические операции как с точечными величинами, так и с интервалами выполняются абсолютно точно. В этом же духе выдержана и настоящая диссертационная работа, посвященная теоретическому анализу и построению численных алгоритмов решения ряда интервальных алгебраических задач, возникающих в теории автоматического управления, исследовании операций, теории принятия решения, теории идентификации и оценивания параметров и ряде смежных дисциплин.
Основным объектом рассмотрения в нашей работе является интервальная система уравнений вида
/1( а1 > • • • 5 ац 2-11«• • > ^л)- = Ьь аь • • • 5 аЬ з-ь • • • ? хп) — Ьг,
(0.1)
/т( а1} • • • > ЗЦ} • • • , £п) = Ьт,
с интервалами а1, ..., а/, Ьь Ьт, которую мы будем также записывать в краткой форме
^(а,*) = Ь (0.2)
ВВЕДЕНИЕ
7
Е =
Л(а,а) ^ {хг
-Р2(а,х) х2
: X = ;
^пі(а,х) у ^ Хп У
и интервальными векторами
а =
'•і Х
а2
к *
Ъ =
/ Ь, ^ Ь2
\ Ьт /
Для интервальных систем уравнений, у которых количество переменных совпадает с количеством уравнений, нам потребуется также переходить от (0.1)—(0.2) к некоторому специальному виду, в котором вектор переменной выделен в левой части “в чистом виде”:
* = <?( а,х),
(0.3)
(7(а,х) = ((?1(а, х), &2(а,х),..., (7П(а, х) )т. Интервальные системы (0.1)—(0.3) мы понимаем как формальные записи, обозначающие семейства точечных систем уравнений той же структуры, образованные варьированием параметров ах, , а/, 61, ..., Ьт в пределах соответствующих интервалов ах, ..., а/, Ьх, ..., Ът.
Значительная часть результатов работы относится не к общим нелинейным системам (0.1)—(0.2), а к более простым (но не менее важным) интервальным линейным системам
ацХх + а12х2 + ... + ах„хп = Ьх,
агі^і + а22х2 + ••• + а2пхп = Ь2,
апіХі + ап2х2 + ... + атопхп = Ьт,
(0.4)
с интервалами ау и Ь,, или в краткой форме
Ах = Ь
(0.5)
с интервальной матрицей А = (ау) и интервальным вектором правой части Ь = (Ь,).
Представляемая работа посвящена решению различных постановок задач, связанных с интервальными системами уравнений (0.1)—(0.2) и (0.4)—(0.5). Но собственно математическим результатам мы предпосылаем исследование процесса постановки и формулировки интервальных задач. Необходимость детального рассмотрения этого вопроса является очень насущной и вызвана его неразработанностью в современном интервальном анализе, а также общей методологической и терминологической запутанностью.
Принятая нами точка зрения состоит в том, что в большинстве случаев некорректно говорить о решении интервальных уравнений (или систем уравнений, неравенств и т.п.) вообще. Правильным является вести речь о решении тех или иных постановок задач связанных с интервальными уравнениями (системами уравнений, неравенств и т.п.). В свою
ВВЕДЕНИЕ
8
очередь, формулировка той или иной постановки интервальной задачи подразумевает указание, как минимум,- множества решений задачи и способа его оценивания.
В этом отношении ситуация в интервальном анализе отчасти напоминает теорию дифференциальных уравнений, где также избегают говорить о решении просто уравнений самих но себе. Вместо этого исследуются и решаются задача Кошя или краевая задача (для обыкновенных дифференциальных уравнений), смешанная задача, задача Дирихле или задача Неймана и т.п. (для уравнений в частных производных).
Итак, в самом начале работы мы даём аккуратную и математически корректную формулировку того, что есть постановка интервальной задачи. Одним из первых итогов нашего критического анализа является обобщение понятия множества решений для интервальных систем уравнений, неравенств и т.п.
Как мы уже отмечали, исторически интервальный анализ возник из необходимости учета ошибок вычислений и задач чувствительности. Поэтому неудивительно, что на первоначальном этапе своего развития множество решений задачи с интервальными данными понималось как множество всевозможных решений точечных задач с коэффициентами, могущими принимать значения из заданных интервалов. В частности, для интервальных систем алгебраических уравнений вида (0.1)—(0.2) в течение многих лет единственным рассматривавшимся множеством решений было так называемое объединённое множество решений
Еиа1- =• { х € 1Г | (За 6 а)(3ё 6 Ь)( 1?(а, х) = 6) },
образованное всеми решениями систем Р(а,х) = ёса€аиб€Ь. Для случал интервальных линейных систем это определение выглядит так
Ны(А, Ь) = { х е К” | (3 А 6 А)(3 Ь € Ь){Ах = 6) }.
Приведённые выше определения, математически наиболее корректные, организованы в соответствии с аксиомой выделения из формальной теории множеств. Именно, точка х принадлежит рассматриваемому множеству тогда и только тогда, когда подстановка её вместо переменной х в предикат, выписанный после вертикальной черты, превращает его в истинное высказывание. Таким образом, имеет смысл называть подобные предикаты выделяющими предикатами соответствующих множеств решений, коль скоро они задают характеристические свойства, которые выделяют точки этого множества.
По мере развития интервальных методов и расширения сферы их приложений постепенно выяснилось, что обыденное понимание множества решений интервальной системы уравнений (неравенств и т.п.) как множества всевозможных решений вещественных систем того же вида с параметрами из указанных интервалов не приложимо в ряде практически важных интервальных задач. Таковой, является, папример, линейная задача о допусках, осознанная в эконометрике [241, 242) и позже в 80-е годы в теории автоматического управления для объектов с интервальными неопределенностями в данных (см. работы Н.А. Хлебалина [85, 80, 81], Е.М. Смагиыой и И.В. Дугаровой [27, 82, 298) и других авторов). Решение линейной задачи о допусках приводит к необходимости рассмотрения так называемого допустимого множества решений интервальных линейных систем вида (0.4)—(0.5), образованного всеми такими векторами х € Кп, что произведение Лх попадает в Ь для любой матрицы А (Е А. Формально это множество определяется как
Е:Ы(А,Ь) = {х € Кп | р/А € А)(36 6 Ь)(А* = 6)},
ВВЕДЕНИЕ
9
и впервые оно было рассмотрено еще в 1972-м году немецким исследователем Е. Нудингом в [223]ол. На наш взгляд, работа Нудинга [223] явилась пионерским вкладом в интервальный анализ и была по достоинству оценена уже в 90-е годы. Нудииг, в действительности, продемонстрировал нам возможность варьирования логических кванторов в выделяющем предикате при определении множества решений интервальной задачи. Следующий шаг на этом пути был сделан лишь в 1991-92 годах, когда несколько российских исследователей независимо и почти одновременно столкнулись с необходимостью введения множества решений
Ее1г1( А, Ь) = { г € ИГ] (У6 € Ь)(3 А 6 А )(Ах = Ь) },
образованного такими векторами х € Кп, что для любого желаемого вектора Ь € Ь мы можем подобрать соответствующую матрицу А € А удовлетворяющую Ах = Ь. В работах [274, 289] С.П. Шарый предложил называть его управляемым множеством решений и, похоже, термин постепенно привился в литературе.
Заметим, что символическое обозначение (УД € А) означает (Уац € ац)(Ус12 € ац)... (VОтп € ат„) и го же самое верно в отношении (ЗД 6 А), (V Ь 6 Ь) и (3 6 6 Ь). Кроме того, кванторы V и 3 не коммутируют друг с другом. Следовательно дальнейшее обобщение понятия множества решений интервальной линейной системы можно получить, разделив действие логических кванторов но отдельным элементам матрицы и правой части и далее комбинируя кванторы V и 3 с различными интервальными параметрами и меняя их порядок. Мы покажем в работе, чаю такие множества решений не являются чисто теоретическим курьёзом но могут быть проинтерпретированы как решения некоторых игр или многошаговых процессов принятия решений в условиях интервальной неопределенности, т.е. как решения минимаксных задач исследования операции.
Основной итог представляемой диссертационной работы — развитие и обоснование эффективных численных методов внешнего и внутреннего оценивания множеств АЕ-решений интервальных систем уравнений. Столь широкая постановка задачи ранее никем не рассматривалась и не решалась (и не только потому, что понятие обобщенного множества решений не существовало). Но отдельные частные задачи оценивания тех или иных множеств решений интервальных уравнений являются достаточно популярными и хорошо изученными.
По-видимому, исторически первая постановка для интервальных систем уравнений — это задача внешнего покоординатного оценивания множества всевозможных решений точечных систем, содержащихся в (0.1)—(0.2) (или в (0.4)—(0.5)), т.е. объединённого множества решений этих интервальных систем уравнений. Как правило, её формулируют в следующем виде
(0-6)
Фактически — это интервальная форма задачи о чувствительности решения системы уравнений к конечным возмущениям. Часто, имея в виду именно эту задачу, говорят (не совсем корректно) о ‘:решении интервальной системы уравнений”.
История задачи внешнего оценивания объединённого множества решений для интервальных систем уравнений, линейных и нелинейных, является давней и насыщенной. Ее формулировка настолько проста и естественна, что, фактически, посвященные ей работы
01В оригинальной статье [223] сам Нудинг называл его множеством внутренних решений.
найти интервальный вектор V, включающий объединённое множество решений интервальной системы уравнений.
ВВЕДЕНИЕ
10
появлялись задолго до выхода в свет классической кпиги P.E. Мура [202], с которой, как принято считать, и началось быстрое развитие интервального анализа. В частности, первой русской работой о характеризации и оценивании объединённого множества решений ИСЛАУ была статья Б.И. Белова и Е.Г. Анциферова [7]. К настоящему времени среди общей массы публикаций по интервальной математике доля тех, в которых рассматриваются различные аспекты решения “внешней” задачи для ИСЛАУ, — одна из наибольших.
Практические приложения “внешней” задачи для ИСЛАУ многочисленны и разнообразны. Е.К. Корноушенко в цикле статей [48] сводит к решению этой задачи проблему оценивания множества достижимых состояний линейной стационарной системы. В работе Н.К. Пылаева и И.Б. Ядыкина [79] “внешняя задача” естественно возникает в связи с синтезом интервального управления по неявной эталонной модели. В.З. Манусов, С.М. Моисеев и С.Д. Перков в [63] приводят к “внешней задаче” для ИСЛАУ решение некоторых линейных задач электротехники с интервальными неопределенностями во входных параметрах. В последние годы работами многих исследователей интенсивное развитие получили методы идентификации систем управления в условиях ограниченных возмущений их параметров (см. обзор А.Б. Куржанского [53] и книгу Э. Вольтера и Л. Пронцато [302]). Для случая систем, описываемых линейными зависимостями “вход-выход”, математической основой этих методов также служит решение “внешней задачи” для ИСЛАУ, как правило, с прямоугольными интервальными матрицами.
Кроме отмеченных выше приложений в технике и естествознании “внешняя задача” для ИСЛАУ имеет и более опосредованные применения. Например, на каждом шаге популярного интервального метода Ньютона требуется решать “внешние задачи” для некоторых промежуточных ИСЛАУ [159]. С необходимостью решения ’’внешней задачи” для интервальных систем алгебраических уравнений (линейных или нелинейных) сталкиваются при дискретизации различных интервальных версий краевых задач для дифференциальных уравнений (см. [42, 266]) и интегральных уравнений [26]. В интервальном методе наименьших квадратов [151] построение регрессионной прямой по заданному семейству результатов наблюдений, имеющих интервальную неопределенность, также сводится к решению “внешней задачи” для ИСЛАУ.
За прошедшие три десятилетия методология решения “внешней задачи” претерпела эволюцию от подражания известным вещественным методам решения СЛАУ (метод Гаусса, нростой итерации и т.п.) до создания самостоятельных “интервальных” концепций и подходов. Хорошие обзоры методов решения задачи внешнего оценивания объединённого множества решений ИСЛАУ (по состоянию на середину 80-х годов) были сделаны А. Ной-майером в [208, 212]. Немало материалов, касающихся интервальных алгебраических систем (линейных, в частности), воспроизведено в широко известных монографиях Р. Мура [202, 204], Г. Алефельда и 10. Херцбергера [4], А. Ноймайера [212], С.А. Калмыкова, Ю.И. Шокина и З.Х. Юлдашева [42], Б.С. Добронца и В.В. Шайдурова [26], Р.Б. Кир-фотта [174]. Тем не менее, на сегодняшний день подавляющая часть результатов но этой теме остается разбросанной но разрозненным журнальным публикациям. Среди работ последних лет отметим статьи Ю. Гарлоффа [148], Д. Гея [149], монографию Р.Б. Кирфот-та [174], работы Г. Майера по выяснению условий применимости интервального метода Гаусса [198, 199, 200], капитальную монографию А. Ноймайера [212] и его последующие статьи [213, 214], многочисленные исследования И. Рона [240, 249, 250, 251, 255], 3. Румпа [259, 261], X. Швандта [265].
В последние годы в связи с бурным развитием теории и практики параллельных вычислений все возрастающее количество публикаций посвящается реализации различных
5
ВВЕДЕНИЕ 11
интервальных алгоритмов на векторных и параллельных ЭВМ. Решение на таких вычислителях ’’внешней задачи” для ИСЛАУ рассмотрено, например, в [266).
Интересно сопоставить саму интервальную постановку задачи о внешнем оценивании множеств решений (0.6) и интервально-аналитические подходы к её решению с другими методиками, которые более или менее успешно применялись и применяются для решения задач, аналогичных (0.6). Это, во-первых, широко известные методы анализа чувствительности решений систем уравнений [150, 211] и, во-вторых, так называемые методы гарантированной точности для решений систем уравнений, интенсивно развивавшиеся в работах школы O.K. Годунова [20].
В традиционном анализе чувствительности оценке вариации решений обычно предшествует линеаризация исходного уравнения относительно некоторого частного решения, на основе которой и выводят заключение о влиянии на решение тех или иных параметров. Так как члены второго и более высоких порядков при этом игнорируются, то подобная методика работоспособна лишь при “достаточно малых” изменениях параметров системы и к тому же не обеспечивает гарантированности оценок решений.
В методах гарантированной точности из [20] вариации параметров (коэффициентов) системы вообще рассматриваются как некоторый нежелательный паразитный эффект, искажающий исходно точную постановку задачи. В связи с такой методологической установкой, а также из-за особенностей применяемой в [20] техники “большие” изменения параметров решаемой системы (иначе называемые также крупномасштабными или нелокальными) школой С.К. Годунова просто не рассматриваются. Напомним, что в современном интервальном анализе “очень широкие” интервальные данные в системах (0.1)—(0.2) и (0.4)-(0.5) также вызывают затруднения, но задачи для интервальных линейных систем с сильно невырожденными интервальными матрицами (см. Определение 3.5.1) надежно решаются без особых проблем. Наконец, как вариации параметров системы, так и оценки вариаций решения С.К. Годунов и его последователи измеряют отклонением но норме (т.е. одним числом), тогда как в интервальном анализе в постановке задачи и ответе неопре-делённость с гораздо большей степенью детализации описывается многомерным интервалом.
Изложим кратко содержание представляемой диссертационной работы. Структурно она состоит из Введения, указателя обозначений, собственно основного текста, разбитого на шесть Г лав и списка литературы. Мы предполагаем уже известными читателю основные понятия и факты интервального анализа, не уделяя их развёрнутому изложению специального места в диссертации (для введения в предмет мы рекомендуем, например, книги [4, 26, 42, 159, 174, 212]). Вместо этого, чтобы придать тексту самодостаточный характер, необходимые известные результаты даны конспективно и с подробными литературными ссылками.
Каждая из шести глав основного текста диссертации концентрируется вокруг одной или нескольких родственных основных идей.
Для Главы 1 это концепции обобщённого множества решений и общей постановки так называемых интервальных задач оценивания. Глава 2 представляет результаты по характеризации и геометрическим свойствам обобщённых множеств решений, как для общего нелинейного случая, так и для интервальных линейных систем.
Глава 3 посвящена развитию методик внешнего интервального'1 оценивания множеств АЕ-решений. При этом отдельное внимание уделяется классической задаче внешнего оценивания объединённого множества решений ИСЛАУ, и нам удаётся существенно продвинуться в этом вопросе. Основные результаты Главы 3 — алгебраический подход и метод
ВВЕДЕНИЕ
12
Гаусса-Зейделя для задач оценивания множеств АЕ-решений интервальных линейных системна также предобуславливанис.
При внешнем оценивании множеств решений особую ценность и в теории и для практики имеет получение интервального вектора, объемлющего решение и имеющего наименьшую возможную ширину, или, что эквивалентно, нахождение оптимальных (точных) покоординатных оценок множеств решений. Но подобная усиленная постановка “внешней задачи” оказалась крепким орешком. Даже для объединённых множеств решений большинство разработанных до сих пор методов позволяют эффективно находить интервальный вектор, гарантированно содержащий множество, но лишь немногие из практических алгоритмов обеспечивают в общем случае его оптимальность. При этом все они имеют, в конечном счёте, переборный характер и потому чрезвычайно трудоёмки. Основные итоги Главы 4 представляемой работы — построение двух классов алгоритмов — методов дробления решений и методов дробления параметров (иначе называемых ещё Р55-алгоритпмами и РРв-алгоритмами) — для нахождения именно оптимальных или близких к оптимальным решений “внешней задачи” для И СЛАУ и некоторых нелинейных систем уравнений. Решающей предпосылкой для их создания послужило представление “внешней задачи” как задачи конечномерной оптимизации. При этом вместо традиционной формулировки “внешней задачи” в виде (0.3) в алгоритмах Главы 4 предлагается перейти к вычислению гшп{ хи | х 6 Е0^(А,Ь)} и шах{ | х € Еа<?(А,Ь)} для каждого отдельного о = 1,2,...,п. Мы докажем сходимость развиваемых алгоритмов и рассмотрим некоторые из их обобщений на случай более общих интервальных алгебраических задач. В предварительном порядке часть из излагаемых ниже результатов была опубликована в работах автора по оптимальному оцениванию объединённых множеств решений ИСЛАУ [98, 268, 269, 270, 278], но теперь мы рассматриваем более общую ситуацию.
Параграфы §4.6 и 4.9 Главы 4 содержащий описание и сравнительный анализ численных экспериментов с различными методами дробления решений и методами дробления параметров. Самостоятельным результатом этих параграфа можно считать также использованное в расчётах параметрическое семейство ИСЛАУ для тестирования алгоритмов решения “внешней задачи”.
Короткая, но очень важная Глава 5 диссертации посвящена решению задачи внутреннего — с помощью гипербрусов — оценивания множеств решений интервальных линейных систем уравнений. Несмотря на большой устойчивый спрос на решение подобных задач со стороны инженеров и практиков, имеется лишь очень небольшое количество работ по этой теме (см. X. Бек [126], А. Ноймайер [209], А.Ф. Бочков и Т.В. Евтушенко [11]). Мы предлагаем результаты, концентрирующиеся вокруг алгебраического подхода, которые позволяют эффективно и с хорошим качеством решать задачи внутреннего интервального оценивания множеств АЕ-решений интервальных линейных систем и некоторого специального класса нелинейных систем. Кроме того, на основе тонких геометрических свойств множеств решений ИСЛАУ с неотрицательными матрицами мы предлагаем в §5.5 ещё одну простую и гибкую методику внутреннего оценивания множеств решений. Оба этих подхода дают для ИСЛАУ максимальные по включению внутренние интервальные оценки множеств решений.
Наконец, предмет заключительной Главы 6 диссертации — развитие подходов и методов нахождения алгебраических решений в полной интервальной арифметике Каухера для различных интервальных линейных систем, которые возникают при практической реализации алгебраического подхода к задачам внутреннего и внешнего оценивания множеств решений интервальных систем уравнений. Помимо собственно численных методов в этой
ВВЕДЕНИЕ
12
Гаусса-Зейдсля для задач оценивания множеств А Б-решений интервальных линейных системна также предобуславливание.
При внешнем оценивании множеств решений особую ценность и в теории и для практики имеет получение интервального вектора, объемлющего решение и имеющего наименьшую возможную ширину, или, что эквивалентно, нахождение оптимальных (точных) покоординатных оценок множеств решений. Но подобная усиленная постановка “внешней задачи” оказалась крепким орешком. Даже для объединенных множеств решений большинство разработанных до сих пор методов позволяют эффективно находить интервальный вектор, гарантированно содержащий множество, но лишь немногие из практических алгоритмов обеспечивают в общем случае его оптимальность. При этом все они имеют, в конечном счёте, переборный характер и потому чрезвычайно трудоёмки. Основные итоги Главы 4 представляемой работы — построение двух классов алгоритмов — методов дробления решений и методов дробления параметров (иначе называемых ещё Р55-алгоритмами и РРв-сичгоритмами) — для нахождения именно оптимальных или близких к оптимальным решений “внешней задачи” для ИСЛЛУ и некоторых нелинейных систем уравнений. Решающей предпосылкой для их создания послужило представление “внешней задачи” как задачи конечномерной оптимизации. При этом вместо традиционной формулировки “внешней задачи” в виде (0.3) в алгоритмах Главы 4 предлагается перейти к вычислению т1п{х4, | х 6 Е0/з(А,Ь)} и тах{^„ | х € 5а-?(А,Ь)} для каждого отдельного и — 1,2,...,п. Мы докажем сходимость развиваемых алгоритмов и рассмотрим некоторые из их обобщений на случай более общих интервальных алгебраических задач. В предварительном порядке часть из излагаемых ниже результатов была опубликована в работах автора по оптимальному оцениванию объединённых множеств решений ИСЛАУ [98, 268, 269, 270, 278], но теперь мы рассматриваем более общую ситуацию.
Параграфы §4.6 и 4.9 Главы 4 содержащий описание и сравнительный анализ численных экспериментов с различными методами дробления решений и методами дробления параметров. Самостоятельным результатом этих параграфа можно считать также использованное в расчётах параметрическое семейство ИСЛАУ для тестирования алгоритмов решения “внешней задачи”.
Короткая, но очень важная Глава 5 диссертации посвящена решению задачи внутреннего — с помощью гипербрусов — оценивания множеств решений интервальных линейных систем уравнений. Несмотря на большой устойчивый спрос на решение подобных задач со стороны инженеров и практиков, имеется лишь очень небольшое количество работ по этой теме (см. X. Бек [126], А. Ноймайер [209], А.Ф. Бочков и Т.Н. Евтушенко [11]). Мы предлагаем результаты, концентрирующиеся вокруг алгебраического подхода, которые позволяют эффективно и с хорошим качеством решать задачи внутреннего интервального оценивания множеств АЕ-решений интервальных линейных систем и некоторого специального класса нелинейных систем. Кроме того, на основе тонких геометрических свойств множеств решений ИСЛАУ с неотрицательными матрицами мы предлагаем в §5.5 ещё одну простую и гибкую методику внутреннего оценивания множеств решений. Оба этих подхода дают для ИСЛАУ максимальные по включению внутренние интервальные оценки множеств решений.
Наконец, предмет заключительной Главы 6 диссертации — развитие подходов и методов нахождения алгебраических решений в полной интервальной арифметике Каухера для различных интервальных линейных систем, которые возникают при практической реализации алгебраического подхода к задачам внутреннего и внешнего оценивания множеств решений интервальных систем уравнений. Помимо собственно численных методов в этой
ВВЕДЕНИЕ
13
главе мы также рассматриваем вопросы существования и единственности алгебраических решений, свойства операторов в интервальных пространствах. После вводного §6.1, посвященного исследованию конструкции погружения интервальных пространств в евклидовы пространства двойной размерности, мы излагаем в §6.2 теорию операторов, индуцированных умножениями на интервальную матрицу. Наконец, параграфы §§6.4-6.6 представляют собственно численные методы для нахождения алгебраических решений интервальных линейных систем и результаты вычислительных экспериментов с ними. Главным достижением этой части работы является субдифференциальный метод Ньютона, позволяющий эффективно и качественно находить алгебраические решения широких классов интервальных линейных систем.
Автор благодарен A.B. Лакееву, В.А. Новикову, И.О. Голосову, Б.С. Добронцу, В.В. Шайдурову, A.B. Кулибабе, П.С. Панкову за плодотворные научные дискуссии, а также академику Ю.И. Шокину за поддержку в занятиях интервальным анализом.
Обозначения
Наша система обозначений следует, в основном, тем неофициальным международным рекомендациям, которые были выработаны в результате дискуссии и подытожены в книге [174]0,2. Всюду в тексте работы интервалы и другие интервальные величины (векторы, матрицы и др.) будут обозначаться жирным шрифтом, например, А, В, С, х, у, г, тогда как неинтервальные (точечные) величины никак специально не выделяются. Арифметические операции с интервальными величинами — это операции соответствующих интервальных арифметик: либо классической интервальной арифметики Ш (см., например, [4, 26, 42, 159, 174, 212]), либо полной интервальной арифметики Каухера Ш, краткому описанию которой мы посвящаем §2.1 г. Наконец, иод векторами (точечными или интервальными) всюду понимаются вектор-столбцы.
Другие обозначения
N множество натуральных (положительных целых) чисел
К множество вещественных (действительных) чисел
множество вещественных п-мерных векторов Ктхп множество вещественных т х гг-матриц
Ш классическая интервальная арифметика, или её носитель
— множество замкнутых интервалов [а, 6] на R, а < Ь 43
IIR" множество п-мерных интервальных векторов
ШтХп множество интервальных m х п-матриц
HR полная интервальная арифметика Каухера, или её
носитель — множество всех пар [а, 6], а, Ь б Е 47
a, а левый и правый концы интервала а, соответственно 47
|а| абсолютная величина интервала а 47
(а) наименьшее из расстояний точек интервала а до нуля,
антипод абсолютной величины интервала 93
(А) матрица сравнения для интервальной матрицы А 93
mid а середина (медиана) интервала а 53
wid а ширина интервала а 53
0 2См. также http://cs.utep.edu/ijiterval_corap/notations/suggestion.html
ОБОЗНАЧЕНИЯ
15
гас! а радиус интервала а 53
сієу а отклонение интервала а от нуля : 102
сіиаі а дуальный к а интервал 47
орр а противоположный к а интервал 48
рго а правильная проекция интервала а 47
© операция в ПК, обратная сложению 48
0 операция в ПК, обратная умножению 49
х+, X" положительная и отрицательная части интервала х 218
хМ функционал Рачека — “относительная узость” интервала 76
«(х) знак середины интервала х
“шм объединённое множество решений
интервальной системы уравнений 31, 65
Ьоі допустимое множество решений
интервальной системы уравнений 31, 65
=СІГІ управляемое множество решений
интервальной системы уравнений 31, 66,
=■0,0 множество АЕ-решений типа ог/3
интервальной системы уравнений 65
Ас характеристическая матрица, соответствующая
некоторому АЕ-множеству решений ИСЛАУ 71
а‘ характеристический вектор параметров, соответствующий
некоторому АЕ-множеству решений интервальной системы 59
Ьс характеристический вектор правой части, соответствующий
некоторому АЕ-множеству решений ИСЛАУ 59, 71
с№ (а, Ь) расстояние (метрика) в интервальных пространствах 52
(а, Ь) расстояние (псевдометрика) в интервальных пространствах 52
о знак композиции отображений
ері / надграфик функции / 215
Ьур/ подграфик функции / 215
д{ субдифференциал функции / 213
уегі а множество концов (крайних точек) интервала
или вершин интервального вектора (матрицы) 72
3~ матрица, сопутствующая для матрицы 0 207
А минимум в частично упорядоченном множестве
V максимум в частично упорядоченном множестве
И условная решеточная операция 53
□У интервальная оболочка множества 5 44
ОБОЗНАЧЕНИЯ
16
х знак вещественного числа х
х+, х~■ положительная и отрицательная части числа х 49
іігі X топологическая внутренность множества X
I единичная матрица соответствующих размеров
сііа^ {.гі,... у2п} диагональная п х п-матрица
с элементами ..., гп по главной диагонали || • || какая-нибудь из эквивалентных норм в или же
индуцированная матричная (операторная) норма || • ||и векторная (или индуцированная матричная норма),
масштабированная положительным вектором и р{А) спектральный радиус матрицы А
К интервальным векторам и матрицам все введённые выше операции за исключением операции (•) будут применяться покомпонентно, так что если, к примеру, а = (а,) — интервальный вектор, то mid а — это вещественный вектор (mid а,).
Глава 1
Постановки интервальных задач
Формально, предметом этой главы являются математические вопросы моделирования си* стем в условиях неопределенности и неоднозначности, заданных в интервальной форме. Но, в действительности, содержание этой части работы совсем не исчерпывается прикладными рассмотрениями. Мы используем практическую постановку задачи как повод для более широкого обсуждения и уточнения таких понятий как интервальная задача, решение интервальной задачи, а также некоторых других фундаментальных концепций интервального анализа, которые будут далее интенсивно использоваться во всей работе. Мы делаем попытку рассмотрения интервальных статических систем с общей нелинейной зависимостью вход-выход, но детально и во всех тонкостях исследуется более простой линейный случай.
1.1 Анализ интервально заданных систем 1.1а Описание практической ситуации
Нашим основным практическим примером будет так называемая обратная задача системного анализа11 для статических (безынерционных) систем, заданных зависимостью вход-состояние-выход:
Для заданных входов и выходов системы найти (или как-то оценить) её состояние.
Особенность ситуации, с которой мы будем иметь дело, заключается в тем, что входы и выходы системы не являются заданными точно. Для них будут известны лишь границы их возможных значений (изменений), верхняя и нижняя, или, что эквивалентно, нам даны только интервалы, в пределах которых могут находиться значения входов и выходов.
Пусть внутреннее состояние системы, входной сигнал и выходной отклик описываются вещественными векторами х € Кп, а € К* и Ь € соответственно. Во множестве всех входных воздействий мы будем выделять
• возмущения ах,... ,Ог, которые действуют независимо от нашей воли в пределах интервалов ,..., аг, и
11 Часто её называют также задачей идентификации.
ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ ЗАДАЧ
18
• управления аг+1,..., а/, значения которых мы сами можем устанавливать в интервалах £Ц.+х,..., а/.
Возмущения оказывают дестабилизирующее воздействие на систему, стремятся вывести её из заданного режима, в то время как подходящими управлениями мы стремимся компенсировать влияние этих возмущений и способствовать достижению требуемых характеристик функционирования. В классической теории управления выходы системы, на которых требуется поддержание сигнала на некотором заранее заданном уровне или же его изменение в соответствии с предопределённым планом, называются, как известно, регулируемыми выходами. Но введение интервальности для описания конечного назначения системы вносит дополнительную специфику в рассматриваемую ситуацию. Именно, мы должны разделить множество всех выходов системы па
• компоненты &1, &2, • • • 5 которые мы должны быть способны перевести в любое значение из заранее заданных интервалов Ьх,..., Ь3 (будем называть их интервалами достижимости), и
• компоненты 6,+1,... ,6^, для которых мы должны обеспечить гарантированное попадание в интервалы Ьа41,... ,Ьт (будем называть их интервалы стабилизации).
Соответственно, выходы первого типа мы будем называть управляемыми, тогда как выходы второго типа будут называться стабилизируемыми.
Примером управляемого выхода системы может служить координата “механической руки” робота-манипулятора Положение этой руки должно гарантированно “накрывать” каждую точку некоторой данной рабочей области. Если это накрытие имеет место, то обычно не возражают и против того, чтобы манипулятор мог дополнительно достигать некоторые другие позиции вне рабочей области.
возмущающие сії, ..., аТ
ВХОДЫ
ог+1, ..., о/
управляющие
управляемые 61,...,6.
ВЫХОДЫ
^і41> • • • » стабилизируемые
Рисунок 1.1: Структурная схема статической системы управления.
Типичным примером стабилизируемого выхода системы является температура внутри химического реактора в ряде химико-технологических процессов. Она не должна отличаться от номинальной Т больше, чем на некоторую предписанную величину 6Т, но любая температура из интервала [Т—<5Т, Т+<5Т] равно допустима и конкретное значение этой температуры £ не имеет значение при условии, если выполнено включение * € [Т*— 6'1\Т+6Т]. В частности, некоторые значения из [Т - 6Т,Т + 671] могут оказаться недостижимыми реальным процессом.
ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ.ЗАДАЧ
19
Предположим, что зависимость вход-состоянис-выход в рассматриваемой системе имеет вид
Г(а,х) = Ь (1.1)
с некоторым отображением Г : К' х —» К”1. В самом общем случае отображение Я может иметь очень сложный вид, но в значительной части нашей работе мы будем считать, что компоненты ж), г = 1,2являются 'рациональными выражениями, т.е. конечными комбинациями переменных о, х и констант с элементарными арифметическими операциями (ср. [204, 212]). Будем также предполагать, что все Е* непрерывны на своих областях определения, так что деление на нуль не встречается в ^,(а,х) в пределах рассматриваемых интервалов ах,... ,а/ и области значений х. В целом ситуация описывается структурной схемой, представленной на Рисунке 1.
Уместно отметить, что в описанной выше ситуации наше использование терминов “управление”, “регулирование”, “управляемый” и т.п. пе вполне совпадает с тем, которое принято в классической теории автоматического управления и технической кибернетике, где обычно исследуются динамические системы, с непрерывным либо дискретным временем. Тем не менее, развитие общей теории систем привело к пониманию того, что зависимость от временной переменной является второстепенной при определении “управления” и “управляемости” (см., например, [67]). Это обстоятельство делается особенно прозрачным при абстрактной математической постановке задач управления, когда фазовые траектории, фазовые ограничения, управляющие воздействия и т.п. представляются как элементы некоторых функциональных пространств. В наиболее общей форме понятие “управляемости системы” (или, более общо, параметризованного отображения) тесно связано с понятием “достижимости”.
Месарович и Такахара [67], в частности, управляемость формулируют как условие того, что всякий элемент из некоторого выделенного подмножества множества прибытия1-2 отображения может быть достигнут (накрыт) при условии подходящего выбора параметров и аргументов отображения. Более точно, пусть функция Ф(с) описывает результат функционирования системы (выход) в зависимости от параметра (управления) с. Тогда система является (полностью) управляемой в том и лишь в том случае, если выполнено следующее условие:
для любого состояния Я из некоторого отмеченного множества существует управляющее воздействие С из допустимой области, такое что Я = Ф(С).
Но в таком виде понятие управляемости в равной мере применимо также и к статическим (безынерционным) системам, в которых переменная времени и временной интервал вообще не фигурируют (см., например, [289]).
Напомним также, что теория автоматического управления не является единственной дисциплиной, имеющей дело с “управлениями”. В частности, смысл, в котором мы используем термин “управление” (и ему родственные) находится в хорошем согласии с терминологией исследования операций. Напомиим следующее повсеместно принятое определение [3, 40]: операцией называется целенаправленное действие, которое может быть количественно оиисано как
и = /(Х, У),
1-2Сос1отат по английски.
ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ ЗАДАЧ
20
где и есть полезность или значение критерия, характеризующего качество функционирования системы, X — вектор переменных, которыми можно управлять, а У — вектор переменных (и постоянных), не поддающихся управлению (т.е. неуправляемых, или, иначе, возмущающих). Так или иначе, наше словоупотребление вполне законно.
Другое замечание. Слово неопределенность, которое мы используем в связи с управляющими входами системы, строго говоря, не вполне адекватно практическому смыслу, который вкладывается в интервальные границы возможных значений. Например, не совсем корректно говорить о “неопределенности” по отношению к интервалам, представляющим множества возможных положений рулей высоты и направления в самолёте. Тем не менее, для единообразия терминологии мы далее используем все-таки слово “неопределённость”, имея в виду как наше незнание (недостаток информации), так и неединственность (неоднозначность) возможных значений (альтернатив), аналогично тому, как это имеет место в приведенном выше примере с самолётом.
1.16 Предварительная постановка задачи
В связи с описанной в предшествующих пунктах управляемой системой могут возникать вопросы различного сорта, но мы далее будем исследовать следующую математическую постановку — задачу гарантированного оценивания внутреннего состояния системы но значениям сигнала на её входах и выходах:
Для каких состояния системы х при любых внешних возмущениях а\ € аь ..., аг € аг и любых a priori заданных значениях />i € Ьь ..., b3 G Ь3, мы можем выбрать соответствующие управления ar+j € аг+ь о/ € а] та к, чтобы выходной отклик системы F(a,x) был бы в точности равен Ь\, ..., Ь3 на управляемых выходах и находился бы внутри bi+1, ..., bm на стабилизируемых выходах?
(1.2)
Если все входы и выходы системы были бы определены точно, то решение задачи, аналогичной (1.2) свелось бы к решению относительно х уравнения (1.1). В рассматриваемом нами случае, когда входы и выходы системы имеют интервальную неопределенность, мы в соответствии с терминологической традицией интервального анализа также будем говорить по поводу задачи (1.2), что “задана интервальная система уравнений
Да,*) = Ь (1.3)
с интервальными параметрами а = (а^, а2,..., а/)т Є Ш* и Ь = ( Ьі, Ьг,... }Ьт)т € Шт”. Но необходимо подчеркнуть, что интервальную систему (1.3) саму по себе следует понимать лишь как формальную запись, обозначающую семейство точечных систем Л(а, х) = Ь с коэффициентами а € а и 6 Є Ь, не более. В частности, мы даже не имеем права выполнять с (1.3) какие-либо преобразования (приводить подобные, переносить члены из одной части в другую и т.п.), пока не определены точный смысл “решения” системы и то, как следует понимать эквивалентность преобразований с (1.3). Таким образом, некоторые слова, проясняющие постановку задачи, совершенно необходимы в пашем контексте, и первоначально мы определим, что имеется в виду под “множеством решений” системы (1.3).
ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ ЗАДАЧ
21
Начнем с того, что переформулируем словесную постановку основной задачи (1.2) в математически строгих терминах. Для этого мы воспользуемся языком исчисления предикатов первого порядка с логическими кванторами V (квантор всеобщности, “для всех”) и 3 (квантор существования, “существует”) [46]. В частности, условие
для любых й\ £ аТ € аг и для любых Ь\ € Ьь
■ Ьа € Ь„ существуют аг+1 € аг+ь ..., о/ € а/ такие что /\(а, х), ..., Га(а, х) равны Ь\, ..., Ь„ и ^+1(а, *),...,
Кп(а, д) находятся в Ь,+ь ..., Ьт,
которое является сердцевиной постановки задачи (1.2), должно быть эквивалентным образом переформулировано как следующий предикат (логическая формула):
(У<ц € аО* • • (Уаг €'аг) (У6Ж € Ь*)• • • (УЬЛ € Ь,) 4
(Заг+1 € аг+1) • • • (За/ € а/) (36в+1 € Ьа+1) • • • (3&™ € Ьт) (Г(а,х) = Ь).
В целом, множество всех состояний х удовлетворяющих вопросу задачи (1.2) (мы будем обозначать его посредством Е), описывается следующим образом:
Е := { х € К" |
( Уах е ах ) ••• (Уаг€аг)( Уб1 € Ьч ) ••• ( У65 € Ьа )
( Заг+1 € аг+1) ••• ( За/€ а/)( 36л+1 € Ьл+1 ) ••• ( ЗЬт € Ьт )
(Да,*) = 6)},
в то время как рассматриваемая нами основная задача может быть переформулирована так:
Найти (или как-нибудь оценить) множество "Б, определённое (1.5).
Определение (1.5), математически наиболее корректное, организовано в соответствии с так называемой аксиомой выделения формальной теории множеств ZFC (названной по первым буквам фразы Zcrmelo-Fracnkel-axiom of Choice, см., например (46, 52)). Именно, точках х принадлежит множеству (1.5) тогда и только тогда, когда подстановка её значения вместо переменной х в предикате (1.4) приводит к верному высказыванию. Иными словами, свойство (1.4), которое указано в виде предиката после вертикальной черты в записи (1.5) “выделяет” некоторые значения х, которые и образуют множество решений.
Определение 1.1.1 Логическая формула, выписанная после вертикальной черты в определении множества решений (1.5) и задающая характеристическое свойство точек этого множества, будет называться выделяющим предикатом соответствующего множества решений.
Подчеркнем, что, помимо задания функциональной зависимости F и интервальных векторов а и Ь, ключевым моментом в определении (1.5) является указание нами кванторов V и 3 при различных параметрах а и b системы (1.3). При этом множество Е, определяемое посредством (1.5) имеет полное право также быть названным множеством решений
ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ ЗАДАЧ
22
интервальной системы уравнений (1.3), наряду, например, с множеством всевозможных решений точечных систем Г(аух) = 6са€аи&£Ь. Ясно, что это и есть множество решений в некотором обобщенном смысле, который мы обсудим в следующих параграфах. Поэтому впредь множества решений, задаваемые посредством (1.5) и аналогичными определениями, в которых встречаются вхождения различных логических кванторов мы будем называть обобщенными множествами решений интервальных систем уравнений.
1.2 Обобщённые множества решений интервальных уравнений
1.2 а Кванторный формализм
Подытожим сделанное в параграфе 1.1. Взяв в качестве практического примера обратную задачу системного анализа (1.2), мы пришли к необходимости рассмотрения множества решений (1.5). При этом мы применили логические кванторы всеобщности и существования по отношению к интервально заданным входам системы а^ чтобы выразить принципиальное различие между
• входными воздействиями, не зависящими от нашей воли и являющимися внешними неконтролируемыми возмущениями (это соответствует записи uWaj € а/!),
и
• входными воздействиями, которые мы сами можем варьировать в пределах некоторых заданных интервалов, т.е. управлять ими по нашему желанию (это соответствует записи За у £ а/’).
По отношению к интервально заданным выходам системы 6; логические кванторы были применены для того, чтобы различать между
• коридорами стабилизации системы, в пределах которых требуется обеспечить функционирование системы вне зависимости от значений возмущений (это соответствует записи “36,- 6 Ь,”),
и
• множествами достижимости системы, каждый элемент из которых должен быть накрыт в результате подходящего выбора управляющих воздействий (это соответствует записи “\/6, € Ь;г).
Но математический объект, описываемый определением (1.5), имеет и самостоятельное значение, а к введению общего определения множеств решений (1.5) можно было бы прийти также с совершенно абстрактной точки зрения, не привлекая практические соображения из анализа интервально заданных систем, на которых мы останавливались в параграфе 1.1.
Заметим, что любой интервал, представляющий неопределенность (незнание, неоднозначность) некоторой вещественной величины, может быть интерпретирован двояко в соответствии с двойственной природой, присущей самой интервальной неопределенности. Дело в том, что в реальных практических задачах интервалы редко интересуют нас сами
ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ ЗАДАЧ
23
по себе, как самостоятельные целостные и внутренне нерасчленимые объекты без внутренней структуры. В подавляющем большинстве случаев мы используем некоторый интервал V лишь потому, что он содержит точки, и для этих принадлежащих ему точек выполнено или не выполнено некоторое свойство (обозначим его через Р\ реально это может быть вещественное уравнение, неравенство и т.п.). В этих условиях могут представиться следующие две принципиально различные ситуации:
либо рассматриваемое свойство Р(ь) имеет место для всех точек V ■ из заданного интервала V,
либо свойство выполняется лишь для некоторых точек V из интервала V, не обязательно всех (возможно, что даже только для одного значения и).
Сказанное означает, в частности, что в первом случае интервал V отождествляется с совокупностью всех своих точек, тогда как во втором он представляет из себя лишь границы, вместилище для некоторой неизвестной величины, которая может и не принимать некоторых значений из заданного интервала. Это различие между двумя типами интервальной неопределенности особенно выпукло проявляется в тех ситуациях, когда рассматриваемая система имеет несколько интервальных параметров, описывающих воздействия различной природы, которые, возможно, конфликтуют друг с другом (как возмущение-управление).
В формальной записи очерченное выше различие выражается использованием логических кванторов — либо квантора всеобщности V, либо квантора существования 3:
• в первом случае мы пишем “( Ун € V) Р(у)”
и будем говорить о V-типе (А-типе) неопределенности,
• во втором случае мы пишем “(Зг? € г») Р(у)”
и станем говорить о 3-типе (Е-типе) неопределенности
Следует подчеркнуть, что наши рассуждения, мотивирующие использование кванторов и кванторного языка в отношении интервально неопределённых параметров в равной мере приложимы не только к интервальным алгебраическим системам вида (1.3), но также к интервальным неравенствам, интервальным дифференциальным уравнениям и т.п. В частности, цри определении для них “решений” и “множеств решений” мы должны
аккуратно принимать во внимание различие между указанными типами интервальной
неопределённости.
Рассмотрим конкретные примеры. Пусть некоторый объект описывается системой дифференциальных уравнений
дх
— = /(£,*,и), (1.6)
«€[0,21, *(0) = *о, (1-7)
где £ — переменная времени,
х(£) — вектор фазового состояния,
и(1) — вектор управления, который предполагается ограниченным
и принадлежащим некоторому интервалу и, т.е. и(1) € и.
Множеством достижимости рассматриваемой системы называется, как известно [41, 61], множество всех концов х{Т) траекторий системы (1.6)—(1.7), исходящих из точки х0 и