Уилкинсон Дж.X. Алгебраическая проблема собственныx значений. - М., 1970. -565 с.
Книга посвящена численным методам решения задач алгебры, в основном методам отыскания собственных значений матриц и соответствующих им собственных векторов. Однако в ней достаточно полно представлены методы решения и других задач алгебры, таких как решение систем линейных алгебраических уравнений, отыскание корней функций и т. д. Книга состоит из девяти глав.
В главах I, II излагается вспомогательный материал, содержащий основы теории линейной алгебры.
Главы III, IV, V содержат анализ ошибок округления простейших операций, некоторых линейных преобразований, методов решения систем линейных уравнений. Материал этих глав является фундаментом всех дальнейших исследований.
Главы VI, VII содержат описание и анализ ошибок методов приведения общей матрицы к матрице специального вида. Рассматриваются методы решения полной проблемы собственных значений этих матриц.
В главах VIII, IX излагается обширный материал с анализом ошибок по решению полной проблемы собственных значений степенными методами.
ОГЛАВЛЕНИЕ
Предисловие переводчиков..............................................15
Предисловие автора......................................................16
Глава 1. Теоретическое обоснование......................................19
Введение ............................................................19
Определения ........................................................20
Собственные значения и собственные векторы транспонированной матрицы 21
Различные собственные значения ....................................22
Преобразования подобия..............................................23
Кратные собственные значения и канонические формы матриц общего вида 24
Неполная система собственных векторов..............................26
Жорданова (классическая) каноническая форма........................27
Элементарные делители ..............................................28
Сопровождающая матрица характеристического полинома..............28
Полные матрицы ....................................................29
Каноническая (рациональная) форма Фробениуса......................31
Связь между жорданойой и фробениусовой каноническими формами ......32
Преобразования эквивалентности......................................32
λ-матрицы............................................................33
Элементарные операции ..............................................33
Каноническая форма Смита ..........................................34
Наибольший общий делитель k-строчных миноров λ-матрицы............36
Инвариантные множители (А — λI)....................................36
Треугольная каноническая форма......................................37
Эрмитовы и симметричные матрицы....................................38
Элементарные свойства эрмитовых матриц..............................39
Комплексные симметричные матрицы..................................40
Приведение к треугольной форме унитарными преобразованиями .... 40
Квадратичные формы ................................................40
Необходимые и достаточные условия положительной определенности ......41
Дифференциальные уравнения с постоянными коэффициентами..........43
Решения, соответствующие нелинейным элементарным делителям .... 43
Дифференциальные уравнения высшего порядка........................45
Уравнения второго порядка специального вида........................46
Явное решение уравнения Ву = —А у..................................47
Уравнения вида (АВ — λI) х=0.......................................48
Минимальный полином вектора........................................49
Минимальный полином матрицы......................................49
Теорема Кэли — Гамильтона............................................50
Соотношения между минимальным полиномом и каноническими формами 51
Корневые векторы....................................................53
Элементарные преобразования подобия................................54
Свойства элементарных матриц........................................55
Приведение к треугольной канонической форме элементарными преобразованиями подобия..................................................56
Элементарные унитарные преобразования............................57
Элементарные унитарные эрмитовы матрицы (матрицы отражения) ... 58
Приведение к треугольному виду элементарными унитарными преобразованиями ..........................................................59
Нормальные матрицы ..............................................60
Коммутирующие матрицы ..........................................61
Собственные значения А В..............................................63
Векторные и матричные нормы........................................63
Подчиненные матричные нормы ......................................64
Евклидова и спектральная нормы....................................65
Нормы и пределы....................................................67
Некоторые оценки без использования бесконечных матричных рядов . . 69
Дополнительные замечания............................................69
Глава 2. Теория возмущений..............................................70
Введение ............................................................70
Теорема Островского о непрерывности собственных значений..........71
Алгебраические функции..............................................72
Численные примеры..................................................73
Теория возмущений для простых собственных значений................74
Возмущение соответствующих собственных векторов....................74
Матрица с линейными элементарными делителями......................75
Возмущения первого порядка собственных значений....................75
Возмущения первого порядка собственных векторов....................76
Возмущения высоких порядков ......................................77
Кратные собственные значения........................................77
Теоремы Гершгорина ...........................................78
Теория возмущений, основанная на теоремах Гершгорина..............79
Возмущения,[соответствующие общему распределению нелинейных делителей 85
Теория возмущений для собственных векторов матриц, основанная на исследовании жордановой канонической формы..........................86
Возмущения собственных векторов, соответствующих кратным собственным
значениям (линейные элементарные делители)......................88
Ограничения теории возмущений......................................88
Соотношения между sі..............................................89
Обусловленность вычислительных проблем............................90
Числа обусловленности ..............................................90
Спектральное число обусловленности матрицы по отношению к проблеме
собственных значений............................................90
Свойства спектрального числа обусловленности........................91
Инвариантные свойства чисел обусловленности........................92
Очень плохо обусловленные матрицы..................................93
Теория возмущений] для вещественных симметричных матриц .... 96
Несимметричные возмущения........................................96
Симметричные возмущения ........................................96
Классическая техника..............................................97
Симметричная матрица с рангом единица............................99
Экстремальные свойства собственных значений........................100
Минимаксные свойства собственных значений..........................101
Собственные значения суммы двух симметричных матриц..............103
Практические применения ............................................104
Дальнейшие применения принципа минимакса..........................104
Теорема разделения................................................104
Теорема Виландта — Гофмана ......................................105
Дополнительные замечания............................................109
Глава 3. Анализ ошибок................................................110
Введение ............................................................110
Операции с фиксированной запятой....................................110
Накопление скалярного произведения ................................111
Операции с плавающей запятой......................................112
Упрощенные выражения для границ ошибок..........................113
Оценки ошибок для некоторых основных вычислений с плавающей запятой ИЗ
Оценки норм матриц ошибок..........................................115
Накопление скалярных произведений в арифметике с плавающей запятой 115
Оценки ошибок для некоторых основных вычислений fl2 () с двойным числом
разрядов..........................................................116
Вычисление квадратных корней ................................118
Блочно-плавающие векторы и матрицы . . .............................118
Основные ограничения t-разрядных вычислений..........................119
Методы определения собственных значений, основанные на подобных
преобразованиях..................................................121
Анализ ошибок методов, основанных на элементарных неунитарных преобразованиях ......................................................123
Анализ ошибок методов, основанных на элементарных унитарных преобразованиях ...........................................................124
Преимущество унитарных преобразований..............................125
Вещественные симметричные матрицы..................................126
Ограничения унитарных преобразований..............................127
Анализ ошибок вычисления плоских вращений с плавающей запятой . . 128
Умножение на плоское вращение......................................130
Умножение на последовательность плоских вращений..................131
Ошибка в произведении приближенных плоских вращений............135
Ошибки в подобных преобразованиях..................................136
Симметричные матрицы ..............................................137
Плоские вращения в арифметике с фиксированной запятой..............139
Другое вычисление sin 0 и cos 0........................................140
Левое умножение на приближенное вращение с фиксированной запятой 141
Умножение на последовательность плоских вращений ..............142
Вычисленное произведение приближенной последовательности плоских
вращений ........................................................143
Ошибки в подобных преобразованиях..................................144
Общее замечание об оценках ошибки..................................146
Матрицы отражения с плавающей запятой..............................147
Анализ ошибок вычисления матрицы отражения........................148
Численный пример ..................................................151
Левое умножение на приближенную матрицу отражения................152
Умножение на последовательность приближенных матриц отражения . . 154
Неунитарные элементарные матрицы, аналогичные плоским вращениям 156
Неунитарные элементарные матрицы, аналогичные матрицам отражения 157
Левые умножения па последовательность неунитарных матриц..........159
Априорные оценки ошибок............................................160
Отклонение от нормальности..........................................160
Простые примеры....................................................162
Апостериорные оценки..................................................163
Апостериорные оценки для нормальных матриц..........................163
Отношение Релея ..................................................165
Ошибка в отношении Релея............................................166
Зрмптовы матрицы....................................167
Патологически близкие собственные значения............................169
Ненормальные матрицы ..............................................171
Анализ ошибок для полной собственной системы........................172
Численный пример ..................................................173
Условия, ограничивающие достижимую точность........................173
Нелинейные элементарные делители ..................................174
Приближенные инвариантные подпространства..........................176
Почти нормальные матрицы ..........................................178
Дополнительные замечания............................................178
Глава 4. Решение линейных алгебраических уравнений......................179
Введение ............................................................179
Теория возмущений..................................................179
Числа обусловленности ..............................................180
Уравновешенные матрицы ............................................181
Простые практические примеры........................................182
Обусловленность матрицы собственных векторов........................183
Явное решепие ......................................................184
Общие замечания об обусловленности матриц..........................184
Связь плохой обусловленности и почти вырожденности................185
Ограничения, накладываемые ^-разрядной арифметикой................186
Алгорифмы решения линейных уравнений..............................187
Метод Гаусса........................................................188
Треугольное разложение ............................................189
Структура матриц треугольного разложения..........................189
Явные выражения для элементов треугольных матриц..................190
Несостоятельность метода Гаусса......................................192
Численная устойчивость ..............................................192
Значение перестановок................................................193
Численный пример ..................................................194
Анализ ошибок метода Гаусса........................................196
Верхние оценки матриц возмущения для арифметики с фиксированной
запятой ........................................................197
Верхняя оценка для элементов преобразованных матриц................198
Выбор главного элемента по всей матрице............................199
Практический процесс с выбором главного элемента по столбцу .... 200
Анализ ошибок с плавающей запятой..................................200
Разложение с плавающей запятой без выбора главного элемента .... 201
Потеря верных знаков............................202
Общераспространенная ошибка........................................203
Матрицы специального вида..........................................203
Метод Гаусса на быстродействующей вычислительной машине............205
Решения, соответствующие различным правым частям..................206
Прямое треугольное разложение......................................206
Связь метода Гаусса с прямым треугольным разложением..............207
Примеры несостоятельности и неединственности разложения............208
Треугольное разложение с перестановкой строк........................209
Анализ ошибок треугольного разложения..............................211
Вычисление определителей............................................212
Разложение Холецкого ..............................................213
Произвольные симметричные матрицы..................................213
Анализ ошибок разложения Холецкого в арифметике с фиксированной
запятой ..........................................................214
Плохо обусловленная матрица........................................216
Триангуляризация, использующая матрицы отражепия..................218
Анализ ошибок триангуляризации Хаусхолдера........................219
Триангуляризация элементарными устойчивыми матрицами типа Mji . . . 219
Вычисление главных миноров ........................................220
Триангуляризация плоскими вращениями..............................221
Анализ ошибок преобразования Гивенса..............................222
Единственность ортогональной триангуляризации ......................223
Ортогонализация Шмидта ............................................224
Сравнение методов триангуляризации..................................226
Обратная подстановка................................................228
Высокая точность вычисленного решения треугольной системы уравнений 230
Решение общей системы уравнений....................................232
Вычисление общей обратной матрицы..................................233
Точность вычисленных решений ......................................233
Плохо обусловленные матрицы, которые дают немалые ведущие элементы 234
Итерационное улучшение приближенного решения......................235
Влияние ошибок округления на итерационный процесс................236
Итерационный процесс в вычислении с фиксированной запятой..........236
Простой пример итерационного процесса................................237
Общие замечания по итерационному процессу..........................230
Родственные итерационные процессы..................................240
Ограниченность итерационного процесса................................240
Строгое обоснование итерационного метода............................241
Дополнительные замечания............................................241
Глава 5. Эрмитовы матрицы..............................................243
Введение ............................................................243
Классический метод Якоби для вещественных симметричных матриц . . . 243
Быстрота сходимости ................................................244
Сходимость к фиксированной диагональной матрице..................245
Циклический метод Якоби............................................246
Круги Гершгорина ..................................................247
Асимптотическая квадратичная сходимость методов Якоби..............247
Близкие и кратные собственные значения..............................248
Численные примеры..................................................250
Вычисление cos 0 и sin 0..............................................251
Более простое определение углов вращения............................253
Циклический метод Якоби с преградами................................254
Вычисление собственных векторов......................................254
Численный пример ..................................................255
Анализ ошибок метода Якоби..........................................255
Точность вычисленных собственных векторов............................256
Оценки ошибок для вычислений с фиксированной запятой................257
Организационные проблемы ..........................................257
Метод Гивенса........................................................258
Процесс Гивенса на вычислительной машине с двухступенчатой памятью 259
Анализ ошибок процесса Гивенса в арифметике с плавающей запятой 261
Анализ ошибок в арифметике с фиксированной запятой................262
Численный пример ..................................................262
Метод Хаусхолдера ..................................................264
Использование симметрии ............................................266
Некоторые соображения о необходимой величине памяти................261
Процесс Хаусхолдера на вычислительной машине с двухступенчатой
памятью..........................................................267
Метод Хаусхолдера в арифметике с фиксированной запятой..............268
Численный пример ..................................................269
Анализ ошибок метода Хаусхолдера................................270
Собственные значения симметричной трехдиагональной матрицы .... 272
Свойство последовательности Штурма..................................272
Метод деления пополам..............................................274
Численная устойчивость метода деления пополам........................275
Численный пример ..................................................277
Общие замечания о методе деления пополам..........................277
Малые собственные значения..........................................278
Близкие собственные значения и малые Р............................279
Вычисление собственных значений в арифметике с фиксированной запятой 283
Вычисление собственных векторов трехдиагональной матрицы............285
Неустойчивость явного выражения для собственного вектора............286
Численные примеры..................................................288
Обратная итерация .................................................290
Выбор начального вектора ..........................................291
Анализ ошибок......................................................292
Численный пример ..................................................294
Близкие собственные значения и малые βi..............................295
Линейно независимые векторы, соответствующие совпадающим собственным
значениям........................................................296
Другой метод вычисления собственных векторов......................298
Численный пример ..................................................299
Замечания о проблеме собственных значений для трехдиагональных матриц 300
Завершение методов Гивенса и Хаусхолдера............................300
Сравнение методов....................................................302
Квазисимметричные трехдиагональные матрицы........................302
Вычисление собственных векторов..........................303
Уравнения вида.........................304
Численный пример ..................................................305
Одновременное приведение А и В к диагональному виду............307
Трехдиагональные А и В............................................307
Комплексные эрмитовы матрицы....................................308
Дополнительные замечания ..........................................310
Глава 6. Приведение общих матриц к матрицам специального вида .... 311
Введение........................................................311
Метод Гивенса...... ....... ............311
Метод Хаусхолдера ................ ..............313
Соображения о необходимой величине памяти........................315
Анализ ошибок..................................................315
Связь методов Гивенса и Хаусхолдера..............................316
Элементарные устойчивые преобразования ............................318
Значение перестановок............................................319
Прямое приведение к форме Хессенберга............................321
Введение перестановок.......... ............................322
Численный пример ..................................................323
Анализ ошибок................... ..........327
Дальнейший анализ ошибок....................................329
Плохая определимость матрицы Хессенберга..........................331
Приведение к форме Хессенберга матрицами типа Mji....................331
Метод Крылова......................................................332
Метод Гаусса с исключением по столбцам............................332
Практические трудности..............................................333
Обусловленность С для некоторых стандартных расположений собственных
значений..........................................................334
Начальный вектор высоты, меньшей чем п..............................336
Практическое применение ............................................337
Обобщенные процессы Хессенберга....................................338
Срыв обобщенного процесса Хессенберга..............................339
Метод Хессенберга....................................................340
Практическая процедура..............................................341
Связь метода Хессенберга и предыдущих методов......................341
Метод Арнольди ....................................................342
Практические рассмотрения ..........................................343
Значение переортогонализации........................................345
Метод Ланцоша......................................................347
Срыв процесса ......................................................348
Численный пример .....................................349
Практический процесс Ланцоша......................................349
Численный пример ..................................................350
Общие замечания к несимметричному процессу Ланцоша................352
Симметричный процесс Ланцоша......................................352
Приведение матриц Хессенберга к более компактному виду..............353
Приведение нижней матрицы Хессенберга к трехдиагональному виду . . 353
Использование перестановок..........................................354
Влияние малого ведущего элемента....................................355
Анализ ошибок......................................................356
Процесс Хессенберга в применении к нижней матрице Хессенберга . 358
Связь процесса Хессенберга и процесса Ланцоша........................358
Приведение матрицы общего вида к трехдиагональпому виду............359
Сравнение с методом Ланцоша........................................360
Повторное исследование приведения к трехдиагональному виду..........360
Приведение матриц в верхней форме Хессенберга к форме Фробениуоа . . 361
Влияние малых ведущих элементов....................................362
Численный пример ..................................................363
Общие замечания об устойчивости....................................363
Специальная верхняя форма Хессенберга..............................364
Прямое определение характеристического полинома....................365
Дополнительные замечания............................................365
Глава 7. Собственные значения матриц специального вида..................367
Введение ..........................................................367
Явно заданная полиномиальная форма..................................367
Числа обусловленности явно заданных полиномов......................369
Несколько типичных расположений корней............................370
Окончательная оценка метода Крылова................................374
Общие замечания о явно заданных полиномах..........................374
Трехдиагональные матрицы .............................376
Определители матриц Хессенберга......................................378
Влияние ошибок округления..........................................379
Накопление с плавающей запятой....................................380
Вычисление при помощи ортогональных преобразований................381
Вычисление определителей матриц общего вида......................382
Обобщенная проблема собственных значений............................383
Косвенное определение характеристического полинома..................383
Метод Леверье ......................................................384
Итерационные методы, основанные на интерполяции....................385
Асимптотическая скорость сходимости ................................386
Кратные корни ......................................................388
Обращение функционального соотношения..............................389
Метод деления отрезка пополам........................................390
Метод Ньютона......................................................391
Сравнение метода Ньютона с методом интерполяции....................392
Методы, дающие кубическую сходимость..............................393
Метод Лагерра ......................................................393
Комплексные корни..................................................395
Комплексно сопряженные корни........ ......................397
Метод Берстоу ......................................................398
Обобщенный метод Берстоу............................................399
Влияние ошибок округления на асимптотическую сходимость............401
Метод деления отрезка пополам........ ........................401
Последовательная линейная интерполяция..............................403
Кратные и патологически близкие собственные значения................404
Другие интерполяционные методы ....................................405
Методы, в которых: используются производные........................407
Критерий достижения корня..........................................408
Влияние ошибок округления..........................................408
Удаление вычисленных корней ......................................410
Исчерпывание для матриц Хессенберга................................410
Исчерпывание для трехдиагональной матрицы..........................412
Исчерпывание при помощи вращений или устойчивых элементарных преобразований ........................................................414
Устойчивость исчерпывания ..........................................415
Общие замечания об исчерпывании....................................417
Удаление вычисленных нулей ........................................417
Удаление вычисленного квадратичного множителя ....................418
Общие комментарии о методах удаления..............................418
Асимптотическая скорость сходимости..................................419
Сходимость в целом..................................................420
Комплексные корни..................................................422
Рекомендации ......................................................423
Комплексные матрицы................................................424
Матрицы, содержащие независимый параметр..........................424
Дополнительные замечания............................................425
Глава 8. LR- и QR-алгорифмы............................................426
Введение ............................................................426
Вещественные матрицы с комплексными собственными значениями . . . 427
Доказательство сходимости последовательности As......................429
Положительно определенные эрмитовы матрицы........................433
Комплексно сопряженные собственные значения........................434
Введение перестановок..................................................437
Численный пример ..................................................438
Сходимость модифицированного процесса..............................439
Предварительная подготовка исходной матрицы........................439
Инвариантность верхней формы Хессенберга . . . .....................440
Одновременное действие со строками и столбцами......................441
Ускорение сходимости................................................442
Объединение сдвигов..................................................443
Выбор сдвига........................................................444
Исчерпывание матрицы ..............................................445
Экспериментальная проверка сходимости................................446
Улучшенный выбор сдвига............................................447
Комплексyо сопряженные собственные значения........................448
Критика модифицированного Li?-алгорифма............................449
QR-алгорифм ........................................................450
Сходимость QR-алгорифма............................................451
Формальное доказательство сходимости................................452
Нарушение порядка собственных значений..............................453
Равные по модулю собственные значения..............................454
Другое доказательство для LR-метода................................455
Практическое применение QR-алгорифма..............................457
Сдвиг ..............................................................458
Разложение матриц As................................................458
Численный пример ..................................................460
Практическая процедура..............................................460
Устранение комплексно сопряженных сдвигов..........................461
Двойной QR-шаг с использованием матриц отражения..................464
Вычислительные детали ..............................................465
Разложение матриц As................................................466
Прием двойного сдвига для LR........................................467
Сравнение LR- и QR-алгорифмов......................................468
Кратные собственные значения........................................469
Специальное использование процесса исчерпывания . .................472
Симметричные матрицы ..............................................472
Связь между LR- и QR-алгорифмами..................................473
Сходимость LR-алгорифма Холецкого..................................474
Кубическая сходимость QR-алгорифма................................476
Сдвиг в LR-алгорифме Холецкого....................................477
Срыв факторизации Холецкого........................................478
Кубически сходящийся LR-процесс....................................479
Ленточные матрицы..................................................481
LR-разложение ленточной матрицы....................................483
Анализ ошибок ......................................................486
Несимметричные ленточные матрицы....................................487
Одновременное разложение и переумножение в QR-алгорифме............489
Уменьшение ширины ленточной матрицы..............................491
Дополнительные замечания............................................491
Глава 9. Итерационные методы............................................493
Введение ............................................................493
Степенной метод......................................................493
Прямые итерации одного вектора......................................494
Сдвиг начала................. ...................495
Влияние ошибок округления..........................................496
Изменение р ........................................................498
Специальный выбор р................................................499
Процесс ускорения Эйткена............................................500
Комплексно сопряженные собственные значения ........................501
Вычисление комплексного собственного вектора........................502
Сдвиг начала.............................................503
Нелинейные делители................................................504
Одновременное определение нескольких собственных значений..........504
Комплексные матрицы................................................505
Исчерпывание ......................................................505
Исчерпывание, основанное на преобразованиях подобия................506
Исчерпывание, использующее инвариантные подпространства............507
Исчерпывание при помощи устойчивых элементарных преобразований . . 508
Исчерпывание при помощи унитарных преобразований................509
Численная устойчивость..................................510
Численный пример ................................................512
Устойчивость унитарных преобразований..............................513
Исчерпывание при помощи неподобных преобразований..................514
Общее приведение, использующее инвариантные подпространства .... 517
Практическое приложение............................................518
Ступенчатые итерации................................................520
Точное определение комплексно сопряженных собственных значений . . 522
Очень близкие собственные значения..................................523
Метод ортогонализации ..............................................523
Аналог ступенчатых итераций, использующий ортогонализацию..........524
Биортогонализация ..................................................525
Численный пример ..................................................526
Процесс уточнения Ричардсона........................................529
Возведение матрицы в степень........................................530
Численная стабильность.......................................531
Использование полиномов Чебышева..................................532
Общая оценка методов, основанных на прямых итерациях..............533
Обратные итерации ........................................534
Анализ ошибок при обратных итерациях..............................534
Общие комментарии к анализу........................................536
Дальнейшее уточнение собственных векторов..........................536
Нелинейные элементарные делители....................................539
Обратные итерации с матрицами Хессенберга..........................540
Вырожденные случаи ................................................541
Обратные итерации с ленточными матрицами..........................541
Комплексно сопряженные собственные векторы........................542
Анализ ошибок......................................................544
Численный пример ..................................................545
Обобщенная проблема собственных значений............................547
Изменение приближенных собственных значений......................547
Уточнение системы собственных значений..............................549
Численный пример ..................................................551
Уточнение собственных векторов......................................552
Комплексно сопряженные собственные значения........................554
Совпадающие и патологически близкие собственные значения..........555
Замечания о программах на АСЕ......................................557
Дополнительные замечания............................................558
Литература..........................................................559
Часть 1
Часть 2
