Хемминг Р. В. Численные методы для научных работников и инженеров. - М., 1972. - 399 c.
Книга посвящена численным методам математического анализа, используемым на современных электронных вычислительных машинах. Она состоит из четырех частей. Часть 1, Дискретное исчисление конечных разностей (гл. 1-6), излагает основные понятия конечных разностей, суммирования конечных числовых рядов и конечных рядов Фурье. Часть 2, Приближение многочленами (гл. 7-20), содержит изложение классических численных методов интерполяции, численного интегрирования и численного решения дифференциальных уравнений, основанных на аппроксимации функции обычными алгебраическими многочленами. При этом рассматриваются приближения в смысле точного совпадения в узлах, в смысле наименьших квадратов и в смысле наименьшего отклонения по Чебышеву. Часть 3, Немногочленные приближения (гл. 21-27), посвящена аппроксимации функций с помощью экспоненциальных, а также с помощью рядов и интеграла Фурье. Часть 4, Алгоритмы и эвристические методы (гл. 28-32), кроме некоторых известных алгоритмов для отыскания корней функции и для ряда задач линейной алгебры, рассматривает примеры моделирования, применения метода Монте-Карло и некоторые игровые задачи. Отдельная заключительная глава посвящена вопросам организации вычислительной работы. Третья и четвертая части книги содержат ряд новых задач и методов. Изложение всех численных методов сопровождается разбором примеров из вычислительной практики автора.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ..................................................12
ЧАСТЬ I. ДИСКРЕТНОЕ ИСЧИСЛЕНИЕ КОНЕЧНЫХ РАЗНОСТЕЙ
Глава 1. Исчисление разностей................................................17
§ 1.1. Введение и система обозначений....................................17
§ 1.2. Разностный оператор..............................19
§ 1.3. Повторные разности....................................................21
§ 1.4. Таблицы разностей......................................................23
§ 1.5. Факториалы..............................................................27
§ 1.6. Деление многочленов..................................................29
§ 1.7. Числа Стирлинга первого рода......................................32
§ 1.8. Числа Стирлинга второго рода......................................34
§ 1.9. Пример....................................................................35
§ 1.10. Альтернативные замечания..........................................36
§ 1.11. Общие замечания и справки........................................37
Глава 2. Погрешности округления....................................37
§ 2.1. Введение..................................................................37
§ 2.2. Область ответа..........................................................38
§ 2.3. Двойная точность......................................................39
§ 2.4. Счет со значащими разрядами......................................39
§ 2.5. Статистический подход................................................40
§ 2.6. Случайное округление..................................................41
§ 2.7. Переменная точность..................................................41
§ 2.8. Оценка шума в таблице..............................................41
§ 2.9. Теория «младшего значащего разряда............................47
§ 2.10. Теория «старшего значащего разряда..........................49
§ 2.11. Анализ распространения ошибки при небольшом вычислении .............................52
§ 2.12. Общие замечания и библиография................................53
Глава 3. Исчисление сумм......................................................53
§ 3.1. Введение и система обозначения....................................53
§ 3.2. Формулы суммирования..............................................56
§ 3.3. Суммирование по частям..............................................58
§ 3.4. Общие замечания......................................................59
Глава 4. Вычисление бесконечных рядов..................................59
§ 4.1. Введение..................................................................59
§ 4.2. Метод Куммера......................................61
§ 4.3. Некоторые специальные суммы....................................62
§ 4.4. Метод Эйлера............................................................62
§ 4.5. Нелинейное преобразование..........................................66
§ 4.6. Степенные ряды ........................................................67
§ 4.7. Разложение по специальным функциям............................68
§ 4.8. Интегралы как приближения сумм ................................68
§ 4.9. Дигамма-функция........................................................69
Глава 5. Уравнения в конечных разностях..............................71
§ 5.1. Система обозначений..................................................71
§ 5.2. Пример разностного уравнения первого порядка................72
§ 5.3. Пример уравнения второго порядка................................74
§ 5.4. Линейные разностные уравнения с постоянными коэффициентами ..................................................................75
§ 5.5. Пример....................................................................76
Глава 6. Конечные ряды Фурье..............................................78
§ 6.1. Введение..................................................................78
§ 6.2. Ортогональность на дискретном множестве точек..............79
§ 6.3. Точность разложения..................................................81
§ 6.4. Вычисление коэффициентов..........................................83
§ 6.5. Метод двенадцати ординат............................................85
§ 6.6. Методы с минимумом умножений..................................87
§ 6.7. Разложение по косинусам............................................87
§ 6.8. Локальные ряды Фурье...........................88
ЧАСТЬ II. ПРИБЛИЖЕНИЕ МНОГОЧЛЕНАМИ — КЛАССИЧЕСКИЙ ЧИСЛЕННЫЙ АНАЛИЗ
Глава 7. Введение в многочленные приближения......................90
§ 7.1. Ориентация..............................................................90
§ 7.2. Альтернативные формулировки......................................92
§ 7.3. Узловые точки, информация..........................................95
§ 7.4. Класс функций..........................................................96
§ 7.5. Согласие..................................................................97
§ 7.6. Точность..................................................................98
Глава 8. Интерполяция многочленами. Данные с произвольными промежутками..................99
§ 8.1. Философия................................................................99
§ 8.2. Интерполяционные многочлены......................................99
§ 8.3. Метод интерполяции Лагранжа...................103
§ 8.4. Интерполяционная формула Ньютона...............106
§ 8.5. Другая форма для таблицы разделенных разностей......109
§ 8.6. Погрешность многочленной аппроксимации...........110
§ 8.7. Трудности приближения многочленом...............113
§ 8.8. О выборе узловых точек.......................116
Глава 9. Интерполяция многочленами. Равноотстоящие узлы. . . 117
§ 9.1. Формула Ньютона для интерполирования............117
§ 9.2. Интерполирование в таблицах...................118
§ 9.3. Ромбовидная диаграмма..............................................119
§ 9.4. Замечания к выведенным формулам................123
§ 9.5. Смешанные интерполяционные формулы.............124
Глава 10. Единый метод нахождения интерполяционных формул 125
§ 10.1. Введение................................125
§ 10.2. Несколько типичных формул интегрирования.........127
§ 10.3. Фиксированные узлы.........................132
§ 10.4. Некоторые примеры формул....................135
§ 10.5. Значения функции и производной в фиксированных точках 137
§ 10.6. Свободные узлы; квадратура Гаусса...............139
§ 10.7. Смешанный случай..........................И1
§ 10.8. Замечания................................142
§ 10.9. Линейные ограничения на веса..................144
§ 10.10. Формула Грегори..........................147
§ 10.11. Выводы.................................150
Глава 11. О нахождении остаточного члена формулы........152
§ 11.1. Потребность в остаточном члене................. . 152
§ 11.2. Порядок остаточного члена.....................152
§ 11.3. Функция влияния...........................153
§ 11.4. Случай, когда G (s) имеет постоянный знак..........156
§ 11.5. Случай, когда функция влияния меняет знак.........158
§ 11.6. Слабое место в методе рядов Тейлора.............160
Глава 12. Формулы для определенных интегралов..........161
§ 12.1. Введение................................161
§ 12.2. Формулы Ньютона—Котеса.....................164
§ 12.3. Использование формулы Грегори.................166
§ 12.4. Открытые формулы.........................168
§ 12.5. Квадратура Гаусса..........................169
§ 12.6. Формулы интегрирования смешанного гауссового типа ... 170
§ 12.7. Суммирование рядов.........................171
§ 12.8. Эффекты замены переменной...................172
§ 12.9. Интегралы с параметром......................173
Глава 13. Неопределенные интегралы...................173
§ 13.1. Описание содержания главы и система обозначений .... 173
§ 13.2. Несколько простых формул для неопределенных интегралов ....................................175
§ 13.3. Общий метод.............................177
§ 13.4. Ошибка вследствие отбрасывания членов...........178
§ 13.5. Устойчивость..............................181
§ 13.6. Шум округления...........................184
§ 13.7. Итоги ..................................186
§ 13.8. Некоторые общие замечания........................................187
§ 13.9. Экспериментальная проверка устойчивости....................189
§ 13.10. Пример интеграла свертки, иллюстрирующий идею устойчивости ................................. 189
Глава 14. Введение В дифференциальные уравнения........191
§ 14.1. Природа и смысл дифференциальных уравнений.......191
§ 14.2. Поле направлений ..........................192
§ 14.3. Численное решение..........................193
§ 14.4. Пример..................................................................І95
§ 14.5. Устойчивость метода простого прогноза............197
§ 14.6. Устойчивость коррекции......................198
§ 14.7. Несколько общих замечаний....................200
§ 14.8. Системы уравнений.........................201
Глава 15. Общая теория методов прогноза и коррекции......202
§ 15.1. Введение ................................202
§ 15.2. Ошибка от отбрасывания членов.................204
§ 15.3. Устойчивость..............................205
§ 15.4. Помехи округления..........................209
§ 15.5. Прогноз по трем точкам......................209
§ 15.6. Прогнозы типа Милна........................210
§ 15.7. Прогнозы типа Адамса—Башфорта................212
§ 15.8. Общие замечания о выборе метода...............213
§ 15.9. Выбор прогноза............................214
§ 15.10. Некоторые формулы........................215
§ 15.11. Выбор шага и оценка точности.................216
§ 15.12. Экспериментальная проверка...................219
Глава 16. Специальные методы интегрирования обыкновенных
дифференциальных уравнений.................220
§ 16.1. Введение и общее описание....................220
§ 16.2. Методы Рунге—Кутта........................221
§ 16.3. Методы для уравнения второго порядка, когда отсутствует у..................................222
§ 16.4. Линейные уравнения.........................224
§ 16.5. Метод, который использует значения у, у' и у".......225
§ 16.6. Случай, когда решение трудне аппроксимировать многочленом ..................................226
§ 16.7. Краевые задачи............................229
Глава 17. Метод наименьших квадратов. Теория...........232
§ 17.1. Введение................................232
§ 17.2. Метод наименьших квадратов...................232
§ 17.3. Другие критерии...........................234
§ 17.4. Ошибки с нормальным распределением.............234
§ 17.5. Проведение подходящего многочлена..............237
§ 17.6. Ортогональные функции......................240
§ 17.7. Общие свойства ортогональных функций ...........242
§ 17.8. Неравенство Бесселя и полнота..................244
§ 17.9. Метод наименьших квадратов и коэффициенты Фурье . . . 245
§ 17.10. Ортогональные многочлены....................247
§ 17.11. Классические ортогональные многочлены...........249
§ 17.12. Сравнение метода наименьших квадратов и разложения в степенные ряды.......250
§ 17.13. Метод наименьших квадратов с ограничениями; продолжение примера из § 1.9.........251
§ 17.14. Последние замечания о методе наименьших квадратов.....252
Глава 18. Метод наименьших квадратов. Практика..........252
§ 18.1. Общие замечания о многочленном случае...........252
§ 18.2. Трехчленное рекуррентное соотношение............253
§ 18.3. Построение квазиортогональных многочленов.........255
§ 18.4. Немногочленный случай.......................255
§ 18.5. Нелинейные параметры.......................256
Глава 19. Многочлены Чебышева......................257
§ 19.1. Введение................................257
§ 19.2. Некоторые тождества........................259
§ 19.3. Критерий Чебышева.........................260
§ 19.4. Экономизация.............................262
§ 19.5. Механизация процесса экономизации..............263
§ 19.6. Смещенные многочлены Чебышева.........................265
§ 19.7. тау-процесс Ланцоша..........................266
§ 19.8. Видоизменение тау-метода.......................268
§ 19.9. Несколько замечаний о чебышевском приближении.....270
§ 19.10. Критерий совпадения моментов.................270
Глава 20. Рациональные функции......................272
§ 20.1. Введение................................272
§ 20.2. Непосредственный подход......................273
§ 20.3. Чебышевское приближение рациональными функциями.....274
§ 20.4. Обратные разности (симметричные)...............275
§ 20.5. Пример.................................278
ЧАСТЬ III. НЕМНОГОЧЛЕННЫЕ ПРИБЛИЖЕНИЯ
Глава 21. Периодические функции. Аппроксимация Фурье.....280
§ 21.1. Цель этой теории...........................280
§ 21.2. Замена переменных и выбор узлов................281
§ 21.3. Ряды Фурье; периодические явления..............282
§ 21.4. Интерполяция периодических функций.............285
§ 21.5. Интегрирование............................288
§ 21.6. Метод общего оператора.....................290
§ 21.7. Несколько замечаний относительно общего метода.....293
Глава 22. Сходимость рядов Фурье.....................294
§ 22.1. Сходимость степенных рядов и рядов Фурье.........294
§ 22.2. Функции с простым разрывом...................295
§ 22.3. Функция, имеющая непрерывные производные более высокого порядка..............297
§ 22.4. Улучшение сходимости ряда Фурье...............298
§ 22.5. Спектр мощности...........................299
§ 22.6. Явление Гиббса............................300
§ 22.7. Сигма-множители Ланцоша.....................301
§ 22.8. Сравнение методов сходимости..................303
§ 22.9. Техника дифференцирования по Ланцошу...........304
Глава 23. Непериодические функции. Интеграл Фурье.......305
§ 23.1. Цель главы...............................305
§ 23.2. Обозначения и краткое изложение результатов .......306
§ 23.3. Интеграл Фурье............................310
§ 23.4. Преобразование Фурье некоторых функций..........311
§ 23.5. Функции с ограниченным спектром и теорема выборки . . 313
§ 23.6. Теорема свертки ...........................315
§ 23.7. Эффект конечного суммирования.................316
Глава 24. Линейные фильтры. Сглаживание и дифференцирование .....................317
§ 24.1. Введение................................317
§24.2. Пример простого сглаживающего фильтра...........318
§ 24.3. Пример построения фильтра....................319
§ 24.4. Фильтры вообще...........................320
§ 24.5. Анализ простых формул для дифференцирования......321
§ 24.6. Как избежать вычисления производных?............322
§ 24.7. Метод Филона.............................323
§ 24.8. Заключительные замечания.....................325
Глава 25. Интегралы и дифференциальные уравнения.......326
§ 25.1. Содержание главы..........................326
§ 25.2. Метод передаточной функции для интегрирования......327
§ 25.3. Общие формулы интегрирования.................331
§ 25.4. Дифференциальные уравнения...................332
§ 25.5. Построение фильтров по методу Чебышева..........334
§ 25.6. Некоторые детали метода Чебышева..............336
Глава 26. Экспоненциальная аппроксимация..............340
§ 26.1. Введение ................................340
§ 26.2. О нахождении формул, использующих экспоненты, когда
показатели экспонент известны..................340
§ 26.3. Неизвестные показатели.......................342
§ 26.4. Предупреждения ...........................343
§ 26.5. Экспоненты и многочлены.....................344
§ 26.6. Остаточные члены..........................344
Глава 27. Особенности..............................344
§ 27.1. Введение................................344
§ 27.2. Пример интеграла с особенностью в бесконечности.....345
§ 27.3. Особенность в линейном дифференциальном уравнении . . 346
§ 27.4. Общие замечания...........................349
ЧАСТЬ IV. АЛГОРИТМЫ И ЭВРИСТИЧЕСКИЕ МЕТОДЫ
Глава 28. Нахождение нулей.........................350
§ 28.1. Алгоритмы и эвристические методы...............350
§ 28.2. Метод деления пополам для нахождения корня функции.....351
§ 28.3. Линейная интерполяция.......................352
§ 28.4. Параболическая интерполяция...................352
§ 28.5. Некоторые общие замечания....................353
§ 28.6. Метод Берстоу для нахождения комплексных корней многочлена...............355
Глава 29. Системы линейных алгебраических уравнений......359
§ 29.1. Введение................................359
§ 29.2. Метод исключения Гаусса.....................360
§ 29.3. Варианты метода Гаусса......................362
§ 29.4. Метод Гаусса—Зайделя.......................363
§ 29.5. Повышенная точность........................364
§ 29.6. Общие замечания...........................364
Глава 30. Обращение матриц и собственные значения.......365
§ 30.1. Введение................................365
§ 30.2. Обращение матрицы методом исключения по Гауссу ........ 365
§ 30.3. Задача нахождения собственных значений...........366
§ 30.4. Наименьшие собственные значения................368
§ 30.5. Несколько замечаний........................368
Глава 31. Некоторые примеры моделирования.............369
§ 31.1. Введение ................................369
§ 31.2. Простой пример дискретного моделирования.........370
§ 31.3. пример моделирования складских операций..........374
§ 31.4. Трехмерные крестики — нолики..................375
§ 31.5. Общие замечания о дискретном моделировании.......379
§ 31.6. Непрерывное моделирование....................380
Глава 32. Случайные числа и методы Монте-Карло..........381
§ 32.1. Понятие случайного числа.....................381
§ 32.2. Генерирование случайных чисел в машине, работающей в
двоичной системе...........................382
§ 32.3. Генерирование случайных чисел на десятичной машине . . 386
§ 32.4. Другие распределения........................386
§ 32.5. Метод Монте-Карло.........................388
§ 32.6. Еще одна иллюстрация метода Монте-Карло.........389
§ 32.7. Метод жулика.............................390
Глава N+l. Искусство вычислять для инженеров и ученых....... 391
§ N+l.1. Важность вопроса........................391
§ N+l.2. Что мы собираемся делать с ответом?...........392
§ N+l.3. Что мы знаем?..........................393
§ N+l.4. Обдумывание вычислений...................394
§ N+l.5. Повторение предыдущих шагов...............395
§ N+l.6. Оценка усилий, необходимых для решения задачи . . . 395
§ N+l.7. Изменения первоначального плана..............396
§ N+l.8. Философия.............................397
§ N+l.9. Заключительные замечания..................398
Литература........................................399
