Дж. Деммель - Вычислительная линейная алгебра, страница 46

Пусть А — квадратная матрица с собственными значениями Л,. Применяя к форме Шура матрицы А вопрос 4.4 либо к жордановой форме равенство (4.6), убедиться, что собственными значениями матрицы )'(А) являются числа ~(Л;). Это утверждение называется теоремой о спектральном отобраэкении. Данный результат используется в доказательстве теоремы 6.5 и в разд. 6.5.6. Вопрос 4.6 (средней трудности). В этой задаче будет показано, как решается уравнение Сильвестра АХ вЂ” ХВ = С, где Х и С вЂ” матрицы размера т х п, А— матрица размера т х т и  — размера п х п (при т = п, В = А это уравнение называется уравнением Ляпунова).

Уравнение Сильвестра представляет собой систему из тп линейных уравнений относительно элементов матрицы Х. 1. Пусть известны разложения Шура матриц А и В. Указать способ преобразования уравнения АХ вЂ” ХВ = С в уравнение А'У вЂ” УВ' = С', где А' и В' — верхнетреугольные матрицы. 2. Указать способ последовательного вычисления элементов матрицы У, аналогичный обратной подстановке. Какое условие для собственных значений матриц А и В гарантирует невырожденность системы уравнений относительно элементов искомой матрицыу 3.

Указать способ преобразования матрицы У в матрицу Х. Вопрос 4.7 (средней трудности). Предположим, что матрица Т = ~ ~А С1 имеет форму Шура. Требуется найти матрицу Я, такую, что Б 'ТБ ! А 0 1 л1 ~. Оказывается, что можно взять матрицу Я вида ~ г, ~. Указать способ вычисления матрицы Я. Вопрос 4.8 (средней трудности; Х.Ваг). Пусть А — матрица размера т х и, а  — матрица размера и х т. Показать, что матрицы В 0 В ВА подобны. Вывести отсюда, что ненулевые собственные значения матриц АВ и ВА совпадают. Вопрос 4.9 (средней трудности; Т Ва1). Пусть А — матрица порядка п с собственными значениями Лы..., Л„. Доказать, что 1=1 Вопрос 4.10 (средней трудности; Е Ва)). Пусть А — матрица порядка п с собственными значениями Лы ., ., Л„.

