Парлетт Б. Симметричная проблема собственных значений. Численные методы: Пер. с англ. - М., 1983, 384 с.
Книга известного американского специалиста по вычислительной алгебре, содержащая систематическое описание численных методов решения задач на собственные значения. В ней представлены важные разделы, недостаточно полно освещенные а литературе на русском языке -- полная теория метода Ланцоша, методы одновременных итераций и др. Для чтения не требуется высокой математической подготовки.
Для математиков-вычислителей, инженеров, решающих задачи алгебры на ЭВМ.
Оглавление
Предисловие к русскому изданию....................................5
Предисловие........................................................7
Введение . ...................................................11
Глава 1. Основные сведения о самосопряженных матрицах ...... 16
§ 1.1. Введение...........................16
§ 1.2. Евклидово пространство..................................16
§ 1.3. Собственные значения................. . 20
§ 1.4. Самосопряженные матрицы ...............................21
§ 1.5. Квадратичные формы......................................25
§ 1.6. Матричные нормы........................................28
§ 1.7. Обобщенная проблема собственных значений................31
Глава 2. Задачи, помехи и средства . .'..............................33
§ 2.1. Что мало? Что велико? .................. 33
§ 2.2. Задачи ................................35
§ 2.3. Противоречивые требования . ....... ... . . 36
§ 2.4. Арифметика конечной точности 39
§ 2.5. Взаимное уничтожение ........................42
§ 2.6. Анализ скалярного произведения...................45
§ 2.7. Можно ли находить малые собственные значения с малой
относительной ошибкой? ..... .......................49
§ 2.8. Существующие программы .................50
§ 2.9. Длительность вычислений...... 52
§ 2.10. Другие виды машинной архитектуры ......53
Глава 3. Количество собственных значений 55
§ 3.1. Треугольное разложение........................55
§ 3.2. Анализ ошибок треугольного разложения . .........59
§ 3.3. Деление спектра ..............................62
§ 3.4. Связь с последовательностями Штурма .......... 68
§ 3.5. Методы деления пополам и секущих .......... . 69
§ 3.6. Скрытые собственные значения ........ 71
§ 3.7. Характеристический многочлен ...... 72
Глава 4. Простые векторные итерации .............. 74
§ 4.1. Собственные векторы матриц ранга ...... 74
§ 4.2. Прямая и обратная итерация ........ 75
§ 4.3. Преимущества плохо обусловленной системы .......81
§ 4.4. Сходимость и ортогональность.......... . 84
§ 4.5. Простые оценки ошибок............... 85
§ 4.6. Итерация с отношением Релея ........... 86
§ 4.7. Локальная сходимость ............... 68
§ 4.8. Монотонность невязок ............91
§ 4.9. Глобальная сходимость ............... 92
Глава 5. Исчерпывание ......................
§ 5.1. Исчерпывание вычитанием ........... . . 97
§ 5.2. Исчерпывание посредством сужения........................100
§ 5.3. Исчерпывание посредством подобных преобразований .... 101
Глава 6. Полезные ортогональные матрицы. (Орудия ремесла.) ...... 103
§ 6.1. Важность ортогональности .............. 10З
§ 6.2. Перестановки...... 104
§ 6.3. Отражения (или симметрии)................105
§ 6.4. Плоские вращения................ 108
§ 6.5. Распространение ошибки в последовательности ортогональных конгруэнций......110
§ 6.6. Обратный анализ ошибок ..................... 113
§ 6.7. QR-разложение и процесс Грама—Шмндта ................ 114
§ 6.8. Быстрые масштабированные вращения ...............116
§ 6.9. Ортогонализация в условиях округлений ...............121
Глава 7. Трехдиагональная форма ................ 127
§ 7.1. Введение......... 127
§ 7.2. Единственность приведения ................... 128
§ 7.3. Минимальные характеристики ................... 130
§ 7.4. Явное приведение заполненной матрицы ................. 132
§ 7.5. Приведение ленточной матрицы .................. 136
§ 7.6. Кажущаяся неустойчивость ................... 139
§ 7.7. Собственные значения — простые...................... 140
§ 7.8. Ортогональные многочлены ...................141
§ 7.9. Собственные векторы ................ 144
§ 7.10. Последовательность Штурма ..............147
§ 7.11. Когда можно пренебречь внедиагональным элементом ................. 150
§ 7.12. Обратные задачи на собственные значения 152
Глава 8. Алгоритмы QR в QL ....................... 156
§ 8.1. Введение 156
§ 8.2. QL-преобразование ...157
§ 8.3. Сохранение ширины ленты ...158
§ 8.4. Связь между алгоритмами QL и QR... 159
§ 8.5. QL, степенной метод и обратная итерация ...160
§ 8.6. Сходимость основного QL-алгоритма .... 162
§ 8.7. Отношение Релея как сдвиг ......163
§ 8.8. Внедиагональные элементы.......................165
§ 8.9. Оценка невязки прн сдвиге по Уилкинсону .....166
§ 8.10. Трех диагональный QL-алгоритм сходится всегда ........ . 168
§ 8.11. Асимптотическая скорость сходимости....... . . 171
§ 8.12. Трехдиагональный QL-алгоритм с явными сдвигами ........ 174
§8.13. Вытеснение выступа ............176
§ 8.14. Сдвиги на любой случай ................ 179
§ 8.15. Как избавиться от квадратных корней .........181
§ 8.16. QL-алгоритм для ленточных матриц .............. 188
Глава 9. Методы Якоби ............ 191
§ 9.1. Вращение плоскости................... 191
§ 9.2. Вращения Якоби ....................... 192
§ 9.3. Сходимость ........................ 195
§ 9.4. Различные стратегии......197
§ 9.5. Асимптотически квадратичная сходимость 198
§ 9.6. Оценка методов Якоби............................201
Глава 10. Оценки для собственных значений ................203
§ 10.1. Теорема Коши о разделении ................... 204
§ 10.2. Минимаксные характеризацни .............206
§ 10.3. Теорема о монотонности ..............209
§ 10.4. Теорема о разделении с учетом невязок ............212
§ 10.5. Оптимальные интервалы Леманна................216
§ 10.6. Использование оценок для отсутствующей подматрицы ............. 221
§ 10.7. Использование лакуи в спектре ................. 225
Глава 11. Аппроксимации из подпространства ............... 228
§ 11.1. Подпространства и их представление ....... 228
§ 11.2. Инвариантные подпространства ............230
§ 11.3. Процедура Релея —Ритца ............ 232
§ 11.4. Оптимальность..........................234
§ 11.5. Оценки через невязку для очень близких значений Ритца ...........237
§ 11.6. Оценок для векторов Ритца через невязки не существует ............. 240
§ 11.7. Отделенность в спектре ................ 241
§ 11.8. Сжатие невязки......................245
§ 11.9. Априорные оценки для внутренних аппроксимаций Ритца................. 246
§ 11.10. Неортогональные базисы ...................... 249
§ 11.11. Теорема о расширении ................... 251
Глава 12. Подпространства Крылова .................255
§ 12.1. Введение........................................255
§ 12.2. Основные свойства..................... 257
§ 12.3. Полиномиальные представления ..............259
§ 12.4. Оценки Каниэля и Саада для ошибок ............262
§ 12.5. Сравнение со степенным методом ......... 270
§ 12.6. Частичное приведение к трехднагональному виду.................... 272
Глава 13. Алгоритмы метода Ланцоша...................... 276
§ 13.1. Подпространства Крылова + процедура Релея — Ритца = метод Ланцоша 276
§ 13.2. Оценивание точности f ............. 279
§ 13.3. Влияние арифметики с конечной точностью ............. 281
§ 13.4. Теорема Пэжа . . . . ............ 284
§ 13.5. Альтернативная формула для Ру.......... 288
§ 13.6. Сходимость вызывает потерю ортогональности .............. 289
§ 13.7. Сохранение ортогональности ............292
§ 13.8. Выборочная ортогоналнзация ..............295
§ 13.9. Анализ выборочной ортогонализации................ 300
§ 13.10. Ленточный (нли блочный) алгоритм Ланцоша ............ 305
Глава 14. Итерирование подпространства ................ 309
§ 14.1. Введение .................. 309
§ 14.2. Реализации ..................... 311
§ 14.3. Усовершенствования .................. 316
§ 14.4. Сходимость....................... 318
§ 14.5. Секционные методы .................. 322
Глава 15. Обобщенная линейная проблема собственных значений .................. 325
§ 15.1. Введение................................................325
§ 15.2. Симметрии недостаточно..................................326
§ 15.3. Одновременная диагонализация двух квадратичных форм 329
§ 15.4. Явное приведение к стандартной форме..................332
§ 15.5. Приведение Фикса — Хайбергера ..........334
§ 15.6. QZ-алгоритм........... ...............338
§ 15.7. Обобщенный метод Якоби......................338
§ 15.8. Неявное приведение к стандартной форме . ...........340
§ 15.9. Простые векторные итерации......341
§ 15.10. Аппроксимации Релея — Ритца ............345
§ 15.11. Алгоритмы Ланцоша.........................346
§ 15.12. Итерирование подпространства ....................349
§ 15.13. Практические соображения ...... ..................352
Приложение А. Элементарные матрицы и матрицы ранга единица................354
Приложение В. Многочлены Чебышева . . ........................356
Литература................ . 359
Аннотированная библиография ...........................367
Обозначения ...............369
Именной указатель .........371
Предметный указатель ........... 373
