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

Однако зто возможно для к-мерного инвариантного подпространства, натянутого на эти векторы. Детали можно найти в [197!. 5.2.1. Теории относительных возмущений Теперь мы выведем для собственных значений и собственных векторов более точные оценки, чем в предыдущем разделе. Они понадобятся нам при обосновании высокоточных алгоритмов для вычисления собственных значений и сингулярных чисел, описанных в разд. 5.4.2 и 5.4.3. Сопоставим эти новые оценки с оценками предыдущего раздела для одномерного случая.

Пусть даны число а, возмущенное число а = а + е и граница [е! < г. Тогда можно указать очевидную оценку [а — а! < г для абсолюгпной погрешнос«пи приближения а. Именно такой подход был принят в предыдущем разделе. Рассмотрим теперь возмущенное число вида а = хга и границу [хг — Ц < г. Здесь можно оценить относительную погрешность числа а: [а — ! [а! =[х — 1!<«. Перенесем это простое сопоставление на случай матриц. В предыдущем разделе мы оценивали абсолютные расстояния между собственными значениями а, матрицы А и собственными значениями аг матрицы А = А + Е посредством неравенств вида !аг — а,! < [[Е[[г. Теперь же мы станем оценивать относительные разности чисел а, и собственных значений аг матрицы А = ХтАХ посредством величины г = [[Х~ Х вЂ” 1![г.

Теорема 5.6 («относительная» теорема Вейля). Пусть матрица А имеет собственные значения а«, а матрица А = ХтАХ вЂ” собственные значения аг. Положим г = [[Х~ Х вЂ” 1[!г. Тогда [ૠ— а,! < [аг[г. Если а, ф О, то зти оценки можно записать в виде !а; — а;! !аг! (5.8) Заметим, что если Х вЂ” ортогональная матрица, то г = [[ХтХ вЂ” 1[!э = О, н теорема подтверждает, что матрицы ХтАХ и А имеют одни и те же собственные значения.

Если матрица Х «почти» ортогональна, т. е. если число г Доказательство. Поскольку «-е собственное значение матрицы А — а;1 равно нулю, то же самое, в силу теоремы Сильвестра об инерции, верно для матрицы Хт(А — сг 1)Х (ХзАХ вЂ” а 1)+а (1 ХтХ) Н+ Е Согласно теореме Вейля, [Лг(Н) — О! < [[г'[[г, или [а, — а,! < [а;! ![Х Х вЂ” 1!!» = !а;[г. П 220 Глава 5. Симметричнаи проблема собственных значений мало, то, согласно теореме, собственные значения обеих матриц мало разнятся в смысле относительной погрешности.

Следствие 5.2. Пусть магприца С имеет сингулярные числа о„а матрица д = У~СХ вЂ” сингулярнъге числа д;. Положим е = шах(!!Х Х— 1))г,))1'~1' — 1~)г). Тогда ~дг — о,~ < ео;. Если ог ~ О, то зти оценки можно записагпь в виде (о, — о,! (5.9) Чтобы оценить различия между собственными векторами д, матрицы А и собственными векторами д; матрицы А = ХтАХ, можно аналогичным образом обобщить теорему 5.4. Для этого нам понадобится определение оганосительной отделенности собственного значения.

Определение 5.4. Относительной отделенностью собственного значения сг, матрицы А называется число ге! кар(г, А) = ппп тн )-ф — '". Теорема 5.7. Пусть матрица А имеет собственные значения ол и соответствующие нормированные собственные векторы 00 а матрица А = Х АХ— собственные значения бг и нормированные собственные векторы ф. Обозначим через 0 острьгй угол между векторами о; и дг. Положим ег —— ~)1— Х ~Х ~((г иге — — )~Х вЂ” 1()г. Предположим, что ег < 1 иге! кар(г,Х АХ) > О. Тогда 1 ег 1 — г!п20 < т + ег' 2 1 — ег ге1 кар(г, ХтАХ) Доказательство.

Пусть и = аг — ап Н = А — сгг1 и Е = сгг(1 — Х тХ г). Заметим, что Н+ Е = А — сггХ тХ г = Х т(ХтАХ вЂ” йг1)Х Таким образом, Нбв = — г!ог и (Н + Р)(Х$) = О, т.е. Хф есть собственный вектор матрицы Н + Р, относящийся к ее 1-му собственному значению О. Пусть 0г — острый угол между векторами бч и Хоь Согласно теореме 5.4, справедлива оценка 1 . !!т !!2 — з!и 20г < (5.10) бар(г, Н+ Е) При этом !!и!)г = !сг,(ег.

Отметим, что величина бар(г, Н+ Р) равна наименьшему из модулей ненулевых собственных значений матрицы Н+ Р. Поскольку собственными значениями матрицы Х~(Н+Р)Х = ХтАХ вЂ” о;1 являются числа с11 — бн из теоремы 5.6 вытекает, что собственные значения матрицы Н+ Е заключены в интервалах с концами в точках (1 — ег) (гг — Йг) и (1+ ег) (Й вЂ” аг). Поэтому дар(г, Н + Е) > (1 — ег)бар(г', ХтАХ). Используя это неравенство для оценки (5.10), получаем 1 — ейп20г < ег)٠— (5.11) 2 (1 — ег)бар(г, Хт АХ) (1 — ег)ге!.яар(1, ХтАХ) 221 5.2.

Теория возмущений Пусть 0г — острый угол между векторами Хог и д,, так что 0 < Ог + 0г. Из тригонометрических соображений, ьйпдг < з(Х вЂ” 1)01вг < вХ Х5г = ег. Теперь, применяя неравенство треугольника (см. вопрос 5.11), имеем 1, 1, 1 — сйп20 < — э1п20г + — ьйп20г 2 2 2 1 2 < — в1п 20г + эш 0г < +ег, (1 — ег)ге) кар(г, ХтАХ) что и требовалось. Аналогичное утверждение можно доказать для сингулярных векторов [101]. Пример 5.6. Используем связанную систему материальных точек из примера 5.1, чтобы показать, что оценки для собственных значений, предоставляемые теоремой Вейля (т.

е. теоремой 5.1), могут быть много хуже (менее точны) оценок из «относительного» варианта этой теоремы (т. е. теоремы 5.6). Мы также увидим, что оценка для собственного вектора из теоремы 5.7 может быть гораздо лучше (точнее) оценки из теоремы 5.4. Предположим, что М = гйая(1, 100, 10000), а Кгг = бгаб(10000, 100, 1).

Вслед за примером 5.1, определим матрицы К = ВкггВт н К = М г~гкМ г7г, где 1 — 1 а потому Г 10100 -10 К = М-'7гКМ-'~г = -10 1.О1 —.ОО1 —.001 .0001 С точностью до пяти десятичных разрядов, собственными значениями матрицы К являются числа 10100, 1.0001 и 0.00099. Предположим теперь, что каждая из масс (ти) и калсдый из коэффициентов жесткости (Йгг н) возмущены не более чем на 1%. Насколько при этом могут измениться собственные значения? Если заменить тгг на .99, а игг гг на 10100, то наибольший элемент матрицы, а именно Км, примет значение 10305, т.

е. его изменение составит 205. Но тогда, согласно теореме Вейля, каждое собственное значение может измениться на х205, что совершенно исказит два младших собственных значения. Оценка для собственного вектора из теоремы 5.4 также показывает, что соответствующие собственные векторы могут полностью измениться. Применим теперь теорему 5.6 к матрице К или, фактически, следствие 5.2 1/г к матрице С = М '/гВкг~7, в соответствии с примером 5.1, К = ССг. Изменение каждой массы не более чем на 1% равносильно замене матрицы С на ХС, где Х вЂ” диагональная матрица с диагональными элементами, заключенными между 1/~/.99 е 1.005 и 1/Я.01 — 0.995.

Согласно следствию 5.2, сингулярные 222 Глава 5. Симметричная проблема собственных значений числа матрицы С могут, самое большое, приобрести множители, находящиеся в интервале [0.995,1.005], поэтому изменения в собственных значениях матрицы М составят не более 1%. Другими словами, подобно наибольшему собственному значению, младшее собственное значение может измениться разве что в своем втором десятичном разряде.

Точно так же, изменение коэффициентов жесткости, не превышающее 1%«, равносильно замене С на ХС, и снова собственные значения не могут измениться более чем на 1%. Одновременное возмущение матриц М и Кп может повлечь за собой возмущения собственных значений примерно на 2%. Поскольку собственные значения сильно различаются по величине, все относительные отделенности довольно велики, а потому и возмущения в собственных векторах, измеряемые углами, не превысят приблизительно О.ОЗ. О Описание другого подхода к анализу относительных ошибок, более приспособленного для матриц, порождаемых дифференциальными («неограниченнымие) операторами„дано в [161].

5.3. Алгоритмы дли симметричной проблемы собственных значений Мы рассмотрим ряд алгоритмов для симметричной проблемы собственных значений, при этом, как было указано во введении, только прямые л«етоды. Рассмотрение итерационных мегаодое откладывается до гл. 7. В главе 4, посвященной несимметричной проблеме собственных значений, единственным обсуждавшимся алгоритмом была 14Рс-итерация. Она предназначена для вычисления всех собственных значений и, при необходимости, собственных векторов. Для симметричной проблемы собственных значений имеется гораздо болыпе хороших алгоритмов, что повышает гибкость и эффективность вычислений. Например, описываемый ниже алгоритм бисекции способен находить только собственные значения, принадлежащие отрезку [а, 5], указанному пользователем. Это требует куда меньше времени, чем вычисление всех собственных значений. Все рассматриваемые алгоритмы, за исключением Щ-итерации и метода Якоби, предполагают, что матрица была вначале приведена к трехдиагональной форме посредством модификации алгоритма 4.6, описанной в равд.

4.4.7. Стоимость этого начального этапа составляет «п флопов или еп флопов, если нужны и собственные векторы. 1. Трехдиагоиальнал ь)К-итерация. Этот алгоритм находит все собственные значения и, если необходимо, собственные векторы симметричной трехдиагональной матрицы. Среди практических методов вычисления всех собственных значений симметричной трехдиагональной матрицы эффективно реализованная СгГ«-итерация является наибыстрейшей. Она обходится в 0[па) флопов, что при достаточно больших п составляет пренебрежимо малУю часть от «гпз флопов, необходимых длЯ пРиведениЯ исходной плотной матрицы к трехдиагональной форме. Однако если нужны и все собственные векторы, то 14й-итерация в среднем требует несколько больше, чем 6пг флопов, и остается самым быстрым алгоритмом лишь для малых 5.3.

Алгоритмы для симметричной проблемы собственных значений 223 матриц порядка, не превосходящего и = 25. Именно ЯВ-итерация стоит за Ма1!аЬ-командой е15' и ЬАРАСК-программами ввуеч (для плотных матриц) и ввтеч (для трехдиагональных матриц). 2. Яч-итерация. Этот алгоритм лежит в основе ать-итерации, но мы рассматриваем его отдельно от нее, чтобы упростить анализ его чрезвычайно быстрой сходимости, а также потому, что ВЯ-итерация может применяться и как самостоятельный алгоритм. В общем случае, алгоритм сходится кубически (как и ь4В-итерация), что означает: число верных знаков в приближенных результатах асимптотически ршраиваетсл на каждом шаге. 3.