Уилкинсон Райнш. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. Перевод с английского. Под ред. д-ра техн. наук проф. Ю. И. Топчеева. М., «Машиностроение», 1976 г.
В книге приведены алгоритмы решения всех основных задач линейной алгебры. Соответствующие алгоритмы реализованы в виде процедур на алгоритмическом языке АЛГОЛ-бО, сопровождаемых тестовыми задачами. Особый интерес для специалистов по теории управления представляют алгоритмы решения полной проблемы собственных значений для произвольных матриц.
Книга предназначена для широкого круга научных работников, инженеров, использующих вычислительные машины для решения прикладных задач, а также для специалистов по программированию, аспирантов и студентов различных специальностей.
Оглавление
Предисловие к русскому изданию.................. И
Предисловие к английскому изданию ................ 12
Часть I
Системы линейных уравнений, метод наименьших квадратов и линейное программирование
Алгоритмы и их назначение .................... 13
1. Введение (13). 2. Список процедур (13). 3. Положительно определенные матрицы (14). 4. Неположительные симметрические матрицы (16). 5. Произвольные матрицы (17). 6. Метод наименьших квадратов и псевдообращение матриц (18). 7. Задача линейного программирования (19)
Алгоритм 1.1. Треугольное разложение положительно определенных симметрических матриц............. 20
1. Теоретические предпосылки (20). 2. Применение атго-ритма (23). 3. Список формальных параметров (24). 4. Программы на языке АЛГОЛ (26). 5. Организация процедур и обозначения (33). 6. Оценка точности решения (35). 7. Примеры использования процедур и результаты их проверки (36).
Алгоритм І.2. Итерационное уточнение решения системы уравнений с положительно определенной матрицей .............. 40
1. Теоретические предпосылки (40). 2. Применение алгоритма (41). 3. Список формальных параметров (42). 4. Программы на языке АЛГОЛ (43). 5. Организация процедур и обозначения (46). 6. Оценка точности решения (47). 7. Примеры использования процедур и результаты их проверки (49).
Алгоритм 1.3. Обращение положительно определенных матриц методом Гаусса.....................•......... 52
1. Теоретические предпосылки (52). 2. Применение алгоритма (53). 3. Список формальных параметров (53). 4. Программы на языке АЛГОЛ (53). 5. Организация процедур и обозначения (54). 6. Оценка точности решения (55). 7. Примеры использования процедур и результаты их проверки (55).
Алгоритм 1.4, Симметричное треугольное разложение положительно
определенных ленточных матриц ................. 56
1. Теоретические предпосылки (56). 2. Применение алгоритма (57). 3. Список формальных параметров (57). 4. Программы на языке АЛГОЛ (58). 5. Организация процедур и обозначения (59). 6. Оценка точности решения (60). 7. Примеры использования процедур и результаты их проверки (61).
Алгоритм 1.5. Метод сопряженных градиентов . ........... 63
1. Теоретические предпосылки (63). 2. Применение алгоритма (64). 3. Список формальных параметров (65). 4. Программы на языке АЛГОЛ (65). 5. Организация процедур и обозначения (66). 6. Оценка точности решения (67). 7. Примеры использования процедур и результаты их проверки (68).
Алгоритм 1.6. Решение систем уравнений с ленточными матрицами и вычисление собственных векторов ленточных матриц ........ 71
1. Теоретические предпосылки (71). 2. Применение алгоритма (74). 3. Список формальных параметров (75). 4. Программы на языке АЛГОЛ (77). 5. Организация процедур и обозначения (85). 6. Оценка точности решения (86). 7. Примеры использования процедур и результаты их проверки (88).
Алгоритм 1.7. Решение действительных и комплексных систем линейных уравнений .......... 92
1. Теоретические предпосылки (92). 2. Применение алгоритма (95). 3. Список формальных параметров (95). 4. Программы на языке АЛГОЛ (97). 5. Организация процедур и обозначения (102). 6. Оценка точности решения (103). 7. Примеры использования процедур и результаты их проверки (104).
Алгоритм 1.8. Применение преобразований Хаусхолдера при реализации метода наименьших квадратов ..... 107
1. Теоретические предпосылки (107). 2. Применение алгоритма (108). 3. Список формальных параметров (108). 4. Программы на языке АЛГОЛ (109). 5. Организация процедур и обозначения (111). 6. Оценка точности решения (111). 7. Примеры использования процедур и результаты их проверки (112).
Алгоритм 1.9. Решение систем уравнений и проблема наименьших квадратов .............................. 113
1. Теоретические предпосылки (113). 2. Применение алгоритма (115). 3. Список формальных параметров (115). 4. Программы на языке АЛГОЛ (116). 5. Организация процедур и обозначения (121). 6. Оценка точности решения (122). 7. Примеры использования процедур и результаты их проверки (123).
Алгоритм Ї.10. Разложение по сингулярным числам и проблема наименьших квадратов........ 125
1. Теоретические предпосылки (125). 2. Применение алгоритма (129). 3. Список формальных параметров (131). 4. Программы на языке АЛГОЛ (131). 5. Организация процедур и обозначения (136). 6. Оценка точности решения (137). 7. Примеры использования процедур и результаты их проверки (137).
Алгоритм 1.11. Реализация симплекс-метода с использованием треугольного разложения .............. 140
1. Теоретические предпосылки (140). 2. Применение алгоритма (147). 3. Список формальных параметров (148). 4. Программы на языке АЛГОЛ (156). 5. Организация процедур и обозначения (164). 6. Оценка точности решения (165). 7. Примеры использования процедур и результаты их проверки (167).
Часть II
Алгебраическая проблема собственных значений
Алгоритмы и их назначение ..........................173
1. Введение (173). 2. Список процедур (174). 3. Действительные плотные симметрические матрицы (174). 4. Симметрические ленточные матрицы (176). 5. Одновременное определение собственных значений и векторов симметрических редких матриц (177). 6. Обобщенная проблема собственных значений для симметрических матриц (177). 7. Эрмитовы матрицы (178). 8. Действительные плотные несимметрические матрицы (178). 9. Несимметрические ленточные матрицы (180). 10. Плотные несимметрические матрицы с комплексными элементами (180).
Алгоритм II. 1. Метод Якоби для действительных симметрических матриц 182
1. Теоретические предпосылки (182). 2. Применение алгоритма (183). 3. Список формальных параметров (183). 4. Программы на языке АЛГОЛ (18)4. 5. Организация процедур и обозначения (185). 6. Оценка точности решения (186). 7. Примеры использования процедуры и результаты проверки (187).
Алгоритм II.2. Преобразование Хаусхолдера для приведения симметрической матрицы к трехдиагональной форме............. 190
1. Теоретические предпосылки (190). 2. Применение алгоритма (191). 3. Список формальных параметров (192). 4. Программы на языке АЛГОЛ (193). 5. Организация процедур и обозначения (197). 6. Оценка точности решения (199). Г. Примеры использования процедур и результаты их проверки (200).
Алгоритм 11.3. Применение QR и методов для определения собственных значений и векторов симметрических матриц.......... 203
1. Теоретические предпосылки (203). 2. Применение алгоритма (206). 3. Список формальных параметров (207). 4. Программы на языке АЛГОЛ (207). 5. Организация процедур и обозначения (210). 6. Оценка точности решения (211). 7. Примеры использования процедур и результаты их проверки (211).
Алгоритм Н.4. QL-алгоритм с неявным сдвигом 216
1. Теоретические предпосылки (216). 2. Применение алгоритма (218). 3. Список формальных параметров (218). 4. Программы на языке АЛГОЛ (219). 5. Организация процедур и обозначения (221). 6. Оценка точности решения (221). 7. Примеры использования процедур и результаты их проверки (221).
Алгоритм 11.5. Вычисление собственных значений симметрической трех-диагональной матрицы методом деления отрезка пополам .... 22 ^
1. Теоретические предпосылки (223). 2. Применение алгоритма (224). 3. Список формальных параметров (224). 4. Программы на языке АЛГОЛ (224). 5. Организация процедур и обозначения (226). 6. Оценка точности решения (227). 7. Примеры использования процедур и результаты их проверки (228).
Алгоритм 11.6. ф/?-алгоритм в сочетании с методом Ньютона для вычисления отдельных собственных значений симметрических трехдиагональных матриц ......................... 230
1. Теоретические предпосылки (230). 2. Применение алгоритма (233). 3. Список формальных параметров (233). 4. Программы на языке АЛГОЛ (234). 5. Организация процедур и обозначения (235). 6. Оценка точности решения (235). 7. Примеры использования процедур и результаты их проверки (236).
Алгоритм 11.7. Q/^-алгоритм для симметрических ленточных матриц . . , 238
1. Теоретические предпосылки (238). 2. Применение алгоритма (238). 3. Список формальных параметров (238). 4. Программы на языке АЛГОЛ (239). 5. Организация процедур и обозначения (241). 6. Оценка точности решения (242). 7. Примеры использования процедур и результаты их проверки (242).
Алгоритм 11.8. Приведение симметрической ленточной матрицы к трех-диагональной форме ........ 244
1. Теоретические предпосылки (244). 2. Применение алгоритма (246). 3. Список формальных параметров (246). 4. Программы на языке АЛГОЛ (246). 5. Организация процедур и обозначения (247). 6. Оценка точности решения (248). 7. Примеры использования процедур и результаты их проверки (249).
Алгоритм 11.9. Метод одновременной итерации для симметрических матриц ............................ 252
1. Теоретические предпосылки (252). 2. Применение алгоритма (252). 3. Список формальных параметров (252). 4. Программы на языке АЛГОЛ (255). 5. Организация процедур и обозначения (260). 6. Оценка точности решения (263). 7. Примеры использования процедур и результаты их проверки (264).
Алгоритм 11.10. Решение полной проблемы собственных значений для систем уравнений общего вида с симметрическими матрицами..... 267
1. Теоретические предпосылки (267). 2. Применение алгоритма (268). 3. Список формальных параметров (268). 4. Программы на языке АЛГОЛ (269). 5. Организация процедур и обозначения (272). 6. Оценка точности решения (273). 7. Примеры использования процедур и результаты их проверки (274).
Алгоритм 11.11. Масштабирование матриц при вычислении собственных значений и векторов.............. 277
1. Теоретические предпосылки (277). 2. Применение алгоритма (280). 3. Список формальных параметров (280). 4. Программы на языке АЛГОЛ (281). 5. Организация процедур и обозначения (282). 6. Оценка точности решения (283). 7. Примеры использования процедур и результаты их проверки (283).
Алгоритм 11.12. Решение проблемы собственных значений по методу Якоби с понижением нормы для действительных матриц....... 287
1. Теоретические предпосылки (287). 2. Применение алгоритма (288). 3. Список формальных параметров (289). 4. Программы на языке АЛГОЛ (289). 5. Организация процедур и обозначения (292). 6. Оценка точности решения (293). 7. Примеры использования процедуры и результаты ее проверки (293).
Алгоритм 11.13. Приведение матриц общего вида к форме Хессенберга 298
1. Теоретические предпосылки (298). 2. Применение алгоритма (300). 3. Список формальных параметров (300). 4. Программы на языке АЛГОЛ (302). 5. Организация процедур и обозначения (307). 6. Оценка точности решения (308). 7. Примеры использования процедур и результаты их проверки (309).
Алгоритм 11.14. р/?-алгоритм для вычисления собственных значений действительной матрицы в форме Хессенберга............ 316
1. Теоретические предпосылки (316). 2. Применение алгоритма (319). 3. Список формальных параметров (320). 4. Программы на языке АЛГОЛ (320). 5. Организация процедур и обозначения (322). 6. Оценка точности решения (323). 7. Примеры использования процедур и результаты их проверки (323).
Алгоритм 11.15. LR и -алгоритмы для вычисления собственных векторов действительных и комплексных матриц .......... 327
1. Теоретические предпосылки (327). 2. Применение алгоритма (428). 3. Список формальных параметров (329). 4. Программы на языке АЛГОЛ (330). 5. Организация процедур и обозначения (339)., 6, Оценка точности решения (340). 7. Примеры использования процедур и результаты их проверки (342).
Алгоритм 11.16. Модифицированный £/?-алгоритм для вычисления собственных значений комплексной матрицы в форме Хессенберга . . . 348
1. Теоретические предпосылки (348). 2. Применение алгоритма (350). 3. Список формальных параметров (350). 4. Программы на языке АЛГОЛ (351). 5. Организация процедур и обозначения (353). 6. Оценка точности решения (353). 7. Примеры использования процедур и результаты их проверки (353).
Алгоритм 11.17. Решение проблемы собственных значений по методу Якоби с понижением нормы для комплексных матриц......... 355
1. Теоретические предпосылки (355). 2. Применение алгоритма(356). 3. Список формальных параметров (356). 4. Программы на языке АЛГОЛ (357). 5. Организация процедур и обозначения (360). 6. Оценка точности решения (362). 7. Примеры использования процедур и результаты их проверки (362).
Алгоритм 11.18. Определение отдельных собственных векторов методом обратной итерации ............... 367
1. Теоретические предпосылки (367). 2. Применение алгоритма (369). 3. Список формальных параметров (370). 4. Программы на языке АЛГОЛ (371). 5. Организация процедур и обозначения (380). 6. Оценка точности решения (381). 7. Примеры использования процедур и результаты их проверки (382).
Список литературы ........................ 385
Литература, добавленная при переводе книги ............ 386
