6 Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. Перевод с английского. Под ред. д-ра техн. наук проф. Ю. И. Топчеева. М., «Машиностроение», 1976 г.
389 с. с ил.
В книге приведены алгоритмы решения всех основных задач линей, ной алгебры. Соответствующие алгоритмы реализованы в виде процедур на алгоритмическом языке АЛГОЛ-60, сопровождаемых тесто, выми задачами. Особый интерес для специалистов по теории управления представляют алгоритмы решения полной проблемы собственных значений для произвольных матриц.
Книга предназначена для широкого круга научных работников, инженеров, использующих вычислительные машины для решения прикладных задач, а также для специалистов по программированию, аспирантов и студентов различных специальностей.
30502-013 038 (01)-76
13—76
6Ф7.3
Оглавление
Предисловие к русскому изданию.................. 11
Предисловие к английскому изданию ................ 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).
Алгоритм 1.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. Теоретические предпосылки (ИЗ). 2. Применение алгоритма (115). 3. Список формальных параметров (115). 4. Программы на языке АЛГОЛ (116). 5. Организация процедур и обозначения (121). 6. Оценка точности решения (122). 7. Примеры использования процедур и результаты их проверки (123).
Алгоритм 1.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).
Часть П
Алгебраическая проблема собственных значений
Алгоритмы и их назначение .................... 173
1. Введение (173). 2. Список процедур (174). 3. Действительные плотные симметрические матрицы (174). 4. Симметрические ленточные матрицы (176). 5. Одновременное определение собственных значений и векторов симметрических редких матриц (177). 6. Обобщенная проблема собственных значений для симметрических матриц (177). 7. Эрмитовы матрицы (178). 8. Действительные плотные несимметрические матрицы (178). 9. Несимметрические ленточные матрицы (180). 10. Плотные несимметрические матрицы с комплексными элементами (180).
Алгоритм П.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 и QL-методов для определения собственных значений и векторов симметрических матриц.......... 203
1. Теоретические предпосылки (203). 2. Применение алгоритма (206). 3. Список формальных параметров (207). 4. Программы на языке АЛГОЛ (207). 5. Организация процедур и обозначения (210). 6. Оценка точности решения (211). 7. Примеры использования процедур и результаты их проверки (211).
Алгоритм II.4. ^/.-алгоритм с неявным сдвигом ........... 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).
Алгоритм Н.6. QR-алгоритм в сочетании с методом Ньютона для вычисления отдельных собственных значений симметрических трехдиаго-вальных матриц . ........................ 230
1. Теоретические предпосылки (230). 2. Применение алгоритма (233). 3. Список формальных параметров (233). 4. Программы на языке АЛГОЛ (234). 5. Организация процедур и обозначения (235). 6. Оценка точности решения (235). 7. Примеры использования процедур и результаты их проверки (236).
Алгоритм II.7. Q/7-алгоритм для симметрических ленточных матриц . . . 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).
Алгоритм Н-9. Метод одновременной итерации для симметрических
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 и Q/7-алгоритмы для вычисления собственных векторов действительных и комплексных матриц............ 327
1. Теоретические предпосылки (327). 2. Применение алгоритма (428). 3. Список формальных параметров (329). 4. Программы на языке АЛГОЛ (330). 5. Организация процедур и обозначения (339). 6. Оценка точности решения (340). 7. Примеры использования процедур и результаты их проверки (342).
Алгоритм 11.16. Модифицированный LR-алгоритм для вычисления собственных значений комплексной матрицы в форме Хессенберга . . . 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
Предисловие к русскому изданию
Предлагаемый вниманию читателя перевод «Справочника алгоритмов на языке АЛГОЛ. Линейная алгебра» Уилкинсона и Райнша будет с интересом встречен всеми, кто использует в своей научной и практической деятельности цифровые вычислительные машины. Справочник содержит 84 процедуры, написанные на языке АЛГОЛ-60, и охватывает широкий класс алгоритмов, связанных с решением систем линейных уравнений, псевдообращением матриц, вычислением собственных значений и собственных векторов. При описании каждого алгоритма исследована область применения, дано подробное описание процедуры на алгоритмическом языке, а также оценка точности и результаты тестовой проверки. При разработке процедур значительное внимание было уделено экономии памяти и обеспечению высокой скорости сходимости алгоритмов.
Данный справочник существенно дополнит известные справочники алгоритмов [102—106, 112 ]. Он позволит значительно повысить эффективность использования ЦВМ при решении прикладных задач оптимального управления, планирования и проектирования автоматизированных систем. Алгоритмы, приведенные в справочнике, можно использовать для построения специализированных рабочих программ анализа и синтеза автоматических систем, построения переходных процессов, обработки информации, оценки эффективности автоматизированных систем.
С теоретическими основами решения систем линейных уравнений, методов оптимальной обработки информации, линейного программирования и обобщенной проблемой собственных значений читатель может ознакомиться в отечественных книгах, приведенных в списке литературы, добавленной при переводе. Для читателей, желающих освоить приемы программирования на языке АЛГОЛ, мы также даем перечень соответствующих книг.
Проверка значительной части алгоритмов показала, что без каких-либо модификаций они могут применяться на отечественных вычислительных машинах (БЭСМ-6, БЭСМ-4, М-220; ЕС ЭВМ), оснащенных трансляторами с языка АЛГОЛ-60.
Выпуск данного справочника свидетельствует о том, что автоматизация программирования достигла высокого уровня развития и позволяет реализовать преемственность алгоритмов, независимо от типа используемых ЦВМ.
Книга рассчитана на научных работников и инженеров, использующих вычислительные машины для решения прикладных задач, а также для специалистов по программированию, аспирантов и студентов различных специальностей.
Ю. Топчеев
Цена: 300руб.
