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

д1 = 7 — 31 + 42, дг = 1 + 1~ + 2~, дз = 2 + 2~ — 2~, Х1Х2 + Хз 3 — Хз 5 + Х1 + Х2 + хз + Х1Х2 + Х1хз + Х2Хз Р= Х2 — 7ХЗ 1 — Х1 + ХЗХ2ХЗ 3 + х1 + Зхз — 9хзхз 2 ЗХ1 + 5хз — 7хз + 8 хз1 х42+ 4хзз Ваш отчет по этому заданию должен состоять из следующих пунктов: ° математическая постановка задачи в терминах проблемы собственных значений; ° описание алгоритма, самое большое, на двух страницах. Оно должно включать в себя «дорожную карту» вашей программы (т.е. имена подпрограмм для всех операций высокого уровня).

Из этого описания должно быть видно, как математическая постановка ведет к алгоритму и как соответствуют друг другу алгоритм и программа; ° ответы на следующие вопросы: — каково максимальное возможное число дискретных решений? — все ли вычисленные собственные значения представляют реальные пересечения? Для каких собственных значений это верно? — накладывает ли ваша программа какие-либо ограничения на входные данные? — что происходит, если В и С не пересекаются? — что происходит, если Я содержит С? ° математическое описание оценок ошибок; ° описание алгоритма, вычисляющего оценки ошибок, самое большое, на двух страницах. Оно должно включать в себя «дорожную карту» вашей программы (т. е. имена подпрограмм для всех операций высокого уровня).

Из этого описания должно быть видно, как математическая формулировка ведет к алгоритму и как соответствуют друг другу алгоритм и программа; ° листинг программы. Для калглого из семи примеров в отчет должны входить: ° исходная постановка задачи; ° полученная из нее задача на собственные значения; ° вычисленные решения; ° графики Я и С.

Соответствуют ли этим графикам вычисленные решения? ° результат подстановки вычисленных решений в уравнения, определяющие 5 и С. Удовлетворяются ли эти уравнения (в пределах точности вычислений)? Глава 5 Симметричная проблема собственных значений и сингулярное разложение 5.1. Введение В разделе 5.2 обсуждается теория возмущений для симметричной проблемы собственных значений, в разд.

5.3 и 5.4 — алгоритмы ее решения, а в равд. 5.5 (а также в других разделах) — ее приложения. Рассматривается также родственная задача о сингулярном разложении (ВЧП) матрицы. Поскольку спек- О Ат тральное разложение симметричной матрицы Н = А б очень просто связано с ВЧП матрицы А (см. теорему 3.3), большинство теорем о возмущениях и алгоритмов для симметричной проблемы собственных значений переносятся на БЧП. В соответствии с обсуждением в начале гл.

4, алгоритмы для симметричной проблемы собственных значений (и ВЪЧ)) в первом приближении можно разделить на две группы: прямые и итерационные методы. В этой главе рассматриваются только прямые методы. Они предназначены для вычисления всех (или избранного подмножества) собственных значений и (если нужно) собственных векторов. Их стоимость для плотных матриц составляет 0(пз) операций.

Итерационные методы обсуждаются в гл. 7. В последние годы был достигнут значительный прогресс в алгоритмике и приложениях симметричных задач на собственные значения. Проиллюстрируем его тремя примерами. ° В разделе 5.3.3 обсуждается алгоритм для решения симметричной проблемы, основанный на стратегии «разделяй-и-властвуй». Это самый быстрый из имеющихся методов вычисления всех собственных значений и собственных векторов полной или ленточной симметричной матрицы высокого порядка (а также ВЧО произвольной матрицы). Он значительно быстрее ь4К- итерации, которая прехсде была «рабочей лошадкой» для этого класса задач'.

° В разделах 5.2А, 5.4.2 и 5.4.3 обсуждаются высокоточные алгоритмы, основанные на методе Якоби и дифференциальном алгоритме частных и раз- г Из недавних публикаций [201, 203] может возникнуть еще более быстрый и точный алгоритм, основанный на идеях обратной итерации (см, алгоритм 4.2). Однако по состоянию на июнь 1997 г.

и теория, и программы алгоритма не приняли еще завершенного вида. 207 5.1. Введение ностей (4«1дз). Эти алгоритмы способны находить малые собственные значения (или сингулярные числа) с большей точностью, чем альтернативные методы типа «разделяй-и-властвуй», хотя, как и метод Якоби, они работают более медленно. ° В разделе 5.5 исследуется «нелинейная» колебательная система, которая описывается дифференциальным уравнением, называемым яотиоком Тода. Ее непрерывное решение тесно связано с промежуточными шагами 14Е- алгоритма для симметричной проблемы собственных значений. Пример 5.1. Симметричные задачи на собственные значения часто возникают при анализе механических колебани«у. Подробно рассмотренный образец такого анализа был представлен в примере 4.1. Мы используем обозначения из этого примера, поэтому рекомендуем читателю вначале заглянуть туда.

