Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 43
Текст из файла (страница 43)
Во всяком случае после умножения каждого из них на любые числа аг Ф О и а2 Ф О полученные 'векторы агх* и а2х снова являются собственными. Поэтому имеет смысл стремиться не к тому, чтобы векторы х* и х были близки по норме, а к тому, чтобы они были близки по направлению.
Исходя из этого, примем в качестве меры близости х' к х величину ~згп у~, где у— угол между векторами х* и х, вычисляемый по формуле ((х, х)1 у = агссов ~ —,ф-~- . Задача вычисления собственных векторов симметричной матрицы хорошо обусловлена, если собственные значения хорошо отделены друг от друга. В подтверждение сказанного приведем следующий результат. Т е о р е м а 8.10. Пусть А и А, — симметричные матрицы. То~да верна оценка )згп р! ч !~А — А.Ь 7 Здесь уг — угол иежду векторами х* и х, а ~ — расстояние от Л* до ближайигего из несовпадагогцих с Л собственных значений матрицы А.
В случае, когда матрица А несимметрична, собственные векторы могут оказаться очень плохо обусловленными. 3 а м е ч а н и е. Подавляющее большинство встречающихся на практике матриц являются матрицами простой структуры. Это обстоятельство, а также большая простота анализа методов вычислений и формулировок соответствующих результатов позволяют 220 нам в основном остановиться на проблеме собственных значений для матриц простой структуры. $8.2. Степенной метод Пусть требуется вычислить максимальное по модулю собственное значение Л1 матрицы А, причем известно, что (8. 12) 3 а м е ч а н и е. Собственное значение Л1 в данном случае должно быть вещественным, поскольку в противном случае собственным 1.
Степенной метод без сдвигов. Опишем простейший вариант степенного метода, применяемого для вычисления Л1. Возьмем произвольный начальный вектор х<о~ и построим последовательности векто- (8,13) х~ "~ = Ах~"'~ (8.14) . 3 а м е ч а н и е. Правая часть формулы (8.14) — это просто отно- шение Рэлея, вычисленное при х = х(~ '>.
В самом деле, Л~ "~ Справедлива следующая теорема. Т е о р е м а 8.11. Пусть А — матрица простой структуры, для которой выполнено условие (8.12). Предположим, что в разложении (8.15) х<о~ = с1е1 + сне~ + ... + с„,еп по базису из собственных векторов коэффициент с1 не равен нулю. Тоьда Л("1 ~ Л1 при й ~ м и верна оценка относительной погрешности 1 значением было бы также равное ему по модулю число Ль ров (х'"') о и приближений (Л~"')ь о к Лп используя формулы Л<"' = (х~ ь) х~ ь-1) ) х, х = (Ах~"'~, х<" 1~)/(х'"'~, х~~')) = р (х~Ь"). (8.16) 221 и Как легко установить, вектор *(Ь) удовлетворяет равенству х' ()) = = АЪх(о), т.е.
получается из х(о) умножением на Й-ю степень матрицы А (отсюда и название метода). Так как Ае, = Л;е;, то А~с, = Л)е( и, следовательно, х('с) = А~х(о) = Л(с)е) + Лгсгег + ... + Лас)))ет ~ (о) (8.17) х' "' Положим х(А) = — и заметим, что х(~) ~ с) е) при й ~ оо, причем Л/с в(") = х(е) — с)е) — — ~ — ~ сгег+ ... + 1 — ~ с е,„ 1Л! Щ Таккак ~ — ~ 4 ~ — ~ для всех1~2,то 1л,! 1л,! $аи(~> ~ ~ с — ~ Л) (8.18) Теперь нетрудно установить, что (х("), х(" )) ) (с1е), с)е)) '() '( при Ф ~ ю. Более того, ~Л, — Л) ~ (х~ х~~~ х~А ()) (в)~~с~ м(е) х~)'( ) (л,) (~~ -» ~ 1)) — ( ( -1~ ~ -1) (~ )9) ~(щ(Ь н)(й 1) х((с 1))~ ( ~н)(й) я)(й 1) ~!)~х((с 1) )~ (8.20) Из равенства (8.19) и оценок (8.18), (8.20) следует, что ~(Л(ь)) - 3 '"-~ "6 М"'11+ 5 '""$.
,~ ~~г ® 222 Используя неравенство Коши — Буняковского $ (х, у) ! < ф х~ ~ у!$, имеем 3 а м е ч а н и е 1. В действительности теорема 8.11 справедлива для произвольных матриц, удовлетворяющих условию (8.12). Предположение о том, что матрица А — простой структуры, потребовалось лишь для упрощения доказательства. 3 а м е ч а н и е 2. Если ~А)~ ) 1, то 1х'"' ~ -~ ~ при 1 ~ ю (см. формулу (8.17)) и при вычислении на ЭВМ возможно переполнение.
Если же ~ Л) ~ < 1, то ~ х( "' ~ - О и возможно исчезновение порядка. Для предупреждения этих ситуаций обычно вектор х'"' нормируют, например, так, чтобы 1х(") ~ = 1 для всех )с ) 1. Одна из используемых модификаций такова: (8.21) Предполагается, что $х(в) ~ = 1. Теорема 8.11 для метода ('8.21) остается справедливой. Более того, последовательность х'"' сходится к собственному вектору по направлению, т.е. в(п (р("' — О при ))с - со, где у(") — угол между векторами х(") и е).
3 а м е ч а н и е 3. Крайне маловероятно, чтобы в разложении (8.15) вектора х(в' по собственным векторам коэффициент с) при е) оказался равным нулю. Теоретически в этой исключительной ситуации метод не должен давать сходящуюся к Л) последовательность. Однако при вычислении на ЭВМ по формулам (8.12) через несколько итераций вследствие погрешностей округления почти наверняка появится ненулевой коэффициент при е) в разложении вектора х("'. Итерационный процесс снова окажется сходящимся (правда, потребуется выполнить большее число итераций). 2.
Апостериорная оценка погрепшости. В общем случае для решения проблемы собственных значений не существует эффективных апостериорных оценок погрешности, в особенности для собственных векторов. Более простой эта проблема выглядит для симметричных матриц. Для оценки погрешности приближения Л' к собственному значению Л симметричной матрицы полезно использовать следующую теорему, Т е о р е м а 8.12. Пусть Л* — произвольное число, а х* — произвольнь(й ненулевой вектор. То(да для любой сил(л(етричной иатрицы А существует собственное значение этой л(атрицы А такое, что справедлива оценка !Л-Л*! < 1~ '!! (8.22) Если х' — приближенно вычисленный собственный вектор, то неравенствр (8.22) позволяет дать простую апостериорную оценку погрешности вычисленного собственного значения Л'. В частности, для степенного метода (8.13), (8.14) из (8.22) следует такая апостериорная оценка: (напомним, что здесь предполагается симметричность матрицы А).
Пусть х' — ненулевой вектор, рассматриваемый как приближение к собственному вектору х, который отвечает собственному значению Л. Далее, пусть р* = р (х') — отношение Рэлея, г = Ах' — р'х* — вектор невязки, а =, . Если собственное значение Л хорошо отделено от 1 Ч х остальных собственных значений матрицы А, то для оценки погрешности может быть использован следующий результат. Т е о р е и а 8.13. Пусть Л вЂ” блихайи)ее к р* собственное значение симметричной матрицы А, х — соответствую)ций собственный вектор и <р — у)ол мезкду векторами х' и х.
То)да справедливы оценки о о2 )Б1п )о) ~ ~—, ~Л р ~ ( —. 7 7 Здесь 7 = ппп, ~Л, — р*') — расстояние от р' до бли)кайшеьо из отлич- Л;ФЛ ных от Л собственных значений иатрицы А. Приведем еще одно важное свойство симметричных матриц. Т е о р е и а 8 14. Пусть А — симметричная матрица, х* — произвольный ненулевой вектор, р =,р (х*~. Тоьда р* и х* являются точными собственным числом и собственным вектором некоторой мап)- рицы А„для которой (8.23) Оценка (8.23) может оказаться очень полезной для обратного анализа ошибок (о существе такого подхода к анализу ошибок мы говорили в ~ 3.6).
Например, очень часто матрица А, для которой на ЭВМ производится вычисление собственных значений, является лишь приб- лиженным представлением "истинной" матрицы А, собственными значениями и векторами которой в действительности и интересуется исследователь. Пусть известен порядок погрешности в = !!А — А!!2 приближенно заданной матрицы и для найденной пары х*, р* — () (х*) величина (т =, оказывается сравнимой с вели!! Ах' — р *х*!! х чиной 3 или даже су)цественно меньше ее. В такой ситуации р' и х* оказываются собственными значением и вектором матрицы А„кото- рая отличается от "истинной" матрицы почти так же, как отличается от нее матрица А. Вряд ли тогда следует стремиться к получению "более точных" решений.
Пример 8.5. Используя степенной метод, найдем для матрицы (8.5) максимальное по модулю собственное значение Л1, а также отвечающий ему собст- венный вектор. Возьмем х(о> = (1, О, 0)т и будем вести вычисления по формулам (8.21). 1 и т е р а ц и я. Вычисляем у<1' = 2х'о' — 9х'о' + 5х'Ш = 2 у'1' г 3 ' 2 3 ' ' 3 1 2 ' 3 — 1 2х(о) 5 39993(о) + бх(о> — 1 2 у(1) = х(о> — х(о> 7 5х(о) — 1 тогда Л(1) (у(1) х(о) ) у(1) х(о) + у(1) х(о) + у(1) х( о) 2 1 + 1 1 2 2 з з у(1) м 2.53772 и х(1) = и (0.788110, !!у'" !! + 1.2 О + 1 ° 0 = 2.
Д . !!у'"!! = 0 472866 0 394055)т Результаты десяти первых итераций с шестью знаками мантиссы приведены в табл. 8.1. Таблица81 Номер итера- .(Ь з х' "' 2 х( Й) 1 Л<"' 1 ции Й 8-28 2.00000 -1.24159 -6.08121 -9.50971 -8.23499 -7.94591 1.000000 0.788110 — 0.250056 -0.611733 0.700557 -0.716752 0.720030 0.000000 0.472866 0.266743 -0.593143 0.583736 -0.579514 0.578443 0.000000 0.394055 -0.930763 0.523415 -0.410455 0.387853 — 0.383353 Л, — Л; станет минимальным по модулю, а максимальным по модулю окажется сдвиг другого собственного значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
