Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Дж. Деммель - Вычислительная линейная алгебра

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

Описание файла

PDF-файл из архива "Дж. Деммель - Вычислительная линейная алгебра", который расположен в категории "книги и методические указания". Всё это находится в предмете "квантовые вычисления" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 43 страницы из PDF

Одним из таких множеств является малая окрестность матрицы О 1 О О 1 О Ь О О вЂ” 5 О О О 1 О Число Ь получается умножением машинного эпсилона на константу, равную нескольким тысячам. Чтобы устранить подобные случаи несходимости, в современные реализации алгоритма был добавлен еще один «особый сдвиг». Однако построение стратегии сдвигов, которая гарантировала бы быструю сходимость для всех матриц, остается все еще открытой проблемой. 4.5, Друтие типы несимметричных спектральных задач 4.5.1. Регулярные матричные пучки н каноническая форма Вейерштр асса В стандартной проблеме собственных значений разыскиваются числа и, для которых матрица А — г1 вырожденна; эти числа называются собственными значениями.

Существует несколько важных обобщений этого понятия. Определение 4.6. Пусть А и  — матрицы размера т х и. Матрица А — ЛВ называется матричным пучком, или просто пучком. Здесь Л вЂ” параметр, а не конкретное число. Определение 4Л. Если А и  — квадратные матрицы и бег(А — ЛВ) не равен нулю тождественно, то пучок А — ЛВ называют регулярным. В противном случае, пучок н зывагтся сингулярным. Для регулярного пучка А — ЛВ многочлен р(Л) = «)е»(А — ЛВ) называется характеристическим многочленом, а собственныг значения пучка А — ЛВ определяются как: 186 Глава 4. Несимметричная проблема собственных значений (1) корни многочлена р(Л) = О и, если г1еб(р) < п, (2) сю (кратности, равной п — Лей(р)). Пример 4.12. Пусть А — ЛВ= 1 — Л О Тогда р(Л) = г(ег(А — ЛВ) = (1 — 2Л) (1 — ОЛ) . (Π— Л) = (2Л вЂ” 1)Л, поэтому собственными значениями являются —, О и со.

1 О Матричные пучки возникают естественным образом во многих математических моделях физических систем; ниже мы приведем соответствующие примеры. В следующем предложении указывается связь между собственными значениями регулярного пучка А — ЛВ и собственными значениями некоторой матрицы. Предложение 4.6.

Пусть пучок А — ЛВ регуллрен. Если матрица В невырожденна, то все собственные значения пучка конечны и совпадают с собственными значениами матрицы АВ г или матприцы В гА. Если  — вырожденная матрица, то А — ЛВ имеет собственное значение со кратности п — гапЦВ). Если матприца А невырожденна, то собственные значения пучка А — ЛВ суть числа, обратные к собственным значениям матрицы А 'В или матрицы ВА г. При этпом нулевому собстпвенному значению матприцы А гВ соответствует бесконечное собственное значение пучка А — ЛВ. Доказательство. Если Л' — собственное значение пучка и матрица В невырожденна, то О = г(ег(А — Л'В) = г1еь(АВ ' — Л'1) = г1ес(В ~А — Л'1), поэтому Л' является собственным значением и для матриц АВ ' и В 'А. Для вырожденной В положим р(Л) = г(ег(А — ЛВ) и подставим сюда сингулярное разложение В = УЕИт матрицы В.

Имеем р(Л) = деГ(А — ЛПЕ(тт) = бег(П(ПтАР— ЛЕ)Ит) = ~г(ег(ПтАР' — ЛЕ) Поскольку гапк(В) = гапк(Е), то на диагонали матрицы ПтА)г — ЛЕ параметр Л появляется только гела(В) раз. Поэтому степень многочлена г1е1(ПтАИ вЂ” ЛЕ) равна гапк(В). Если А — невырожденная матрица, то равенство г(еь(А — ЛВ) = О эквивалентно равенству г1еь(1 — ЛА тВ) = О или равенству т1еС(1 — ЛВА г) = О. Эти последние равенства могут выполняться лишь, если Л ,-Е О и -„' есть собственное значение матриц А гВ и ВА '.

П Определение 4.8. Пусть Л' — конечное собственное значение регулярного пучка А — ЛВ. Ненулевой вектор х, такой, что (А — Л'В)х = О или, что эквивалентно, Ах = Л'Вх, называется правым собственным вектором. Длл собственного значения Л' = оо правым собственным вектором называетсл вектпор х ф О, тпакой, чтпо Вх = О. Левый собственный вектор пучка А — ЛВ определяется как правый собственный вектор пучка А* — ЛВ'. Пример 4.13. Рассмотрим пучок А — ЛВ из примера 4.12. Так как А и В— диагональные матрицы, то правые и левые собственные векторы — это просто столбцы единичной матрицы. О 187 4.5. Другие тяпы несимметричных спектральных зааач Пример 4.14. Рассмотрим связанную систему материальных точек из примера 4.1. С этой системой естественным образом связаны два матричных пучка.

Во-первых, задачу на собственные значения — М ' — М 'К можно записать в виде =Л Эта постановка задачи может быть более удачной, если матрица М очень плохо обусловлена, поскольку в этом случае трудно вычислить хорошие приближения к матрицам М 'В и М 'К. Во-вторых, часто рассматривают случай, когда В = 0 (нет затухания). Исходное дифференциальное уравнение в этом случае превращается в Мх(г) + Кх(1) = О. Если искать его решения вида х,(1) = е~*'»х,(0), то получим Лзе""Мх;(0) + е~нКхг(0) = О, или ЛгМх,(0) + Кх,(0) = О. ДРУгими словамн, — Лз есть собственное значение, а х;(0) — правый собственный вектор пучка К вЂ” ЛМ.

Поскольку, по предположению, матрица М невырожденна, — Лз и х,(0) являются собственным значением и собственным вектором и для матрицы М !К. О Бесконечные собственные значения тоже возникают в практических задачах вполне естественным образом. Например, ниже в этом разделе мы покажем, как бесконечные собственные значения связаны с импульсным откликом системы, описываемой обыкновенными дифференциальными уравнениями с линейными ограничениями, иначе говоря, дифференции«ьно-алгебраическими уравнениями (41].

См. также вопрос 4.16, где обсуждаются приложения матричных пучков к вычислительной геометрии и машинной графике. Вспомним, что и теория, и алгоритмы для матричной проблемы собственных значений предусматривали приведение исходной матрицы А с помощью подобия 5 'АЯ к некоторой форме, более «простой», чем А.

Приводимое ниже определение указывает, как обобщить понятие подобия на случай матричных пучков. После этого будут обобщены для пучков и формы Жордана и Шура. Определение 4.9. Пусть Рь и Рл — произвольные невирожденные матри- цы. Роворят, что пучки А — ЛВ и РсАРя — ЛРьВРя эквивалентны. Предложение 4.7. Эквивалснтнмс регулярные пучки А — ЛВ и Р»АРя— ЛРьВРя имеюта одни и те лсе собственные значенил.

Вектор х тогда и только тогда является правым собственным вектором пучка А — ЛВ, когда Р 'х является правым собствснны.м вектором пучка РвАРя — ЛРьВРя. Вектор у тогда и только тогда является левым собственным вектором пучка А — ЛВ, когда (Р~) 1у является левым собственнькм вектором пучка РсАРя — ЛРьВРя.

Доказательство. Равенство с(ег(А — ЛВ) = 0 эквивалентно равенству г(ес(Рь(А — ЛВ)Ря) = О. Равенство (А — ЛВ)х = 0 эквивалентно равенству Рг. (А — ЛВ)РяР 'х = О. 188 Глава 4. Несимметричная проблема собственных значений Равенство (А — ЛВ)'у=О эквивалентно равенству Рл(А — ЛВ)'Р;(Р,*) 'у=О.ГС В следующей теореме каноническая форма Жордана обобщается на случай регулярных матричных пучков. Теорема 4.10 (каноническая форма Вейерштрасса). Для регулярного пучка А — ЛВ найдутся невьсрожденные матрицы Рс. и Рн, такие, что Рь(А — ЛВ)Рй = гйа8(дп,(Лс) Л1пс1 ° Упс(Лп,) Л1п, «п«««п, Дгп«) где У„,.

(Л,) — жорданов блок порядка пс с собственным значением Л,: Л, 1 .Упс(Лс) = 1 Л, а Усспм — гжорданов блок для собственного значения оо кра«пности тс»м 1 Л = 1, — Л,У,. (0). Л 1 Доказательство теоремы можно найти в [110]. Приложения форм Жордаиа и Вейерштрасса к дифференциальным уравнениям Рассмотрим задачу Коши для линейного дифференциального уравнения х(г) = Ах(1) + У(1), х(0) = хо. Ке решение можно выписать в явном виде: х(1) = елсхо + у е"!с «>у(т)дт. Коли мы умеем приводить А к форме Жордана: с лс, А = ЯУЯ ', то, производя в дифференциальном уравнении замену переменного у(с) = Я 'х(1), получим у(с) = Уу(г) + Б с)(С), у(0) = уо = Я 'хо. Решение этой задачи имеет вид у(с) = емуо + ) ед' '>$ сУ(т)сУт.

Имеется явная форз с-« мула, позволяющая найти езс нли любую другую функцию от жордановой матрицы 1. (Эту формулу не следует использовать в машинных вычислениях! В вопросе 4.4 обсуждается более надежный подход к вычислению функций от матрицы.) Предположим, что функция У задана своим рядом Тейлора У(г) = ~ с о —,.; —, а .У вЂ” жорданов блок:,У = Л1+ М; в матрице М первая нэддиагональ состоит из единиц, а прочие элементы равны нулю. Имеем 10> (О) (ЛУ+ 1Ч) с с! с=о У<сс(0) с«с — г (')г-гяс ф««г и с! с=о 1=0 189 4.5. Другие тилы несимметричных спектральных задач /О)(0) /4 «.)»' 'нс Рч«у г! У=е ~=1 = ~ а* ~ Г',"' (*) у=с Л 1 пхн " 'Л /ОО(Л) З з=е /(1) =/ 1 Л у(Л) ур(Л) У" (л): %++л11 (4.6) /'(Л) /(Л) Итак, 1(з) — верхняя треугольная матрица, на у-й налдиагонали которой стоит число /®(Л)/у!.

Для решения более общей задачи Вх = Ах + /(1), где пучок А — ЛВ регулярен, используем форму Вейерштрасса. Предположим, что пучок Рь(А— ЛВ)Рн находится в форме Вейерштрасса, и перепишем уравнение в виде РьВРнР,'х = РьАРнР,'х + Рь/(1). Положим Рл'х = у и Рь/Я = д(1). Теперь задача разлагается в сумму подзадач: 1 „ В последнем равенстве использовано то обстоятельство, что № =О для у)п — 1. Заметим, что при у' < п матрица № содержит единицы на у-й налдиагонали и нули во всех прочих позициях.

Наконец, заметим, что ~, . —,, (,'./ Л' т есть разложение Тейлора для /®(Л)/Я. Таким образом, 100 Глава 4. Несимметричная проблема собственных значений Каждая подзадача у = .7„, (Л,)у+д(т) =,Уу+у(т) есть стандартное линейное дифференциальное уравнение, решение которого имеет вид ,г у(Ю) = у(0)ел+ / езр ~~д(т)дт, о Решение системы д (0)у = у + д(т) достигается обратной подстановкой, исходя из последнего уравнения. Запишем систему более подробно: 0 1 д1 у1 у1 ды Уы Из т-го (т.е. последнего) уравнения имеем 0 = у + д, или у = — д Уравнение с номером г' есть у,, = у;+д,, откуда у; = уг+, — д; и, как следствие, Следовательно, решение зависит от производных функции д, а не выражается интегралом от д, как для обычного дифференциального уравнения. Поэтому для непрерывной, но не дифференцируемой функции д мы можем получить разрывное решение. Такую ситуацию иногда характеризуют термином импульсный отклик.

Свежие статьи
Популярно сейчас