Интервальные алгебраические задачи и их численное решение тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Введение

1 Постановки интервальных задач

1.1 Анализ интервально заданных систем

1.1а Описание практической ситуации.

1.16 Предварительная постановка задачи

1.2 Обобщённые множества решений интервальных уравнений

1.2 а Кванторный формализм

1.26 Интерпретация.

1.2 в Множества АЕ-решений

1.3 Детальная постановка задачи

1.3 а Обсуждение.

1.36 Что такое интервальная "задача оценивания"?

1.3в. Задачи, которые будут рассматриваться.

2 Характеризации и свойства множеств решений

2.1 Интервальные арифметики.

2.1 а Классическая интервальная арифметика.

2.1 б Интервальная арифметика Кахана

2.1 в Неформальное обсуждение.

2.1 г Полная интервальная арифметика.

2.1 д Интервальные векторы и матрицы.

2.1 е Арифметика Каухера—минимаксная интервальная арифметика

2.2 Характеризации множеств АЕ-решений.

2.3 Множества АЕ-решений интервальных линейных уравнений.

2.3 а Кванторный формализм в линейном случае.

2.36 Характеризация и постановки задач

2.4 Управляемое множество решений интервальных линейных систем.

3 Внешнее оценивание множеств решений

3.1 Основы алгебраического подхода

3.2 Оптимальность внешнего оценивания.

3.3 Интервальный метод Гаусса-Зейделя для обобщённых множеств решений

3.4 Исследование обобщённого метода Гаусса-Зейделя.

3.5 Предобуславливание.

3.6 Внешнее оценивание для нелинейных систем.

3.7 Обсуждение и численные эксперименты

4 Оптимальное внешнее оценивание множеств решений

4.1 .Оптимальные решения и их цена.

4.2 Пассивный переборный алгоритм.

4.3 Интервальные методы глобальной оптимизации.

4.4 Методы дробления решений.

4.4 а Решение одномерных включений

4.46 Основной алгоритм.

4.4 в Доказательство сходимости

4.5 Модификации методов дробления решений

4.5 а Оценивание по знакоопределённым брусам.

4.56 Использование локальных решателей.

4.5 в Новая стратегия дробления.

4.5 г Итоговая схема.

4.6 Численные эксперименты с методами дробления решений

4.7 Методы дробления параметров.

4.7 а Общая схема методов.

4.76 Решение линейных систем.

4.8 Модификации методов дробления параметров.

4.8 а Тест на монотонность.

4.86 Стратегия дробления.

4.8 в Влияние базового алгоритма.

4.8 г Отсев бесперспективных записей

4.8 д Итоговая схема алгоритма.

4.9 Численные эксперименты с методами дробления параметров

4.10 Последовательно гарантирующие и финально гарантирующие алгоритмы

5 Внутреннее оценивание множеств решений

5.1 Алгебраический подход.

5.2 Внутреннее оценивание для интервальных линейных систем

5.3 Максимальность внутренних оценок

5.4 Коррекция внутренних оценок.

5.5 Интервальные линейные системы с неотрицательными матрицами

5.5 а Теоретическая основа.

5.5 6 Алгоритм.

5.5 в Выбор начальной точки.

5.5 г Численные эксперименты.

6 Численное нахождение алгебраических решений

6.1 Погружение в линейное пространство.

6.1 а Зачем погружать?

6.16 Определение и основные свойства.

6.1 в Стандартное погружение.

6.1 г Сопутствующие матрицы.

6.1 д Вполне невырожденные матрицы.

6.2 Исследование индуцированных уравнений.

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

6.26 Полиэдральность

СОДЕРЖАНИЕ

6.2 в Оценки субдифференциалов

6.3 Существование и единственность алгебраических решений.

6.4 Субдифференциальный метод Ньютона.

6.4 а Алгоритм.

6.46 Доказательство сходимости

6.4 в Вычисление субдифференциала.

6.5 Численные эксперименты с субдифференциальным методом Ньютона

6.6 Стационарные одношаговые итерационные методы

6.6 а Общий подход: расщепление матрицы ИСЛАУ.

6.66 Отщепление вещественного слагаемого.

6.6 в Треугольное расщепление матрицы системы.

6.7 Численные эксперименты со стационарными итерационными методами

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

Интервальный анализ, по существу, можно рассматривать как вычислительный отдел хорошо знакомого теоретическим математикам многозначного анализа. Но интервальная идея по самой своей сути алгоритмична, требует реализации на машине, и потому неудивительно, что в докомпьютерную эпоху развитие интервального анализа не состоялось. Но уже в 50-е годы, с появлением и распространением первых ЭВМ, потребность в интервальных методах и оценках стала ощущаться столь остро, что пионерские работы по интервальному анализу появились практически одновременно и независимо в Японии, СССР, США и Польше. Первая русская теоретическая работа по интервальному анализу [43] принадлежит перу академика JI.B. Канторовича и опубликована в одном из первых томов "Сибирского математического журнала".

Таким образом, интервальный анализ и интервальные методы первоначально возникли как средство автоматического учета ошибок округлений при счете на ЭВМ с конечной точностью представления чисел (конечной разрядной сеткой). На протяжении ряда лет этот акцент в развитии интервального анализа был доминирующим, и именно так представлена новая научная дисциплина, например, в "Математической энциклопедии" [64] и "Математическом энциклопедическом словаре" [65]. В некоторых странах (например, в Германии) это обстоятельство со временем повлекло за собой даже постепенную эволюцию научной терминологии. Выявилась, в частности, отчетливая тенденция к устранению самих слов "интервальный", "интервальность" и т.п., некогда характеризовавших отдельное и целостное научное направление. Взамен предлагается говорить о надежных/достоверных/научных вычислениях (соответствующие английские термины — reliable/validated/scientific computation). Под влиянием этих веяний название специализированного научного журнала Interval Computations, возникшего как трибуна специалистов по интервальному анализу и его приложениям, было изменено на Reliable Computing.

Однако идеи, положенные в основу нового научного направления, оказались гораздо шире чисто "округленческих" приложений. Вскоре выяснилось, что нарождающиеся интервальные подходы и модели получают чрезвычайно плодотворное применение как язык описания некоторого особого класса неопределённостей, — так называемых ограниченных по амплитуде неопределённостей (соответствующие английские термины — bounded disturbances, bounded error approach, bounded parameter model и т.п.). А.П.Вощинин и Г.Р.Сотиров в учебнике [16] отмечают, что интервальное представление факторов неопределённости "в последнее время привлекает все большее внимание исследователей как наименее ограничительное и отвечающее широкому классу задач." И далее : "Во многих прикладных задачах часто нет оснований или недостаточно информации для того, чтобы рассматривать факторы неопределённости как случайные---- Это приводит к необходимости учета неопределённости нестатистической (или, в общем случае, неизвестной) природы, когда относительно факторов . ничего неизвестно, кроме их свойства быть ограниченными" [16]. В этом же смысле высказываются А.Б.Куржанский в обзоре [53],

B.А.Грановский и Т.Н.Сирая в монографии [22] и другие авторы. Замечательно, что в упомянутой первой отечественной интервальной статье J1. В. Канторовича [43], где новое научное направление еще не называется явно, но рельефно очерчивается, акцент в приложениях нового подхода делается как на повышении точности и надежности численных алгоритмов, так и на перспективах развития аппарата для оперирования с ограниченными неопределённостями.

