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

О Общая ситуация по существу та же, что и в только что рассмотренном двумерном случае. Теорема 5.4. Пусть А = ЯЛЯт = Ядтад[о;)Я7 есть спектра ьное разло- 7' жение матрицы А, а А+ Е = А = ДЛЯ вЂ” спектральное разложение возмущенной матарицы. Положим Я = [дм...,д„) и 1г = [ды...,д„), где д, и д1 сутпь нормированнтле исходные и возмущенные собственные вектпоры. Пусть д — острый угол между векторами д, и дт.

Тогда [[Е [[7 — вш2д < при условии, что бар[7',А) > О. 2 5ар[т, А) Аналогично, 1 [[Е [[7 — в1п2д < ., если бар[в,А+Е) > О. 2 бар[т',А+ Е) ' Заметим, что при д «1 имеем [1/2) вш 2д — вшд д. Мы формулируем оценку не только с помощью бар[т', А), но и бар[в, А+ Е) по следующей причине: часто бывают известны лишь собственные значения Поэтому и число нулевых собственных значений у них должно быть одинаковым. П 215 5.2. Теория возмуи[еиий матрицы А + Е.

В типичной ситуации, это результаты, найденные использовавшимся спектральным алгоритмом. В подобных случаях, число кар(г, А+ Е) определяется тривиально, тогда как кар(г, А) можно лишь оценить. Если первая верхняя граница превзойдет 1/2, т. е. Щ)з > яар(г, А)/2, то оценка приобретет вид сйп 2о < 1, т. е.

перестанет давать какую-либо информацию об угле д. Поясним, почему в этой ситуации для д нельзя найти сколько- нибудь удовлетворительной оценки. Если возмущение Е так велико, то собственное значение а, матрицы А + .Е может, достаточно отдалившись от а,, превратиться в кратное. В качестве примера, рассмотрим А = Лая(2,0) и А + Е = 1. Неопределенность в задании собственных векторов такой матрицы А+Е слишком велика; действительно, всякий вектор является собственным для матрицы А+ Е = 1. Поэтому нет никакого смысла в попытке оценивания угла о. Те же соображения применймы в том случае, если вторая верхняя граница больше 1/2. Доказательство. Достаточно доказать первую верхнюю оценку.

Вторая будет следовать из нее, если рассматривать А + Е как исходную матрицу, а А = (А + Е) — Е как возмущенную. Пусть д;+Н вЂ” собственный вектор матрицы А+Е. Чтобы устранить неопределенность в векторе и', потребуем, чтобы он был ортогонален к д, (т. е. ссьд,); ниже мы используем это условие ортогональности. Заметим, что, как следствие, вектор д;+ П не является нормированным, поэтому ф = (д;+ д)/Йд, + е(Йз. Далее, Сй д = )Щ и эес о = '0д, + п0з. ч! +и Приравняем 1-е столбцы в матричном соотношении (А + Е)Я = фЛ: (А + Е) (д; + с() = 6;(д; + д).

(5.4) Обе части были умножены на число Йд; + сиз. Положим д = а, — оп Вычитая из (5.4) равенство Ад; = сид; и перегруппировывая члены, имеем (5.5) (А — а;1) й = (д1 — Е) (д; + Н). Поскольку дт(А — а;1) = О, обе части равенства (5.5) ортогональны к вектоРУд;.ПоэтомУ можно написать Я = (01 — Е)(д,+ф = 2 ям Ь д и д= 2 ямбЗдд Используя соотношение (А — сп1)ду = (пу — и;)ду, получаем (А — а,1)Н = ~~~ (ау — а;)6 ду = ~ ~уд = (01 — Е)(д, + д), 1Ф4 уии 216 Глава 5.

Симметричная проблема собственных значений или Отсюда 280 = '6п"6 с 2/2 вследствие ортонормальности векторов о о/ — сг~ 1/2 поскольку наименьший знаменатель < 8ар(2,А) ~ ~ 1/ равен числу бар(2,А) ~1412 кар(2', А) Применив теорему Вейля и неравенство треугольника, мы могли бы выписать оценку 6262 < ЦЕ62 + (0О .

()0, + с(62 < 2!)Е!)2 эес0, откуда следовало бы, что е!п0 < 2Щ!г/бар(2, А). Однако можно получить несколько лучший результат, более аккуратно оценивая величину 6Щ = Цу1 — Е)(дг+ф$~г. Умножая (5А) слева на дт, производя сокращения и перегруппнровывая, находим 2/ = РТЕ(дг + д). Отсюда = (дг+ ~)г/ — Е(0, + 1) = (дг+ 0)ЖЕ(в+0) — ЕИ. + 0) +,1 т 1)Е( +,~) а потому Й2Й2 < Й(0, + й)0Т вЂ” 162 '6ЕЙ2 - )(дг+ оцг. Мы утверждаем, что Й(д, + 0)д( — 1~62 — — )(02+с(62 (см. вопрос 5.7).

Таким образом, 6262 < )(дг+ЫЦ Щ)2, поэтому Й2Й2 )(02+ д(Я()Е62 вес 0 ЙЕЙг 8ар(2, А) 8ар(2, А) 8ар(2, А) или йЕег 280, 1 > = вгпбсое0 = — агп20, 8ар(2, А) эес' 0 2 что и требовалось доказать. Аналогичный результат можно доказать для сингулярных векторов (см. вопрос 5.8).

У отношения Рэлея есть и другие хорошие свойства. В нашей следующей теореме показано, что в некотором естественном смысле отношение Рэлея является енаилучшим приближением» собственного значения. На этом свойстве основана КЯ-итерация из равд. 5.3.2 и итерационные алгоритмы гл. 7. Кроме 217 5.2. Теория возмущений того, с его помощью можно оценить качество приближенной собственной пары, найденной каким угодно способом (а не только посредством обсуждаемых здесь алгоритмов) .

Теорема 5.5. Пусть А — симметричнал матрица, х — нормированный вектор, а 13 — число. Тогда найдется собственная пара (ом о;)) матрицы А (т. е. Арл = сг;71), удовлетворяющал оценке (си — Д < 9Ах — бхЙг. При заданном векторе х величина ЙАх — ~3х(~г минимизируется выбором В = р(х, А). При наличии несколько большей информации о спектре матрицы А можно получить более точные оценки. Положим г = Ах — р(х, А)х.

Пусть а;— собственное значение матрицы А, ближайшее к р(х, А). Введем величину бар' = пппузм ~ау — р(х, А)), лвллющуюсл вариантом введенного выше понятия отделенности. Пусть Π— острьгй угол между векторами х и до Тогда гйпд < —,, !ИЬ (5.6) бар' )ад — р(х,А)( < —. !)г)Я (5. 7) йар' В теореме 7.1 дано обобщение этого результата на случай группы собственных значений. Обратим внимание на то, что в оценке (5.7) разность между частным Рэлея р(х, А) и собственным значением си пропорциональна квадрату нормы невязки ЙгЙг. Именно на этой высокой точности основана кубическая сходимость Ш~-итерации из равд.

5.3.2. Доказательство. Мы докажем только первое утверждение и вынесем остальные в вопросы 5.9 и 5.10 в конце главы. Если )3 является собственным значением матрицы А, то утверждение очевидно. Поэтому предположим, что матрица А — 331 невырожденна. Тогда х = (А — )31) '(А — )31)х и 1= 9Щг < Й(А — )31) ~9г 9(А — )31)х9г Пусть А = ЯЛЯт = Яд1ай(аы..., ао)Ят — спектральное разложение матрицы А.

