В отличие от других подобных изданий, все численные методы излагаются в варианте с автоматической верификацией точности получаемых результатов. <...> В книгу вошли описания численных методов для решения следующих задач: вычисление полиномов, автоматическое дифференцирование функций одной и нескольких переменных, решение линейных и нелинейных уравнений и систем, глобальная оптимизация, вычисление арифметических выражений, нахождение нулей комплексных полиномов, линейное программирование. <...> На сегодняшний день интервальные вычисления имеют уже достаточно богатую историю. <...> Кроме того, такой способ реализации приводил к значительному (до двух порядков) замедлению выполнения программы по сравнению с обычными вычислениями с плавающей точкой. <...> За 70–90-е гг. было разработано (преимущественно в Германии и Швейцарии) целое семейство таких языков: FORTRAN-SC и -XSC, PASCAL-SC и -XSC, MODULA-SC, OBERON-XSC. <...> Объединяют такие системы следующие особенности: строгая спецификация точности всех численных операций, включая вычисление элементарных функций (причем специфицируемая точность обычно является предельно достижимой для данной операции), возможность выполнить любую арифметическую операцию над числами с плавающей точкой с направленным округлением или округлением к ближайшему машинно-представимому числу, наличие предопределенных интервальных типов данных и операций над ними (включая комплексно-интервальные и векторно-матричные), возможность записывать арифметические и логические выражения над переменными определенных пользователем типов в традиционной (инфиксной) форме, ввод-вывод чисел с управляемым округлением, возможность вычисления с наивысшей достижимой точностью выражений типа скалярного произведения и некоторые другие, менее существенные свойства. <...> . На аппаратном уровне SC-языки могут быть поддержаны как специальными процессорами, так и любыми процессорами, следующими известному стандарту на арифметику <...>
Достоверные_вычисления._Базовые_численнные_методы.pdf
УДК 519.6
ББК 22.19
К90
Кулиш У., Рац Д., Хаммер Р., Хокс М.
Достоверные вычисления. Базовые численные методы / Пер.
с англ. — Москва–Ижевск: НИЦ «Регулярная и хаотическая динамика»,
2005. — 496 с. — (Компьютерные математические вычисления).
Книга
представляет собой учебник по базовым методам вычислительной
математики, подготовленный университетскими преподавателями из
Германии. В отличие от других подобных изданий, все численные методы
излагаются в варианте с автоматической верификацией точности получаемых
результатов. Для каждого метода приводятся его математическое
обоснование, описание алгоритма и полный текст соответствующей программы.
Все программы записаны на специально разработанном для реализации
подобных методов языке программирования PASCAL-XSC, полное
руководство по которому предполагается опубликовать 3-м изданием
в серии «Компьютерные математические вычисления».
В книгу вошли описания численных методов для решения следующих
задач: вычисление полиномов, автоматическое дифференцирование
функций одной и нескольких переменных, решение линейных и нелинейных
уравнений и систем, глобальная оптимизация, вычисление арифметических
выражений, нахождение нулей комплексных полиномов, линейное
программирование.
Учебник ранее издавался на немецком и английском языках. Русское
издание дополнено информацией о новейших достижениях в данной области.
Для
преподавателей, аспирантов и студентов вузов, научных работников
и инженеров.
ISBN 5-93972-440-X (рус.)
ISBN 3-540-57118-3 (англ.)
ISBN 0-387-57118-3 (англ.)
http://rcd.ru
http://ics.org.ru
- Перевод на русский язык
с дополнениями, А. Г. Яковлев, 2005
- НИЦ «Регулярная и хаотическая
динамика», 2005
c
- Springer-Verlag, Berlin-Heidelberg, 1993
c
c
Стр.4
Оглавление
Достоверные вычисления и их компьютерная реализация.
В.Я.Крейнович, А. Н.Соболевсий, А. Г.Яковлев
Предисловие
1 Введение
5
23
27
1.1 Краткий обзор ... .. ... .. .. ... .. .. ... .. .. 28
1.2 Структура книги .. .. ... .. .. ... .. .. ... .. .. 28
1.3 Шрифтовые выделения .. .. .. ... .. .. ... .. .. 29
1.4 Запись алгоритмов .. ... .. .. ... .. .. ... .. .. 30
1.5 Реализация .. ... .. ... .. .. ... .. .. ... .. .. 32
1.6 Вычислительное окружение . .. ... .. .. ... .. .. 33
1.7 Зачем нужна верификация результатов вычислений . . 34
1.7.1 Краткая история методов вычислений ... .. .. 35
1.7.2 Арифметические вычисления на компьютере . . 36
1.7.3 Расширение стандартной арифметики
чисел с плавающей точкой ... .. .. ... .. .. 38
1.7.4 Научные и инженерные вычисления
с автоматической верификацией результатов .. 41
1.7.5 Проверка корректности программ
и верификация результатов вычислений .. .. . 46
I Основные понятия
2Особенности PASCAL–XSC
49
50
2.1 Предопределенные типы . .. .. ... .. .. ... .. .. 51
2.2 Универсализация описания операций... .. .. ... .. .. 55
2.3 Совмещение знаков операций... . ... .. .. ... .. .. 57
2.4 Модульность . ... .. ... .. .. ... .. .. ... .. .. 58
Стр.490
Оглавление
491
2.5 Динамические массивы и подмассивы .. .. ... .. .. 60
2.6 Преобразование данных .. .. .. ... .. .. ... .. .. 62
2.7 Высокоточные выражения (#-выражения) . ... .. .. 64
2.8 Строки. .. .. ... .. ... .. .. ... .. .. ... .. .. 65
2.9 Предопределенные арифметические модули ... .. .. 66
2.10 Почему мы выбрали PASCAL–XSC .. .. .. ... .. .. 68
3 Математические основы
69
3.1 Вещественная интервальная арифметика .. ... .. .. 69
3.2 Комплексная интервальная арифметика . .. ... .. .. 80
3.3 Обобщенная интервальная арифметика . .. ... .. .. 83
3.4 Интервальные векторы и матрицы .. .. .. ... .. .. 85
3.5 Арифметика чисел с плавающей точкой . .. ... .. .. 87
3.6 Машинная интервальная арифметика .. .. ... .. .. 90
3.7 Проблема преобразования данных .. .. .. ... .. .. 93
3.8 Основы верификации вычислений .. .. .. ... .. .. 98
II Одномерные задачи
4 Вычисление полиномов
105
106
4.1 Теоретические основы ... .. .. ... .. .. ... .. .. 107
4.1.1 Постановка задачи . .. .. ... .. .. ... .. .. 107
4.1.2 Итерационный метод решения . .. .. ... .. .. 107
4.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 110
4.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 111
4.3.1 Программный код на PASCAL–XSC . ... .. .. 111
4.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 116
4.3.3 Предостережения и указания . .. .. ... .. .. 120
4.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 120
4.5 Литература для дальнейшего чтения . .. .. ... .. .. 121
5 Автоматическое дифференцирование
122
5.1 Теоретические основы ... .. .. ... .. .. ... .. .. 123
5.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 125
5.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 128
5.3.1 Программный код на PASCAL–XSC . ... .. .. 128
5.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 141
5.3.3 Предостережения и указания . .. .. ... .. .. 144
5.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 145
5.5 Литература для дальнейшего чтения . .. .. ... .. .. 145
Стр.491
492
6 Нелинейные уравнения с одним неизвестным
Оглавление
147
6.1 Теоретические основы ... .. .. ... .. .. ... .. .. 148
6.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 151
6.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 155
6.3.1 Программный код на PASCAL-XSC .. ... .. .. 155
6.3.2 Пример ... .. ... .. .. ... .. .. ... .. .. 166
6.3.3 Предостережения и указания . .. .. ... .. .. 169
6.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 170
6.5 Литература для дальнейшего чтения . .. .. ... .. .. 171
7 Глобальная оптимизация
172
7.1 Теоретические основы ... .. .. ... .. .. ... .. .. 173
7.1.1 Проверка значения в средней точке . ... .. .. 173
7.1.2 Проверка на монотонность ... .. .. ... .. .. 175
7.1.3 Проверка на вогнутость .. ... .. .. ... .. .. 176
7.1.4 Шаг интервального метода Ньютона . ... .. .. 177
7.1.5 Верификация .. ... .. .. ... .. .. ... .. .. 178
7.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 179
7.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 185
7.3.1 Программный код на PASCAL–XSC . ... .. .. 185
7.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 198
7.3.3 Предостережения и указания . .. .. ... .. .. 202
7.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 203
7.5 Литература для дальнейшего чтения . .. .. ... .. .. 205
8 Вычисление арифметических выражений
207
8.1 Теоретические основы ... .. .. ... .. .. ... .. .. 207
8.1.1 Нелинейный подход .. .. ... .. .. ... .. .. 208
8.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 211
8.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 216
8.3.1 Программный код на PASCAL-XSC .. ... .. .. 216
8.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 228
8.3.3 Ограничения, указания и усовершенствования . 232
8.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 233
8.5 Литература для дальнейшего чтения . .. .. ... .. .. 234
9 Нули комплексных полиномов
237
9.1 Теоретические основы ... .. .. ... .. .. ... .. .. 237
9.1.1 Постановка задачи . .. .. ... .. .. ... .. .. 237
9.1.2 Итерационный подход . .. ... .. .. ... .. .. 238
9.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 243
9.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 248
Стр.492
Оглавление
493
9.3.1 Программный код на PASCAL-XSC .. ... .. .. 248
9.3.2 Пример ... .. ... .. .. ... .. .. ... .. .. 259
9.3.3 Предостережения и указания . .. .. ... .. .. 262
9.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 262
9.5 Литература для дальнейшего чтения . .. .. ... .. .. 263
III Многомерные задачи
10 Системы линейных уравнений
265
266
10.1 Предварительные теоретические
сведения .. .. ... .. ... .. .. ... .. .. ... .. .. 266
10.1.1 Метод ньютоновского типа ... .. .. ... .. .. 266
10.1.2 Схема итерационного уточнения . .. ... .. .. 267
10.1.3 Приближенное обращение матриц .. ... .. .. 268
10.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 269
10.3 Реализация алгоритма и примеры ... .. .. ... .. .. 274
10.3.1 Программный код на PASCAL-XSC .. ... .. .. 274
10.3.2 Пример ... .. ... .. .. ... .. .. ... .. .. 285
10.3.3 Предостережения и усовершенствования . . . . . 287
10.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 288
10.5 Литература для дальнейшего чтения . .. .. ... .. .. 290
11 Линейное программирование
294
11.1 Теоретические основы ... .. .. ... .. .. ... .. .. 295
11.1.1 Описание задачи .. .. .. ... .. .. ... .. .. 295
11.1.2 Верификация .. ... .. .. ... .. .. ... .. .. 296
11.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 299
11.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 306
11.3.1 Программный код на PASCAL-XSC .. ... .. .. 306
11.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 327
11.3.3 Предостережения и указания . .. .. ... .. .. 333
11.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 333
11.5 Литература для дальнейшего чтения . .. .. ... .. .. 335
12 Многомерное автоматическое дифференцирование
336
12.1 Теоретические основы ... .. .. ... .. .. ... .. .. 337
12.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 340
12.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 342
12.3.1 Программный код на PASCAL–XSC . ... .. .. 342
12.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 376
12.3.3 Предостережения и указания . .. .. ... .. .. 384
Стр.493
494
Оглавление
12.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 384
12.5 Литература для дальнейшего чтения . .. .. ... .. .. 385
13 Системы нелинейных уравнений
386
13.1 Теоретические основы ... .. .. ... .. .. ... .. .. 387
13.1.1 Итерационный метод Гаусса-Зейделя ... .. .. 388
13.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 391
13.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 397
13.3.1 Программый код на PASCAL-XSC . .. ... .. .. 397
13.3.2 Пример ... .. ... .. .. ... .. .. ... .. .. 408
13.3.3 Предостережения, указания и усовершенствования
.. ... .. ... .. .. ... .. .. ... .. .. 411
13.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 412
13.5 Литература для дальнейшего чтения . .. .. ... .. .. 412
14 Глобальная оптимизация
415
14.1 Теоретические основы ... .. .. ... .. .. ... .. .. 416
14.1.1 Проверка значения в средней точке . ... .. .. 416
14.1.2 Проверка на монотонность ... .. .. ... .. .. 417
14.1.3 Проверка на вогнутость .. ... .. .. ... .. .. 418
14.1.4 Шаг интервального метода Ньютона . ... .. .. 418
14.1.5 Верификация .. ... .. .. ... .. .. ... .. .. 420
14.2 Алгоритмическое описание .. .. ... .. .. ... .. .. 421
14.3 Реализация и примеры ... .. .. ... .. .. ... .. .. 429
14.3.1 Программный код на PASCAL–XSC . ... .. .. 429
14.3.2 Примеры .. .. ... .. .. ... .. .. ... .. .. 448
14.3.3 Предостережения и указания . .. .. ... .. .. 452
14.4 Упражнения .. ... .. ... .. .. ... .. .. ... .. .. 453
14.5 Литература для дальнейшего чтения . .. .. ... .. .. 454
Приложение
Вспомогательные модули
П.1 Модуль
П.2 Модуль
П.3 Модуль
П.4 Модуль
Литература
Предметный указатель
460
460
... .. ... .. .. ... .. .. ... .. .. 460
. ... .. ... .. .. ... .. .. ... .. .. 461
. ... .. ... .. .. ... .. .. ... .. .. 461
.. .. ... .. .. ... .. .. ... .. .. 467
469
483
b_ut
il
r_ut
i_uti_ut
mv
il
il
il
Стр.494