Характерная черта исследований, в которых интервальный анализ используется для получения математически гарантированных результатов (т.е. автоматического учета ошибок округлений) на ЭВМ с конечной разрядной сеткой — допущение о малости интервалов изменений "входных" данных, позволяющее во многих случаях осуществлять асимптотический анализ и т.п. Но погрешности вычислений необходимо учитывать при этом во всех без исключения операциях на ЭВМ, формирующих окончательный результат. Существенное влияние на работы по этой тематике оказывают конкретные особенности вычислительных машин и процессоров, их архитектура, языки программирования и пр. За обзорами результатов и подробной библиографией по "округленческому" направлению мы отсылаем читателя к книгам Р. Е. Мура [202, 204], Г. Алефельда и Ю. Херцбергера [4],

C. А. Калмыкова, Ю. И. Шокина и 3. X. Юлдашева [42], Р. Б. Кирфотта [174], О. Аберта [118] и другим.

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

Основным объектом рассмотрения в нашей работе является интервальная система уравнений вида i(ab. .,хп) = Ьь

2( аь., а;, £!,.,£„) = Ь2,

0.1) Im( ai? • • • ) а;,. ., = bm, с интервалами ai, ., а¡, bj, ., bOT, которую мы будем также записывать в краткой форме

F( a,x) = b (0.2)

Ж»,*) Гт(а,х) } х — хх \

Х2 \ / и интервальными векторами а - ах N а2

V а I )

Ь = Ьх \ ь2

Ьт )

Для интервальных систем уравнений, у которых количество переменных совпадает с количеством уравнений, нам потребуется также переходить от (0.1)—(0.2) к некоторому специальному виду, в котором вектор переменной выделен в левой части "в чистом виде": х = С?( а,ж),

0.3)

С(а, ж) = ( Ох(а, х), С2(а, х),., (2п(а, х) )т. Интервальные системы (0.1)—(0.3) мы понимаем как формальные записи, обозначающие семейства точечных систем уравнений той же структуры, образованные варьированием параметров ах, ., а\, . ., Ьт в пределах соответствующих интервалов ах, ., а¡, Ь1; ., Ьто.

Значительная часть результатов работы относится не к общим нелинейным системам (0.1)-(0.2), а к более простым (но не менее важным) интервальным линейным системам ацЖх + а12ж2 + . + а.ыхп = Ьх, а21жх + а22ж2 + . + а2па;„ = Ь2, а„хж1 + ал2ж2 + . +

0.4) с интервалами и Ь,-, или в краткой форме

Ах = Ь

0.5) с интервальной матрицей А = (аг; ) и интервальным вектором правой части Ь = (Ьг).

Представляемая работа посвящена решению различных постановок задач, связанных с интервальными системами уравнений (0.1)-(0.2) и (0.4)-(0.5). Но собственно математическим результатам мы предпосылаем исследование процесса постановки и формулировки интервальных задач. Необходимость детального рассмотрения этого вопроса является очень насущной и вызвана его неразработанностью в современном интервальном анализе, а также общей методологической и терминологической запутанностью.

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

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

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

Как мы уже отмечали, исторически интервальный анализ возник из необходимости учета ошибок вычислений и задач чувствительности. Поэтому неудивительно, что на первоначальном этапе своего развития множество решений задачи с интервальными данными понималось как множество всевозможных решений точечных задач с коэффициентами, могущими принимать значения из заданных интервалов. В частности, для интервальных систем алгебраических уравнений вида (0.1)—(0.2) в течение многих лет единственным рассматривавшимся множеством решений было так называемое объединённое множество решений zuni = {х е Rn I (За € а)(36 G b)(F(a,x) = b)}, образованное всеми решениями систем F(a,x) = 6са€аи6<ЕЬ. Для случая интервальных линейных систем это определение выглядит так

2ы(А, Ь) = { г б Г1 | (ЗА € А)(3 Ь е Ь).(Ае = 6)}.

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

По мере развития интервальных методов и расширения сферы их приложений постепенно выяснилось, что обыденное понимание множества решений интервальной системы уравнений (неравенств и т.п.) как множества всевозможных решений вещественных систем того же вида с параметрами из указанных интервалов не приложимо в ряде практически важных интервальных задач. Таковой, является, например, линейная задача о допусках, осознанная в эконометрике [241, 242] и позже в 80-е годы в теории автоматического управления для объектов с интервальными неопределённостями в данных (см. работы H.A. Хлебалина [85, 86, 81], Е.М. Смагиной и И.В. Дугаровой [27, 82, 298] и других авторов). Решение линейной задачи о допусках приводит к необходимости рассмотрения так называемого допустимого множества решений интервальных линейных систем вида (0.4)—(0.5), образованного всеми такими векторами х £ R", что произведение Ах попадает в b для любой матрицы А £ А. Формально это множество определяется как

Ы(А,Ь) = {z £ Rn I (VA € А)(Эb G b){Ax = b)}, и впервые оно было рассмотрено еще в 1972-м году немецким исследователем Е. Нудингом в [223]ол. На наш взгляд, работа Нудинга [223] явилась пионерским вкладом в интервальный анализ и была по достоинству оценена уже в 90-е годы. Нудинг, в действительности, продемонстрировал нам возможность варьирования логических кванторов в выделяющем предикате при определении множества решений интервальной задачи. Следующий шаг на этом пути был сделан лишь в 1991-92 годах, когда несколько российских исследователей независимо и почти одновременно столкнулись с необходимостью введения множества решений

ЕсЫ(А, Ъ) = { х € ЕГ | (У6 6 Ь)(3 А е А)(Ах = Ь) }, образованного такими векторами х е К.71, что для любого желаемого вектора Ь € Ь мы можем подобрать соответствующую матрицу А € А удовлетворяющую Ах = 6. В работах [274, 289] С.П. Шарый предложил называть его управляемым множеством решений и, похоже, термин постепенно привился в литературе.

Заметим, что символическое обозначение (V А 6 А) означает (V ац € ац)(\/о12 € а.12) • • • (V 0-тп € а тп) и то же самое верно в отношении (ЗА € А), (У6 € Ь) и (3 Ь 6 Ь). Кроме того, кванторы V и 3 не коммутируют друг с другом. Следовательно дальнейшее обобщение понятия множества решений интервальной линейной системы можно получить, разделив действие логических кванторов по отдельным элементам матрицы и правой части и далее комбинируя кванторы V и 3 с различными интервальными параметрами и меняя их порядок. Мы покажем в работе, что такие множества решений не являются чисто теоретическим курьёзом но могут быть проинтерпретированы как решения некоторых игр или многошаговых процессов принятия решений в условиях интервальной неопределенности, т.е. как решения минимаксных задач исследования операций.

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

По-видимому, исторически первая постановка для интервальных систем уравнений — это задача внешнего покоординатного оценивания множества всевозможных решений точечных систем, содержащихся в (0.1)-(0.2) (или в (0.4)-(0.5)), т.е. объединённого множества решений этих интервальных систем уравнений. Как правило, её формулируют в следующем виде

0.6)

Фактически — это интервальная форма задачи о чувствительности решения системы уравнений к конечным возмущениям. Часто, имея в виду именно эту задачу, говорят (не совсем корректно) о "решении интервальной системы уравнений".

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

01В оригинальной статье [223] сам Нудинг называл его множеством внутренних решений. найти интервальный вектор V, включающий объединённое множество решений интервальной системы уравнений. появлялись задолго до выхода в свет классической книги P.E. Мура [202], с которой, как принято считать, и началось быстрое развитие интервального анализа. В частности, первой русской работой о характеризации и оценивании объединённого множества решений ИСЛАУ была статья Б.И. Белова и Е.Г. Анциферова [7]. К настоящему времени среди общей массы публикаций по интервальной математике доля тех, в которых рассматриваются различные аспекты решения "внешней" задачи для ИСЛАУ, — одна из наибольших.

