Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 37
Текст из файла (страница 37)
О Заметим, что для жорданова блока ет и е„являются соответственно правым в левым собственными векторами, поэтому число обусловленности собственного значения равно 1/!е'„ет ~ = 1/О = оо, что согласуется с нашим предыдущим анализом. В качестве противоположного примера рассмотрим важный специальный случай симметричных матриц. Здесь число обусловленности равно 1, так что собственные значения с болыпой точностью определяются элементами матрицы.
Следствие 4.1. Пусть А — симметричная (или, более общо, нормальная) матрица (нормэльность означает, что АА* = А'А). Тогда )бЛ) < ))бА!)+ ОЯЬА!(~). ,т(оказательство. Для симметричной или нормальной матрицы А собственные векторы попарно ортогоиальны, т.е, ('„т*АЯ = Л и ЯЯ* = 1.
Поэтому правые собственные векторы х (т.е. столбцы матрицы Я) совпадают с левыми собственными векторами у (которые сопряжены со строками матрицы Ч*); следовательно, 1/)у'х! = 1. П Для экспериментальной проверки обусловленности собственных значений можно использовать МаПаЪ-программу, обсуждаемую в вопросе 4.14. Позднее мы покажем (см. теорему 5.1), что если бА = бАг, то, в действительности, справедлива оценка !бЛ! < !(ЬА)~г независимо от величины числа !(бА)!г. Теорема 4.4 полезна лишь при достаточно малых )(бА!!.
Мы можем устранить в оценке член ОЯЬА)(г) и получить простую теорему, верную для возмущений !)бА(! произвольной величины, ценой введения дополнительного множителя и в правую часть оценки. Теорема 4.5 (Бауэр — Файк). Пусть все собственные значения матрицы А простые !'т. е. А — диагонализуемая матрица). Обозначим их через Л,, и пусть х; и ут — соответствующие правые и левые собстпвенные векторы, нормированные так, что !~х,)!г = !(у,~! = 1. Тогда собственные значения матрице« А+ бА находятся в кругах В, с центрами Л, и радиусами п))-г))4.
Наше доказательство опирается на теорему Гершгорина (теорема 2.9), формулировку которой мы здесь повторим. Теорема Гершггарии. Пусть  — произвольная матрица. Тогда ее собственные значения принадлежат обвединению и кругов, определяемых неравенствами )Л вЂ” Ьн! < 2 ., )Ь,у ) (т = 1,..., и). Нам понадобятся еще две простые леммы. 162 Глава 4. Несимметричная проблема собственных значений Лемма 4.1. Пусть Я = [хы...,х„] есть нееырожденнал матрица правых собственных векторов матрицы А.
Тогда у1/угх1 у2/у2хг уи)учти Доказательство. Поскольку столбцы х, матрицы Я суть собственные векторы, то АЯ = БЛ, где Л = бйак(Лы...,Л„). Это эквивалентно равенству Я 1А = ЛБ ', поэтому строки матрицы Б ' сопряжены с левыми собственными векторами уо Итак, у,' с1 у„' с„ для некоторых констант со Но 1 = Я 'Я, поэтому 1 = (Я 1Б)н = угх; с„ откуда с„ = †„.',, что и требовалось. Лемма 4.2. Если 2-норма каждого столбца (произвольной) матрицы Б равна 1, то ]Щг < ~/п. Ан логично, если 2-норма каждой строки равна 1, то 2- норма всей матрицы не превосходит х/и.
Доказательство леммы. ]]Б]]з = ]]Б~]]г = шах1 1,— 1]]Вахт]]. Согласно неравенству Коши — Шварца, каждая компонента вектора Я~х ограничена по абсолютной величине единицей. Поэтому ]]Я~х]]г < ]][1,..., 1]~]]г =;/й. 0 Доказательство теоремьг Бауэра-Файна. Применим теорему Гершгорина к соотношению Б '(А + бА)Б = Л + Р, где Л = Б 'АЯ = с(1аи(Лы...,Л„), а Е = Я 15АЯ. Идея состоит в том, чтобы показать, что собственные значения матрицы А+ бА находятся в кругах с центрами Л, и радиусами, указанными в формулировке теоремы. Чтобы сделать это, возьмем определяемые теоремой Гершгорина круги, содержащие собственные значения матрицы Л+ Р: ]Л вЂ” (Л, + (н)] < ~ '] 1„].
уфг Немного расширяя их, получим круги 1/2 < п'~~ ° ~~~ ]16]~ по неравенству Коши-Шварца 4.3. Теория возмущений 163 Теперь дадим оценку для 2-нормы 1-й строки Е(«,:) матрицы Г = Я ~бАЯ: ЦР(к,:)Ц~ = ЦЯ 'бАЯ)(1,:)Ц~ < Ц(Е ')(«,:)Цг ЦбАЦг. ЦЯЦг по лемме 1.7 пЮ < ЦбАЦг согласно леммам 4.1 и 4.2. ~у,'х;~ Эта оценка вместе с (4.5) доказывает теорему.
Мы не хотим оставить у читателя впечатление, что кратные собственные значения вовсе не поддаются вычислению, поскольку имеют бесконечные числа обусловленности. В действительности, мы ожидаем, что в вычисленных приближениях будет верна некоторая доля разрядов (в отличие от потери некоторого фиксированного числа разрядов при вычислении простых собственных значений). В качестве иллюстрации, рассмотрим 2 х 2-матрицу с двойным 1 1) собственным значением 1: А = О 1 ~. Заменяя значение 0 ее (наиболее чувствительного) элемента (2, 1) на машинное эпсилон е, мы изменяем собственные значения с 1 на 1 х ~/е.
Иными словами, возмущенные собственные значения совпадают с точными лишь в половине своих разрядов. Для тройного собственного значения следует ожидать, что верными будут около трети разрядов. Аналогичные эмпирические правила верны при ббльших кратностях (см. вопрос 1.20). Обратимся теперь к геометрическому свойству числа обусловленности, которое наблюдается и в других задачах. Вспомним, что число обусловленности по отношению к задаче обращения, т. е. число ЦАЦ ЦА 'Ц, обладает следующим свойством: число, обратное к нему, измеряет расстояние до ближайшей вырожденной матрицы, т. е. матрицы с бесконечным числом обусловленности (см.
теорему 2.1). Аналогичный факт справедлив для собственных значений. Поскольку кратные собственные значения имеют бесконечные числа обусловленности, множество матриц с кратными собственными значениями играет ту же роль при вычислении собственных значений, какую вырожденные матрицы играли в задаче обращения, где «быть почти-вырожденной» означало плохую обусловленность. Теорема 4.6. Пусть Л вЂ” простое собственное значение матрицы А. Пусть х и у — соответствующие нормированные собственньге векторьц правый и лев»«й, а с = 1/~у'х~ есть число обусловленности Л.
Тогда найдется возмущение бА такое, что Л является кратным собственным значением матрицы А+бА, причем ЦбАЦг 1 ЦАЦг ~/г — 1 Если с » 1, т. е. собственное значение плохо обусловлено, то эта верхняя граница для расстояния ведет себя как 1/~/с~ — 1 1/с, т. е. как величина, обратная числу обусловленности. Доказательство. Покажем прежде всего, что без ограничения общности матрицу А можно считать верхней треугольной (имеющей форму Шура) с эле- 164 Глава 4. Несимметричная проблема собственных значений ментом аы — — Л.
Действительно, преобразование А в форму Шура равносильно замене А матрицей Т = Я*АЯ, где Я вЂ” унитарная матрица. Если х и у— собственные векторы для А, то Ч'х и Я'у — собственные векторы для Т. Поскольку Я*у)'(сд'х) = у*лЯ'х = у*х, то переход к форме Шура не меняет числа обусловленности собственного значения Л. (По-другому, это же можно сказать так: число обусловленности есть секанс угла 0(х, у) между х и у; прн замене х на Я"х и у на Я'у векторы х и у поворачиваются одинаковым образом, поэтому угол между ними не меняется.) ] Л Агг] Итак, без потери общности, можно считать, что А = ~ 1 ~.
Тогда х = ем а у параллелен вектору у = [1, Агг(ЛХ вЂ” Агг) ~]', иначе говоря, у = у1]]у]]г. Таким образом, 1 с = — = —, = ]]у]]г = (1+ ]]Агг(ЛХ вЂ” Агг) ]]гг)Нг ]у'х] ]у'х] или ~/сг — 1 = ]]Агг(ЛХ вЂ” Агг) ~]]г < ]]Агг]]г . ]](ЛХ вЂ” Агг) ]]г ]]А]]г оьаь(ЛХ вЂ” Агг) По определению наименьшего сингулярного числа, найдется возмущение бАгг с нормой ]]бАгг]]г — — о ы(ЛХ вЂ” Агг), такое,что матрица Агг + бАгг — Л1 выролсденна, т.е. Л есть собственное значение матрицы Агг + бАгг.
Поэтому Л [Л Агг является двойным собственным значением для матрицы ~ о А +, 1 Агг + оАгг причем ]]бАгг]]г = оьпь1ЛХ -'122) < ]]А]]г ~/сг — 1 что и требовалось. В заключение, установим соотношения между числами обусловленности собственных значений и минимумом числа обусловленности ]Щ ]]Я ']] по всем матрицам Я, диагонализующим А, т. е. 5 'АЯ = Л = 41аб(Лы..., Л„).
Приводимая ниже теорема утверждает, что если какое-либо собственное значение имеет болыпое число обусловленности, то число обусловленности матрицы Я должно быть примерно столь же большим. Иначе говоря, числа обусловленности при вычислении (хуже всего обусловленного) собственного значения и приведении матрицы к диагональной форме приблизительно одинаковы. Теорема 4.7. Пусть диазонализуемая матрица А имеет собственные значения Л, и соответствующие собсгавенньге векторы (правые и левые) х; и у;; последние нормированы так, что ]]х,]]г — — ]]у;]]г — — 1. Пусть матрица Я такова, что Я гАЯ = Л = йаб(Лд,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