Чтобы задача в примере 4.1 стала симметричной, нужно предположить отсутствие демпфирования. Тогда дифференциальное уравнение движения связанной системы принимает вид Мх(1) = — Кх11), где М = Йаб(тг,..., т„) и ~1 + /«2 /«2 /«2 /«2 + /«3 /«3 К= Поскольку М вЂ” невырожденная матрица, уравнение можно переписать как х(1) = — М 1Кх(1). Разыскивая решения вида х(1) = е~'х(0), получаем езгугх(0) = — М 1Кеггх(0), или М 1Кх(0) = — угх(0).

Иначе говоря, — уг есть собственное значение матрицы М 'К, а х(0) — соответствующий собственный вектор. В общем случае, матрица М 1К не симметрична, однако мы можем симметризовать ее. Положим М'/г = йаб(п21/,..., т„/ ) и умножим обе ча- 1/2 1/2 сти соотношения М 1Кх(0) = — угх(0) на М'/г. Получим М-1/гКх/0) = М 1/ЗК(М-1/2М1/2)х/0) угМ1/гх/0), или Кх = — угх, где й = М~/~х(0) и К = М 1/ЗКМ 1/г. Легко видеть, что матрица »'жг ~ь 2 Ьг.»ьа шг йьг.ь~ пч ~/туЩ -г Как и в гл. 4, мы будем постоянно обращаться к примеру связанной системы материальных точек для иллюстрации особенностей симметричных задач на собственные значения. 208 Глава 5.

Симметричная проблема собственных значений симметрична. Поэтому каждое ее собственное значение — 72 вещественно и каждый собственный вектор х = М112х(0) ортогонвлен другим собственным векторам. Матрица К вЂ” трехдиагональнал. К этой специальной форме можно привести любую симметричную матрицу, используя алгоритм 4.6, модифицированный для симметричного случая в разд.

4.4.7. Большинство алгоритмов вычисления собственных значений и собственных векторов симметричной матрицы, описываемых в рвзд. 5.3, предполагают, что матрица была вначале приведена к трехдиагональной форме. Пользуясь сингулярным разложением, можно предложить и другую интерпретацию задачи о механических колебаниях. Положим Кр = йа8(й1,..., 12„) и Кр — — йа8(Й1,..., Й„). Тогда К может быть разложена в произведение 172 . 1/2 172 К = ВКрВ2', где 1 — 1 Это можно проверить несложными вычислениями.

Таким образом, М-112КМ-1/2 М-1 12ВКрВтМ вЂ” '/2 (М-172ВК") (К "В'М-172) (М вЂ” 172ВК1/2), (М-Ц2ВК172)т ССт (5.1) Следовательно, сингулярные числа матрицы С = М 172ВКр суть квадрат- 1/2 ные корни нз собственных значений матрицы К, а левые сингулярные векторы первой матрицы являются собственными векторами для второй (см. теорему 3.3). Отметим, что в С отличны от нуля только элементы главной диагонали и первой налдиагонали.

Такие матрицы называются деухдиагональными; большинство алгоритмов для вычисления БЧП начинают свою работу с приведения матрицы к двухдиагональному виду, используя для этого алгоритм из разд. 4.4.7. Из разложения К = СС~ следует, что матрица К положительно определена (поскольку С невырожденна). Поэтому все собственные значения — уг матрицы К суть положительные числа. Следовательно, 7 — чисто мнимые числа, а решения х(1) = е11х(0) исходного дифференциального уравнения являются осциллирующими функциями с частотами Ц. МаНаЬ-программа, относящаяся к колебательным связанным системам, находится в НОМЕРАСЕ/Ма11аЬ/шазззрг1пб.ш.

В Ма$1аЬ'е имеется и анимация колебаний сходной физической системы. Чтобы запустить ее, введите команду 11егпо, а затем щелкните мышью на соп11ппе/1пп-ехФтав/ш1есе!1влеопз/Ьепйпб. О 5.2. Теория возмущений 209 5.2. Теории возмущений Пусть А — симметричная матрица с собственными значениями ог » ... сг„ и соответствующими нормированными собственными векторами ум ..., д„. Пусть Š— также симметричная матрица, а А = А + Е имеет (возмущенные) собственные значения с1г » оп и соответствующие (возмущенные) собственные векторы уы..., д„.