Практические приложения "внешней" задачи для ИСЛАУ многочисленны и разнообразны. Е.К. Корноушенко в цикле статей [48] сводит к решению этой задачи проблему оценивания множества достижимых состояний линейной стационарной системы. В работе Н.К. Пылаева и И.Б. Ядыкина [79] "внешняя задача" естественно возникает в связи с синтезом интервального управления по неявной эталонной модели. В.З. Манусов, С.М. Моисеев и С.Д. Перков в [63] приводят к "внешней задаче" для ИСЛАУ решение некоторых линейных задач электротехники с интервальными неопределённостями во входных параметрах. В последние годы работами многих исследователей интенсивное развитие получили методы идентификации систем управления в условиях ограниченных возмущений их параметров (см. обзор А.Б. Куржанского [53] и книгу Э. Вольтера и Л. Пронцато [302]). Для случая систем, описываемых линейными зависимостями "вход-выход", математической основой этих методов также служит решение "внешней задачи" для ИСЛАУ, как правило, с прямоугольными интервальными матрицами.

Кроме отмеченных выше приложений в технике и естествознании "внешняя задача" для ИСЛАУ имеет и более опосредованные применения. Например, на каждом шаге популярного интервального метода Ньютона требуется решать "внешние задачи" для некоторых промежуточных ИСЛАУ [159]. С необходимостью решения "внешней задачи" для интервальных систем алгебраических уравнений (линейных или нелинейных) сталкиваются при дискретизации различных интервальных версий краевых задач для дифференциальных уравнений (см. [42, 266]) и интегральных уравнений [26]. В интервальном методе наименьших квадратов [151] построение регрессионной прямой по заданному семейству результатов наблюдений, имеющих интервальную неопределённость, также сводится к решению "внешней задачи" для ИСЛАУ.

За прошедшие три десятилетия методология решения "внешней задачи" претерпела эволюцию от подражания известным вещественным методам решения СЛАУ (метод Гаусса, простой итерации и т.п.) до создания самостоятельных "интервальных" концепций и подходов. Хорошие обзоры методов решения задачи внешнего оценивания объединённого множества решений ИСЛАУ (по состоянию на середину 80-х годов) были сделаны А. Ной-майером в [208, 212]. Немало материалов, касающихся интервальных алгебраических систем (линейных, в частности), воспроизведено в широко известных монографиях Р. Мура [202, 204], Г. Алефельда и Ю. Херцбергера [4], А. Ноймайера [212], С.А. Калмыкова, Ю.И. Шокина и З.Х. Юлдашева [42], Б.С. Добронца и В.В. Шайдурова [26], Р.Б. Кир-фотта [174]. Тем не менее, на сегодняшний день подавляющая часть результатов по этой теме остается разбросанной по разрозненным журнальным публикациям. Среди работ последних лет отметим статьи Ю. Гарлоффа [148], Д. Гея [149], монографию Р.Б. Кирфот-та [174], работы Г. Майера по выяснению условий применимости интервального метода Гаусса [198, 199, 200], капитальную монографию А. Ноймайера [212] и его последующие статьи [213, 214], многочисленные исследования И. Рона [240, 249, 250, 251, 255], 3. Румпа [259, 261], X. Швандта [265].

В последние годы в связи с бурным развитием теории и практики параллельных вычислений все возрастающее количество публикаций посвящается реализации различных интервальных алгоритмов на векторных и параллельных ЭВМ. Решение на таких вычислителях "внешней задачи" для ИСЛАУ рассмотрено, например, в [266].

Интересно сопоставить саму интервальную постановку задачи о внешнем оценивании множеств решений (0.6) и интервально-аналитические подходы к её решению с другими методиками, которые более или менее успешно применялись и применяются для решения задач, аналогичных (0.6). Это, во-первых, широко известные методы анализа чувствительности решений систем уравнений [150, 211] и, во-вторых, так называемые методы гарантированной точности для решений систем уравнений, интенсивно развивавшиеся в работах школы С.К. Годунова [20].

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

В методах гарантированной точности из [20] вариации параметров (коэффициентов) системы вообще рассматриваются как некоторый нежелательный паразитный эффект, искажающий исходно точную постановку задачи. В связи с такой методологической установкой, а также из-за особенностей применяемой в [20] техники "большие" изменения параметров решаемой системы (иначе называемые также крупномасштабными или нелокальными) школой С.К. Годунова просто не рассматриваются. Напомним, что в современном интервальном анализе "очень широкие" интервальные данные в системах (0.1)—(0.2) и (0.4)-(0.5) также вызывают затруднения, но задачи для интервальных линейных систем с сильно невырожденными интервальными матрицами (см. Определение 3.5.1) надежно решаются без особых проблем. Наконец, как вариации параметров системы, так и оценки вариаций решения С.К. Годунов и его последователи измеряют отклонением по норме (т.е.' одним числом), тогда как в интервальном анализе в постановке задачи и ответе неопределённость с гораздо большей степенью детализации описывается многомерным интервалом.

Изложим кратко содержание представляемой диссертационной работы. Структурно она состоит из Введения, указателя обозначений, собственно основного текста, разбитого на шесть Глав и списка литературы. Мы предполагаем уже известными читателю основные понятия и факты интервального анализа, не уделяя их развёрнутому изложению специального места в диссертации (для введения в предмет мы рекомендуем, например, книги [4, 26, 42, 159, 174, 212]). Вместо этого, чтобы придать тексту самодостаточный характер, необходимые известные результаты даны конспективно и с подробными литературными ссылками.

Выход

Cx ©d = 0.

Алгоритм р{ ~ d, e J2 hüx

END DO

DO FOR i = n - 1 TO 1

END DO d := расстояние между x и x; x := x.

END DO

6.7 Численные эксперименты со стационарными итерационными методами

Пример 1, неоднократно рассматривавшаяся нами интервальная линейная система

2,4] [-2,1] \ / [-2,2] [-1,2] [2,4] ) Х I [—2,2]

2.44) из [124]. Алгоритм Кеа13р1зЛ; за 10 итераций дает 3 верных значащих цифры точного

3' ответа (|, |)т, а за 20 итераций — б верных значащих цифр, что по порядку трудозатрат сравнимо с итерационным методом из [36, 37, 306], основанным на отщепления главной диагонали матрицы ИСЛАУ. Такие же показатели достигаются алгоритмом 11еа13р1:]^ и при нахождении алгебраического решения системы (2.44) с дуализованной матрицей (которая возникает, к примеру, при внутреннем оценивании объединённого множества решений для (2.44)).

Пример 2. Рассмотрим интервальную линейную 40 х 40-систему [1.8,2.2] [-1.1,-0.9] • д

-1.1,-0.9] [1.8,2.2] [-1.1,-0.9] [-1.1,-0.9] [1.8,2.2] 0

1.8,2.2] [-1.1,-0.9] [0.9,1.1] \

1.8,2.2]

2.7,3.3]

X —

35.1,42.9]

1 [36,44] ) матрица которой получена из известной трехдиагональной матрицы, аппроксимирующеи вторую производную на симметричном шаблоне, путём 10%-ного уширения элементов, а правая часть получена таким же уширением вектора юл 10

10 v 10 у

6.79)

Как и в случае с субдифференциальным методом Ньютона, ни она сама, ни ИСЛАУ с дуализованной матрицей не представляют серьёзного труда для методов §6.6. Основанный на вещественном расщеплении алгоритм 11еа13р1з^ уже за 16 итераций находит 12-13 верных значащих цифр для концов компонент алгебраических решений и исходной интервальной системы и системы с дуализованной матрицей. Ниже на отдельной странице мы приводим эти алгебраические решения, сохраняя по шесть знаков после запятой.

