Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 68
Текст из файла (страница 68)
Ря> (Ро Ро) аз+ а,а, + рааз (Р Р1) (Р! Рз) (20) (21) (Р, Р -!) ои-2+ ия-зов — 1— (Ря-н Р»-т) и провести вычисления по прежней схеме. Мы сразу получаем, что Ар!'> = Реп>, так что Р!'> есть собственный вектор, принадлежащий собственному значению >,а = 1. Нетрудно вычислить, что Х, = 16, >з = 1. Принадлежащие им собственные векторы (в подвространстве, натянутом на ре и Р,) вычисляются по формулам (17') ! 1 !! 1 !!' — Ро+ Р1 — '! 2 6) 3,36 !2' 3' 6> 1 ! 7 2 1 4!' г 3 6 1 (, 3 3 3)' 4. Решение линейной системы. Знание базиса Ре, ..., Р„ позволяет также найги решение линейной сисземы АХ= Г.
(18) метОд минимальных итеохций [гл, ш 404 Решив ее относительно а, ..., а„,, получим искомое решение по формуле (19). Однако, как мы увидим ниже, неболыпое изменение метода позволит избежать решения трехдиагональной шштемы и получить явные формулы для коэффициентов разложения решения по некоторой дру~ой системе базисных векторов. В вырожденном случае матрица вспомогательной системы разобьется на несколько трехдиагональных ящиков, и это только облегчит решение системы. $64. Биортогональный алгорифы Биоргогональный алгорифм можно рассматривать как обобщение метода минимальных итераций на случай несимметричной матрицы. При этом разнообразие в возможных причинах вырождения значительно увеличивается по сравнению с симметричным случаем, что несколько усложняет теорию метода.
1. Нормальное течение процесса. Пусть — А несимметричнзя матРица, Ро и Ро — два пРоизвольных начальных вектоРа. СтРоим две последовательности векторов Р| = А Ро — коро (1) Р;+~ = 4 Р~ а1Р— р Р'-1 Р1 = Аро — аоро Р;,, = — АР; — а;Р; — р;Р; где (Аро ро) (рь А'р;) (рь рг) (рь ра) (Арь Рг-и (Рь А'рс — 1) (Рь (2) Ара,) (А'рь р,,) (рь рг) (Ра-ь Ро-1) (Ро-г Р~ — г) 1р -, р - ) (Ра- о р~-г) (Р;-ь Ро-1) Ясно, что Р;=р;(А)ро, р,=р;(А')Ро, где ра(1) — полиномы, связан- ные рекуррентными соотношениями р, „, (Г) =- (1 — и;) ра (1) — Гэра, (Г).
торо + + '(е-гР,-г = 0. Из формул (2) видно, что процесс оборвется, как только в первый раз будет иметь место равенство (Р„, Р„) =-О, так что до обрыва процесса (Ро Ра) чь О, Непосредственным вычислением можно проверить, что для построенных систем векторов выполняются условия биортогональности, т. е., что (р;, Ру)=0 при (+у, Поэтому как вектоРы Ро, Р,, ..., Р„о так и вектоРы Ро, Р,, ..., Р,, линейно- независимы. Действительно, если 405 й 641 виогтогонлльиый Алгогням то, составляя скалярные произведения с ро получим Тг(рг Рг) = О р,=а,у,+ ... +а„(г„ ро=а,)',+ ... +а„1'„.
Легко видеть, что как коэффициенты а,, ..., а„, так и коэффициенты ан ..., а„все отличны от нуля, ибо еслв бы среди коэффициентов а,, ..., а„(или а,, ..., а„) нашлись нулевые, то векторы ра, .... р„, (нли ра, ..., Р„,) были бы линейно-зависимы, так как все они укладывались бы в подпространство меньшей чем л размерности. В силу предположения о нормальном течении биортогонального алгорифма мы построим две системы базисных векторов ра, р,,..., р„ и Ря, Р,,..., Р„, (двойственные, с точностью до ноРмиРованиЯ базиса) и одновременно систему полиномов р,(Г), рг(Г) ° р -г(г) Ря(Г) причем полинам р„(1) будет характеристическим. Пусть его корни найдены.
Будем искать собственные векторы для матриц А и А' в виде Уг~ = сыр~+ ... + с;„, р„, Ъ'ю = сг.ре+ + с;.— Р. (4) я так как (рг, р;) Ф О, то Т, = О, У = О, 1, ..., г — 1. Таким же образом убеждаемся в линейной независимости векторов р,, Р,, . , р„ Отсюда следует, что г ( л, т. е. процесс построения векторов Ро р» и ро, р,, ... должен оборваться не позже чем на а-и шаге.
Будем считать, что биортогональный алгорнфм протекает нормально, если он обрывается на л-м шаге, и является вырожденным, если он обрывается раньше. При нормзльном течении процесса как вектор р„, так и вектор р„равны нулю. действительно, вектор р„ортогонзлен к л линейно-независимым векторам р, р,, ..., р„,, а вектор р„ортогонален к п линейно-независимым векторам рю р,, ..., р„,. Покажем, как решается полная проблема собственных значений при нормальном течении биортогонального алгорифма. Сначала рассмотрим простейший случай, когда собственные значения матрицы А различны. Пусть У,, ..., (.г„— собственные векторы матрицы А, $'о ..., )г„ собственные векторы матрицы А' и пусть 407 $ 64! виОРТОГОНАльный АлГОРием В силу ортогональных свойств базисных векторов (5) Отбрасывая неравные нулю множители, получаем (7 Ро(Л)1 ! ! Р -1(11) 1= — =Ро Ро-1 (Ро Ро) (Ри-и Рп-1) (6) Ро (Ло) + + Ро -1 (Лз) (Ро Ро) (Р— Р»-1) В качестве иллюстрации решим полную проблему собственных значений для матрицы Леверье.
Вычисление двойственных базисов и коэффициентов характеристического полннома дано а табл. 11!.5, структура которой совпадает со структурой табл. Ч!.1 метода минимальных итераций. Конечно, для контроля кроме выполнения условий биортогональности целесообразно вычислять теоретически равные вначения (Аро р,) н (ро А'р;), а также (рь рз) по различным формулам. Заключительный контроль осуществляется вычислением о-1 ~~'., пз = Бр А, 1-О (7) Из табл. !71.5 видно, что характеристический полипом равен <7(!) Ро(С) !о+ 47 888430!з+ 797 2787711+ + 5349А556!+ 12296.55 !. Таким образом, значения для коэффициентов характеристического полинома, найденные по биортогональному алгорифму, почти совпадают с соответствующими значениями, найденными по эскалаторному методу (см.
9 48). Имеем далее Лз = 17 863262' Лз = — 17 152427' Лз = — 7 574044' Лз = — 5. 298 698. Для вычисления собственных векторов предварительно вычисляем множители разложения в табл. Ч!. 6, которая не требует пояснения. Далее вычисляем собственные векторы матриц А и А', нормируя их в соответствии с нормировкой эскалаторного метода (табл. Ч!.7 иИ, 8). (бе Ра) сс» = — ' (Р» Ра) (! Р Р») Се» вЂ”вЂ” (Ра Ра) Р» (Л;) =а; (Ра Ра) р„(л.) = Пз (Р„, Р») 408 МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ (гл. ш 7аолица Уйб Вычисление множителей разложения — 5.298698 — 17.152427 — 17.863262 — 7.574044 1 р, (! !) — 10.359641 ! Ро(Лд(Ро, Ро) Рв (Лв),(Рг Рг) ' Рв ()ч) (Ре Рв) ) Рв Рд (Рв Рв) 1 — 5.4740858 0.9179644 0.4182368 1 — 5.8773660 1.1887052 0.8010094 1 — 0.03995329 — 0.05900865 — 0.00501214 1 1.2509255 0.4399436 0,0313159 Таблана 1Ч.7 Собственные векторы матрицы А 0.032933 — 0.261308 0,236639 0,586694 — 0.019873 0.169806 — 0.187214 0.808482 1.135218 0.112182 0.070589 0.011058 — 0.351235 0.328468 0.260923 0.045007 Сравнение с данными эскалаторного метода показывает хорошее совпадение.
Биортогональный алгорифм не усложняется, если собственные значения матрицы комплексны. 1 4 3 ! Для примера рассмотрим в табл. Ч1.9 матрицу А=1 собственные значения которой Л,= 4+31, Ля=4 — Зй Ро (Лг) Лв — «о —— )ч — о! ! Рв(А ) Л.! — ав Рв (Л!) Лч — ов Рв (Лг) Р',(Лг) — 4.403603 43.857113 — 10.285383 — 234.24261 1.484009 0.00000250 — 91.8 1 — 9.648806 — 3.692768 33.868169 — 9.574548 †!22.30678 2.194844 — 0.0000468 80.7 1 — 0.070423 5.885615 — 2.177116 0.003835 1.465722 11.773227 0.000125 — 224 1 2.204923 8.
! 60961 16.231657 2.27918 ! — 9.15?839 14.048573 0,0000109 338 э 6Ц 409 виогтогонлльный Алгогием Таблица Ь7.8 Собственные веиторы матрицы А' Таблица 1Ч. У Вычисление двойственной пары базисов н коэффициентов характеристического полниома ! 1 1 ! 7 4 0) — 3! — 18 — 21~ О! 0 О ( ! З -6 ~ 3 ~ 24 З О ~ О РЗ ~ 1! 7 7 ) — 1 †!8 --!3 ~ -!3 ~ — 18 ' — 18 На основании табл. Ч1. 9 заключаем, что Рз(М) = 7э — 87+ 25, откуда х,=.4+.31, )э=4 — 3!. Коэффициенты разложения для и, †3! — 3 — 3! и и~ будут 1, — 18 н 1' — 18 . Отсюда и,=(1, !у, и,=(1, — 7у, Будем теперь считать, что среди собственных значений матрицы А (следовательно, и А') есть равные. Соответствующие элементарные — 0.01 4059 0.780381 — 1.140762 0.808484 0.023297 — 0.248476 — 12200904 1.509558 1,441927 ) 1.589924 0.586694 ~ 0.045006 8 7 О! О' — 42 — 18, 0.803091 0.515562 0.430! 26 0.011058 410 МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ (гл.
ш делители должны бьсть взаимно просты, ибо в про~ианом случае минимальный полипом матрицы А (и А') не совпадал бы с характеристическим и зто привело бы к вырождению биортогонального алгорифма не позже, чем на т-м шаге (где т — степень минимального полинома), что противоречит предположению о невырожденном течении алгорифма. Биортогональный алгорифм позволяет определить весь канонический базис пространства. Именно, пусть Ло ..., Л,— различные собственные значение матрицы с кратностями и,, и,..., л,, и, + ... + и, = и. Тогда в канонической форме Жордана будет з ящиков с порядками л,, ..., и,. Каждому ящику соответствует канонический базис и~"1, ..., и(гч ') при 1=1, 2,...,з, причем Аи,— Л,и,пО <о1 1о1 Аи( о-г) ) и('о-1) и(по-о) с Вектор и; =.и~~) есть собственный вектор, принадлежащий собственному значению Ли Проведем биортогональный алгорифм.
Ясно, что последний полипом р (1), полученный по ходу бнортогонального алгорифма, будет характеристическим полиномом матрицы А (и А'). Собственные векторы матрицы А (н А') также будут определяться по прежним формулам (6), которые, однако, требуют обоснования. Легче всего доказать их справедливость непосредственной проверкой, Пусть и,= Ро+ . " + — Р.-, Ро (Ло) Рп-т (Лг) (Ро Ро1 (Рп-1 Рп-д В силу соотношения Ар;=р;,,+ойр;+~ар; имеем Аи;= Ро ~ (р,+о р)+- Р' о (р +а,р,+~,ро)+ ....+ (Ро* Ро) (Рг Рд Р - (Лд ( р +р ) ~ оро(Лд+йгр (Лг)1 (Рп-ь Рп-д 1. (Ро, Ро) (Рь Рг)1 + ("д+ Р('д+РЬ(Л) + ...
+ ((Ро Ро) (Рь Рд (Ро Рд 1 р-ор, -р-по1 + - ~рп 1. (Рп-ь Рп-д (Рп-ь Рп-г) 411 $ 641 БиОРТОГОнАлъный АЛГОРием Но ,ро(ЛД Р,р,(ЛД о+рз(Лз),+Лз —,, 1 ) р,(ЛД (Ро, Ра) (Рм Рз) (Ро Ро) (Ро Ро) (Ро. Ро) (Ро Ро) Ра (лз) + пзрт (Лд+ ргрг(Лд Ьзро (Лд+ и' Р1 (Лд+ Рг(Лд ) Р1 (лд (Ро Ро) (Р1 Р1) (Рь Рг) (Рь Р1) (Р1 Р') р.-г()ч) + ° -зр -1 (Лд р -зри-з(Лд+ "- Р,-1 (Лз) (Ри-г.
Ри-г) (Рп-1 Ри-1) (Ри-ь Рп-П Л Р -1(ЛД 1 (Р -ь р -1) Следовательно, А(1з=лз(1О т. е. (1'; действительно есть собственный вектор, принадлежащий собственному значению Лз. Точно так же верны формулы (РФ Ро) (Рп-з, Рп-1) для собственных векторов матрицы А'. Покажем теперь, что векторы ц Рз(лд Р1-1(зд Й = — — -.-Рз+ . + -' Рп(Рь Рз) (Ри-ь Ри — 1) Л Л. (у(г) за ( д + из = р+...—;— Р -1 2((Рг, Рг) 2((Р 1, Р -1) (8) (ио — 1) (из-1) (т(пз-1) из 1 ) + + Р -1 (д (пз Л)>(рпз-1 Риз-1) (из — 1)'(Ри-1 Рп-1) являются корневыми векторами, принадлежащими собственному значению Ль обРазУющими канонический базис соответствУющето подпространства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
