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

• Автор: Шарый, Сергей Петрович
• Шифр специальности: 01.01.07
• Научная степень: Докторская
• Год защиты: 2000
• Место защиты: Новосибирск
• Количество страниц: 266 с. : ил.

Содержание
Введение
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.6 6 Отщепление вещественного слагаемого
6.6 в Треугольное расщепление матрицы системы
6.7 Численные эксперименты со стационарными итерационными методами
5 Библиография

ГЛАВА 1. ПОСТАНОВКИ ИНТЕРВАЛЬНЫХ ЗАДАЧ

неопределённое™, мы должны будем задействовать один буквенный идентификатор, который соответствует одному вектору интервальной неопределенности. Иными словами, нужно говорить не о “множествах АЕ-решений типа а/3”, а о “множествах АЕ-решений типа а”, употребляя обозначение Ев((7, а):
Ба(в, а) := {г £ I" | (Уа € ау)(УЪ € Ьу)(3а € аэ)(36 € Ь*)( х = в{а + а, х) ) }
1.3 Детальная постановка задачи
1.3 а Обсуждение
Теперь, после того, как мы определили, что является множествами решений для интервальной системы уравнений (неравентсв и т.п.), настало время решить, что делать с ними дальше.
Это не праздный вопрос. Фундаментальный факт, касающийся окружающей нас реальности, состоит в том, что мы можем наблюдать, исследовать и использовать объекты, которые не просто конечны, но даже не слишком сложны. Конечность наших восприятий, рассмотрений, рассуждений, вычислений и т.п. широко осознана людьми и обычно не встречает возражений. Но какое обстоятельство является столь специфичным в интервальных задачах, что мы должны наложить второе требование — “не слишком сложный” ? Ответ заключается в том, что вступая в царство множеств, рассматриваемых как существенно структурированные, составные объекты, образованные из различимых элементарных частей, мы сталкиваемся с растущей (и даже доминирующей ролью) комбинаторных эффектов, которые едва ли обнаруживают себя в традиционной “точечной” математике. Но комбинаторика — это, как известно, основной источник больших, очень больших и огромных чисел, которые могут превзойти любую реальную физическую величину, и уж тем более возможности всех настоящих и будущих ЭВМ.
В частности, всё вышесказанное в полной мере справедливо для обобщённых множеств решений интервальных задач, которые были введены в предшествующем параграфе. Даже в простейших практических ситуациях прямое вычисление и описание обобщённых множеств решений оказывается, как правило, трудоёмким, утомительным, а часто и просто невозможным. Например, для интервальных линейных т х п-систем вида Ах = Ь длина полного описания множеств АЕ-решений в общем случае может расти быстрее, чем 2”, т.е. чем количество ортантов в К.п. Это следует из того, что множество решений Еад(А, Ь) может пересекать каждый из ортантов пространства и все эти пересечения являются выпуклыми полиэдрами, описание каждого из которых требует выписывания всех ограничивающих гиперпрлоскостей и т.п. (см. §2.36). Недавний теоретический результат А. В. Лакеева [58] показывает, что задача распознавания и оценивания множеств АЕ-решений интервальных линейных систем принципиально труднорешаема (КР-трудна) при условии, что мы не накладываем никаких ограничений на интервальную матрицу системы (см. также [184]). Таким образом, сложность упомянутого прямого описания множеств решений становится больше знаменитого “шахматного числа” 2е4 — 1 , если размерность интервальной системы равна всего лишь 64. Когда же размерность достигает нескольких сотен, то длина точного и исчерпывающего описания для Еад(А, Ь) делается сравнимой с количеством элементарных частиц во всей наблюдаемой Вселенной.1'3 Заметим, что рас-
1 3Борель в [10], к примеру, указывает Ю200 как максимально число элементарных событий, которое