Совершенно аналогичная картина быстрой сходимости алгоритма ИеаХЗрШ; наблюдается при вычислении алгебраических решений ИСЛАУ с правой частью (6.79 и матрицами, которые являются 10%-уширениями матриц (4.48) и (4.50), рассмотренных нами вслед за [152, 301]. [221.680216,182.261640] \ [433.306233,354.567627] [632.818428,518.603104] [822.168021,672.771618] [999.512195,818.580931] [1166.585365,954.611973] [1321.761517,1082.195121] [1466.558265,1200.088691] [1599.566395,1309.445676] [1722.086720,1409.201773] [1832.926829,1500.332594] [1933.170731,1581.951219] [2021.842818,1654.855875] [2099.810298,1718.337028] [2166.314363,1773.015521] [2222.005420,1818.359201] [2266.341463,1854.811529] [2299.756097,1882.017738] [2321.924119,1900.243902] [2333.062330,1909.312638] [2333.062330,1909.312638] [2321.924119,1900.243902] [2299.756097,1882.017738] [2266.341463,1854.811529] [2222.005420,1818.359201] [2166.314363,1773.015521] [2099.810298,1718.337028] [2021.842818,1654.855875] [1933.170731,1581.951219] [1832.926829,1500.332594] [1722.086720,1409.201773] [1599.566395,1309.445676] [1466.558265,1200.088691] [1321.761517,1082.195121] [1166.585365,954.611973] [999.512195,818.580931] [822.168021,672.771618] [632.818428,518.603104] [433.306233,354.567627] [221.680216,182.261640] , [181.374722,222.764227] \ [354.523281,433.360433] [517.760532,633.848238] [672.682926,822.276422] [817.782705,1000.487804] [954.478935,1166.747967] [1081.441241,1322.682926] [1199.911308,1466.775067] [1308.736141,1600.433604] [1408.980044,1722.357723] [1499.667405,1833.739837] [1581.685144,1933.495934] [1654.235033,2022.601626] [1718.026607,2100.189701] [1772.439024,2167.018970] [1818.004434,2222.439024] [1854.279379,2266.991869] [1881.618625,2300.243902] [1899.756097,2322.520325] [1908.869179,2333.604336] [1908.869179,2333.604336] [1899.756097,2322.520325] [1881.618625,2300.243902] [1854.279379,2266.991869] [1818.004434,2222.439024] [1772.439024,2167.018970] [1718.026607,2100.189701] [1654.235033,2022.601626] [1581.685144,1933.495934] [1499.667405,1833.739837] [1408.980044,1722.357723] [1308.736141,1600.433604] [1199.911308,1466.775067] [1081.441241,1322.682926] [954.478935,1166.747967] [817.782705,1000.487804] [672.682926,822.276422] [517.760532,633.848238] [354.523281,433.360433] ^ [181.374722,222.764227] у

Отметим, что во всех рассмотренных в этом пункте системах интервальные матрицы не являются строго невырожденными.

Пример 3. Для интервальной линейной 40 х 40-системы с матрицей Ноймайера

40 [0,2] [0,2] 40

0,2] [0,2] \ [0,2] [0,2]

6.80)

0,2] [0,2] ••• 40 [0,2] V [0,2] [0,2] . [0,2] 40 . (т.е. матрица системы (4.46) с параметром 2 — 40) и с вектором правой части [Ю,20] N [10,20]

6.81)

10,20] у алгоритм RealSpl.it за 40 итераций находит приближение к алгебраическому решению [0.25,0.16949152542] ^ [0.25,0.16949152542]

0.25,0.16949152542] с точностью порядка Ю-8.

Совершенно то же самое можно наблюдать и при вычислении алгебраического решения ИСЛАУ с дуализованной матрицей (6.80) и правой частью (6.81). Интересная особенность этого примера — вырожденность интервальной матрицы ИСЛАУ (см. [212]), несмотря на которую развитые нами алгоритмы успешно считают алгебраическое решение.

Пример 4. Для интервальной линейной 7 х 7-системы [4,6] [-9,0] [0,12] [2,3] [5,9] [-23,-9] [15,23] ^ { [-10,95] >

0,1] [6,10] [-1,1] [-1,3] [-5,1] [1,15] Н,-1] [35,14]

0,3] [-20,-9] [12,77] [-6,30] [0,3] [-18,1] [0,1] [-6,2]

Н,1] [-1Д] [-3,1] [3,5] [5,9] [1,2] [1,4] х = [30,7]

0,3] [0,6] [0,20] [-1,5] [8,14] [-6,1] [10,17] [4,95]

-7, -2] [1,2] [7Д4] [-3,1] [0,2] [3,5] [-2Д] [-6,46] [-1,5] [-3,2] [0,8] [1,И] [-5,10] [2,7] [6,82] ) ^ [-2,65] J из работы [282] алгоритм Яеа13р1:^ расходится, но, как мы уже отмечали, алгебраическое решение может быть успешно вычислено с помощью субдифференциального метода Ньютона (за 9 итераций при значении релаксационного параметра т = 1).

ГЛАВА 6. НАХОЖДЕНИЕ АЛГЕБРАИЧЕСКИХ РЕШЕНИЙ 246

При сужении (7,7)-элемента матрицы появляется сходимость алгоритма 11еа13р1гЬ к алгебраическому решению, но она очень медленная. Например, при а7г = [8,82] для получения 5 верных значащих цифр алгоритму требуется около сотни итераций. Резюмируя этот пример, можно сказать, что он весьма убедительно демонстрирует преимущество субдифференциального метода Ньютона не только по эффективности, но и в том, что касается сферы применимости и универсализма.

1. АЩЕПКОВ Л. Т. К проблеме повышения живучести управляемых систем // Модели и методы исследования операций, под ред. Б. А. Бельтюкова и В. П. Булатова. -Новосибирск: Наука, 1988. С. 69-85.

2. Бауэр Ф. Л., Гооз Г. Информатика. В 2-х ч. Москва: Мир, 1990.

3. Белов Б. И., Анциферов Е. Г. К установлению линейной зависимости в условиях неопределённости исходных данных // Информационный сборник трудов Вычислительного Центра ИрГУ; выпуск II. Иркутск: Изд-во Иркутского университета, 1968. - С. 143-147.

4. БИРКГОФ Г. Теория решеток. Москва: Наука, 1984.

5. БИРКГОФ Г., БАРТИ Т. Современная прикладная алгебра. Москва: Мир, 1976.

6. Борель Э. Вероятность и достоверность. Москва: Физматгиз, 1961.

7. ВАТОЛИН А. А. О задачах линейного программирования с интервальными коэффициентами // Журнал Вычисл. Математики и Матем. Физики. 1984. - Т. 24. -С. 1629-1637.

8. Вербицкий В. И., Горбань А. Н., Утю баев Г. Ш., Шокин Ю. И. Эффект Мура в интервальных пространствах // Доклады Академии Наук. 1989. - Т. 304, №1. - С. 17-22.

9. ВОЕВОДИН В. В., КУЗНЕЦОВ Ю. А. Матрицы и вычисления. Москва: Наука, 1984.

10. ВОЩИНИН А. П., СОТИРОВ Г. Р. Оптимизация в условиях неопределенности. -Москва-София: Издательство МЭИ-Техника, 1989.

11. ГАГАНОВ А. А. О сложности вычисления интервала значений полинома от многих переменных // Кибернетика. 1985. - №4. - С. 6-8.

12. Гантмахер Ф. Р. Теория матриц. Москва: Наука, 1988.19. гермейер Ю. Введение в теорию исследования операций. Москва: Наука, 1971.

13. Годунов С.К., Антонов А.Г., КИРИЛЮК О.П., Костин В.И. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах.- Новосибирск: Наука, 1988.

