ISBN 5-93972-585-6 Translation from the English language edition: Applied Interval Analysis by Luc Jaulin, Michel Kieffer, Olivier Didrit and ´ Copyright c All Rights Reserved c http://rcd.ru http://ics.org.ru Springer-Verlag London Limited 2001 Институт компьютерных исследований, 2007 Eric Walter Оглавление Предисловие . <...> В противоположность этому, интервальный анализ дает возможность получать гарантированные аппроксимации множества всех действительных (допустимых) решений рассматриваемой задачи. <...> Точечные величины x —точечный скаляр x∗ — истинное значение неизвестной переменной ˇ x — априорное значение неизвестной переменной ˆ x — апостериорное значение неизвестной переменной x — точечный вектор-столбец xT — точечный вектор-строка 0 — нуль-вектор, вектор с компонентами из нулей 1 — единичный вектор, вектор с компонентами из единиц X — точечная матрица O, OnЧm — нулевая матрица, nЧm матрица с нулевыми элементами I, In — единичная матрица (матрица тождественного преобразоIm(s) — мнимая часть числа s Re(s) — вещественная часть числа s вания), nЧn матрица Интервалы [x]= [x,x] — интервальный скаляр [x]= [x,x] — интервальный вектор [xij]= ([X])ij — интервальный элемент интервальной матрицы [X] ее i-й строки и j-го столбца [X]= [X,X] — интервальная матрица [xi]= ([x])i — i-й интервальный элемент интервального вектора [x] lb([x]) — нижняя граница интервала [x] ub([x]) — верхняя граница интервала [x] w([x]) — ширина интервала [x] mid([x]) — центр интервала [x] 14 Множества ∅ —пустое множество S —множество N — множество всех положительных целых чисел Z — множество всех целых чисел R — множество всех вещественных чисел IR — множество всех интервальных вещественных чисел (множество всех вещественных интервалов) C — множество всех комплексных чисел C− — множество всех комплексных чисел со строго отрицательной вещественной частью B — множество всех булевских переменных IB — множество всех интервальных булевских переменных ∂S — граница множества S [S] — интервальная оболочка множества S S <...>
Прикладной_интервальный_анализ..pdf
УДК 518+519.4
Интернет-магазин
• физика
• математика
• биоло гия
http://shop.rcd.ru
• нефт е г а зовые
т ехнологии
ЖоленЛ., КиферМ., ДидриО., ВальтерЭ.
Прикладной интервальный анализ. — М.–Ижевск: Институт компьютерных
исследований, 2007. — 468 с.
Книга посвящена теории и численным методам гарантированного оценивания
и аппроксимации множеств. Техника и математический аппарат интервального
анализа строго обобщаются на процедуры работы с множествами. В монографической
литературе это одна из первых книг, где детально рассматривается приложение
разработанных методов к большомукругупроблем: решению систем нелинейных
уравнений и неравенств, задачам оптимизации, оценивания параметров и состояний,
робастного управления и робототехники. Приводится подборка примеров и упражнений.
Книга
рассчитана на широкий круг читателей, студентов, аспирантов, инженеров
и научных работников, занятых исследованием и проектированием систем
обработки информации и систем управления, а также на математиков, вычислителей
и программистов.
ISBN 5-93972-585-6
Translation from the English language edition:
Applied Interval Analysis by Luc Jaulin, Michel Kieffer, Olivier Didrit and ´
Copyright c
All Rights Reserved
c
http://rcd.ru
http://ics.org.ru
Springer-Verlag London Limited 2001
Институт компьютерных исследований, 2007
Eric Walter
Стр.4
Оглавление
Предисловие . . . ... .. .. ... .. ... .. .. ... .. ... 11
Обозначения . . . ... .. .. ... .. ... .. .. ... .. ... 13
РАЗДЕЛ I. ВВЕДЕНИЕ
ГЛАВА 1. Введение ... .. .. ... .. ... .. .. ... .. ... 19
1.1. Основные идеи ... ... .... .... .... ... .... . 20
1.2. Предыстория .... ... .... .... .... ... .... . 21
1.3. О сложности вычислений .... .... .... ... .... . 22
1.4. Структура книги . . ... .... .... .... ... .... . 22
РАЗДЕЛ II. АППАРАТ ИНТЕРВАЛЬНОГО
АНАЛИЗА
ГЛАВА 2. Основные понятия интервального анализа .. .. ... 27
2.1. Введение .. .... ... .... .... .... ... .... . 27
2.2. Операции над множествами ... .... .... ... .... . 27
2.2.1. Теоретико-множественные операции . ... .... . 27
2.2.2. Расширенные операции . .... .... ... .... . 29
2.2.3. Свойства операторов над множествами . . . .... . 30
2.2.4. Оболочки .. ... .... .... .... ... .... . 32
2.3. Интервальный анализ .. .... .... .... ... .... . 34
2.3.1. Интервалы . ... .... .... .... ... .... . 35
2.3.2. Интервальные вычисления ... .... ... .... . 37
2.3.3. Замкнутые интервалы .. .... .... ... .... . 38
2.3.4. Интервальные векторы . .... .... ... .... . 42
2.3.5. Интервальные матрицы . .... .... ... .... . 44
2.4. Функции включения ... .... .... .... ... .... . 47
2.4.1. Определения ... .... .... .... ... .... . 47
2.4.2. Естественные функции включения .. ... .... . 50
2.4.3. Центрированные функции включения . ... .... . 54
2.4.4. Смешанные центрированные функции включения . . 55
2.4.5. Тейлоровские функции включения . . . . . .... . 57
Стр.5
6ОГЛАВЛЕНИЕ
2.4.6. Сравнение . ... .... .... .... ... .... . 57
2.5. Проверки включения ... .... .... .... ... .... . 61
2.5.1. Интервальные булевские переменные . ... .... . 61
2.5.2. Проверки .. ... .... .... .... ... .... . 63
2.5.3. Проверки включений для множеств . . ... .... . 65
2.6. Выводы ... .... ... .... .... .... ... .... . 66
ГЛАВА 3. Покрытия .. .. .. ... .. ... .. .. ... .. ... 68
3.1. Введение .. .... ... .... .... .... ... .... . 68
3.2. Топология множеств ... .... .... .... ... .... . 69
3.2.1. Расстояние междукомпактными множествами . . . . 69
3.2.2. Помещение компактных множеств междупокрытиями 72
3.3. Регулярные покрытия .. .... .... .... ... .... . 73
3.3.1. Покрытия и подпокрытия ... .... ... .... . 74
3.3.2. Представление регулярного покрытия
в виде двоичного дерева .... .... ... .... . 76
3.3.3. Основные операции на регулярных покрытиях . . . 77
3.4. Выполнение вычислений с множествами ... ... .... . 80
3.4.1. Обращение множества . .... .... ... .... . 81
3.4.2. Оценивание образа ... .... .... ... .... . 85
3.5. Выводы ... .... ... .... .... .... ... .... . 90
ГЛАВА 4. Сжимающие операторы . . . ... .. .. ... .. ... 92
4.1. Введение .. .... ... .... .... .... ... .... . 92
4.2. Основные сжимающие операторы ... .... ... .... . 94
4.2.1. Конечные разрешающие операторы .. ... .... . 95
4.2.2. Интервальные конечные разрешающие операторы . 98
4.2.3. Метод неподвижной точки ... .... ... .... . 101
4.2.4. Метод вперед-назад ... .... .... ... .... . 107
4.2.5. Подход на основе линейного программирования . . 112
4.3. Внешняя аппроксимация .... .... .... ... .... . 113
4.3.1. Основная идея .. .... .... .... ... .... . 114
4.3.2. Предобуславливание .. .... .... ... .... . 115
4.3.3. Ньютоновский сжимающий оператор . ... .... . 117
4.3.4. Параллельная линеаризация .. .... ... .... . 118
4.3.5. Использование формальных преобразований .... . 120
4.4. Взаимодействие междусжимающими операторами .... . 123
4.4.1. Основная идея .. .... .... .... ... .... . 123
4.4.2. Сжимающие операторы и функции включения . . . 127
4.5. Сжимающие операторы на множествах .... ... .... . 130
4.5.1. Определения ... .... .... .... ... .... . 130
4.5.2. Множества, определяемые ограничениями
в виде равенств и неравенств . .... ... .... . 133
Стр.6
ОГЛАВЛЕНИЕ
7
4.5.3. Улучшение операторов сжатия при использовании
локального поиска .... .... .... ... .... . 134
4.6. Выводы ... .... ... .... .... .... ... .... . 134
ГЛАВА 5. Разрешающие операторы .. ... .. .. ... .. ... 138
5.1. Введение .. .... ... .... .... .... ... .... . 138
5.2. Решение квадратных систем нелинейных
уравнений .. .... ... .... .... .... ... .... . 139
5.3. Описание свойств множеств, определяемых
неравенствами ... ... .... .... .... ... .... . 142
5.4. Интервальная оболочка множества,
задаваемого неравенствами ... .... .... ... .... . 148
5.4.1. Первый подход . .... .... .... ... .... . 148
5.4.2. Второй подход . . .... .... .... ... .... . 149
5.5. Глобальная оптимизация .... .... .... ... .... . 154
5.5.1. Алгоритм Мура–Скелбо .... .... ... .... . 158
5.5.2. Алгоритм Хансена ... .... .... ... .... . 159
5.5.3. Использование метода вперед-назад .. ... .... . 165
5.6. Минимаксная оптимизация . . . .... .... ... .... . 166
5.6.1. Случай отсутствия ограничений .... ... .... . 167
5.6.2. Случай наличия ограничений . .... ... .... . 171
5.6.3. Работа с кванторами .. .... .... ... .... . 175
5.7. Множества уровня целевой функции . .... ... .... . 177
5.8. Выводы ... .... ... .... .... .... ... .... . 178
РАЗДЕЛ III. ПРИЛОЖЕНИЯ
ГЛАВА 6. Оценивание . . . . . ... .. ... .. .. ... .. ... 183
6.1. Введение .. .... ... .... .... .... ... .... . 183
6.2. Оценивание параметров с помощью оптимизации . .... . 186
6.2.1. Оценивание параметров методом наименьших квадратов
при моделировании структур . . ... .... . 188
6.2.2. Минимаксное оценивание параметров . . . .... . 192
6.3. Гарантированное оценивание параметров ... ... .... . 200
6.3.1. Введение .. ... .... .... .... ... .... . 200
6.3.2. Случай известных независимых переменных . . . . 204
6.3.3. Защита от выбросов ... .... .... ... .... . 206
6.3.4. Случай неопределенности независимых переменных 211
6.3.5. Вычисление интервальной оболочки апостериорного
допустимого множества ... .... ... .... . 214
6.4. Гарантированное оценивание состояний .... ... .... . 216
6.4.1. Введение .. ... .... .... .... ... .... . 216
Стр.7
8ОГЛАВЛЕНИЕ
6.4.2. Оценивание начального состояния .. ... .... . 219
6.4.3. Оценивание всех переменных состояния .. .... . 220
6.4.4. Гарантированное оценивание на основе метода
вперед-назад ... .... .... .... ... .... . 224
6.5. Выводы ... .... ... .... .... .... ... .... . 235
ГЛАВА 7. Робастное управление .. .. ... .. .. ... .. ... 238
7.1. Введение .. .... ... .... .... .... ... .... . 238
7.2. Устойчивость детерминированных линейных систем . . . . 239
7.2.1. Характеристический полином . .... ... .... . 240
7.2.2. Критерий Рауса . .... .... .... ... .... . 241
7.2.3. Степень устойчивости . .... .... ... .... . 242
7.3. Основные проверки робастной устойчивости . ... .... . 245
7.3.1. Интервальные полиномы .... .... ... .... . 247
7.3.2. Афинное семейство полиномов .... ... .... . 249
7.3.3. Нелинейная зависимость от параметров .. .... . 250
7.3.4. Заключение ... .... .... .... ... .... . 251
7.4. Анализ робастной устойчивости .... .... ... .... . 252
7.4.1. Области устойчивости . .... .... ... .... . 252
7.4.2. Степень устойчивости . .... .... ... .... . 255
7.4.3. Подход на основе множества значений полинома . . 260
7.4.4. Запасы робастной устойчивости .... ... .... . 268
7.4.5. Радиус устойчивости . . .... .... ... .... . 274
7.5. Синтез регулятора . ... .... .... .... ... .... . 278
7.6. Выводы ... .... ... .... .... .... ... .... . 282
ГЛАВА 8. Робототехника . . . ... .. ... .. .. ... .. ... 283
8.1. Введение .. .... ... .... .... .... ... .... . 283
8.2. Расширенная кинематическая задача для платформ
Стюарта –Гофа ... ... .... .... .... ... .... . 284
8.2.1. Платформы Стюарта –Гофа . . .... ... .... . 284
8.2.2. Переход от системы координат подвижной платформы
к системе координат основания .. ... .... . 285
8.2.3. Решаемые уравнения .. .... .... ... .... . 287
8.2.4. Решение .. ... .... .... .... ... .... . 288
8.3. Планирование маршрута .... .... .... ... .... . 294
8.3.1. Графическая дискретизация пространства конфигураций
.... ... .... .... .... ... .... . 296
8.3.2. Алгоритмы нахождения допустимого маршрута . . . 298
8.3.3. Тестовый пример .... .... .... ... .... . 303
8.4. Определение местоположения
и слежение за мобильным роботом .. .... ... .... . 309
Стр.8
ОГЛАВЛЕНИЕ
9
8.4.1. Формулировка статической задачи определения местоположения
робота . . .... .... ... .... . 311
8.4.2. Модель процесса измерения .. .... ... .... . 317
8.4.3. Обращение множеств .. .... .... ... .... . 321
8.4.4. Обработка выбросов . . .... .... ... .... . 322
8.4.5. Пример статической задачи определения местоположения
.. ... .... .... .... ... .... . 324
8.4.6. Слежение .. ... .... .... .... ... .... . 327
8.4.7. Пример ... ... .... .... .... ... .... . 330
8.5. Выводы ... .... ... .... .... .... ... .... . 331
РАЗДЕЛ IV. РЕАЛИЗАЦИЯ
ГЛАВА 9. Автоматическое дифференцирование . . . ... .. ... 337
9.1. Введение .. .... ... .... .... .... ... .... . 337
9.2. Прямое и обратное дифференцирование .... ... .... . 338
9.2.1. Прямое дифференцирование .. .... ... .... . 338
9.2.2. Обратное дифференцирование . .... ... .... . 340
9.3. Дифференцирование алгоритмов .... .... ... .... . 342
9.3.1. Первое предположение . .... .... ... .... . 342
9.3.2. Второе предположение . .... .... ... .... . 344
9.3.3. Третье предположение . .... .... ... .... . 346
9.4. Примеры . . .... ... .... .... .... ... .... . 348
9.4.1. Пример 1 . . ... .... .... .... ... .... . 349
9.4.2. Пример 2 . . ... .... .... .... ... .... . 352
9.5. Выводы ... .... ... .... .... .... ... .... . 353
ГЛАВА 10. Гарантированные вычисления с числами с плавающей
точкой ... .. ... .. .. ... .. ... .. .. ... .. ... 355
10.1. Введение .. .... ... .... .... .... ... .... . 355
10.2. Числа с плавающей точкой и стандарт IEEE 754 .. .... . 355
10.2.1. Представление .. .... .... .... ... .... . 356
10.2.2. Округление . ... .... .... .... ... .... . 358
10.2.3. Специальные величины . .... .... ... .... . 360
10.3. Интервалы и стандарт IEEE 754 .... .... ... .... . 361
10.3.1. Машинные интервалы . .... .... ... .... . 362
10.3.2. Арифметика замкнутых интервалов . . ... .... . 363
10.3.3. Работа с элементарными функциями . ... .... . 365
10.3.4. Улучшение интервальных оценок ... ... .... . 366
10.4. Источники программного обеспечения для интервальных
вычислений . .... ... .... .... .... ... .... . 368
10.5. Выводы ... .... ... .... .... .... ... .... . 370
Стр.9
10
ОГЛАВЛЕНИЕ
ГЛАВА 11. Материал для самостоятельных упражнений .. ... 371
11.1. Введение .. .... ... .... .... .... ... .... . 371
11.2. Сведения о C++ .. ... .... .... .... ... .... . 372
11.2.1. Структура программы . .... .... ... .... . 372
11.2.2. Стандартные типы ... .... .... ... .... . 374
11.2.3. Указатели . . ... .... .... .... ... .... . 374
11.2.4. Передача параметров в функцию ... ... .... . 375
11.3. Класс INTERVAL . . ... .... .... .... ... .... . 377
11.3.1. Конструкторы и деструкторы . .... ... .... . 379
11.3.2. Другие члены-функции . .... .... ... .... . 380
11.3.3. Математические функции ... .... ... .... . 385
11.4. Интервалы с использованием библиотеки PROFIL/BIAS . . 387
11.4.1. BIAS .... ... .... .... .... ... .... . 388
11.4.2. PROFIL ... ... .... .... .... ... .... . 388
11.4.3. Первое знакомство ... .... .... ... .... . 389
11.5. Упражнения на вычисление интервалов .... ... .... . 391
11.6. Интервальные векторы . .... .... .... ... .... . 392
11.6.1. Класс INTERVAL_VECTOR .. .... ... .... . 393
11.6.2. Конструкторы, операторы присваивания и вызова
функции .. ... .... .... .... ... .... . 394
11.6.3. Функции-друзья . .... .... .... ... .... . 397
11.6.4. Сервисные процедуры (утилиты) ... ... .... . 399
11.7. Векторы с использованием библиотеки PROFIL/BIAS . . . . 400
11.8. Упражнения на интервальные векторы .... ... .... . 401
11.9. Интервальные матрицы . .... .... .... ... .... . 405
11.10.Матрицы с использованием библиотеки PROFIL/BIAS . . . 407
11.11.Упражнения на интервальные матрицы .... ... .... . 408
11.12. Регулярные покрытия с использованием библиотеки
PROFIL/BIAS .... ... .... .... .... ... .... . 412
11.12.1. Класс NODE . . . .... .... .... ... .... . 412
11.12.2. Обращение множеств с покрытиями . ... .... . 415
11.12.3. Оценивание образов с помощью покрытий . .... . 419
11.12.4. Моделирование системы и оценивание ее состояния
с помощью покрытий .. .... .... ... .... . 425
11.13.Обработка ошибок . ... .... .... .... ... .... . 427
11.13.1. Использование оператора Exit . .... ... .... . 427
11.13.2. Обработка исключений . .... .... ... .... . 428
11.13.3. Обработка ошибок математических вычислений . . . 430
Литература .. .. ... .. .. ... .. ... .. .. ... .. ... 431
Дополнительная литература . ... .. ... .. .. ... .. ... 454
Предметный указатель .. .. ... .. ... .. .. ... .. ... 458
Стр.10