Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 45
Текст из файла (страница 45)
4.6. Резюме В приводимом ниже списке суммированы содержащиеся в данной главе сведения о канонических формах, алгоритмах, их стоимостях и приложениях к обыкновенным дифференциальным уравнениям (ОДУ). Даны также некоторые сведения об алгоритмах, использующих симметрию матрицы, хотя более подробно эти алгоритмы рассматриваются в следующей главе. Алгоритмы для разреженных матриц обсуждаются в гл. 7. А — Л1 — ЛКорданова форма; для некоторой невырожденной матрицы Я имеем сихт Л,— Л 1 А — Л1 = Я ° 61ая 1 Л,— Л Форма Шура: для некоторой унитарной матрицы Я имеем А — ЛЕ = Я(Т вЂ” Л1)Сг', где Т вЂ” треугольная матрица.
Вещественная форма Шура вещественной матрицы А: для некоторой вещественной ортогональной матрицы Ч имеем А — Л1 = Я(Т вЂ” Л1)Ят, где Т вЂ” вещественная квазитреугольнал матрица. Приложение к ОДУ: позволяет решать задачу х(1) = Ах($) + 1(1). Алгоритм: выполнить приведение к форме Хессенберга (алгоритм 4.6), а затем с помощью ЯГс-итерации вычислить форму Шура (алгоритм 4.5, реализация которого описана в равд.
4.4.8). Собственные векторы могут быть найдены из формы Шура (как показано в разд. 4.2.1). Стоимость: составляет 10пг флопов, если нужны только собственные значения, 25п флопов, если требуются также матрицы Т и Я, и несколько больше 27п флопов, если нужно вычислить и собственные векторы. Не все составляющие алгоритма могут использовать ВВАЛИ-операции уровня 3, поэтому сравнение с матричным умножением, в действительности, дает менее благоприятные результаты, чем простое сопоставление указанных выше стоимостей с 2пг флопов, требуемых для перемно- 197 4.6. Резюме жения п х п-матриц; на 1ВМ ВЯ6000/590 вычисление собственных значений требует времени, большего не в (10пз)/(2пз) = 5 рвз, а в 23 раза при п = 100 и 19 рвз при п = 1000 [10, стр.
62]. При вычислении на той же машине и собственных значений, и собственных векторов происходит замедление не в (27пз)/(2пз) = 135 раз, а в 41 раз прн и = 100 и 60 раз при п = 1000. Таким образом, вычисление собственных значений несимметричных матриц является дорогостоящей процедурой. (Аналогичная процедура для симметричного случая много дешевле; см. гл.
5.) ЬАРАСК: программы зиеев для вычисления формы Шура и вяеее для вычисления собственных значений н собственных векторов; аналогичные программы вяеевх и вяеечх, дополнительно вычисляющие границы для погрешностей. Ма1!аЬ: команды всЬпг для вычисления формы Шура и е1я для вычисления собственных значений и собственных векторов. Использование симметрии: (более эффективные алгоритмы для случая А = А' обсуждаются в гл.
5, более точно, в равд. 5.3). ° Регулярный пучок А — ЛВ(бес(А — ЛВ) ф О) — Форма Вейерштрасса: для некоторых невырожденных матриц Рь и Рл имеем 1 Л р — 1 я А — ЛВ = Рв 61ая Жордан, Л 1 Обобщенная форма Шура: для некоторых унитарных матриц Яь и Ян имеем А — ЛВ = Яь(Тл — ЛТв)Чя, где обе матрицы Тл и Тв — треугольные. Обобщенная вещественная форма Шура для вещественных матриц А и В: для некоторых вещественных ортогональных матриц Яь и Ял имеем А — ЛВ = Яь(Тл — ЛТвЯй, где Тл и Тв — вещественные матрицы, причем Тл — квазитреугольная, а Тв — треугольная.
Приложение к ОДУ: позволяет регпать задачу Вх(1) = Ах(1) + /(1), решение которой может негладко зависеть от входных данных (импульсный отклик). Алгоритм: приведение матриц А и В соответственно к хессенберговой и треугольной формам; последующее применение ЯХ-итерации (представляющей собой ЯВ;итерацию, которая неявно проводится для матрицы АВ ').
Стоимость: вычисление матриц Тд и Тв требует 30пз флопов. Дополнительное вычисление матриц Яь и Яя увеличивает стоимость до 66пз флопов. Если нужны и собственные векторы, то общая стоимость возрастает почти до 69пз флопов. Как и выше, ВЬАБ-операции уровня 3 могут использоваться не во всех частях алгоритма. ЬАРАСК: программы вбйев для вычисления формы Шура и вбйее для вычисления собственных значений и собственных векторов; анвлогич- 198 Глава 4. Несимметричная проблема собственных значений ные программы в88евх и вяйечх, дойолнительно вычисляющие границы для погрешностей. Ма41аЬч команда е48 для вычисления собственных значений и собствен- ных векторов. Использование симметрии: если А = А*, В = В' и В положительно определена, то задача может быть сведена к вычислению собственных значений одной симметричной матрицы (см.
доказательство теоремы 4.12). Так делается в ЬАРАСК-программах ввуйч, вврй» (для симме- тричных матриц в «упакованной форме») и ваЬ8ч (для симметричных ленточных матриц) ° Сингулярный пучок А — Л — Форма Кронекера: для некоторых невырожденных матриц Рг. и Рл имеем А — ЛВ=Рь си и (пс~-1) йа8 Вейерштрасс, л '. н Обобщенная верхняя треугольная форма: для некоторых унитарных матриц Ць и Ял имеем А — ЛВ = Яг.(Тл — ЛТвЯ*, где Тд и Тн имеют обобщенную верхнюю треугольную форму, диагональные блоки которой соответствуют различным частям формы Кронекера. Подробности относительно формы и алгоритмов см. в [79, 246).
Стоимость: для самой общей и надежной версии алгоритма может доходить до 0(п~) флопов в зависимости от особенностей кронекеровой структуры; это гораздо больше, чем для регулярного пучка А — ЛВ. Имеется также несколько менее надежный алгоритм со стоимостью 0(пз) флопов [27]. Приложение к ОДУ: позволяет решать задачу Вх[4) = Ах(4) + /[~), которая может быть переопределена или недоопределена.
Программы: см. ХЕТЬ1В/11па)8/8пр1гй — Ае з 1 Π— Аа з ° ° .. — Ао О ° О 1 О ° Π— Л1. О 1 О и Матричный пучок 2, Л'А; [118] — Если Ае = 1 (или квадратная матрица Ае достаточно хорошо обусловлена для того, чтобы каждую матрицу А, можно было заменить матрицей Ав 'А,), то линеаризация приводит к стандартной задаче 199 4.8.
Вопросы к главе 4 — Если матрица Аг плохо обусловлена или вырожденна, то задача линеаризуется к пучку — Аа| — Аг г 1 0 0 1 0 — Ао 0 0 0 1 0 4.7. Литература и смежные вопросы к главе 4 Обсуждение свойств собственных значений и собственных векторов см. в [139]. Более подробное обсуждение теории возмущений для спектральных задач можно найти в [161, 237, 52] и гл. 4 книги [10]. Теорема 4.7 доказана в [69]. Вопрос о канонических формах Вейерштрасса и Кронекера освещается в [110, 118]. По поводу приложений этих форм к системам и теории управления см. [246, 247, 78].
Их приложения к вычислительной геометрии, графике и машинному проектированию рассматриваются в [181, 182, 165]. Параллельные алгоритмы для несимметричной проблемы собственных значений обсуждаются в [76]. 4.8. Вопросы к главе 4 Вопрос 4.1 (легкий). Пусть матрица А определена уравнением (4.1). Показать, что бег(А) = П,. Ое1(Аа) и, как следствие, бес(А — Л1) = П,, с(ес(Ан— Л1). Сделать отсюда вывод, что множество собственных значений матрицы А есть объединение множеств собственных значений блоков Ап,..., Аы.
Вопрос 4.3 (легкий; л. Ва1). Пусть Л и р — различные собственные значения матрипы А. Пусть числу Л соответствует правый собственный вектор х, а числу р — левый собственный вектор у. Доказать, что х и у ортогонвльны. Вопрос 4.4 (среднгй трудности). Предположим, что все собственные значения матрицы А различны. Пусть 1(г) = 2~ а,г' — функция, определенная на множестве этих собственных значений. Пусть Я*АД = Т есть форма Шура матрицы А (так что сг унитарная, а Т верхнетреугольная матрицы).
1. Показать, что 7'(А) = Я~(ТЯ*. Таким образом, чтобы вычислить 1(А), достаточно научиться вычислять 1 (Т). Остальная часть данной задачи имеет целью вывод простых рекуррентных формул для вычисления 1(Т). 2. Показать, что (1(Т))н = 1(Та). Таким образом, диагональ матрицы 1(Т) может быть вычислена по диагонали Т. Вопрос 4.2 (средней трудности; Я.
Ва1). Пусть А — норгаальн л матрица, т. е. АА* = А'А. Показать, что если А к тому же треугольная, то она диагональная. Опираясь на этот факт, доказать, что п х н-матрица тогда и только тогда является нормальной, когда она имеет п ортонормированных собственных векторов. Указание: показать, что А — нормальная матрица в том и только в том случае, если ее форма Шура — нормальная матрица.
200 Глава 4. Несимметричная проблема собственных значений 3. Показать, что Т~(Т) = ~(Т)Т. 4. Используя этот результат, показать, что 1-я наддиагональ матрицы 1(Т) может быть вычислена по ее ~г — 1)-й и предшествующим нвддиагоналям. Тем самым, отправляясь от главной диагонали матрицы 1(Т), мы можем вычислить первую нвддиагональ, затем вторую, и т. д. Вопрос 4.5 (легкий).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