Имеем Й(А — В1) 'йг — — ЩЛ вЂ” ~31) 'Я~ 'Пг = Й(Л вЂ” )31) '!)г = 1/ш1п(а, — Д. Таким образом, ппп, (о; — 33) < Й(А — 331)х!)г, что и требовалось. Чтобы показать, что )3 = р(х, А) минимизирует ЙАх — )3х((г, докажем, что х ортогонален вектору Ах — р(х, А)х. После этого применение теоремы Пифагора к сумме ортогональных векторов Ах — )Зх = (Ах — р(х, А)х) + ((р(х, А) — )3)х] даст '5Ах — рх)(~ ~= 'йАх — р(х, А)х))~ ~+ 9(р(х, А) — )3)х)(~~ ) ЦАх — р(х, А)х)/г~, причем равенство возможно лишь в случае ф = р(х, А). 218 Глава 5. Симметричная проблема собственных значений Проверка ортогональности векторов х и Ах — р(х, А)х проводится следующей выкладкой: х (Ах — р(х,А)х) = х ( Ах — х) = х Ах — х Ах — = О.

г (х Ах) х х хгх тео ема оказана. П Этим р д Пример 5.5. Проиллюстрируем теорему 5.5 с помощью матрицы из примера 5.4. Пусть А = ~, где 0 < е < д. Пусть х = (1,0]г и 1+д е1 1 ,д = р(х,А) = 1+д. Тогда г = Ах — )ух = (О,е] и ]]г]]г = и, Собственными значениями матрицы А являются числа а~ = 1 + кг х гг(1 + (г') )'7~, а собственные векторы указаны в примере 5.4 (где А называется матрицей А+ Е). Согласно теореме 5.5, число ]]Ах — (Зх]]г = ]]г]]г = е есть верхняя граница для расстояния от )1 = 1+ д до ближайшего собственного значения ое матрицы А. Это же предсказывается теоремой Вейля (теорема 5.1). Ниже мы увидим, что эта граница гораздо слабее границы (5.7). Если е много меньше, чем д, то одно из собственных значений матрицы А близкб к 1+ д, а соответствующий собственный вектор близок к х.

