Аннотация
Книга посвящена теории, численным методам и практическим алгоритмам для глобальной оптимизации функций и доказательного решения систем нелинейных уравнений. Использование методов интервального анализа обеспечивает глобальный характер развиваемых подходов, вычислительные доказательства существования решений, а также их локализацию. Детально рассматриваются методы решения систем линейных и нелинейных уравнений и приложение разработанных методов к решению задач оптимизации как при отсутствии ограничений, так и с ограничениями в виде равенств и неравенств. Изложение иллюстрируется примерами и рекомендациями по практической реализации алгоритмов. Предлагаемое читателю второе издание содержит много новых результатов.
Книга рассчитана на широкий круг читателей — студентов, аспирантов, инженеров, программистов и математиков, сталкивающихся в своей работе с задачами оптимизации и решением систем уравнений.
Содержание
Предисловие рецензента книги
Предисловие авторов
Перечень рисунков
Перечень таблиц
Список принятых сокращений и обозначений
ГЛАВА 1. Введение
1.1. Обзор
1.2. Предыстория возникновения интервального анализа
1.3. Круг вопросов настоящей книги
1.4. Преимущества и недостатки интервальных вычислений
1.5. Будущее интервальных вычислений
ГЛАВА 2. Интервалы и интервальная арифметика
2.1. Интервалы
2.2. Обозначения
2.3. Арифметика конечных интервалов
2.4. Зависимость интервалов
2.5. Расширенная интервальная арифметика
ГЛАВА 3. Функции от интервалов
3.1. Вещественные функции от интервалов
3.2. Интервальные функции
3.3. Формы интервальных функций
3.4. Дробление интервалов
3.5. Анализ граничных точек
3.6. Монотонные функции
3.7. Практическое оценивание интервальных функций
3.8. Грубые и точные функции
ГЛАВА 4. Замкнутые интервальные системы
4.1. Введение
4.2. Преимущества замкнутой системы
4.3. Теоретико-множественное обоснование замкнутых интервальных систем
4.4. Условие локализации
4.5. Расширенные локусы
4.6. Арифметика над расширенным множеством вещественных чисел
4.7. Замкнутые интервальные системы
4.8. Расширенная основная теорема
4.9. Обозначения для векторов и матриц
4.10. Заключение
ГЛАВА 5. Интервальные линейные уравнения
5.1. Определения
5.2. Введение
5.3. Множество решений
5.4. Метод исключения Гаусса
5.5. Случаи плохой работы интервального метода Гаусса
5.6. Предобуславливание
5.7. Метод Гаусса-Зейделя
5.8. Процедура Хансена-Блика-Рона
5.9. Совместное применение метода Гаусса-Зейделя и процедуры Хансена-Блика-Рона
5.10. Оптимальная внешняя оценка множества решений системы Ax = b
5.11. Специальная предобуславливающая матрица
5.12. Переопределённые системы
ГЛАВА 6. Интервальные линейные неравенства
6.1. Введение
6.2. Случай одного неравенства
6.3. Системы неравенств
6.4. Упорядочение неравенств
6.5. Вспомогательный выбор ведущих элементов
6.6. Перестановки столбцов
6.7. Предобуславливающая матрица
6.8. Решение неравенств
ГЛАВА 7. Разложения на основе наклонов и рядов Тейлора
7.1. Введение
7.2. Оценивание остаточного члена в тейлоровском разложении
7.3. Многомерный случай
7.4. Якобиан и гессиан
7.5. Автоматическое дифференцирование
7.6. Уточнённые оценки на основе тейлоровских разложений
7.7. Разложения, использующие наклоны
7.8. Наклоны для функций, не являющихся рациональными
7.9. Многомерные наклоны
7.10. Наклоны высших порядков
7.11. Наклонные разложения негладких функций
7.12. Автоматическое вычисление наклонов
7.13. Эквивалентные разложения
ГЛАВА 8. Квадратные интервальные уравнения и неравенства
8.1. Введение
8.2. Процедура
8.3. Структура алгоритма
ГЛАВА 9. Нелинейные уравнения одной переменной
9.1. Введение
9.2. Интервальный метод Ньютона
9.3. Процедура в случае, когда интервал f ′(x) производной не содержит нуль
9.4. Критерий остановки
9.5. Структура алгоритма
9.6. Свойства алгоритма
9.7. Численный пример
9.8. Интервальный метод Ньютона на основе наклонов
9.9. Пример, использующий метод на основе наклонов
9.10. Задачи с возмущениями
ГЛАВА 10. Анализ совместности
10.1. Введение
10.2. Совместность по брусу
10.3. Совместность по значениям
10.4. Исследование анализа совместности по значениям
10.5. Реализация анализа совместности по значениям
10.6. Сходимость
10.7. Сходимость в интервальном случае
10.8. Дробление бруса
10.9. Многомерный случай
10.10. Проверка несуществования решения
10.11. Линейные комбинации функций
10.12. Доказательство существования решения
10.13. Сравнение анализа совместности по брусу и анализа совместности по значениям
10.14. Уточнение границ области
10.15. Использование дискриминантов
10.16. Нелинейные уравнения одной переменной
ГЛАВА 11. Системы нелинейных уравнений
11.1. Введение
11.2. Вывод интервальных методов Ньютона
11.3. Различные варианты метода
11.4. Внутренние итерации
11.5. Критерии остановки алгоритма
11.6. Процедура завершения алгоритма
11.7. Скорость процесса
11.8. Дробление бруса
11.9. Аналитическое предобуславливание
11.10. Исходный брус
11.11. Тест применимости линеаризации
11.12. Структура алгоритма
11.13. Обсуждение алгоритма
11.14. Один шаг метода Ньютона
11.15. Свойства интервальных методов Ньютона
11.16. Численный пример
11.17. Задачи с возмущениями и анализ чувствительности
11.18. Переопределенные системы
ГЛАВА 12. Безусловная оптимизация
12.1. Введение
12.2. Общая структура алгоритма
12.3. Исходный брус
12.4. Использование градиента целевой функции
12.5. Оценка сверху на глобальный минимум
12.6. Уточнение оценки сверху
12.7. Выпуклость целевой функции
12.8. Использование метода Ньютона
12.9. Остановка алгоритма
12.10. Интервальная оценка минимума
12.11. Список брусов
12.12. Выбор бруса для обработки
12.13. Дробление бруса
12.14. Структура алгоритма
12.15. Результаты работы алгоритма
12.16. Обсуждение алгоритма
12.17. Численный пример
12.18. Случай нескольких минимумов
12.19. Задачи с недифференцируемыми функциями
12.20. Нахождение всех стационарных точек
ГЛАВА 13. Оптимизация при наличии ограничений
13.1. Введение
13.2. Условия Ф. Джона
13.3. Нормирование множителей Лагранжа
13.4. Использование ограничений
13.5. Решение условий Ф. Джона
13.6. Оценивание множителей Лагранжа
13.7. Первый численный пример
13.8. Второй численный пример
13.9. Использование совместности
ГЛАВА 14. Оптимизация с ограничениями в виде неравенств
14.1. Введение
14.2. Условия Ф. Джона
14.3. Ограничение сверху на минимум
14.4. Линейный поиск
14.5. Строго допустимые решения
14.6. Использование ограничений
14.7. Использование тейлоровских разложений
14.8. Структура алгоритма
14.9. Результаты работы алгоритма
14.10. Обсуждение алгоритма
14.11. Отделение границы
14.12. Подушкообразные функции
14.13. Недифференцируемые функции
ГЛАВА 15. Оптимизация с ограничениями в виде равенств
15.1. Введение
15.2. Условия Ф. Джона
15.3. Ограничение минимума
15.4. Использование ограничений для оценивания минимума
15.5. Выбор переменных
15.6. Удовлетворение основного предположения
15.7. Численный пример
15.8. Использование верхней оценки
15.9. Использование ограничений
15.10. Информация о решении
15.11. Использование условий Ф. Джона
15.12. Структура алгоритма
15.13. Результаты работы алгоритма
15.14. Обсуждение алгоритма
15.15. Недифференцируемые функции
ГЛАВА 16. Общий случай задачи оптимизации
16.1. Введение
16.2. Линейные системы c ограничениями в виде неравенств и равенств
16.3. Существование допустимой точки
16.4. Структура алгоритма
ГЛАВА 17. Задачи с возмущениями и анализ чувствительности
17.1. Введение
17.2. Основные алгоритмы
17.3. Допуски
17.4. Несвязные множества решений
17.5. Точные оценки в задачах оптимизации с возмущениями
17.6. Обоснование Допущения 17.5.1
17.7. Первый численный пример
17.8. Второй численный пример
17.9. Третий численный пример
17.10. Верхняя оценка
17.11. Уточнённые оценки для систем нелинейных уравнений
ГЛАВА 18. Другие случаи задач оптимизации
18.1. Недифференцируемые функции
18.2. Целочисленные и смешанные целочисленные задачи
Литература
Дополнительная литература к русскому изданию
Предметный указатель