4.8. Вопросы к главе 4 201 1. Показать, что А может быть представлена в виде А = Н+Б, где Н = Н*— эрмитова матрица, а Я = — Я* — косоэрмитова матрица. Указать явные выражения для Н и 5 через А. 2. Доказать, что 2 '„"., )ЯЛ,)г < 8Н(ф. 3. Доказать, что 2",ы, )ЭЛ,(г < 8Я('гк. 4. Показать, что А тогда и только тогда является нормальной матрицей (т. е. АА* = А'А), когда 2,", )Л;)г = '8А8ф,.

Вопрос 4.11 (легкий). Пусть Л вЂ” простое собственное значение, а х и у — соответствующие собственные векторы, правый и левый. Определим спектральный проектор, ассоциированный с Л, формулой Р = ху*/(у'х). Доказать следующие свойства проектора Р: 1. Р определен единственным образом несмотря на то, что в его определении вместо векторов х и у можно использовать любые ненулевые их кратные. 2. Р' = Р. (Всякая матрица, удовлетворяющая соотношению Р' = Р, называется проектором) . 3. АР = РА = ЛР. (Эти равенства объясняют название «спектральный проектор», поскольку Р «содержит в себе» информацию о левом и правом собственных подпространствах для собственного значения Л.) 4. Число обусловленности собственного значения Л равно йРйг. Вопрос 4.12 (легкий; Т Ва«).

Пусть А= ~ ~ . Показать, что для обоих соб~а с1 1/г й *р А бу» (1«(~ Таким образом, число обусловленности велико, если разность собственных значений а — Ь мала в сравнении с числом с, характеризующим величину внедиагонэльной части матрицы. Вопрос 4.13 (средней трудности; 2. Ва«). Пусть А — матрица, х — нормированный вектор Ихуг = 1), р — число и г = Ах — рх. Доказать, что найдется матрица Е с нормой )(Е)(к = '8г8г, такая, что р является собственным значением для А+ Е, а х — соответствующим собственным вектором.

Вопрос 4.14 (средней трудности; программирование). В этой задаче используется Ма11аЬ-программа, вычисляющая числа обусловленности собственных значений и выдающая на терминал диаграмму расположения собственных значений возмущенной матрицы. (Программа находится в НОМЕРАСЕ/Ма11аЬ/ е13эса1.ш.) Входными параметрами являются: а = исходная матрица, ег; = величина возмущения, ш = число обрабатываемых возмущенных матриц. На выходе будут получены три диаграммы, на которых собственные значения возмущенных матриц указаны специальными символами: символом «о» обозначается собственное значение исходной матрицы; символ «х» обозначает собственное значение возмущенной матрицы, полученной из а добавлением вещественного возмущения с нормой егг; 202 Глава 4.

Несимметричная проблема собственных значений символ «.» обозначает собственное значение возмущенной матрицы, полученной из а добавлением комплексного возмущения с нормой егг. Кроме того, печатается таблица, содержащая собственные значения матрицы а н их числа обусловленности. Вот примеры некоторых матриц, представляющих интерес для нашего эксперимента. (Постарайтесь взять как можно большее ш; хороший выбор значения т — это число порядка нескольких сотен.) (1) а = галсЫ(5) (если у а нет комплексных собственных значений, примените процедуру гапдп повторно) егг=1е-б, 1е-4, 1е-З, 1е-2, .

1, . 2 (2) а = 41ак(спев (4, 1), 1); егг=1е-12, 1е-10, 1е-8 (3) а=ГГ1 1еб 0 0]; ГО 2 1е-3 0]; ГО 0 3 10]; Го О "1 4П егг=1е-8, 1е-7, 1е-б, 1е-б, 1е-4, 1е-3 (4) Гс(,г]=с(г(гапбп(4,4));а=о»41ак(спев(3, 1), 1)»о' егг=1е-16, 1е-14, 1е-12, 1е-10, 1е-8 (5) а = ГГ1 1еЗ 1еб]; ГО 1 1еЗ]; ГО 0 1]] егг=1е-7, 1е-б, 5е-б, 8е-б, 1е-5, 1.5е-5, 2е-5 (б) а = ГГ1 0 0 0 0 0]; ГО 2 1 0 0 0]; ГО 0 2 0 0 0]; ГО 0 0 3 1е2 1е4]; ГО 0 0 0 3 1е2]; ГО 0 0 0 0 3]] егг=1е-10, 1е-8, 1е-б, 1е-4, 1е-3 Ваша задача состоит в том, чтобы провести вычисления для этих примеров и сравнить области, локализующие вычисленные собственные значения (так называемый псевдоспектр матрицы), с границами ошибок, указанными в равд.

4.3. Каково различие ме»кву вещественными и комплексными возмущениями? Что происходит с областями локализации собственных значений, когда возмущение егг стремится к нулю? Каков предельный размер этих областей при егг, стремящемся к нулю (т.е. сколько верных разрядов имеют вычисленные собственные значения)? Вопрос 4.15 (средней трудности программирование). В этой задаче используется Ма11аЪ-программа, которая выводит на терминал графики диагональных элементов матрицы, обрабатываемой ЯВ;итерацией без сдвигов. Каждому диагональному элементу на графике соответствует своя кривая, полученная нз значений этого элемента после каждой ЯВситерации.

(Программа находится в 4.8. Вопросы к главе 4 203 НОМЕРАОЕ/Ма11аЬ/с)тра.ш; ниже мы приводим ее текст.) Входными пара- метрами являются: а = исходная матрица, ш = число Яй-итераций. На выходе будут получены графики диагональных элементов. Вот примеры, для которых нужно использовать эту программу (возьмите достаточно большое значение ш с тем, чтобы кривые либо успели сойтись к своему предельному значению, либо обнаружили циклическое поведение): а = гапбп(б); Ь = гвпИ(б); а = Ь«41а8([1,2,3,4,5,5])*1вч(Ь); а = [[1 10]; [-1 1]]; ш = 300 а = 41аб((1.5«опев(1,5)) + . 01» (Ыаб(опев (4, 1), 1)+41а8(опев(4, 1), -1) ); в=30 Что происходит в том случае, если у матрицы есть комплексные собственные значения? В каком порядке выстраиваются на диагонали собственные значения матрицы после многих итераций? Проделайте следующий эксперимент: пусть а — симметричная п х и- матрица.

Выполним команду МаНаЬ'а репи=(п:-1:1). Это породит список целых чисел от и до 1 в порядке убывания. Проведем гп шагов ЯН-итерации. Положим а=а(регш,регш); мы называем эту операцию «зерквльным отражением» матрицы а, поскольку она изменяет порядок строк и столбцов на обратный. Снова проделаем ш шагов (]Н-итерации и опять положим а=а(репи,репи). Как эта матрица соотносится с первоначальной? Значение ш не должно быть слишком болыпим (попробуйте взять т = 5), иначе ошибки округлений могут помешать вам выявить искомую взаимосвязь. (См.

также следствие 5.4 и вопрос 5.25.) Измените программу так, чтобы она вычисляла разности между диагональными элементами на калСдом шаге и их предельными значениями (сделайте это в предположении, что все собственные значения матрицы вещественны). Выведите на терминал графики логарифмов указанных разностей как функций от номера шага ш. Как выглядят эти графики асимптотически? Ьо14 оХХ е=41а8(а); Хог 1=1:ш, [й, г] =«1г (а); И=бйаб (в18п (о1а8 (г ) ) ); г=И«г; о=о«И; а=тес; е=[е,41аб(а)]; еЫ с18 р1ог(е', 'в'),8г14 Вопрос 4.16 (трудный; программирование).

В этой задаче описывается приложение нелинейной проблемы собственных значений к компьютерной графике, вычислительной геометрии и автоматизированному проектированию; см. также [181, 182, 155]. Пусть | = (Лр(гы гю гз)) — матрица, элементами которой являются много- члены от трех переменных вь В общем случае, уравнение ое1(Р) = 0 опреде- 204 Глава 4.

Несимметричная проблема собственных значений ляет некоторую двумерную поверхность 5 в трехмерном пространстве. Пусть уравнения х1 — — д1(1), хг = дг(1), хз = дз(1) задают (одномерную) кривую С с параметром 1; функции д1 также являются многочленами.

Требуется найти пересечение Я Г) С. Сформулировать эту задачу как проблему собственных значений (что дает способ ее численного решения). Более общо, указать, как следует находить пересечение поверхности с)ес(Р(х1,...,Х„)) = 0 и кривой (х, = д,(1), 1 < 1 < и). Найти максимальное возможное число дискретных решений как функцию от и, порядка д матрицы Г и максимальной из степеней многочленов Лз и ды Написать Май!аЪ-программу, решающую эту задачу с и = 3 переменными путем сведения к проблеме собственных значений. Входом программы должно быть компактное описание коэффициентов всех многочленов у„. (Ха) и д1(1), а выходом — список точек пересечения. Например, входная информация может состоять из следующих массивов: ° массива ЫшпТеппя(1: 11,1: Ы), где ХшпТеппя (1', у) есть число одночленов в многочлене Ду(х1, хг, хз); ° массива Яяешя(1: 4,1:Тояа1Теппя), где Тоза)Теппя есть сумма всех элементов массива ЫшпТеппя.

Каждый столбец массива Бзеппя дает описание одного одночлена. При этом первые ЫшпТеппя(1,1) столбцов массива БФеппя представляют одночлены, входящие в многочлен У11, следующие ЫпшТеппя(2,1) столбцов массива Бзеппя представляют одночлены из 721, и т. д. Одночлен, описываемый столбцом пеппе(1:4,Й), имеет вид ~л яыгпь11,Ь) яыпп(2,й) я1епп)З,Ф) 'хг ' хз ° массива ЗС(1:3), содержащего степени многочленов д1, дг и дз в указанном порядке; ° массива Спгче(1: 1С(1)+1С(2)+сС(3)+3), содержащего коэффициенты многочленов д1, дг и дз. Многочлены следуют один за другим и коэффициенты каждого перечисляются в порядке от свободного члена к коэффициенту при наивысшей степени. Ваша программа должна еще вычислять оценки ошибок для полученных результатов. Это будет возможно лишь, если к решаемой задаче на собственные значения применймы оценки ошибок из теорем 4.4 или 4.5.

