Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 47
Текст из файла (страница 47)
Таким образом, мы видим, что решение системы (6.2.11) можно использовать в качестве аппроксимации искомого собственного вектора, Подчеркнем, что нас интересует только направление вектора у», и мы можем нормировать его на любую величину. Два фактора влияют на точность полученной аппроксимации. Во-первых, если Х» очень близко к другому собственному значению, скажем к Х»+1, л то разность Х»+, — Х» тоже будет малой, и первый член в (6.2.12) уже не будет доминирующим. В этом случае окажется, что мы аппроксимируем некоторую линейную комбинацию векторов у» и у»+1. Близость собственных значений, являясь свойством, внутренне присущим данной конкретной ") Это гарантируется также и симметричностью матрицы А„1.
Однако последующие рассуждения остаются справедливыми и для несимметричных матриц. 13а 195 матрице, порождает трудности при использовании любого численного метода нахождения собственных векторов. Вторым фактором является возможность того, что коэффициент у~ будет очень малым, так что первый член в (6.2.12) снова окажется не настолько доминирующим, чтобы дать хорошее приближение к нужному собственному вектору.
В принципе, мы могли бы этого избежать, выбрав вектор д так, чтобы коэффициент 'уь не был малым. Однако с полной уверенностью мы можем осуществить такой выбор только в том случае, если мы знаем все собственные векторы, что, конечно, не имеет места. Обнаружено, что выбор в качестве И вектора, все координаты которого равны единице, работает обычно вполне удовлетворительно. Близкая стратегия, которая иногда работает даже лучше, заключается в применении алгоритма гауссова исключения к матл рице А„, — Хь1 с целью получения верхней треугольной матрицы 11и последующем реше~ии системы 1~ = х, где з — вектор с координатами, равными единице.
В этом случае вектор И не задается явно, а определяется неявно как вектор, который при гауссовом исключении приводит к вектору из всех единиц. Очевидно, что в выборе вектора Ы имеется большой произвол. На самом деле, очень мала вероятность того, что "случайное'* задание вектора д приведет к слишком малому значению коэффициента уь. Обычно оказывается полезным еще раз решить трехдиагональную систему, использовав в качестве правой части только что вычисленный приближенный собственный вектор. Даже если первоначальный вектор д имеет очень маленький коэффициент ук, приближенный собственный вектор будет иметь большее значение Ъ„так что еще одно решение системы может дать приемлемую аппроксимацию, Эту итерационную процедуру можно повторять сколь угодно раз, но обычно одного дополнительного решения оказывается достаточно.
После того как приближенный собственный вектор матрицы А„, найден, он должен быть преобразован в приближенный собственный вектор самой матрицы А. Согласно (6,2. 1) мы имеем А„, = РАР, где Р = Р„ ... РгР,. Если х — собственный вектор матрицы А„~, то, как видно из Ау =АР х =Р РАР х=Р А„х= ХР~х= Ху, вектор у = Р х является собственным вектором матрицы А.
Следовательно, если х — приближение к собственному вектору А„~, то,применяя те же самые преобразовании, получаем у — Р х — (Ри — 2 РзР~) х — Р~ Ра Рп эх (6.2.13) =Р,Рэ... Р„эх = (1 — 2иг,м~~ )... (1 — 2и'„эв„з)х. Эти преобразования очень легко выполняются, если, конечно, мы прн приведении к трехдиагональной форме запомнили векторы и„..., ю„ В этом случае мы сначала выполняем преобразование (1 2®и — 2 ии — 2) х х 2(и'л — 2х) ®л — 2 ~ затем к этому вектору применяем следующее преобразование с матрицей (1 — 2и„э и,~ э) и т.д. 196 Теперь приведем пример, который легко просчитывается на карманном калькуляторе. Пусть 120 80 40 -16 80 120 16 -4 А = 40 !6 !20 8 — 16 -40 -80 1 (6.2.14) Это специально подобранная матрица, собственные значения и собственные векторы которой известны, так что мы будем в состоянии проверить точность наших вычислений.
Собственные значения этой матрицы — 16, 64, 144 и 256, а соответствующие собственные векторы— 1 — 1 — 1 — 1 1 — 1 — 1 * "2 — ~э т4 — 1 ' 1 ' — 1 — 1 — 1 — 1 1 — 1 т, — 1 Начинаем с приведения матрицы к трехднагоналыюй форме по методу Хаусхолдера. Вычисляя по (6.2.4) вектор и,: а = — 90,86, и~т = (О, 0,9696, 0,2270, — 0,0908), и выполняя затем первое преобразование (6.2.1), получаем 120 — 90,86 0 0 — 90,86 157,2 — 16,17 65,63 0 — 16,17 102,9 -51,44 0 65,63 — 51,44 98,89 Далее, 0 О 446,26 78,84 Матрица А з имеет нужную трехдиагональную форму. Теперь перейдем к вычислению собственных значений матрицы Аз по методу последовательности Штурма.
Так как ЙАз Й = 315,7, в качестве отрезка [1, и[, содержащего все собственные значения Аз, можно взять отрезок [ — 315,7, 315,7]. Положим, Л = 0 — зто средняя точка отрезка [1, и] . Отметим, что при вычислении значений полиномов р ~ (Л),..., р„(Л) существует опасность возникновения переполнения или исчезновения. Эта опасность значительно уменьшается, если вычислять отношения г; (Л) = р; (Л)/р; ! (Л), 1 = 1,..., и, г;(Л) =а; — Л вЂ” Ь~ р,.
(Л)[р; ~ (Л), 1=2,...,и, г~(Л) =р,(Л) =а~ — Л. 197 т=67,59, ю~~ =(О, О, — 0,7872, 120 — 90,86 — 90,86 157,2 0 67,59 О 0 0,6168), 0 67,59 124,0 — 46,26 Так как ра(Л) — = 1, то значение с(Х), равное числу совпадений знаков соседних членов последовательности ре (Л), р, (Л),..., р„(Л), есть просто число неотрицательных членов последовательности «~(Л), . . ., «„(Л). ДляАз н Л =О мы имеем «, (0) = 120, «г (0) = 157,2 — ( — 90,86)а/120 = 88,42, «з (0) = 124,0 — (67,59) /88,42 = 72,34, «4 (0) = 78,84 — ( — 46,26) /72,34 = 49,25. Так как все ««(0) неотрицательны, то с(0) = 4, и все собственные значе- ния А, лежат на отрезке [О, 315,7].
Теперь возьмем Л = 157,8 — среднюю точку нового отрезка — и вычислим последовательность значений «~(157,8) (1 = 1, 2, 3, 4). Это дает с(157,8) = 1, так что одно собственное значение матрицы Аз находится на отрезке [157,8, 315,7], а остальные — на отрезке [О, 157,8]. Если мы теперь сосредоточимся на вычислении макси- мального собственного значения Х ~, то получим следующую последователь- ность шагов: Л= 236,7, с(Л) = 1, Л~ (=-[236,7, 315,7], Л=276,2, с(Х)=0, Х, Е [236,7, 276,2], Х= 256,5, с(Л)=0, Х, Е [236,7,- 256,5], Л= 246,6, с(Л) = 1, Л~ Е [246,5, 256,5], Можем продолжать эти вычисления сколь угодно долго, получая все меньший и меньший отрезок, на котором содержится Х,.
Потребуется еще около двадцати таких шагов, чтобы получить приближение к Л~ с точностью до восьми знаков. Для вычисления остальных собственных значений мы должны вернуться к отрезку [О, 157,8], который, как мы видели, содержит три младших собственных значения, и повторить ту же самую поце дуру. В заключение мы рассмотрим вычисление собственного вектора, соответствующего максимальному собственному значению.
Пусть найденное приближение к максимальному собственному значению есть Х,= 255,99998. Так как точное значение равно 256, то наше приближение верно до двух единиц последнего разряда, Применяя гауссово исключение к систе- л ме (А, — Л, 1)х = И, мы получаем верхнюю треугольную матрицу — 136,0 — 90,86 0 0 67,59 — 132,0 — 46,27 — 46„26 — 177,2 0,9298.
10 ' Воспользуемся рассмотренной выше стратегией неявного задания вектора И, так чтобы правая часть преобразованной треугольной системы была вектором г, все координаты которого равны единице. Решая далее систему Ух = х и обозначая решение через х, получаем хт 10а(4 884 7 310 4 119 1 075) 198 л л Затем снова решаем систему (Аз — Х,l) х=х, где в правой части стоит только что найденный приближенный собственный вектор. Это дает х = 101о(5 250 7 862 4430 1 157) и после выполнения преобразований (б.2.13) мы получаем соответствующий собственный вектор матрицы у" = 10' (5,250, 5,250, 5,250, — 5,250), который после деления на 5,250 .
10' совпадает с точным собственным вектором. Остальные собственные векторы, соответствующие Х„Хз н Хч, могут быть вычислены аналогичным образом. Теперь сделаем ряд общих замечаний относительно погрешностей методов этого раздела. Преобразования, которые выполняются при приведении матрицы к трехдиагональной форме, численно очень устойчивы, и ошибки округления не представляют здесь серьезной проблемы. При вычислении собственных значений ошибки округления могут повлиять на результаты только в том случае, если знак некоторого р,(Х) будет определен неверно, так что значение функции с(Х) будет ошибочным. Это, по существу, та же самая проблема, с которой мы встречались в разделе 4.2 при рассмотрении метода половинного деления. В общем случае такие ошибки будут влиять на собственные значения только тогда, когда требуется очень высокая точность. Более всего подвержено влиянию ошибок определение собственных векторов, и особенно тогда, когда матрица имеет несколько очень близких собственных значений.
В последнем случае нельзя рассчитывать на точное нахождение отдельных собственных векторов, а можно только пытаться правильно выделить собственное подпространство, соответствующее этой группе собственных значений. За исключением этих возможных трудностей при определении неквторых собственных векторов, описанные методы оказываются вполне удовлетворительными н проявляют на практике весьма малую чувствительность к ошибкам округления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