14. Голуб Дж., ван Лоан Ч. Матричные вычисления. Москва: Мир, 1998.22. грановский В. Г., Сирая Т. Н. Методы обработки экспериментальных данных при измерениях. Ленинград: Энергоатомиздат, 1990.

15. Гэри м., джонсон д. Вычислительные машины и труднорешаемые задачи. -Москва: Мир, 1982.

16. ДЕМЬЯНОВ В. Ф., МаЛОЗЕМОВ В. Н. Введение в минимакс. Москва: Наука, 1972.

17. ДЭННИС Дж., мл., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. Москва: Мир, 1988.26. добронец Б. С., шайдуров В. В. Двусторонние численные методы. Новосибирск: Наука, 1990.

18. ДУГАРОВА И. В., СМАГИНА Е. М. Обеспечение устойчивости системы с неопределенными параметрами // Автоматика и Телемеханика. 1990. - №11. - С. 176-181.

19. ЕВТУШЕНКО Ю.Г. Численный метод нахождения глобального экстремума функции // Журнал Вычисл. Математики и Матем. Физики. 1971. - Т. 11. - С. 1390-1403.

20. ЕВТУШЕНКО Ю.Г., РАТЬКИН В.А. Метод половинных делений для глобальной оптимизации функции многих переменных // Известия АН СССР. Техническая кибернетика. 1987. - №1. - С. 119-128,

21. ЕРЕМИН И. И. Противоречивые модели оптимального планирования. Москва: Наука, 1988.31. жйглявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума.- Москва: Наука, 1991. г

22. ЗаманскиЙ М. Введение в современную алгебру и анализ. Москва: Наука, 1974.

23. ЗЮЗИН В. С. Итерационный метод решения системы алгебраических сегментных уравнений первого порядка // Дифференциальные уравнения и теория функций (выпуск 8). Саратов: Изд-во Саратовского университета, 1989. - С. 72-82.

24. Ив лев P.C. Построение и исследование свойств многомерных систем управления интервально-заданными объектами. Диссертация . канд. техн. наук. Алматы: ИПИУ HAH Республики Казахстан, 1999.

25. Ив лев Р. с., соколова С. П. Построение векторного управления многомерным интервально-заданным.объектом // Вычислительные Технологии. 1999. - Т. 4, №4.- С. 3-13.

26. Исследование операций. Методологические основы и математические методы, под ред. Дж. Моудера и С. Элмаграби. Москва: Мир, 1981.41. калман Р., Фале П., АРБИБ М. Очерки по математической теории систем. -Москва: Мир, 1971.

27. Калмыков С. А., Шокин Ю. И., Юлдашев 3. X. Методы интервального анализа. Новосибирск: Наука, 1986.

28. КАНТОРОВИЧ J1.B. О некоторых новых подходах к вычислительным методам и обработке наблюдений // Сибирский Математический Журнал. 1962. - Т. 3, №5. -С. 701-709.

29. Канторович JI. В., Акилов Г. П. Функциональный анализ. Москва: Наука, 1984.

30. Карлюк А.Ю. Численный метод нахождения алгебраического решения ИСЛАУ, основанный на треугольном расщеплении // Вычислительные Технологии. Т. 4, №4. - С. 14-23.

31. КЛИНИ С. К. Математическая логика. Москва: Мир, 1973.

32. КРАСНОСЕЛЬСКИЙ М. А., ЗабреЙКО п. п. Геометрические методы нелинейного анализа. Москва: Наука, 1975.

33. Красносельский М. А., Лифшиц Е. А., Соболев А. В. Позитивные линейные системы. Москва: Наука, 1985.

34. Куратовский К., Мостовский А. Теория множеств. Москва: Мир, 1970.

35. КУРЖАНСКИЙ А. Б. Задача идентификации — теория гарантированных оценок // Автоматика и Телемеханика. 1991. - №4. - С. 3-26.

36. КУРОШ А. Г. Лекции по общей алгебре. Москва: Наука, 1973.

37. КУРПЕЛЬ Н. С., ШУВАР Б. А. Двусторонние операторные неравенства и их применения. Киев: Наукова думка, 1980.

38. ЛАКЕЕВ А. В. Оценка спектрального радиуса нерасширяющих матриц // Вычислительные Технологии. 1998. - Т. 3, №2. - С. 21-30.

39. ЛАКЕЕВ А. В. Существование и единственность алгебраических решений интервальных линейных систем в полной арифметике Каухера // Вычислительные Технологии. 1999. - Т. 4, №4. - С. 33-44.

40. Ли Э. Б., МАРКУС Л. Основы теории оптимального управления. Москва: Наука, 1972.62. мальцев А. И. Основы линейной алгебры. Москва: Наука, 1970.

41. Манусов В.З., Моисеев С.М., Перков С.Д. Интервальный анализ в задачах расчета токов короткого замыкания // Техническая электродинамика. 1987. - №5.- С. 13-18.

42. Математическая энциклопедия. Том 2. Москва: Советская Энциклопедия, 1979.

43. МЕСАРОВИЧ М., ТАКАХАРА Я. Общая теория систем: математические основы. Москва: Мир, 1978.

44. НИКАЙДО X. Выпуклые структуры и математическая экономика. Москва: Мир, 1972.

45. Обэн Ж.-П. Нелинейный анализ и его экономические приложения. Москва: Мир, 1988.

46. ОБЭН Ж.-П. и Экланд И. Прикладной нелинейный анализ. Москва: Мир, 1988.

47. Панков П. С. Доказательные вычисления на ЭВМ. Диссертация . докт. физ.-мат. наук. Фрунзе: Институт Математики АН Киргизской ССР, 1985.76. пападимитриу X., стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Москва: Мир, 1985.

48. ПИЯВСКИЙ С.А. Один алгоритм отыскания абсолютного экстремума функции // Журнал Вычисл. Математики и Матем. Физики. 1972. - Т. 12, №4. - С. 888-896.78. пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. Москва: Наука, 1980.

49. ПЫЛАЕВ Н. К., ядыкин И. Б. Интервальные алгоритмы адаптивного управления с неявной эталонной моделью // Автоматика и Телемеханика. №6. С. 63-72.

50. Рокафеллар Р. Выпуклый анализ. Москва: Мир, 1973.

51. СМАГИНА Е. М., ДУГАРОВА И. В. Синтез модального регулятора для системы с неопределенными параметрами. Москва, 1987. - 38 с. - Депонировано в ВИНИТИ, №789-В87.

52. СУХАРЕВ А. Г. Минимаксные алгоритмы в задачах численного анализа. Москва: Наука, 1989.

53. ХАЧИЯН Л.Г, Полиномиальный алгоритм в линейном программировании // Доклады Академии Наук. 1979. - Т. 244, №. - С. 1093-1096.

54. ХЛЕБ АЛИК Н. А. Аналитический метод синтеза регуляторов в условиях неопределённости параметров объекта // Аналитические методы синтеза регуляторов. -Саратов: Саратовский политехнический ин-т, 1981. С. 107-123.

55. ХЛЕБАЛИН Н. А. Синтез интервальных регуляторов в задаче модального управления // Аналитические методы синтеза регуляторов. Саратов: Саратовский политехнический ин-т., 1988. - С. 26-30.

56. ХЛЕБАЛИН H.A., Шокин Ю.И. Интервальный вариант метода модального управления // Доклады Академии Наук. 1991. - Т. 316, №4. - С. 846-850.

57. Хорн Р., Джонсон Ч. Матричный анализ. Москва: Мир, 1989.

58. ЧЕРНИКОВ С.Н. Линейные неравенства. Москва: Наука, 1968.

59. ЧЕРНОУСЬКО Ф. Л. Оценивание фазового состояния динамических систем. Москва: Наука, 1988.