Если вы встретитесь с более общим случаем, то вычисление границ для ошибок опускается. (Оценки ошибок для более общих спектральных задач можно найти в (10, 237).) Написать еще одну Ма$1аЪ-программу, которая для случая ти = 3 выводила бы графики поверхности Я и кривой С, а также помечала бы точки пересечения. Предусмотрены ли в ваших программах какие-либо ограничения на входные данные? Что произойдет, если Б и С не пересекаются? Что произойдет, если С целиком принадлежит о? Посчитайте с помощью ваших программ, по крайней мере, приводимые ниже примеры.

Для первых пяти из них вы сможете найти ответ посредством ручных вычислений. Это поможет проверить правильность работы программ. Х1+Х2+ХЗ 0 0 Зхг + 5хг — 7хз + 10 4,8. Вопросы к главе 4 205 х1 + хз + хз 0 0 Зх» + 5хз — 7хз + 10 Х1+ Хз+ ХЗ 0 0 Зхз + 5хз — 7хз + 10 ! 1 0 0 ЗХ1 + 5хз — Тхз + 9 ! Х1 + Х2 + ХЗ 0 0 Зхз + 5хз — 7хз + 8 ! Х1 + Х2 + ХЗ Х1 хз Зх» + 5хз — 7хз + 10 2. д1 = »~, дз = 1+»~, дз = 2+ 2~, Г = 3 д1 22 дз 1+12 дз = 2+12 г' 4. д1 = 12 дз = 1+ 12, дз = 2+ 12, Г = 5. д1 = 22, д2 = 1 + »2 дз = 2 + 12, Г = 6 д1 = 4~ дз = 1+2~ дз = 2+2~, Р' = 7.