Нашей главной целью в данном разделе будет оценивание разностей между собственными значениями си и сц и собственными векторами дг и дг через «величину» матрицы Е. Большинство наших оценок принимают в качестве меры величины норму )~ЕЙг. Исключением является разд. 5.2.1, где обсуждается теория «относительных» возмущений.

Первая оценка для возмущений собственных значений была уже получена в гл. 4. Там было доказано следствие 4.1: пусть А — симметричная матрица с собственными значениями о1 » .. сг„, Пусть матрица А+ Е танисе симметрична и имеет собственные значен я бг » . сг„. Если ои — простое собственное значение, то ~сг, — б,~ < Щ|г+ ОИПг). Слабость этого результата в том, что он предполагает простоту собственного значения и полезен лишь для достаточно малых значений 5Е5г. Следующая теорема устраняет оба этих недостатка.

Теорема 5.1 (Вейль). Пусть А и Š— — симметричные п хп-матрицы. Пусть ог » . о„— собственные значенил матрицы А, а сгг » . с1„ собственные значения матрицы А = А+ Е. Тогда (ог — гг,~ < ЙЕйг. Следствие 5.1. Пусть С и Р— произвольные матрицы одинакового размера, причем С имеет сингулярные числа ог » о'„,. а С+Р— сингулярные числа о' » .. о' . Тогда ~ог — д;! < Щ)г.

С помощью теоремы Вейля можно получить оценки ошибок для приближенных собственных значений, вычисленных любым обратно устойчивым алгоритмом, например ЯВ;итерацией. Действительно, такой алгоритм вычисляет приближения сг,, которые являются точными собственными значениями для матрицы А = А+ Е, где йЕйг = 0(е)ЙА~(г. Поэтому ошибки в этих приближениях можно оценить так: )си — б,) < !)Е5г = 0(е)))А5г = О(е) шах )о,ф Это вполне удовлетворительная оценка, особенно для больших собственных значений (тех аи что сравнимы по величине с 9Айг), которые могут быть вычислены с большинством верных разрядов.

В малых собственных значениях ((сг;~ << йАЙг) число верных разрядов будет меньше (однако см. равд. 5.2.1). Мы докажем теорему Вейля, опираясь на другой полезный классический результат, а именно минимаксную теорему Куранта — Фишера. Чтобы сформулировать эту теорему, потребуется ввести отношение Рзлея (Нау)егбЬ), которое будет играть важную роль и в нескольких алгоритмах, например в алгоритме 5.1. Определение 5.1. Отношение Рэлея для симметричной матрицьг А и нену- левого вектора и — зто число р(и, А) = (ииАи)((и и). Приведем некоторые простые, но важные свойства числа р(и,А). Вопервых, р(уи,А) = р(и,А) для всякого ненулевого скзляра у.

Во-вторых, если Аул = сггу,, то р(до А) = оь Более общо, предположим, что А имеет спек- 210 Глава 5. Симметричная проблема собственных значений тральное разложение ЯтАсэ = Л = б!аб(а;), где Я = (ум..., д„]. Разложим и по собственным векторам де, и = Я(чти) = ЧС = ~,. д2С,. Тогда стсэтАдс стЛс ~,г,сг р ) бтдтдб ~Г~ ~ ~2 шах !р(и, А)) = шах((сг2), (а„!) = )!А))2.

ь40 (5.2) Теорема 5.2 (минимаксная теорема Куранта — Фишера). Пусть А — симметричн я матрица с собственными значениями сг1 ) ) ои и соответствующими нормированными собственными векторами вы ..., д„. Тогда шах ппп р(г, А) = о - = гп!и гпах р(з, А). Нг ветви> Б" иы Офавз" им В левой формуле для сг максимум берется по всем у-мерным подпространствам Ву прострапства К", а внутренний минимум — по всем ненулевым векторам г из Кг. Максимум достигается для поднространства Вд = $рап(дыог,..., д ), а минимум реализуетнся вектором г = оа. В правой формуле для сг. минимум берется по всем подпространствам Яь 1+ размерности п — у + 1, а внутренний максимум — по всем ненулевым векторам з из Б" 1+2.

Минимум достигаетлся для надпространства Я" 1+2 = Брав(дг, д ~.ы..., д„), а максимум реализуется вектором з = д . Пример 5.2. Пусть у = 1, тогда ад есть наибольшее собственное значение. Если К' задано, то р(г, А) имеет одно и то же значение для всех ненулевых векторов г б К~, поскольку эти векторы пропорциональны друг другу. Поэтому левое выражение для а2 упрощается к виду сгз = шах„мо р(г, А). Точно так же, поскольку п — у+ 1 = п, единственным подпространством 8" 1+' является все пространство К".