Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 55
Текст из файла (страница 55)
По формуле (8) находим Ы, = — 0.000263; )ч = — 17.863263. Приводим также результаты вычислений для ! = 2, 3, 4. ! ! и2 ! и, 0.032933 — О.'261309 0.236640 0.586694 )2 = — 17.152428, ).8 = — —,.574013, )4 = — 5.2)8696. Полученные значения для собственных чисел и компонент собственных векторов верны уже с точностью до 2 10 --0.020 ( 0.033 ~ — 0.351 0.170 . '--0.26! ' 0.328 П.!87 , '0.237 0.261 0.808 ~ 0.587 , '0.045 ~ — 0.351235 0.328466 0.260925 0.045006 О.О 13 ( —.1?01 ! 1.442 ) 0.587 ,' 1.!35218 ~ 0.112182 0,070589 0.011058 — 0.248 0.803 !.510 0.516 !.590 1 1ОЛЗО 0.045 ) 0,011 ГЛАВА 1г ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ Настоящая глава посвящена частичной проблеме собственных значений, которая состоит, как было сказано выше, в определении одного нли нескольких, как правило немногих, собственных значений матрицы и принадлежащих им собственных векторов. Своеооразие частичной проблемы заключается в том, что методы для ее решения должны основываться на косвенных соображениях, использующих те или другие свойства собственных значений и собственных векторов.
Все методы для решения частичной проблемы являются итерационными методамя. Для построения этих методов используются две, по существу различные, основные идеи. Первую идею мы поясним в предположении, что в пространстве существуе~ базис из собственных векторов. Исходя из некоторого вектора, вообще ~оворя, произвольного, строят бесконечную последовательность векторов так, чтобы в этой последовательности все более преобладала одна составляющая в разложении по собственным векторам. Тогда построенная последовательность будет сходиться по направлению к выделенному собственному вектору. Попутно определяется и собственное значение. Процессы, основанные на этой идее могут быть применены н при отсутствии базиса из собственных векторов.
В этом случае при их обосновании можно использовать разложение по каноническому базису. При этом некоторое видоизменение методов позволяет вычислять несколько векторов из канонического базиса. Вторзя идея основывается на экстремальных свойствах собственных значений и применима только к симметричным матрицам. Эта идея близка к идее релаксации для решения линейной системы уравнений.
Методы, основанные на этой идее, дают последовательность векторов, все лучше реализующих максимум (или минимум) отно- (АХ, Х) шения — '-.- .. (Х,Х) ' Выбор поправок для перехода от предыдущего вектора к последующему может осуществляться различно. Важнейшая группа методов, использующих эту идею, в которых поправки берутся в на- й 33) нливольшвв по модтлю совстввнное знлчвнив 329 правлении градиента функционала ' , будет рассмотрена в (АХ, Х) (Х, Х) главе НП.
В этой же главе будут вкратце рассмотрены методы, аналогичные методам координатной релаксации, простой и групповой. $53. Определение наибольшего по модулю собственного значения матрицы при помощи последовательных итераций В настоящем параграфе мы изложим метод, позволяющий вычислять наибольшее по модулю собственное значение матрицы и принадлежащий ему собственный вектор при помощи вычисления последовательности игерацнй произвольного вектора. Излагаемый метод называется с т е п е н н ы и и является простейшим и.ерационным процессом для решения частичной проблемы собственных значений.
Он применим для произвольной матрицы, хотя ход итерационного процесса существенно зависит от того, как входит наибольшее по модулю собственное значение матрицы в ее кзноническую форму Х<ордана. В связи с этим приходится различать несколько возможных случаев. Мы, однако, не будем исследовать проблему во всей общности и ограничимся рассзютрением лишь важнейших частных случаев. Лля упрощения изложения мы будем предполагать, что все собственные значения ма~рицы, кроме, может быть, наибольшего по модулю, имеют линейные элементарные делители, хотя выводы, которые мы сделаем, имеют место и без этого предположения.
Будем также считать, что элементы исследуемых матриц вещественны. 1. Наибольшее по модулю собственное значение вещественное н простое. В этом случае наибольшему но модулю собственному значению соответствует один линейный элементарный делитель, так что в силу только что сформулированного соглашения, все элементарные делители матрицы линейны. Поэтому существует базис из собственных векторов б и (,г,, ..., (Г,, принадлежащих собственным значениям )ч, )э, ..., )вн расположенным в порядке убывания модулей, причем !)ч( ~ !) (, но среди остальных могут быть равные.
Возьмем произвольный вектор У, и образуем последовательность его итераций матрицей А АУо А')'о А" Уо Напишем разложение вектора Уз по собственным векторам Уз= а,(Г, +азП + ... + а„(Г„. (1) Среди чисел а, некоторые могут равняться нулю. Предположим, однако, что а, + О. ') г) Так как ат =(Ъ'м Уз), где Ут первый собственный вектор трансзонирозанной матрицы, то требование ат ~ О будет выполнено в случае, если вектор Уа не будет ортогонален к вектору Ъ'м ЧАСТИЧНАЯ ПРОВЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИИ (гл. ч Очевидно, что А)' = агЛ,Ю1-+ а Л (/ + ....+ а„ЛЯ(7„ А Уе — — азЛ1(71+- азЛ".(71+ ... + а„Л„'0„.
(2) Обозначим ААУЯ = Уа = (упн у,„,..., увь)' и выясним структуру компонент вектора У„. Пусть (7 =-( и " и.)' (7з=(п1' л' н„У ., (~в=-= =(пн„мз„..., ин„)'. Тогда из (2) получим уц =- агин)1+ пзн11ЛЯ+ + пзмзь).1' причем коэффициент сг не зависит от индекса Ф н с, -= О. Рассмотрим отношение компонент двух соседних итераций, уг, 1,1ч +сзтз -г- ...
+с„1„ .АЭ1 А-1-1, ЬЭ1 УА сзЛ1' -1- сзАА + ... + с„Л„" 1+ Ь а~+1+ Ь, з~т~+ ... + Ь иьчз ) з з з з ''' н и (4) 1+Ьзазз'+Ьзаз Ь . +Ь А~~ где ег Лг Л ' (5) Сг' Произведя деление и удерживая члены до порядка а;'А и азь включительно, получим ~+~ = Л, (1 — Ь,,'аь — Ь„,'аь+ Ь ЬЯЯ1+ о (а~+ е~з). (6) где ЬЗ=Ьз(1 "з). (7) Отсюда мы видим, что если Лз достаточно велико, то Л1 УА+1 УА (8) Так как обычно все компоненты вектора с)1 отличны от нуля, то в качестве у„может быть взята, как правило, любая компонента Коэффициент при Л1; по крайней мере в одной из компонент не равен нулю, так как и, + О по предположению и вектор (71 не нулевой.
Пусть у„(первый индекс опускаем) какая-либо из компонент вектора Уь, для котороИ коэффициент при ),", отличен от нуля. Тогда ул — — сгЛ~1+сзЛЯ+ ... +С„Л,, (8) $ 531 МАИБОльшее по ИОдулю ООБственное знАчение зз( вектора г'„. Таким образом, первое собственное значение приближенно равно отношению любых соответствующих компонент двух соселних достаточно высоких итераций произвольного вектора матрицей А, При практическом выполнении итераций следует вычислять отношения — для нескольких компонент.
Хорошее совпадение этих УА+ ! Ул отношений будет показывать, что в выражении (б) различие значений коэффициентов (!,,', Ь! уже перестало играть заметную роль. Быстрота сходимости процесса в рассматриваемом случае определяется величиной отношения — "' н может бь!ть медленной, если это >, отношение близко к единице.
Для того чтобы избежать роста компонент, иногда целесообразно при вычислении итераций тем или другии способом нормировать на каждом шагу получаемые векторы. Удобными нормировками являются деление вектора на его первую компоненту, нли на наибольшую компоненту, нлн, наконец, нормировка к единичной длине. При этом вместо последовательности УА л!ы получим последовательность г'А =,!аул, где р!, нормирующие множители, и для получения )ч надо брать отношения компонент векторов Аг'„н 'га. Может случиться, хотя это и маловероятно. что начальный вектор г'з выбран неудачно, именно так, что коэффициент а, равен нулю, или очень близок к нулю.
В этом случае не будет ясной картины сходимости итераций по направлению. Действительно, на первых шагах итерации преобладающим будет член, зависящий от А, (если ле Ф 0). Однако в дальнейшем, если даже а, точно равно нулю, то после нескольких шагов итерации слагаемое, зависящее от ), появится, благодаря ошибкам округления, сначала с очень малым коэффициентом; по мере дальнейших итерациИ зто слагаемое будет довольно быстро возрастать по сравнению с остальными. .Борьба за преобладание" членов, зависящих от ),! и )а, вызывает неясность в холе процесса. При неудачном выборе, в указанном смысле, начального вентора, его необходимо изменить. Описанный процесс дает возможность определить также и все компоненты собственного вектора, принадлежащего наибольшему собственному числу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