60. ШаЙДУРОВ В. В., ШАРЫЙ С. П. Решение интервальной алгебраической задачи о допусках. Красноярск, 1988. - 27 с. - (Препринт / ВЦ СО АН СССР ; №5).

61. ШАЙДУРОВ В. В., ШАРЫЙ С. П. Интервальная алгебраическая задача о допусках // Информационно-оперативный материал (интервальный анализ). Красноярск, 1988. - (Препринт / ВЦ СО АН СССР; №6). - С. 38-40.

62. ШаЙДУРОВ В. В., ШАРЫЙ С. П. Некоторые методы решения линейной задачи о допусках // Информационно-оперативный материал (интервальный анализ). Красноярск, 1989. - (Препринт / ВЦ СО АН СССР; №9). - С. 38-41.

63. ШАРАЯ И. А. О максимальной внутренней оценке множеств решений интервальных линейных систем // Вычислительные Технологии. 1998. - Т. 3, №2. - С. 55-66.

64. ШАРЫЙ С. П. Об одной интервальной задаче линейной алгебры // Информационно-оперативный материал. Красноярск, 1987. - (Препринт / ВЦ СО АН СССР; №2). - С. 45-46.

65. ШАРЫЙ С. П. О некоторых методах решения линейной задачи о допусках. Красноярск, 1989. - 45 с. - (Препринт / ВЦ СО АН СССР; №6).

66. ШАРЫЙ С. П. Об оптимальном решении интервальных систем линейных алгебраических уравнений. I. Красноярск, 1989. - 24 с. - Депонировано в ВИНИТИ, №4180-В89.

67. ШАРЫЙ С. П. К вопросу разрешимости линейной задачи о допусках. Красноярск, 1990. - 8 с. - Депонировано в ВИНИТИ, №3353-В89.

68. ШАРЫЙ С. П. О характеризации объединенного множества решений интервальной линейной алгебраической системы. Красноярск, 1990. - 20 с. - Депонировано в ВИНИТИ, №726-В91.

69. ШАРЫЙ С. П. Оптимальное решение интервальных систем линейных алгебраических уравнений // Информационно-оперативный материал. Часть 1 (интервальный анализ). Красноярск, 1990. - (Препринт / ВЦ СО АН СССР; №16). - С. 39-41.

70. ШАРЫЙ С. П. О разрешимости линейной задачи о допусках // Interval Computations.- 1991. №1. - С. 92-97.

71. ШАРЫЙ С. П. Новый класс алгоритмов для оптимального решения интервальных линейных систем // Конференция "Актуальные проблемы прикладной математики", Саратов, 20 22 мая 1991 г. - Саратов, 1991. - С. 113-119.

72. ШАРЫЙ С. П. Решение "внешней" и "внутренней" задач для интервальной системы линейных алгебраических уравнений. Диссертация на соискание учёной степени кандидата физико-математических наук. Красноярск: ВЦ СО РАН, 1992. - 212 с.

73. ШАРЫЙ С. П. Решение "внешней" и "внутренней" задач для интервальной системы линейных алгебраических уравнений. Автореферат диссертации на соискание учёной степени кандидата физико-математических наук. Красноярск: ВЦ СО РАН, 1992.- 45 с.

74. ШАРЫЙ С. П. Линейные статические системы с интервальной неопределенностью: эффективные алгоритмы для решения задач управления и стабилизации. Красноярск, 1994. - 13 с. - (Препринт / ВЦ СО РАН; №7).

75. ШАРЫЙ С. П. Алгебраический подход к анализу статических систем с интервальной неопределённостью // 10-я Байкальская школа-семинар "Методы оптимизации и их приложения". Иркутск: СЭИ, 1995. - С. 141-142.

76. ШАРЫЙ С. П. Линейные статические системы с интервальной неопределенностью: эффективные алгоритмы для решения задач управления и стабилизации // Вычислительные Технологии (Сборник научных трудов ИВТ СО РАН, Т. 4, №13), Новосибирск, 1995. С. 64-80.

77. ШАРЫЙ С. П. Алгебраический подход к анализу линейных статических систем с интервальной неопределённостью // Актуальные проблемы информатики, прикладной математики и механики. Красноярск: ВЦ СО РАН, 1995. - С. 331-356.

78. П1АРЫЙ С. П. Численное нахождение алгебраического решения интервальных линейных систем // Дискретная математика. Красноярск: КГТУ, 1996. - С. 129— 145.

79. ШАРЫЙ С. П. Алгебраический подход к анализу линейных статических систем с интервальной неопределённостью // Известия РАН. Теория и системы управления. 1997. - №3. - С. 51-61.

80. ШАРЫЙ С. П. Новый подход к анализу статических систем с интервальной неопределённостью в данных // Вычислительные Технологии. 1997. - Т. 2, №1/ -С. 84-102.

81. ШАРЫЙ С. П. Интервальный анализ: прошлое, настоящее и будущее // Наука в Сибири. 1997. - №41 (2127). - С. 3.

82. ШАРЫЙ С. П. Алгебраический подход во "внешней задаче" для интервальных линейных систем // Вычислительные Технологии. 1998. - Т. 3, №2. - С. 67-114.

83. ШАРЫЙ С.П. Анализ чувствительности интервальных линейных статических систем // Труды XI международной Байкальской школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 5-12 июля 1998 г., секция 4■ ~ Иркутск: ИСЭМ, 1998. С. 187-190.

84. AsaitHAMBI n. s., shen ZuHE, Moore r. e. On computing the range of values // Computing. 1982. - Vol. 28, №3. - P. 225-237.

85. Aubin J.-P. Viability Theory. Boston: Birkhäuser, 1991.

86. BAUMANN M. Numerical experience with methods for solving an interval linear system // Freiburger Intervall-Berichte. 1984. - №7. - S. 61-66.

87. CAPRANI O., MADSEN K. Iterative methods for interval inclusion of fixed points // BIT. 1978. - Vol. 18. - P. 42-51.

88. CAPRANI O., MADSEN K. Experiments with interval methods for nonlinear systems // Freiburger Intervall-Berichte. 1981. - №7. - S. 1-13.

89. CHIRIAEV D., WALSTER G. W. Interval Arithmetic Specification. Файл в формате PostScript доступен в Интернете по адресуhttp://www.mscs.mu.edu/~georgec/Classes/GlobSol/Papers/spec.ps

90. COXSON G. E. Computing exact bounds on elements of an inverse interval matrix is NP-hard // Reliable Computing. 1999. - Vol. 5. - P. 137-142.

91. Dean T. L., Boddy M. An analysis of time dependent planning // Proceedings of AAAI-88 Conference. St. Paul, 1988. - P. 49-54.

92. DEIF A- S. Sensitivity Analysis in Linear Systems. Berlin: Springer-Verlag, 1986.

93. Dimitrova N.S., Markov S.M., Popova E.D. Extended interval arithmetics: new results and applications // Computer Arithmetic and Enclosure Methods; Atanassova L. and Herzberger J., eds. Amsterdam: Elsevier, 1992. - P. 225-232.

94. DOBRONETS B. S. On some two-sided methods for solving systems of ordinary differential equations // Interval Computations. 1992. - №1(3). - P. 6-21.

95. FlLIPPOV A. F. Ellipsoidal estimates for a solution of a system of differential equations // Interval Computations. 1992. - №2(4). - P. 6-17.

96. Fujii Y., ICHIDA K., OzASA M. Maximization of multivariable functions using interval analysis // Interval Mathematics 1985; K. Nickel, ed. New York: Springer Verlag, 1986.- P. 17-26. (Lecture Notes in Computer Science; vol. SIS).

97. Gardenes E., Trepat A. Fundamentals of SIGLA, an interval computing system over the completed set of intervals // Computing. 1980. - Vol. 24. - P. 161-179

