Часть I, Дискретное исчисление конечных разностей (гл. 1-6), излагает основные понятия конечных разностей, суммирования конечных числовых рядов и конечных рядов Фурье.

Часть II, Приближение многочленами (гл. 7-20), содержит изложение классических численных методов интерполяции, численного интегрирования и численного решения дифференциальных уравнений, основанных на аппрок­симации функции обычными алгебраическими многочленами. При этом рас­сматриваются приближения в смысле точного совпадения в узлах, в смысле наименьших квадратов и в смысле наименьшего отклонения по Чебышеву.

Часть III, Немногочленные приближения (гл. 21-27), посвящена аппрок­симации функций с помощью экспоненциальных, а также с помощью рядов и интеграла Фурье.

Часть IV, Алгоритмы и эвристические методы (гл. 28-32), кроме некото­рых известных алгоритмов для отыскания корней функции и для ряда задач линейной алгебры, рассматривает примеры моделирования, применения метода Монте-Карло и некоторые игровые задачи. Отдельная заключительная глава посвящена вопросам организации вычислительной работы.

Третья и четвертая части книги содержат ряд новых задач и методов. Изло­жение всех численных методов сопровождается разбором примеров из вычис­лительной практики автора.

Таблиц 32, рисунков 43, библиографических ссылок 44.

Второе издание печатается с матриц предыдущего, исправлены лишь заме­ченные опечатки.

**

ОГЛАВЛЕНИЕ

Предисловие редактора перевода ..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.9251
§ 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