18 Симметричная проблема собственных значений. Численные методы: Пер. с англ.— М.: Мир, 1983. 384 с.
Книга известного американского специалиста по вычислительной алгебре, содержащая систематическое описание численных методов решения задач на собственные значения. В ней представлены важные разделы, недостаточно полно освещенные в литературе на русском языке — полная теория метода Ланцоша, методы одновременных итераций и др. Для чтения не требуется высокой математической подготовки
Для математиков-вычислителей, инженеров, решающих вадачи алгебры на ЭВМ
Предисловие к русскому изданию
Профессор Бересфорд Парлетт сейчас является одним из самых видных американских специалистов по вычислительной алгебре. Он приобрел известность еще в 60-е годы, опубликовав цикл статей по геометрической теории сходимости LR и QR-ме-тодов. Другие его заметные достижения связаны с работой по созданию алгоритмов решения симметричных неопределенных линейных систем и численной реализации метода Ланцоша. В первом случае речь идет об алгоритмах, которые имея быстродействие и запросы к памяти, сравнимые с методом Холесского, обладали бы для неопределенных систем относительной устойчивостью, свойственной методам типа метода Гаусса с выбором главного элемента. Эта деятельность, начатая вместе с Рейдом и продолженная совместно с Банчем, привела в конечном счете к появлению двух эффективных алгоритмов, называемых сейчас методом Аасена и методом Банча соответственно.
Очень большой вклад внесен Парлеттом в теорию и практику метода Ланцоша, который в последние годы стал основным средством решения разреженных симметричных задач.
В гл. 13 читатель познакомится с алгоритмом выборочной ортогонализации, разработанным автором (совместно со Скоттом) и предназначенным для отыскания группы младших или старших собственных чисел и соответствующих собственных векторов. В последующих работах, уже не отраженных в книге, Парлетт обращается к алгоритму Ланцоша как методу вычисления всего спектра, а затем как методу решения больших симметричных систем уравнений. (Изложение этих работ Парлетта, как и работ других авторов, связанных с методом Ланцоша, читатель найдет в моем обзоре «Разреженные матрицы», опубликованном в сборнике «Математический анализ. Т. 20» ежегодника ВИНИТИ «Итоги науки и техники».)
В литературе по численной алгебре, отечественной и переводной, имеются существенные пробелы. Возьмем, к примеру, методы вычисления собственных значений и обратимся к популярному «Справочнику алгоритмов на языке АЛГОЛ» Уил-кинсона — Райнша, переведенному в 1976 г. в издательстве «Машиностроение». Ни в одной книге, изданной на русском языке после 1970 г., мы не найдем описания ряда методов, реализован-
Оглавление
Предисловие к русскому изданию.................. 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. Собственные векторы матриц ранга 1 ,......., , , 74
§ 4.2. Прямая и обратная итерация............., , 75
§ 4.3. Преимущества плохо обусловленной системы .,,,.,, 81
§ 4.4. Сходимость и ортогональность . ,........, , , , 84
§ 4.5. Простые оценки ошибок............., , > , 85
§ 4.6. Итерация с отношением Релея . . . ........... 86
§ 4.7. Локальная сходимость , , , , , , . , , , , , , , • . , , • 88
4.8. Монотонность невязок
4.9. Глобальная сходимость
Глава 5. Исчерпывание ,....,,,.,,,,,,,,,,.... 97ч
§ 5.1. Исчерпывание вычитанием ...'.,. ........... 97 V:
§ 5.2. Исчерпывание посредством сужения ......... ... lOO^1"
§ 5.3. Исчерпывание посредством подобных преобразований .... 101 '
•tj
Глава 6. Полезные ортогональные матрицы. (Орудия ремесла.) . , , . 103
§ 6.1. Важность ортогональности .,....,.,,,,,,,. 103 *#
§ 6.2. Перестановки ....... ......,,,.,.,,. 104
§ 6.3. Отражения (или симметрии) ,,,,,,,,,.,,,.. 105 -
§ 6.4. Плоские вращения .................... 108 ••
§ 6.5. Распространение ошибки в последовательности ортогональных >•
конгруэнции ........... , ..... , , , . . ^ 1 10 *
§ 6.6. Обратный анализ ошибок ,..,,..•.., ..... , . 1 13
§ 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-преобразование ..... ..... ....... t •• 15?
§ 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-алгоритм с явными сдвигами I , . . 174 §8.13, Вытеснение выступа -> . ...... ..,..,.,»*• 176 ~
§ 8.14. Сдвиги на любой случай ,...,. , , ,,,,.,. ;, 179 § 8Д5,, Как избавиться от квадратных корней ,,,,,,..,. 181 §8.16, QL-алгоритм для ленточных матриц , . , . , ,. ., . , , , 188
Глава в. 'Методы Якоби ...,,,.,,,,...,,.,, , , , . I91 '•
8.1. Вращение плоскости
9.2. Воащения Якоби .
§ 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. От|Ь11енность в спектре................, 241
§ 11.8. Сжтие невязки.....,............... 245
*§ 11.9. Априорные оценки для внутренних аппроксимаций Ритца 246
*§ 11.10. Неортогональные базисы .,.,.,....,.,.., 249
*§ 11.11. Теорема о расширении .,,,,,,.,,,..,,,. 251
Глава |2. Подпространства Крылова .,,,.,,,.,,,,,,., 255
§ 12.1. Введение...................., , , , 255
§ 12.2. Основные свойства.......,.....,,.,,, 257
§ 12.3. Полиномиальные представления......, ,..... 259
*§ 12.4. Оценки Каниэля и Саада для ошибок....., , . , . 262
§ 12.5. Сравнение со степенным методом.......... i i i 270
§ 12.6. Частичное приведение к трех диагональ ному виду . . , , , 272
Глава 13. Алгоритмы метода Ланцоша............... 276
§13.1. Подпространства Крылова + процедура Релея—Ритца = метод Ланцоша ..,,,,......,,,,,,,,, 276
§ 13.2. Оценивание точности ,.............., , , 279
§ 13.3. Влияние арифметики с конечной точностью....... 281
§ 13.4. Теорема Пэжа...............,,.,., 284
§ 13.5. Альтернативная формула для Р/ ............ i 288
§ 13.6. Сходимость вызывает потерю ортогональности .,.,,., 289
413.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
Цена: 150руб.