98. Gardenes E., Trepat A., Janer J. M. SIGLA-PL/1 development and applications // Interval Mathematics 1980; Nickel K., ed. New York: Academic Press, 1980. - P. 301315.

99. Gardenes E., Trepat A., Janer J. M. Approaches to simulation and to the linear problem in the SIGLA system // Freiburger Intervall-Berichte. 1981. - №81/8. - P. 128.

100. Gardenes E., Trepat A., Mielgo H. Present perspective of the SIGLA interval system // Freiburger Intervall-Berichte. 1982. - №82/9. - P. 1-65.

101. Gardenes E., Mielgo H., Trepat A. Modal intervals: reason and ground semantics // Interval mathematics 1985; Nickel K., ed. Berlin: Springer Verlag, 1986. - P.

102. GaRLOFF J. Block methods for the solution of linear equations // SIAM Journal on Matrix Analysis and Applications. 1990. - Vol. 11. - P. 89-106.

103. Gay D. M. Solving interval linear equations // SIAM Journal on Numerical Analysis.- 1982. Vol. 19, №4. - P. 858-870.

104. Gay D. M. Computing perturbation bounds for nonlinear algebraic equations // SIAM Journal on Numerical Analysis. 1983. - Vol. 20. - P. 638-651.

105. Gay D. M. Interval least squares — a diagnostic tool // Reliability in Computing; Moore R. E., ed. New York: Academic Press, 1988. - P. 183-205.

106. Gregory R.T, Karney D.L. A Collection of Matrices for Testing Computational Algorithms. New York: Wiley Interscience, John Wiley and Sons, 1969.

107. HANSEN E. R. Global optimization using interval analysis — the multidimensional case // Numerische Mathematik. 1980. - Vol. 34, №3. - P. 247-270.

108. Hansen E. Bounding the solution of interval linear equations // SIAM Journal on Numerical Analysis. 1992. - Vol. 29, №5. - P. 1493-1503.159. hansen e. Global Optimization Using Interval Analysis. New York: Marcel Dekker, 1992.

109. Hansen E. R., greenberg R. I. An interval Newton method // Applied Mathematics and Computation. 1983. - Vol. 12. - P. 89-98.

110. KAUCHER E. Algebraische Erweiterungen der Intervallrechnung unter Erhaltung Ord-nungs- und Verbandsstrukturen // Computing Supplement. 1977. - Vol. 1. - P. 65-79.

111. KAUCHER E. Interval analysis in the extended interval space IR // Computing Supplement. 1980. - Vol. 2. - P. 33-49.

112. KEARFOTT R. B. Preconditioners for the interval Gauss-Seidel method // SIAM Journal on Numevical Analysis. 1990. - Vol. 27, №3. - P. 804-822.

113. KEARFOTT R. B. Rigorous Global Search: Continuous Problems. Dordrecht: Kluwer, 1996.

114. KELLING B. Geometrische Untersuchungen zur eigenschränkten Lösungsmenge Intervallgleichungssysteme // ZAMM. 1994. - B. 74, №12. - P. 625-628.

115. KELLING B., OELSCHLÄGEL D. Zur Lösung von linearen Toleranzproblemen // Wiss. Zeitschrift TH Leuna-Merseburg. 1991. - B. 33, №1. - P. 121-131.

116. Keeny R. L., Raifa H. Decision with Multiple Objectives: Preferences and Value Tradeoff. New York: John Wiley, 1976.

117. Klatte P., ullrich Ch. Complex sector arithmetic // Computing. 1980. - Vol. 24.- P. 139-148.

118. KOLACZ H. On the optimality of inclusion algorithms // Interval Mathematics 1985; Nickel K., ed. New York: Springer Verlag, 1986. - P. 67-80. - (Lecture Notes in Computer Science; vol. 212).

119. KUPERMANN I. B. Approximate Linear Algebraic Equations. New York: Van Nostrand, 1971.

120. LAKEYEV A. V. On existence and uniqueness of solutions of linear algebraic equations in Kaucher's interval arithmetic // Developments in Reliable Computing; Csendes T., ed.- Dordrecht: Kluwer, 1999. P. 53-65.

121. Laveuve S. E. Definition einer Kahan-Arithmeticund ihre Implementierung // Interval Mathematics; Nickel K., ed. Berlin: Springer Verlag, 1975. - P. 236-245. - (Lecture Notes in Computer Science; vol. 29).

122. LHOMME O. Consistency techniques for numeric CSPs // IJCAI'93. Chambery, France, August 1993. - P. 232-238.

123. Mackworth A. K. Consistency in network of relations // Artificial Intelligence. 1977.- Vol. 8. P. 99-119.

124. Mayer G., Rohn J. On the applicability of the interval Gaussian algorithm /'/ Reliable Computing. 1998. - Vol. 4, №3. - P. 205-222.

125. MOORE R. E. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979.

126. MOORE R. E. Interval methods for nonlinear systems // Fundamentals of numerical computation (computer-oriented numerical analysis). Computing Supplement Alefeld G., Grigorieff R. D., eds. Wienn: Springer Verlag, 1980. - P. 113-120.

127. Moore R. е., Jones S. T. Safe starting regions for iterative methods // SI AM Journal on Numerical Analysis. 1977. - Vol. 14. - P. 1051-1065.

128. Nickel K. Using interval methods for the numerical solution of ODE's // ZAMM. -1986. B. 66, № 11. - P. 513-523.

129. NlNG S., kearfott R. B. A comparison of some methods for solving linear interval equations // SIAM Journal on Numerical Analysis. 1997. - Vol. 34, №4. - P. 1289-1305.

130. NUDING E. Intervallrechnung und Wirklichkeit // Interval Mathematics; Nickel K., ed.- Berlin: Springer Verlag, 1975. P. 263-269. - (Lecture Notes in Computer Science; vol. 29).

131. Е. NüDING, Schrankentreue Algorithmen // Beiträge zur Numerische Mathematik. -1983. Vol. 11.-P. 115-137.

132. NUDING E. Ein einfacher Beweis der Satze von Oettli-Prager und J. Röhn // Freiburger Intervall-Berichte. 1986. - №9/86. - S. 1-3.

133. Nuding E., Wilhelm W. Über Gleichungen und über Lösungen // ZAMM. 1972. -B. 52. - P. T188-T190.224. oettli W. On the solution set of a linear system with inaccurate coefficients // SI AM Journal on Numerical Analysis. 1965. - Vol. 2, №1. - P. 115-118.

134. OETTLI W., PRAGER W. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides // Numerische Mathematik. -1964. Vol. 6. - P. 405-409.

135. Petkovic M. S., Mitrovic Z. M., Petkovic, L. B. Arithmetic of circular rings // Interval Mathematics 1985; Nickel K., ed. New York: Springer Verlag, 1986. - P. 133142. - (Lecture Notes in Computer Science; vol. 212).

136. Petunin D., Semenov A. The use of multi-intervals in the UniCalc solver // Scientific Computing and Validated Numerics; Alefeld G., Frommer A. and Lang В., eds. Berlin: Akademie Verlag, 1996. - P. 91-97.

137. POPOVA E. D. Generalized interval distributive relations and their applications // MISC'99 — Workshop on Applications of Interval Analysis to Systems and Control, Girona, Spain, February 24~26, 1999. Girona: Universität de Girona, 1999. - P. 13-23.

138. Quingrong L., Zhiying J. The SOR method for solving linear interval equations // Freiburger Intervall-Berichte. 1987. - №7/87. - S. 1-7.

139. RaTSCHEK H. Teilbarkeitskriterien der Intervallarithmetik // J. Reine Angew. Mathematik. 1972. - В. 252. - S. 128-138.

