Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 70
Текст из файла (страница 70)
„А до; среди всех векторов вида А'до+Я, где Л~;1ь вектор дг имеет наименьшую А-длину. Далее, если процесс проъекает без вырождения, то оператор с матрицей А имеет в базисе д, ..., о„, трехдиагональную матрицу Якоби. То оо 1 Т, 8, Тл-г Р-г 8 1 Т Отсюда следует, что и — 1 ~~,'а Т; = 8 р А. г=о (11) Наконец, (Адн Ад ) = О при ~1 — у ! ) 1.
В случае нрежлевременного обрыва процесса всегда можно достроить систему А-ортогональных векторов до базиса всего пространства аналогично тому, как это делалось в методе минимальных итераций. Такую достройку нужно производить, если ставится задача об обращении матрицы или о решении большой серии уравнений с данной матрицей коэффициентов А, но с различными свободными членами.
При решении же одной системы достройка оказывается ненужной, если за начальный вектор до взят свободный член системы, так как при таком выборе начального вектора преждевременный обрыв процесса только сокращает объем вычислений. Действительно, пусть процесс А-минимальных итераций обрывается на г-м шагу.
Тогда г)„Я=1".+сГгт" +...+г1„гг+Ф„есть минимальный аннулируюший вектор г полипом, так что А"Р+ с1,А" Р+ ... + г1„,АР+ г)„Р = О, . , откуда Х=А г = — [ — А" 'г — ... — г1,,Г~. Поэтому Х принадлежит подпространству 1,1г. 4! 9 й 65! МЕТОД А-МИНИМАЛЬНЫХ ИТЕРАЦИЙ Векторы да, ..., д„, образуют базис подпростраиства Я„так что решение Х представляется в виде 1' — г Х=~~' а;дн а 0 Для коэффициентов а; сохраняются прежние фориулы а;= — ' (1=0, 1, .... г — 1).
(Р' я;) (Ал, у,.) С тем же успехом вместо свободного члена Г в качестве начального вектора д„можно взять любую невязку ге= à — АХ, где Хв произвольный вектор. Действительно, система АХ=- Р равносильна системе А (Х вЂ” Хе) = гы свободным членом которой является ге. В этом случае решение системы получаегся в форме где Если матрица А симметрична, но не положительно-определенна, то построение векторов (1, также возможно. Однако в этом случае может произойти „тупиковое" окончание процесса, в котором на некотором шагу может обратиться в нуль скалярное произведение (Ало дг), хотя д; чь О.
Так же как в бнортогональном алгорифме тупиковое окончание связано с неудачным выбором начального вектора и может быть устранено его заменой. Рассмотрим примеры на решение системы и обращение матрицы. Отметим, что вычислительная схема для построения векторов ды . ..., д„, почти ничем не отличается от вычислительной схемы метода минимальных итераций. Хорошим заключительным контролем при невырожденном течении процесса является выполнение неравенства (11) Дтг= Вр А.
В табл. Ч1. 12 приведено решение системы (9) $23. Части 1 — !Ч табл. Н1. 12 аналогичны соответствующим частям табл. Ч1.1. В части Ч выписываются (Р', д,) и коэффициенты ан Полученное решение (ср. э" 23) верно с точностью до 2 ° 1О в каждой компоненте. [ГЛ. ТТ 420 МЕТОД [БОСФ О ! О С0 СО ЯЖЕЯ О О О О О 1 О О СО СЧ СО 4 1 1 О О СО 00 Ос 04 О О О О О ОсО О Я 1 "0 СО ОЪ О '0 Ос У «СО ОЯ СЧСЧ Д СО ОООО О О О О 4 1 О «1 01 СО «0 Ф ОООО ! Б 00 Ос О О О О О О 0 О О О О СО С4 СО С СЧ 1' С'0 О СО 1' СО 1 СЧ СО СО С4 О СО СО ОО О О О О О С'1 СО 00 СЧ О О СО СЧ 04 С'4 С'4 04 О О О СС И Ос «0 сО 1 О О 1' О О О О О О Сс Я 1' С'0 1' О 1' О О О О О О О МИНИМАЛЬНЫХ ИТЕРАЦИЙ 0- О О О О оо о О О О О СО СО 1' СО 1' О о СЧ з Ос С4 С'4 СО «0 о О4 сО О л О О 421 9 65! МЕТОД А МИНИМАЛЬНЫХ ИТЕРАЦИЙ Вычислим также обратную матрицу для матрицы А.
Целесооб-г разно предварительно вычислить матрицу Я = Я'ь с элементами 40 Чы= 1, где 9гг — есть /-я компонента вектора дг. Имеем (Ад, 4,.) Тогда А = 911', согласно формуле (5). Вычисляя, получим, что 2.507586 — 0.123039 — 1 011489 — 1.378342 — 0.123039 1.322213 — 0.261427 — 0.447454 — 1.011489 — 0.261427 1,531827 0,445608 А — 1.378342 — 0.447454 0.445608 2.008551 Расхождение с даниымн Э 23 наблюдается лишь в трех элементах, причем в каждом элементе не превосходит 1 ° 10 ' В случае нормального течения алгорифма все собственные значения матрицы находятся как корни полииома д„(Г). Лля собственных векторов справедлива формула Чо (~г) 4 я в г ( г) (Чо АЧа) ' ' ' (44„~ Чч-г) (12) В случае обрыва алгорифма (не тупикового) последний полипом даст минимальный аннулирующий де полипом, а собственные векторы, найденные по формуле Чо (1г) Чг г (;) ггг — г)е ', ....+ 4„о (12 ) образуют базис из собственных векторов подпространства (Г„.
Процессом достройки можно определить все собственные значения и полную систему собственных векторов. Определим коэффициенты характеристического полинома и один из собственных векторов рассмотренной выше матрицы. Приводим вычисления, проведенные на основе таблицы Ъ'!.12. Прежде всего (Аоз Ада) = 0.000045183277 Тз= 0 69087467 еа = 0.01963390, 0.10869565 3.9932723 0.10869565 — 1.8247403 0.10869565 — 3.1470159 0.10869565 0.0264455 — 18. 922959 1.6149668 — 4.8704929 116.83158 2.5262182 — 99. 914532 23.681593 — 22.026662 422 [гл. ш метод минимлльных итеглций )»злее, вычисляем рекуррентно коэффициенты характеристического полинома: 1 1 — 4.00000001 1 — 3.30912534 4.75200003 — 2.88638288 2.48544305 — 2.11!85600 1.30929117 — 0.45139731 0.28615248 1 1 — 2.3! 8 Таким образом, 9 (Г) = Ч» (С) = »» — 4.00000001!з+ 4,75200003»з — 2.1118560001+ + 0.28615248.
Один иа корней этого полинома есть ),,= 0.63828371, Определим собственный вектор, принадлежаший этому собственному вначению. Предварительно вычислим коэффициенты рааложения по схеме: Лз 0 6382837! Чо () з) Чз(~з) = Лз — То — 1 6797163 Лз Т» 0.06990083 Ч, (Лз) — 0,12563391 )з — (з 0.21554125 Чз () з) 0.046903344 Лз — Тз — 0.05259096 Ч, (Лз) — 0.8263 ° 10™ Ч» (Лз) 0.106 Чо(Л»)ЯЧз Чо) 0.10869565 Чз (Л»ИЧ» Чз) — 22.210478 Чз (Лз)/(Чг Чг) — 37 716811 Чз(Л»)Г(Ч» Чз) 717.17535. Теперь собственный вектор находится по формуле (12).
Именно, 0»=( — 4.145756 9 265433 0 391085 3 944060)'= = 9.265433( — ОА47443, 1.000000, 0.042209, — 0.425675)'. Наибольшее расхождение с данными 9 63 не превосходит 1 ° 10 Если матрица системы АХ=»". не симметрична, то решение системы уравнений все же возможно найти посредством метода А-минимальных итераций, который нужно применять к равносильной системе, полученной первой или второй трансформацией Гаусса.
В обоих случаях расчетные формулы можно преобравовать так, чтобы набежать действительного вычисления соответствуюших матриц А'А или АА'. 5 6'! 423 метод л-минимальных итевхцнй При первой трансформации имеем »т»е» — 4 А»»» Т»»»» 3»ь»»-» — 4 т»» Т»»»» 3»»»»-1 о» = А»»» (А'Ау» А'А»г») (А'в», А в») Т» (А Ал» в») (А'А»уь»!») (о», еВ (о», о») (13) (А'А»)»», г»») (о»», в»») в-1 в- 1 (А'Айь»)») (о», еВ »-о »-а (оь о~)=(А»)», А»)») =(А'А»)», д))=0. Отметим, что А = гЛ»",»', (14) где матрицы )/ и Я составлены из столбцов ое, о,, ..., о„, и»ге, д», ..., »)„» соответственно, Л=[(ое, о,), ..., (о„,, о„»)[.
Аналогично вторая трансформация Гаусса приводит к методу АА'-и и н и м а л ь и ы х и т е р а ц и й. расчетные формулы метода тв» = А'»!» »»»»-» = Ат⻠— Т»»»» 3»й-» (А»а», Ан») (ы», в»») (в»ь ьи) о;= (ы»-»»я»-1) (15) Х=А' ~ч'„ащ = ~я~ а»»в» Легко видеть„что (и»», и~у)=0. В табл. Ч1. 13 и Ч!. 14 приведено решение системы (по данным табл. !!.1) методами А'А и АА'-минимальных итераций. Во второй части таблиц проверяется выполнение контрольных соотношений ортогональности. Описанный метод будем навывать методом А'А-минимальных итераций.
Для контроля можно испольвовать попарную ортогональность векторов о. Действительно, 424 [гл, ч! 11зя ! х ~63$ о о о ! О: ! ь а ! о а о о о Ц _#_ СЙ Мо фа 8 О О оооо й Я Фбй3 ЯВЛЯ обоб о о Ю с ! О О О! ОИ б о Я. О И Ъ С ° со соо ! Ф О! 3 п Я Е. О о ИФ=-" В о М боба О о а о о М ,О О Ю й й й й й Я б -"Р$= о о баас ! о о б о 3 '3 б О О О Й О а о оооо ОО О б % 3 Вйфй оооо ! Ф=И3 ообо ! О:О Й~~Иф о 2 о 'ба ! ! й ! ИЗДАМ й О О о о о' о ! О ! оооО ю1~.
! О ! оосб ! О б ! ! О » й3 Зо ба о ос О О о , о О О ! ообо 3:-.=3 ! ! а О! ! О О О а б а о О о ба о ! ! а ! а В й 6~ 3л О! оо ! О! О й М й й й й й й О О! О й й й и Ю б О и й В о и о И Ф МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ О~ й О О М ! й О й й о О О О О й й О 425 й 66] л-Биогтогонлльный Алгогием Я 66. А-бнортогональнуяй алгорнфм Наряду с описанными выше приемами симметрнзацин для решения систем с несимметричной матрицей можно использовать видоизменение биортогонального алгорифма — А-биортогональный' алгорифм. Сущность его заключается в построении двух систем векторов Че, ..., Ч„, и Че, ..., ~у„, таких, что (АЧо Чу) = О при У + / и (АЧь Ч;) Ф О (дяойствеиная пара сопряженных базисов). Системы векторов строятся по рекуррентным соотношениям Ч1 = АЧо ТоЧо Чг = А Чо ТоЧв Ч,1= — АЧ Т'й е~Чг-г Ч1,.1 ='" й Ти?! —.е1Чь-1 где (Айв А'Чг) (АЧг ЧВ (Айв Ч ) е;= (АЧг-г Чг-~) (2) После построения двойственной пары сопряженных базисов решение линейной системы вычисляется по формуле и- ь (3) а-е есть характеристический полином.
Найдя его корни, соответствующие собственные векторы можно построить по формулам (у Че Р') + + Ч -г (1г) (6) (АЧо Чо) ' ' (АЧ„ь Ч„-д) Канонический базис, в случае. если матрица А не приводится к диагональной форме, находится по формулам, аналогичным формулам биортогонального алгорифма. В табл, .Ч!. 15 приведено решение системы с данными табл. 11. ! по А-биортогональному алгорифму. Мы не будем вдаваться в исследование возможных вырождений процесса, так как это было бы почти дословным повторением п.
2 й 64. Отметим только, что одностороннего и тупикового окончания процесса можно избежать за счет перехода к другой системе начальных векторов. А-биортогональный алгорифм дает возможность решить полную проблему собственных значений. Так, при нормальном течении алгорнфма, полипом Ч„(г) в последовательности полиномов, построенных по формулам Ч~+г(у) = уЧГ(у) — Т;Ч;(у) — 6;Ч; г(Г), Ч, (Г) = г — Ты (4) 426 итеелций !гл. ч! вр 3О ! о о. о о а ! 38 яВБЖ 3333 $=-;3 3333 1 ! а и о и Я Х а а о 1 1 ! о о а а 'о 1 'а Ф а ! а 3 Йво 33й3 ооо ! !и Я о 1 1 ооа 3 бы о а 1 ' а и$ ! 3 о 3 3, ОООО 'ооо ! а о 3~3Й 3 3 й оооо ! а $„з= ! ! а 'о 1 ! о М "939 о о а В =3 о о о о О о О и 4 й о О. о й О й й й й О. » и 3 й й й й а о о о о метод минимлльных о я 3 Ъ оооо ! ! ЗЗЯ$ 8333 оыоо ! о ! ! о о о Р о о ! Я 3 3 ! 427 6 671 двгчлвнныв еогмглы 5 67.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