Другое собственное значение находится вблизи 1, а отвечающий ему собственный вектор близок к (О, 1]т. Это означает, что бар' = ]а — р(х, А)] = кг(1+ (1+ (г')г)'7г), поэтому юв (5.6) вытекает такая оценка для угла д между х и точным собственным вектором: эшд < — = ]]г]]г 2е/д 8ар' 1+ (1+ ( — ")г)'7г и Из явных формул для собственных векторов, приведенных в примере 5.4, видно, что полученная верхняя граница в действительности равна сйд, что для малых д почти то же самое, что э1п д. Таким образом, оценка (5.6) весьма точна. Перейдем теперь к оценке (5.7) для разности ])1 — ач.]. Оказывается, что для рассматриваемого 2 х 2-примера и величина ]д — а+], и граница для нее точно равны числу ]] Я 2е/д бар! 1+ (1+ (г )г)г/г ' Вычислим значения указанных границ в специальном случае д = 10 г и е = 10 в.

Тогда собственные значения матрицы А будут приближенно равны числам ач. — — 1.01000001 = 1.01+ 10 е и а = .99999999 = 1 — 10 е. Первая оценка принимает вид ])У вЂ” ач.] < ]]г]]г = 10 э; эта граница в 10г рэз превышает действительную ошибку 10 в. Напротив, оценка (5.7) дает ]11 — аЦ < ]]гЦ/йар' = (10 э)г/(1.01 — а ) 10 е, т.е. это очень точная оценка. Угол д между х и точным собственным вектором для собственного значения а~ составляет примерно 10 з и почти то же значение дает граница ]]г]]г/бар' = 10 в/(1.01 — сг ) ~м 10 з. О В заключение обсудим ситуацию, когда имеется кластер из и собственных значений и нужно вычислить соответствующие собственные векторы.

Под 219 5.2. Теория возмущений «кластером» понимается группа близких собственных значений, находящихся на значительном удалении от собственных значений, не входящих в эту группу. Примером могли бы быть 1« = 20 собственных значений на отрезке [0.9999,1.0001! при том, что все остальные собственные значения больше, чем 2. Теоремы 5.4 и 5.5 заставляют думать, что отдельные собственные векторы не удастся определить с хорошей точностью.