140. RaTSCHEK H. Optimal approximations in interval analysis // Interval Mathematics 1980; Nickel К., ed. New York: Academic Press, 1980. - P. 181-202.

141. RaTSCHEK H. Inclusion functions and global optimization // Mathematical Programming. 1985. - Vol. 33. - P. 300-317.

142. Rex G., Röhn J. Sufficient conditions for regularity and singularity of interval matrices // SI AM Journal on Numerical Analysis. 1999. - Vol. 20. - P. 437-445.

143. RÖHN J. Input-output planning with inexact data // Freiburger Intervall-Berichte. -1978. №9/78. - S. 1-16.

144. Röhn J. Input-output model with interval data // Econometrica. 1980. - Vol. 48. -P. 767-769.

145. RÖHN J. Duality in interval linear programming // Interval Mathematics 1980\ Nickel K., ed. New York: Academic Press, 1980. - P. 521-529.

146. RÖHN J. Interval linear systems with prescribed column sums // Linear Algebra and its Applications. 1981. - Vol. 39. - P. 143-148.

147. Röhn J. Inverse-positive interval matrices // ZAMM. 1987. - B. 57, №5. - S. T492-T493.

148. RÖHN J. A two-sequence method for linear interval equations // Computing. 1989. -Vol. 41, №1-2. - P. 137-140.

149. Röhn J. An asymptotic result for linear interval systems // BIT. 1989. - Vol. 29, №92.- P. 372-374.

150. RÖHN J. On singular matrices contained in an interval matrix // Ekonomicko-Matematicky Obzor. 1989. - Vol. 25, №3. - S. 320-322.

151. RÖHN J. A Farkas-type theorem for linear interval equations // Computing. 1989. -Vol. 43. - P. 93-95.254. rohn j. On nonconvexity of the solution set of a system of linear interval equations // BIT. 1990. - Vol. 30, №1. - R 161-165.

152. ROHN J. Cheap and tight bounds: the recent result by E. Hansen can be made more efficient // Interval Computations. 1993. - №4. - P. 13-21.

153. ROHN J. NP-hardness results for linear algebraic problems with interval data // Topics in Validated Numerics] Herzberger J., ed. Amsterdam: North-Holland, 1994. - P. 463-471.

154. Rohn J., kreinovioh V. Computing exact componentwise bounds on solutions of linear system is NP-hard // SIAM Journal on Matrix Analysis and Applications. 1995.- Vol. 16. P. 415-420.

155. ROHN J., KRESLOVA J. Linear interval inequalities // Linear and Multilinear Algebra.- 1994. Vol. 38. - P. 41-43.

156. RUMP S. M. Solving algebraic problems with high accuracy // A New Approach to Scientific Computation; Kulisch U. W. and Miranker W. L., eds. New York: Academic Press, 1983. - P. 51-120.

157. RUMP S. M. Solution of linear and nonlinear algebraic problems with sharp guaranteed bounds // Computing Supplement. 1984. - Vol. 5. - P. 147-168.

158. RUMP S. M. Verification methods for dense and sparce systems of equations // Topics in Validated Numerics; Herzberger J., ed. Amsterdam: Elsevier, 1994. - P. 63-135.

159. RUMP S. M. The distance between regularity and strong regularity // Scientific Computing and Validated Numerics; Alefeld G., Frommer A. and Lang В., eds. Berlin: Akademie Verlag, 1996. - P. 105-117.

160. RUMP S. M., KAUCHER E. Small bounds for the solution of systems of linear equations // Computing Supplement. 1980. - Vol. 2. - P. 157-164.264. saaty T. L. Analytic Hierarchy Process. New York: McGrow Hill, 1980.

161. SCHWANDT H. Iterative methods for systems of equations with interval coefficients and linear form // Computing. 1987. - Vol. 38, №2. - P. 143-161.

162. SCHWANDT H. Cyclic reduction for tridiagonal systems of equations with interval coefficients on vector computer // SIAM Journal on Numerical Analysis. 1989. - Vol. 26, №3. - P. 661-680.

163. SCHWEPPE F. C. Uncertain Dynamic Systems. Englewood Cliffs: Prentice Hall, 1973.

164. SHARY S. P. A new class of algorithms for optimal solution of interval linear systems // Interval Computations. 1992. - №2(4). - P. 18-29.

165. Shary S. P. Solving interval linear systems with nonnegative matrices // Abstracts of International Congress on Computer Systems and Applied Mathematics (CSAM-93), St. Petersburg, July 19-23, 1993. St. Petersburg, 1993. - P. 100.

166. SHARY S. P. Solving interval linear systems with nonnegative matrices // Scientific Computations and Mathematical Modelling: Proceedings of the International Conference MMSC-93; Markov S. M., ed. Sofia: DATECS Publishing, 1993. - P. 179-182.

167. SHARY S. P. On controlled solution set of interval algebraic systems // Interval Computations. 1993. - №6. - P. 66-75.

168. SHARY S. P. Solving the tolerance problem for interval linear systems // Interval Computations. 1994. - №2. - P. 6-26.

169. SHARY S. P. Numerical computation of algebraic solutions to interval linear systems // IMACS-GAMM International Symposium on Numerical Methods and Error Bounds, Universität Oldenburg, Germany, July 9-12, 1995. Extended abstracts. P. 30.

170. SHARY S. P. On optimal solution of interval linear equations // SIAM Journal on Numerical Analysis. 1995. - Vol. 32, №2. - P. 610-630.

171. SHARY S. P. Solving the linear interval tolerance problem // Mathematics and Computers in Simulation. 1995. - Vol. 39. - P. 53-85.

172. SHARY S. P. Algebraic approach to the interval linear static identification, tolerance and control problems, or One more application of Kaucher arithmetic // Reliable Computing. 1996. - Vol. 2, №1. - P. 3-33.

173. SHARY S. P. Algebraic solutions to interval linear equations and their applications // Numerical Methods and Error Bounds; Alefeld G. and Herzberger J., eds. Berlin: Akademie Verlag, 1996. - P. 224-233.

174. SHARY S. P. A new approach to the analysis of static systems under interval uncertainty 11 Scientific Computing and Validated Numerics; Alefeld G., Frommer A. and Lang B., eds. Berlin: Akademie Verlag, 1996. - P. 118-132.

175. SHARY S. P. Algebraic approach to the analysis of linear static systems with interval uncertainty // Russian Journal of Numerical Analysis and Mathematical Modelling. -1996. Vol. 11, №3. - P. 259-274.

176. SHARY S. P. Algebraic approach in the "outer problem" for interval linear equations // Reliable Computing. 1997. Vol. 3, №2. - P. 103-135.

177. SlIARY S. P. Controllable solution sets to interval static systems // Applied Mathematics and Computation. 1997. - Vol. 86, №2-3. - P. 185-196.

178. SHARY S. P. Outer estimation of generalized solution sets to interval linear systems // Developments in Reliable Computing; Csendes T., ed. Dordrecht: Kluwer, 1999. -P. 323-335.

179. SHARY S. P. Outer estimation of generalized solution sets to interval linear systems // Reliable Computing. 1999. - Vol. 5. - P. 323-335.

180. SHOKIN Yu. I. On interval problems, interval algorithms and their computational complexity // Scientific Computing and Validated Numerics; Alefeld G., Frommer A. and Lang B., eds. Berlin: Akademie Verlag, 1996. - P. 314-328.

181. SIGLA/X GROUP. Modal intervals (Basic tutorial) // MISC'99 Workshop on Applications of Interval Analysis to Systems and Control. Girona, Spain, February 24~26, 1999. - Girona: Universität de Girona, 1999. - P. 139-207.1. БИБЛИОГРАФИЯ266297