Справочное пособие содержит подробное описание современных эффективных методов приближенного решения на ЭВМ многих важных и широко распространенных задач вычислительной и прикладной математики: статистической обработки данных, аппроксимации функций, численного интегрирования и дифференцирования, решения операторных уравнений, в том числе интегральных уравнений и задач Коши для систем обыкновенных дифференциальных уравнений, минимизации функций и математического программирования. Особое внимание уделено плохо разработанным задачам, например вычислению особых интегралов, решению жестких систем дифференциальных уравнений и др. Для многих методов, задач и ЭВМ приведены оценки их основных характеристик: полной погрешности решения задач на ЭВМ, а также времени и памяти, необходимых для реализации методов на ЭВМ. Впервые систематически изложены результаты по оптимизации численных методов. Даны примеры, таблицы графики и другие сведения, облегчающие применение ряда методов.
Для широкого круга специалистов и студентов, занимающихся разработкой и применением методов решения прикладных задач на ЭВМ.
Методы вычислений на ЭВМ: Справочное пособие. Иванов В. В. — Киев. Издательство "Наукова думка", 1986 —584 с.
© Издательство «Наукова думка», 1986
ОГЛАВЛЕНИЕ книги Методы вычислений на ЭВМ
Предисловие
Список принятых сокращений
Глава 1. Общие вопросы
1.1. Классы задач прикладной математики
1.1.1. Классификация задач в вычислительной математике (5). 1.1.2. Определение понятия задачи; процесс решения задачи (6). 1.1.3. Классификация задач в кибернетике (6): 1. Классификации «со стороны» решающей системы (6). 2. Классификация на отношениях между задачей, решающей системой и средой (7). 3. Классификация по особенностям процесса решения задач (7). 4. Классификация задач по их количественным характеристикам (7).
1.2. Рассматриваемые методы
1.2.1. Определение понятия метода в вычислительной математике (9). 1.2.2. Численные методы (9). 1.2.3. Аналитические методы (11). 1.2.4. Численно-аналитические методы (11). 1.2.6. Более детальная классификация методов (11). 1.2.6. Общие вычислительные схемы (12). 1.2.7. Вопросы взаимодействия «Исполнителя» и «Заказчика» (13).
1.3. Применяемые в СССР типы ЭВМ и ВС
1.3.1. Особенности выполнения арифметических операций на ЭВМ (13). 1.3.2. Правила округлений на ЭВМ (14). 1.3.3. О наборе операций ЭВМ (14). 1.3.4. Быстродействие ЭВМ (14). 1.3.5. Память ЭВМ (15). 1.3.6. Формы эксплуатации ЭВМ и ВС (15). 1.3.7. Математическое обеспечение ЭВМ и ВС (16). 1.3.8. Классификация ВС (16).
1.4. Характеристики задач, методов и ЭВМ
1.4.1. Основные понятия (18). 1.4.2. Общее время решения задачи на ЭВМ (18). 1.4.3. Необходимая память (18). 1.4.4. Мера полной погрешности (19). 1.4.5. Характеристики времени, памяти и точности на классе задач (19). 1.4.6. Эффективное быстродействие ЭВМ (20). 1.4.7. Эффективное быстродействие ЭВМ на классе задач (20). 1.4.8. Эталонные операционные векторы (21). 1.4.9. Технико-экономические характеристики (21). 1.4.10. Характеристики оценок характеристик (22). 1.4.11. Характеристики вычислительного процесса и вычислительных систем (23).
1.5. Общая теория погрешностей вычислений и решения некорректно поставленных задач
1.5.1. Причины возникновения погрешностей (23). 1.5.2. Погрешность математической модели (24). 1.5.3. Общая схема оценок полных абсолютных погрешностей (24). 1.5.4. Вычисление производной функции на отрезке [—1,П] (26). 1.5.5. Виды мер точности (27). 1.5.6. Верные значащие цифры (28). 1.5.7. Виды оценок погрешностей (28). 1.5.8. Методы получения оценок (29). 1.5.9. Одна важная статистическая оценка наследственной погрешности (29). 1.5.10. Понятия приближенного решения задачи (30). 1.5.11. Приближенное решение некорректно поставленных задач (30): 1. Метод регуляризации А. Н. Тихонова (30). 2. Методы квазирешений и принципа невязки (31).
1.6. Методы оценки необходимой памяти и времени решения задач на ЭВМ
1.6.1. Оценка необходимой памяти (32). 1.6.2. Оценки времени решения (33). 1.6.3. Задача отыскания интерполяционного многочлена (34). 1.6.4. О сложности алгоритмов и вычислений (37). 1.6.5. Оценка времени решения методом статистического моделирования программ на ЭВМ (37). 1.6.6. Об оценках времени для многопроцессорных систем (38).
1.7. Об оптимизации алгоритмов решения задач на ЭВМ
1.7.1. Общие постановки задач (38). 1.7.2. Вопросы оптимизации алгоритмов по точностн (40). 1.7.3. Задача вычисления алгебраического многочлена (41): 1. Различные формы представления многочленов (41). 2. Сравнение вычисления многочленов в степенной форме н форме разложения по многочленам Чебышева (43). 3. Сравнение с вычислением многочленов в других формах записи (44). 1.7.4. Некоторые способы формального задания алгоритмов (46): 1. Алгоритмы как машины Тьюринга (46). 2. Алгоритмы как абстрактные автоматы (46). 3. Нормальные алгоритмы Маркова (47). 4. Язык операторных алгоритмов (47). 5. Алгоритмы над алгебраической структурой (47). 6. Алгоритмы для решения задач математической физики (48). 1.7.5. Об оптимизации алгоритмов по памяти (48): 1. Алгоритмы (48) 1.7.6. Об оптимизации алгоритмов по времени (49). 1.7.7. Об алгебре преобразовния программ В. М. Глушкова (53): 1. Основные понятия (53). 2. Формальные преобразования регулярных микропрограмм (54). 3. Преобразование микропрограммы умножения двух чисел (55).
1.8. Дополнения и замечания к главе 1
1.8.1. Графы (56). 1.8.2. Булевы функции (57). 1.8.3. Псевдобулевы функции (58). 1.8.4. R-функции (59). 1.8.5. Обобщенные циклические матрицы (60). 1.8.6. Ветвящиеся цепные дроби (61). 1.8.7. Стохастические модели ошибок округления (61). 1.8.8. Оценки погрешностей для суммы парных произведений (63). 1.8.9. О методе Монте-Карло (65). 1.8.10. NР-полные задачи (66). 1.8.11. Алгоритмическая полнота и сложность микропрограмм (67). 1.8.12. Замыкание вычислительного алгоритма (70). 1.8.13. Об общей теории оптимальных алгоритмов Трауба и Вожьняковского (70).
Глава 2. Статистическая обработка экспериментальных данных
2.1. Предварительная обработка данных
2.1.1. Алгоритмы опроса датчиков информации (72). 2.1.2. Отбраковка ложной информации (74). 2.1.3. Сжатие информации (76). 2.1.4. Анализ точности представления сигналов в ЭВМ (78).
2.2. Основные положения теории статистических оценок
2.2.1. Виды оценок (80). 2.2.2. Метод максимума правдоподобия (81). 2.2.3. Некоторые другие методы (82). 2.2.4. Выборочные распределения (83). 2.2.5. Доверительные области (85). 2.2.6. Теория статистических решений (86).
2.3. Методы оценки средних величин
2.3.1. Основные понятия (87). 2.3.2. Оценки среднего для нормального распределения (87): 1. Оценка в режиме off-line (87). 2. Оценка в режиме on-line (88). 2.3.3. Оценка оценок (89): 1. Погрешность метода (89). 2. Наследственная погрешность (90). 3. Погрешность округления (92). 4. Полная погрешность (93). 2.3.4. Об экономии памяти и числа операций ЭВМ (94). 2.3.5. Сравнение алгоритмов (95). 2.3.6. Оценки среднего для некоторых других законов распределения (95): 1. Распределения, используемые для сравнения оценок (95). 2. Основные оценки среднего (96). 3. Влияние асимметрии на смещение оценок (101). 2.3.7. Оценки дисперсии для нормального распределения (101). 2.3.8. Оценки корреляционных моментов случайных величин (102). 2.3.9. Оценки математического ожидания для эргодического стационарного процесса (104). 2.3.10. Оценки математического ожидания для нестационарного процесса (104).
2.4. Методы оценки корреляционных функций стационарных эргодических процессов
2.4.1. Стандартный метод (106). 2.4.2. Косвенный метод на основе БПФ (107). 2.4.3. Об одном экономичном алгоритме (108). 2.4.4. Некоторые другие методы (109). 2.4.5. Оценки оценок (110). 2.4.6. Об оценке взаимной корреляционной функции (110).
2.5. Методы оценки соответствующих спектральных плотностей
2.5.1. Стандартный метод (111). 2.5.2. Методы прямого преобразования Фурье с применением БПФ (112): 1. Первичная оценка (112). 2. Некоторые семейства окон данных (ИЗ). 3. Другие первичные оценки (115). 4. Сглаженные оценки (115). 5. Об одном экономичном алгоритме (116). 2.5.3. Об оценке взаимной спектральной плотности (116).
2.6. Методы оценки законов распределения случайных векторов
2.6.1. Оценка условных интегральных законов (117): 1. Вычислительная схема (117). 2. Оценки погрешностей (118). 2.6.2. Оценка плотностей вероятностей (120): 1. Вычислительная схема в случае одной переменной (120). 2. Полная погрешность (121). 3. Обобщение на случай n переменных (122). 4. Сравнительный анализ алгоритмов (122). 2.6.3. Оценка апостериорных законов распределения (123).
2.7. Методы решения некоторых других задач обработки
2.7.1. Задача расчета надежности (124). 2.7.2. Задача выделения скрытых периодичностей (125): 2.7.3. Задача оценки статистических зависимостей (125). 2.7.4. Задача генерирования временного ряда с известными свойствами (127). 2.7.5. Задача проверки и принятия гипотез (128). 2.7.6. Об автоматизированных системах обработки данных (130): 1. Универсальные и специализированные системы (130). 2. Метод рационального сочетания принципов универсальности и специализации (131). 3. Структура математического обеспечения систем (131). 2.7.7. Элементы проблемного математического обеспечения УСОД (132): 1. Оценка статистических характеристик и проверка гипотез (132). 2. Парный корреляционно-регрессиоииый анализ (135). 3. Множественный корреляциоиио-регрессиоииый анализ (138). 4. Спектральио-корреляционный анализ случайных процессов (140). 5. Статистическая обработка больших объемов данных (142).
Глава 3. Аппроксимация и вычисление функций
3.1. Классы областей, функций и функционалов
3.1.1. Классы областей (144). 3.1.2. Классы измеримых функций (144). 3.1.3. Классы Дифференцируемых функций (146). 3.1.4. Классы аналитических функций (148). 3.1.5. Классы функционалов (149). 3.1.6. Обобщенные функции (149). 3.1.7. Теоремы вложения (150).
3.2. Постановка задач и оценки величин наилучшей аппроксимации
3.2.1. Общие определения и свойства (151). 3.2.2. Случаи пространств Lp и С (1S3). 3.2.3. Некоторые другие случаи (155). 3.2.4. Обратные теоремы теории аппроксимации (156).
3.3. Методы интерполяции
3.3.1. Линейная интерполяция функций одной переменной (157): 1. Основные формулы (157). 2. Наследственные погрешности (159). 3. Погрешности методов (161). 4. Погрешности округлений (162). 5. Полные погрешности (162). 3.3.2. Линейная интерполяция функций многих переменных (162): 1. Случай линейной системы (162). 2.Случаи ортогональной системы (163). 3. Случай системы многочленов Чебышева (164). 4. Некоторые другие случаи (164). 5. Об оценках погрешностей (166). 3.3.3. Обобщенная интерполяция (166). 3.3.4. Обратное интерполирование (167).
3.4. Методы среднеквадратичной аппроксимации
3.4.1. Линейная аппроксимация (167): 1. Основные методы (168). 2. Примеры ортонормальных систем (169). 3. Оценки погрешностей (171). 4. Оценки необходимой памяти и числа операций на ЭВМ (172). 3.4.2. Нелинейная аппроксимация (173). 3.4.3. Обобщенная аппроксимация (174).
3.5. Методы чебышевской (равномерной) аппроксимации
3.5.1. Аппроксимация функций одной переменной при помощи алгебраических многочленов (174): 1. Методы Ремеза (175). 2. Некоторые другие методы (176). 3. Оценки погрешностей (176). 3.5.2. Аппроксимация функций одной переменной с помощью дробно-рациональных функций (177): 1. Основные методы (178). 2. Оценки погрешностей (178). 3.5.3. Ряд других случаев чебышевской аппроксимации (179). 1. Линейная обобщенная аппроксимация (179). 2. Нелинейная аппроксимация (180). 3. Некоторые случаи аналитического построения наилучших чебышевских приближений (180).
3.6. Методы сплайновой аппроксимации
3.6.1. Основные понятия (181). 3.6.2. Оценки погрешностей аппроксимации (182): 1. Одномерный случай (182). 2. Многомерный случай (183). 3. Обобщенный случай (183). 3.6.3. Методы вычисления сплайнов (184): 1. Формы представления полиномиальных сплайнов (184). 2. Вычисление интерполяционных параболических сплайнов (185). 3. Вычисление интерполяционных кубических сплайнов (186). 4. Вычисление частичных сплайнов (186). 5. Вычисление интерполирующих операторных сплайнов (187). 6. Вычисление некоторых других сплайнов (187).
3.7. Об оптимальных алгоритмах аппроксимации
3.7.1. Постановки задач (187): 1. Пассивная чистая минимаксная стратегия (187). 2. Последовательная чистая минимаксная стратегия (189). 3. Некоторые другие стратегии (189). 3.7.2. Об алгоритмах, оптимальных по точности (190) 3.7.3. Об алгоритмах, оптимальных по некоторым другим критериям (196).
3.8. Оптимизация алгоритмов вычисления основных элементарных функций на ЭВМ
3.8.1. Постановка задачи в резервы оптимизации (197). 3.8.2. Оптимизация по точности (198): 1. Мннимизацня наследственной погрешности (198). 2. Минимизация погрешности округлений (199). 3.8.3. Оптимизация повремени (199): 1. Кусочно-многочленная аппроксимация (199). 2. Кусочно-рациональная аппроксимация (201). 3. Некоторые другие виды аппроксимации (202). 4. Об оптимальной аппроксимации (203). 3.8.4. Оптимизация по другим критериям (206).
3.9. Вычисление специальных функций
3.9.1. Определение и некоторые свойства специальных функций (206): 1. Гамма-функция (206). 2. Гипергеометрическая функция (207). 3. Функции Лежандра (207). 4. Функции Бесселя (207). 5. Эллиптические функции и интегралы (208). 6. Некоторые другие функции (209). 3.9.2. Основные способы вычисления (209). 3.9.3. Об оптимизации алгоритмов вычисления специальных функций (211).
3.10. Дополнения и замечания к главе 3
3.10.1. Аппроксимация по хаусдорфовой мере (211). 3.10.2. Односторонняя аппроксимация (212). 3.10.3. Монотонная аппроксимация (212). 3.10.4. Кусочная аппроксимация (213). 3.10.5. Адаптивная аппроксимация (213). 3.10.6. Стохастическая аппроксимация (214). 3.10.7. Метод граничных функций для построения оптимальных по точности аппроксимаций (215). 3.10.8. Вопросы построения математических моделей объектов моделирования на ЭВМ (215).
Глава 4. Численное интегрирование и дифференцирование
4.1. Оптимизация методов численного интегрирования
4.1.1. Постановки задач (217): 1. Пассивные чистые минимаксные стратегии (217): 2. Последовательные чистые минимаксные стратегии (218). 3. Некоторые другие стратегии (218). 4.1.2. Результаты общего характера (219). 4.1.3. Результаты в классе L2'kN6 ^ (220). 4.1.4. Результаты в классах функций с условием Липшица (221): 1. В классе С"L (221). 2. В классе C"L N (222). 3. В классе Н^ (fi) (222). 4.1.5. Результаты в классах дифференцируемых функций (223): 4.1.6. Результаты в классах аналитических функций (230). 4.1.7. Результаты в классах целых функций (231). 4.1.8. Результаты в некоторых других классах (232). 4.1.9. Об оценках наследственной погрешности и погрешности округлений (232). 4.1.10. Об экономии числа операций и памяти ЭВМ (233).
4.2. Методы вычисления особых интегралов
4.2.1. Интегралы вида j f (х) g (х) dx (233). 4.2.2. Одномерные сингулярные интегралы с ядром Коши (235). 4.2.3. Кратные сингулярные интегралы (236). 4.2.4. Одномерные интегралы Фурье (237): 1. Оптимальные квадратуры (238). 2. БПФ (240). 3. Оценки погрешностей (240). 4. Некоторые модификации БПФ (241). 4.2.5. Кратные интегралы Фурье (243). 4.2.6. Интегралы свертки (244). 4.2.7. Некоторые другие интегралы (244).
4.3. Методы отыскания первых производных
4.3.1. Метод регуляризации (245). 4.3.2. Метод квазирешений (248). 4.3.3. Метод невязки (249). 4.3.4. Некоторые другие методы (249):
4.4. Методы отыскания производных высших порядков
4.4.1. Сводка формул численного дифференцирования (252). 4.4.2. О регуляризации задач численного дифференцирования (253). 4.4.3. Метод дифференцирования интерполяционных формул (253). 4.4.4. Метод невязок (254): 1. Общая схема (254) : 2. Разложение по собственным функциям оператора L (255). 3. Численное интегрирование (256). 4. Дискретное преобразование Фурье (257). 5. Применение сплайн-функций (258). 6. Сведение к решению уравнения Эйлера (259). 4.4.5. Некоторые другие методы (259): 1. Применение преобразований Фурье и сверток (259). 2. Метод сведения к интегральным уравнениям первого рода (259). 3. Дифференцирование разрывных функций (260) 4. О наилучшем приближении операторов дифференцирования (260).
4.5. Дополнения и замечания к главе 4
4.5.1. О квадратурах на сфере (261): 1. Квадратуры типа Гаусса — Маркова (261). 2. Квадратуры типа Чебышева (264). 3. Оценка погрешностей (264). 4. Метод Монте-Карло (265). 4.5.2. О вычислении континуальных интегралов по гауссовым мерам (265): 1. Основные понятия и свойства (265). 2. Приближенные формулы (269). 3. Метод Монте-Карло (272). 4 5.3. Некоторые оптимальные по точности формулы для интегралов(273).
Глава 5. Решение операторных уравнений
5.1. Общая теория приближенных методов
5.1.1. Основные положения (277). 5.1.2. Случай уравнений типа Фредгольма второго рода (277). 5.1.3. Случай линейных положительно определенных операторов (279). 5.1.4. Случай нормально разрешимых операторов (280). 5.1.5. Случай линейных ограниченных операторов (281). 5.1.6. Случай линейных замкнутых операторов (282). 5.1.7. Случай нелинейных операторов (283). 5.1.8. Случай двусторонних приближенных методов (284). 5.1.9. Апостериорная оценка погрешности (284). 5.1.10. Об ином подходе к общей теории приближенных методов (286). 5.1.11 Об оптимальной регуляризации (287). 5.1.12. О методе эквивалентных возмущений (288).
5.2. Прямые методы для линейных уравнений
5.2.1. Метод наименьших квадратов (289): 1. Основы метода (289). 2. Алгоритм ортогонализации (291). 3. Алгоритм Гаусса с выбором главного элемента (293). 4. Алгоритм покоординатного спуска (Гаусса — Зейделя) (293). 5. Алгоритм наискорейшего спуска (Л. В. Канторовича) (294). 6. Некоторые другие алгоритмы (295). 5.2.2. Проекционные методы (295): 1. Основные определения (295). 2. Общая теория методов (296). 3. Метод Галеркина для уравнений второго рода (297). 4. Переход к уравнению второго рода (298). 5. Решение краевых задач для обыкновенных дифференциальных уравнений (298). 6. Метод Бубнова — Галеркина для уравнений с положительно определенной главной частью (300). 7. Метод Ритца (301). 8. Устойчивость метода Галеркина — Петрова (301). 5.2.3. Некоторые другие методы (302): 1. Метод моментов (302). 2. Об оптимальных проекционных методах (303). 3. Обобщение метода наименьших квадратов (304). 4. Методы на подпространствах (305).
5.3. Прямые методы для нелинейных уравнений
5.3.1. Вариационные методы (305). 5.3.2. Проекционные методы (307). 5.3.3. Разностные методы (308).
5.4. Итеративные методы для линейных уравнений
5.4.1. Метод простой итерации (310): 1. Уравнение с оператором сжатия (310). 2, Влияние нулевого приближения (311). 3. Влияние ошибок округления (311). 4. Уравнения с монотонными операторами (312). 5.4.2. Сведение уравнений к условиям применимости метода простой итерации (312): 1. Случай положительно определенного оператора (312). 2. Случай неотрицательно определенного оператора (313). 3. Случай ограниченного оператора в гильбертовом пространстве (314). 4. Случай замкнутого оператора в гильбертовом пространстве (314). 5. Случай банахова пространства (314). 5.4.3. Метод аналитического продолжения (314). 5.4.4 Методы типа наискорейшего спуска (317): 1. Общая схема (317). 2. Случай гильбертова пространства и линейного ограниченного оператора (317). 3. Метод минимальных невязок (318). 4. а-Процессы (319). 5.4.5. Метод Зейделя (319). 5.4.6. Методы расщепления (320). 5.4.7 Чебышевские циклические итеративные методы (321). 5.4.8. Методы возмущений (323). 5.4.9. Метод приближения обратного оператора (324). 5.4.10. Случайные итеративные процессы (324).
5.5. Итеративные методы для нелинейных уравнений
5.5.1. Метод простой итерации (325): 1. Основные понятия (325). 2. Общая теорема о неподвижной точке (326). 3. Частные случаи теоремы о неподвижной точке (326). 4. Нелинейная краевая задача (327). 5. Вопросы точности (329). 5.5.2. Методы типа Ньютона (329): 1. Основные понятия (329). 2. Обычный метод Ньютона (330). 3. Упрощенный метод Ньютона (331). 4. Усиленный метод Ньютона (331). 5.5.3. Интерполяционные (многоточечные) методы (333): 1. Основные понятия (333). 2. Метод секущих и его обобщение (333). 5.5.4. Уравнения с монотонными операторами (334): 1°. Основные понятия (334). 2. О сходимости последовательных приближений 5.5.5. Уравнения на компактных множествах (336): 1. Осиовны понятия об одном методе эффективного решения (337). 5.5.6. Некоторые другие методы. 1. Модификации метода Ньютона (338). 2. Методы расщепления (339) 3. метод наискорейшего спуска (339). 4. Методы дифференциального спуска 5.5.7. Общая теория итеративных процессов. 1. Основные понятия (341). 2. Основные результаты (344). 3. Об оптимальных методах (345). 4. Ускорение сходимости итеративных процессов (346).
5.6. Комбинированные методы
5.6.1. Постановка задачи (348). 5.6.2. Метод продолжения решения по параметру. 5.6.3. Составные нелинейно-линейные методы (349). 5.6.4. Метод осреднения функциональных поправок (Соколова) и его обобщения (350). 5.6.5. СР-методы Об оптимизации методов (352): 1. Случай линейных задач (352) 5.6.6. Об оптимизации методов (352): 1. Случай линейных задач (352). 2 Случай нелинейных задач (354).
5.7. Дополнения и замечания к главе 5
5.7.1. Регулярные методы решения некорректно поставленных задач (355) 1. Основные понятия (355). 2. Теория точности регулярных методов (356). 3. Примеры регулярных методов (357). 5.7.2. Вычисление оценочной функции (357): 1. Общие результаты (357). 2. Примеры (358). 5.7.3. Численные алгоритмы выбора параметра регуляризации (359). 5.7.4. Об отыскании всех решений операторных уравнений (360) 1. Случай линейных уравнений (360). 2. Случай нелинейных уравнений (362) 5.7.5. Обобщенные решения операторных уравнений (363): 1. Негативные пространства (363). 2°. Операторы осреднения (364). 3. Некоторые приложения (364).
Глава 6. Решение интегральных уравнений
6.1. Линейные интегральные уравнения типа Фредгольма второго рода
6.1.1. Определение и основные свойства (365). 6.1.2. Оценка наследственной погрешности (366). 6.1.3. Прямые методы (367): 1. Метод замены ядра на вырожденное (367). 2. Метод коллокации (совпадения) (370). 3. Метод механических квадратур (371). 1. Другие методы (371). 6.1.4. Итеративные методы (371). 6.1.5. Комбинированные методы (372). 6.1.6. Об оптимальных методах (372).
6.2. Линейные интегральные уравнения типа Фредгольма первого рода
6.2.1. Метод регуляризации (375). 6.2.2. Метод квазирешений (378). 6.2.3. Метод принципа невязки (380). 6.2.4. Об оптимальных по точности методах (381).
6.3. Линейные сингулярные интегральные уравнения с ядром Коши и типа свертки
6.3.1. Решение характеристического уравнения (381). 6.3.2. Решение уравнения Винера - Хопфа второго рода (383). 6.3.3. Решение уравнения Винера—Хопфа первого рода (383). 6.3.4. Решение уравнения типа Винера—Хопфа на всей оси (386). 6.3.5. Решение уравнения типа Вннера—Хопфа на конечном отрезке (386). 6.3.6. Решение полного сингулярного интегрального уравнения (387).
6.4. Нелинейные интегральные уравнения
6.4.1. Уравнение Гаммерштейна (389): 1. Определение и свойства (389). 2. Методы приближенного решения (прямые и итеративные) (390). 6.4.2. Уравнение Урысона (391). 6.4.3. Уравнение Вольтерры (392): 1. Определение и свойства (392). 2. Методы типа Рунге — Кутта (393). 3. Некоторые другие методы (394). 6.4.4. Сингулярные уравнения (394). 6.4.5. Некоторые другие уравнения (395).
6.5. Дополнения и замечания к главе 6
6.5.1. Решение интегральных уравнений теории потенциала (396): 1. Основные понятия (396). 2. Методы приближенного решения (397). 6.5.2. Решение интегральных уравнений теории переноса излучения (398). 6.5.3. Решение интегральных уравнений в некоторых других областях математической физики (398). 6.5.4. Решение задач для интегро-дифференинальных уравнений (399).
Глава 7. Численное решение задач Коши для обыкновенных дифференциальных уравнений
7.1. Общие численные методы решения задачи Коши для ОДУ
7.1.1. Основные определения (401). 7.1.2. Линейные многошаговые формулы (402): 1. Аппроксимация (402). 2. Устойчивость (403). 3. Сходимость (404). 4. Формулы Адамса (404). 5. Формулы типа Адамса (405). 6. Обобщенные формулы типа Адамса (406). 7.1.3. Одношаговые формулы (407): 1. Метод Тейлора (407). 2. Методы типа Рунге — Кутта (408). 3. Явные формулы Рунге — Кутта (409). 4. Неявные формулы типа Руите—Кутта (410). 5. Многошаговые формулы типа Рунге—Кутта (411). 6. Устойчивость и сходимость одношаговых формул (413). 7.1.4. Системы ОДУ, ОДУ Высших порядков (413).
7.2. Оптимизация численного решения задач Коши для ОДУ
7.2.1. Устойчивость на более точной модели (415). 7.2.2. Оценки характеристик вычислительных алгоритмов (419): 1. Оценки погрешности дискретизации (419). 2. Оценки погрешности округлений (421). 3. Оценки времени реализации вычислительного алгоритма и требуемой памяти ЭВМ (422). 7.2.3. Вопросы построения вычислительных схем (423): 1. Управление шагом интегрирования (423). 2. Оптимальное распределение узлов интегрирования (423). 3. Параметрическая методика численного интегрирования (424). 4. Схемы предсказания — исправления (предиктор — корректор) (425). 5. Вычисление оценок локальной погрешности метода (426). 6. Двусторонние методы (428). 7.2.4. Оптимизация численных методов по точности и быстродействию (429).
7.3. Решение задач Коши для систем линейных уравнений
7.3.1. Случай постоянных коэффициентов (430). 7.3.2. Случай переменных коэффициентов (431).
7.4. Численные методы решения жестких систем
7.4.1. Введение в теорию жестких систем (437): 1. Пример жесткой системы (437). 2. Основные определения (439). 3. Определение численной устойчивости (439). 7.4.2. Неявные одношаговые методы (440): 1. Неявные и полуявные методы типа Рунге-Кутта (440). 2. Аппроксимация методом Паде (441). 3. Полуявные методы и метод Розенброка (442). 4. Экспоненциальная подгонка (448). 5°. Уравнения высших порядков (448). 7.4.3. Неявные многошаговые методы (448): 1. Формулы дифференцирования назад (448). 2. Методы с переменными матричными коэффициентами (450). 3. Методы, использующие вторую производную (451). 4. Экстраполяционные методы (452). 5. О решении задач специальной структуры (453). 7.4.4. Об оптимизации методов решения жестких систем (454): 1. Постановка задач оптимизации (454). 2. Об оптимальном методе в классе F, (455). 3. Об оптимальном методе в классе Fs (457). 4. Об оптимальных методах в некоторых других классах (458).
7.5. Дополнения и замечания к главе 7
7.5.1. Некоторые дополнительные численные методы (458): 1. Методы Рунге — Кутта — Фельберга (458). 2. Методы экстраполяции (459). 3. Построение параметров ориентации твердого тела (461). 7.5.2. Сведение краевых задач к задачам Коши (463): 1. Линейная краевая задача (463). 2. Нелинейная краевая задача (464). 7.5.3. Сведение к задаче Коши задач минимизации функций и решения уравнений (464): 1. Минимизация функций (464). 2. Решение систем уравнений (465). 7.5.4. Непрерывная регуляризация (466). 7.5.5. Численное решение интегральных иЛинтегро-дифференциальных уравнений Вольтерра (467). 7.5.6. Численное решение задач Коши на гибридной вычислительной системе (ГВС) (470).
Глава 8. Отыскание корней и решение задач минимизации функций
8.1. Отыскание корней алгебраических многочленов
8.1.1. Многочлен одной переменной (472): 1. Методы спуска для отыскания всех корней (472). 2. Некоторые другие методы (474). 8.1.2. Алгебраические многочлены многих переменных4 (474): 1. Метод минимизации модуля многочлена в комплексной области (474). 2. Метод спуска с локальных минимумов (475). 3. Некоторые другие методы (475).
8.2. Методы минимизации унимодальных и выпуклых функций
8.2.1. Функции одной переменной (476): 1. Об оптимальном последовательном поиске (476). 2. Поиск Фибоначчи (476). 3. Метод золотого сечення (477). 4. О некоторых других методах (478). 8.2.2. Негладкие функции многих переменных (478): 1. Классы негладких функций (478). 2. Обобщенный градиентный спуск (479). 3. Метод наискорейшего спуска (480). 4. Методы быстрого спуска и случайного поиска (482). 5. Методы ускорения сходимости (483). 6. Некоторые другие методы (485). 8.2.3. Гладкие функции многих переменных (486): 1. Классы гладких функций (486). 2. Релаксационные методы с применением градиентов (486). 3: Оценки погрешностей для этих методов (487). 4. Ускорение сходимости градиентных методов (488). 5. Методы без применении производных (489). 8.2.4. Об оценках погрешности за счет неточности исходных данных (490).
8.3. Об оптимальных алгоритмах решения многоэкстремальных задач
8.3.1. Постановки задач (492). 8.3.2. Классы функций с условием Липшица (495). 8.3.3. Классы дифференцируемых функций (496). 8.3.4. Классы аналитических и целых функций (498).
8.4. Дополнения и замечания к главе 8
8.4.1. Об оптимальных алгоритмах отыскания корней для некоторых классов функций одной переменной (499). 8.4.2. О решении систем нелинейных алгебраических уравнений (500). 8.4.3. Минимизация позиномов (501). 8.4.4. Минимизация псевдобулевых функций (502). 8.4.5. Об одном методе сведения задач условной минимизации к безусловной (504). 8.4.6. О решении задач линейного программирования с заданной точностью (505): 1. Применение метода невязок (506). 2. О методе Хачняна (507). 8.4.7. Эффективность алгоритмов для дискретных задач математического программирования (507): 1. Полиномиально разрешимые задачи (508). 2. Теория двойственности в дискретном программировании (510). 3. Приближенные алгоритмы с гарантированным отклонением (512). 8.4.8. О методе Монте-Карло для решения многомерных задач оптимизации (513).
Приложения
Приложение 1. Обобщенная классификация задач вычислительной математики
Приложение 2. Обобщенная классификация методов вычислительной математики
Приложение 3. Характеристика основных отечественных ЭВМ
Приложение 4. Обобщенная классификация вычислительных систем
Приложение 5. Характеристика ВП и ВС
Приложение 6. Вспомогательные величины (40 верных десятичных знаков)
Приложение 7. Нормальное распределение
Приложение 8. t-Распределение
Приложение 9. Значения функции Lf, (ep)
Приложение 10. Нижние Yi и верхние у2 границы доверительного интервала
Приложение 11. Уравнения, решения которых — э. ф
Приложение 12. Сводка формул численного дифференцирования
Список литературы
Предметный указатель
Скачать книгу Иванов В. В. Методы вычислений на ЭВМ. Справочное пособие. Издательство "Наукова думка", Киев, 1986
| < Предыдущая | Следующая > |
|---|
