Дж. Деммель - Вычислительная линейная алгебра, страница 44
Описание файла
PDF-файл из архива "Дж. Деммель - Вычислительная линейная алгебра", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 44 страницы из PDF
Она может иметь место лишь, если у задачи есть бесконечные собственные значения. Чтобы задача допускала непрерывное решение у, при 1 = 0 должны выполняться некоторые условия согласования: до †у,(О) = ~ — †, .д,(0). ь=юп Численные методы решения таких дифференциально-алгебраических уравнений (или обыкновенных дифференциальных уравнений с алгебраическими ограничениями), основанные на пошаговом интегрировании, описаны в [41]. Обобщенная форма Шура для регулярных пучков Точно так же, как мы не можем устойчиво вычислять жордалову форму, мы не можем устойчиво вычислить и ее обобщение — форму Вейерштрасса. Поэтому вместо нее будем вычислять обобщенную форму Шура.
Теорема 4.11 (обобщенная форма Шура). Для регулярного пучка А — ЛВ найдутся унитарные матрицы Яь и Ял, такие, что обе дгатрицы ЦьАЯл = Тд и СгьВЯя = Тв — верхние тнреугольные. Собственными значениязии пучка А — ЛВ являютсл числа Тд„(Тнн, т. е. отношения диагональных элементов матриц Тд и Тв. Доказательство очень похоже на вывод обычной формы Шура. Пусть Л'— собственное значение пучка, а х — соответствующий собственный вектор единичной длины: [[х[[г —— 1. Поскольку Ах — Л'Вх = О, векторы Ах и Вх являются кратными одного и того же нормированного вектора у (это верно и в том 191 4.5.
Другие типы несимметричных спектральных задач случае, если какой-то из векторов Ах и Вх равен нулю. Пусть Х = (х, Х] и У = [у, У] — унитарные матрицы, имеющие первыми столбцами соответственнох и у. ТогдаУ'АХ = ~ - ~ и У*ВХ = ~ - по построению. а» аш . Ьп Ьш А22 22 Далее процесс применяется по индукции к пучку Азз — ЛВхь П Для вещественных матриц А и В существует и обобщенная вещественная форма Шура, т.е. найдутся вещественные ортогональные матрицы Ць и Яя, такие, что матрица ЯьАОя — верхняя квазитреугольная, а матрица ЯьВ(,)ив верхняя треугольная. (4Б;алгоритм со всеми его усовершенствованиями может быть обобщен на задачу вычисления обобщенной (вещественной) формы Шура.
Это обобщение называется Я2-алгоритмом и реализовано в ЕАРАСК'е подпрограммой вяяев. В Ма$1аЬ'е Я2-алгоритм активируется командой е1й(А,В). Определенные пучки Более простой специальный случай, часто возникающий на практике,— это пучок А — ЛВ, где А = Ат, В = Вт и матрица В положительно определена. Такие пучки иыываются определенными. Теорема 4.12. Пусть А = Аз, В = Вт и матрица В положительно определена.
Теада найдется вещественная нееырежденная матрица Х, такал, что Х АХ = 41ая(аы..., о„) и ХтВХ = сйаб(Д,..., Д,). В частности, есе собственные значения а;/)1, пучка А — ЛВ вещественны и конечны. Доказательство. Наше доказательство представляет собой алгоритм, фактически используемый для решения задачи: (1) Пусть Т,.от = В есть разложение Холесского матрицы В. (2) Положим Н = Б 'АТ т; заметим, что Н вЂ” симметричная матрица. (3) Положим Н = ЯЛ(д~, где Я ортогональная, а Л вЂ” вещественная диагональная матрица. Тогда для матрицы Х = В тЯ имеем ХгАХ = ЯтТ 'АТ г(~ = Л и ХтВХ = дтТ 'ВТ д = 1. () Отметим, что утверждение теоремы сохраняет силу и в том случае, когда положительно определена не В, а матрица аА + ))В для некоторых скаляров и и,З.
Описанный алгоритм реализован ЬАРАСК-программой ввуяч. Пример 4.15. Рассмотрим пучок К вЂ” ЛМ из примера 4.14. Он определен, поскольку матрица жесткости К симметрична, а матрица масс М симметрична и положительно определена. Б действительности, для этого очень простого примера матрица К трехдиагональная, а матрица М диагональная; диагональным будет и ее множитель Холесского Б, а матрица Н = Е 'КЕ т снова симметричная и трехдиагональная. В гл.
б мы рассмотрим ряд алгоритмов для симметричных трехдиагональных задач на собственные значения. О 192 Глава 4. Несимметричная проблема собственных значений 4.5.2. Сингулярные матричные пучки н каноническая форма Кронекера Обратимся теперь к сингулярным пучкам. Напомним, что пучок А — ЛВ сингулярен, если матрицы А и В не являются квадратными, либо они квадратные, но бес(А — ЛВ) = 0 для всех значений Л. Как показывает следующий пример, нужна осмотрительность при распространении понятия собственного значения на этот случай. (1 01 (1 01 Пример 4.16. Пусть А = ~ 0 0 ) и В = ~ 0 0 ~.
Производякакугоднома- ( 1 е1 1 , ( 1 ез 1 лые возмущения, можем получить матрицы А' = ~ ~ и В = ~ '(ег 0 ~ Собственные значения возмущенного пучка — это отношения е1/ез и ег/е4, которые могут быть произвольными комплексными числами. Таким образом, чувствительность собственных значений исходного пучка бесконечна. О Как мы увидим ниже, несмотря на эту крайнюю чувствительность, сингулярные пучки используются при моделировании некоторых физических систем.
Покажем теперь, как обобщить формы Жордана и Вейерштрасса на случай сингулярного пучка. Помимо жордановых и «бесконечных жордановых» блоков, мы введем в каноническую форму два новых «сингулярных блока». Теорема 4.13 (каноническая форма Кронекера). Пусть А и  — произволы ные прямоугольные матрицы размера т х п. Тогда найдутся квадратные не- вырожденные матрицьг Рс и Рл, такие, что матрица РвАРл — ЛРг.ВРп блочно-диагональная и на ее диагонали присутствуют четыре типа блоков, а именно: Л' — Л 1 ды(Л') — Л1 = ,жорданов блок порядка т; 1 Л' — Л 1 Л жорданов блок порядка т для Л = со; Л 1 правый сингулярный блок размера т х (т+ 1); левый сингуллрньгй блок размера (т + 1) х т. 1 Л 19З 4.5.
Другие типы несимметричных спектральным задач Приложения формьс Кронекера к дифференциальным уравнениям Пусть нужно решить уравнение Вх = Ах+ у'(1), которому соответствует сингулярный пучок А — ЛВ. Записывая задачу в виде РьВРнРл 'х = РьАРлРл 'х+ Рь) [с), мы разложим ее в сумму независимых подзадач, соответствующих диагональным блокам. Имеется четыре типа подзадач, по одному для каждого типа блоков в форме Кронекера. При исследовании регулярных пучков и формы Вейерштрасса уже было показано, как обрабатываются блоки,7 (Лс) — ЛХ и Жт, поэтому достаточно рассмотреть блоки В и Вт.
Для блока В имеем т.е. Уз — — 91 + 91, или 92[1) = 92[0) + ]' (91(т) + 91(т))с)т, Уз —— Уз+ 92, или Уз[с) Уз[0) + ~дат) +92[т))зт, с Ут.1-1 Уса + 9т~ или Ут-ь1(С) Ут-ь1(0) + ]а(Ут[т) + 9т(т))с'т. Это означает, что можно взять в качестве 91 произвольную интегрируемую функцию и получить из нее решение задачи посредством указанных рекурсий. Дело обстоит таким образом потому, что в системе число неизвестных на единицу больше,чем число уравнений, т.е. система недоопределена. Для блока Е~ имеем [:.1 91 или 0 — У, +9„ У1 У2+ 92 Упс — 1 = Ут + 9т~ У =9 -ь Матрица Ь называется правым сингулярным блоком, потому что ее [правое) ядро содержит при всех Л вектор [Л, — Л ',..., хЦ.
Аналогичный вектор из (левого) ядра имеет матрица Вт. Доказательство теоремы можно найти в [110]. Подобно тому как форма Шура была обобщена в предыдущем разделе на случай регулярных матричных пучков, она может быть распространена и на сингулярные пучки. Обсуждение канонических форм, теории возмущений и существующих программ дано в [27, 79, 246]. Сингулярные пучки используются как модели в теории систем и теории управления.
Мы приведем два примера таких приложений. 194 Глава 4. Несимметричная проблема собственных значений Начиная с первого уравнения, последовательно получаем у1= дс дг й з — 1 — т — -гдм а также условие согласования д ~1 — — — д — ° — а дь. Если функции д; не удовлетворяют этому условию, то система не имеет решений.
Здесь число уравнений на единицу больше, чем число неизвестных, т.е. данная подзадача переопределена. риложения формы Кронекера к теории систем и теории управления Управляемым подпространством уравнения х(С) = Ах(4) + Виф называется множество состолний, которые могут быть достигнуты решением х(1), исходящим из положения х(О) = О, под воздействием входного управления и(~). Это уравнение используется для моделирования систем управления (с обратной связью), где и(~) выбирается инженером так, чтобы сообщить решению х(1) требуемые свойства, например ограниченность.
С помощью формулы г' (~ — т)г х(с) = / елр 1Ви(т)ат = / ~~ ~, А'Ви(т)пт =о й — А'В / ч и(т) дт Г' (Ф вЂ” т)* /. можно показать, что управляемое подпространство имеет вид врзл([В, АВ, АгВ,, А" 'В[). Компоненты решения х(г), не принадлежащие этому подпространству, не могут управляться изменением и(1). Чтобы определить, может ли моделируемая физическая система управляться входом и(1), приходится вычислять управляемое надпространство на практике. Для этого к сингулярному пучку [В, А — Л7) применяют метод типа Я)1-алгоритма. Относительно деталей см.
[78, 246, 247). 4.5.3. Нелинейные задачи на собственные значения В заключение, рассмотрим нелинейную проблему собственных значений, или матричный многочлен И ~~~,Л'А = Л Аз+ Ла 1Аа-1+ .. + ЛА1 + Ао. (4.7) Для болыцей простоты предположим, что все А, суть п х п-матрицы, причем Ае невырожденна. ОпРеделение 4.10. Многочлен Р(Л) = с1е1 (~.
с ЛгА;) называетсЯ хаРактеристическим многочленом матричного многочлена (4.7). Собставенные значения определяются как корни уравнения р(Л) = О. Можно проверить, что степень р(Л) равна д п, поэтому имеется с1 п собственных значений. Пусть 7 — собственное значение. Ненулевой вектор х, такой, что 2,'г 7гА;х = О, 195 4.5. Другие типы несимметричных спектральных задач называется правым собственным вектором для собственного значения 7.
Левый собственный вектор у определяется аналогично посредством условия 2.;=07'У'А* = О. Пример 4.17. Снова обратимся к примеру 4.1. Там мы имели дифференциальное уравнение Мх(1) + Вх(1) + Кх(1) = 0 (см. (4.3)). Если искать решения вида х(г) = е"яхг(0), то получим е"л(Л(Мхг(0) + Л,Вх;(0) + Кх;Л(0)) = О, или Л~Мх,(0) + Л;Вх,(0) + Кх;(0) = О. Таким образом, Л, и х,(О) суть собственное значение и собственный вектор матричного многочлена ЛгМ+ ЛВ+ К. 0 Поскольку матрица Ае, по предположению, невырожденна, можно умножить исходную задачу на Аа ~ и получить эквивалентную задачу с многочленом Ла1+ А,, ' Ае г Ле ' +... + А,, ' Ао.
ПоэтомУ, длЯ УпРощениЯ обозначений, можем в дальнейшем считать, что Ае = 1 (по поводу общего случая см, равд. 4.6). В наиболее простом случае, когда все А; суть матрицы размера 1 х 1, т.е. сквляры, исходный матричный многочлен совпадает с характеристическим многочленом.
Мы можем свести задачу вычисления собственных значений матричного многочлена к стандартной проблеме собственных значений, пользуясь приемом, аналогичным известному приему преобразования обыкновенного дифференциального уравнения высокого порядка в систему уравнений первого порядка.
Начнем с простейшего случая п = 1, где все матрицы А; являются скалярами. Пусть 7 — корень многочлена. Тогда вектор х' = [7~ ', 7~ ~,..., 7, 1] удовлетворяет соотношению -Аа-г -Ае-г - -Ао 1 0 ......... 0 0 1 0 ...... 0 Сх = 0 ... ... 0 1 0 Таким образом, х' и 7 являются собственным вектором и собственным значением матрицы С, которая называется сопровождающей матрицей много- члена (4.7). (В Ма1!аЬ-программе госсе, вычисляющей корни многочлена, хессенбергова ЯВ;итерация из равд.
4.4.8 применяется к сопровождающей матрице С. Этот метод вычисления корней, хоть он и дорог, считается в настоящее время одним из самых надежных [100, 117, 241]. Сейчас разрабатываются более дешевые альтернативные методы.) Та же идея работает и в сгучае, когда А, являются матрицами. Матрица С имеет порядок п - Ы и называется блочной сопровождающей матрицей много- члена (4.7). В (блочных) строках 2,..., с1 вместо единиц и нулей стоят теперь соответственно единичная и нулевая матрицы порядка и. Вектор х' принимает вид у" гх 7е гх х' = ух х 196 Глава 4.
Несимметричная проблема собственных значений где х — правый собственный вектор матричного многочлена. По-прежнему вы- полняется соотношение Сх' = ух'. Пример 4.18. Снова возвращаясь к многочлену ЛгМ + ЛВ + К, вначале заменим его на многочлен Л 1 + ЛМ 'В + М 'К, а затем перейдем к сопровождающей матрице — и 'в — и 'к Она совпадает с матрицей А в уравнении (4.4) примера 4.1. Отметим, в заключение, что в вопросе 4.16 обсуждается использование матричных многочленов для решения одной задачи из вычислительной геометрии.