Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 69
Текст из файла (страница 69)
Проверим первую из этих формул. Для упрощения выкладки введем обозначения Рз (Лд Ри-1(лз) 1 - П1= (Рь Рд (Ри-ь Ри-1) Имеем Аи,' — )чи" = (,Арз+...+д„зА „,— Лз тзрз — — ЛР(п р.— =- = глзоз(ро+ (з(Р1+ зогагг Лзиз)Р1+ Ж+ з(гпг + "загз — ) зз(з)рз+ + +(з)п — +Д вЂ” и — — Л1Д -)Р,- = = (лоро+ Рзрз + + злп-зрп-з.
р 64) 413 БиОРТОГОнАльный АлГОРнем Таблица !г/, /б Вычисление двойственной нары бавнсов н коэффициентов характеристического полинома Ро Ро АроА'Ро| Р1 Р~ Ар, А'р, р — 8! — 8 О 3' — 8 — 1/4 1| 3 — 5/8 О О О !О~О О ! Π— 5 — 1 ~ — 2 — 1/8 1 7| О,— 4! — 13! ΠΠ— 8| 13 !3| 1/8 | 1/8 5/64 5/64 | 4| 4| — 8 Согласно табл. Ч1.10, р,(!) =/г — 3/г+ Зг — 1, ?, = Аг =) г = 1, Далее вычисляем р,'(1) = Р„(1) =1 р,(!) = — 3 1 рг(1) = 8 Рг(') = — 8 3 р" (1) = 2 1 1 — 3 8 Ро+ Рг+ 1 о 8 ! 8 (/1," = Рг=(1 ° 1 1) 3 1 8 — 8рг+ 1 Рг = (О 1 ° 2) 8 (/!'! = — р =(О, — 2, — б)'. 2!— 8 (/!г! 1 1 ! О О О' О 4| 4' 2~ — 03/8 — 1/64 ! 1 — 19(8 3/2 - | Рг ~ Арг Арг |Ро|ро 1/8 — 1/8 ΠΠΠ— 1/4,'— 3/8 --1(8 ( ΠΠΠ— 4/8 О р,"(1) = 0 р,"(1) =-0 414 метОд минимальных итераций [гл.
Тп Аналогично Рз=(1, 2, — 1)' ЗР =(О, — 1, 1)' 8р, = (О, 1, — 2)'. !2! В качестве второго примера рассмотрим матрицу, каноническая форма которой состоит из двух ящиков (один нз которых первого порядка), а именно матрицу 13 16 16 — 6 — 7 — 6 — 8 — 7 Ее собственными значениями будут Л,=Л =1, Лз — — 3. Таблица Ъ7.77 Вычисление двойственной пары базисов и коэффициентов характеристического полииома Ар,! ~А'р, Ар, ~ А'р, ) ! р, р, 1 Ар.,!АР, р, Р. — 176 !з !3 — 5 1б — 16!и -16/И 71 32 16!и — 16П1 16 -6 О -23 - 32!и 96!и — 176 — 176 2446 — 512П ! -бы!И -Он!И 13 13 — 176 512/121 512 121 !з !Ч -Иб -153!и 327!21 — 17и ч -!з 3, Согласно табл.
Л.11, Рз(Г) = 73+ Р— 67+ 3, ).,=) = 1, ),,= — 3. Далее вычисляем Ро (Л!) = 1 Ро(!ч) = 1 р'(Л) =О Р'()ц) = 32 Р'Ь) =11 Р1(Л!) = — 12 Р,(Л,) = — 16 32 Р,(Л,) = — —, 16 Рз(Л3) = 11 1 о о " 1 — Ро+ Р!+ ои - 3- 4и 8 Р1 о 16 16 1 нки — 53!и о — 192!и 1в77и о о о 6471! О О 32П1 О О 416 й 64) БИОРТОГОНАЛЬНЫй АЛГОРИФМ У1 — — (1,— —, — — ~; У1 =(0,1,— 2)', Уз = ~1 — 2 ~ 2 ) ° 4' 21' 2.
Вырожденное течение алгорифма. Изучим возможные причины обрыва алгорифма, Допустим, что. алгорифм обрывается на г-м шагу, так что (рг,)11) чь О, 1=0, ..., г — 1 и (р„р„)=0. Как мы видели, системы векторов и,, ..., Л„1 и )те, ..., р„1 линейно- независимы. ВвидУ того, что вектоРы Ре, АРш ..., А" 'пе линейно выРажаютсЯ чеРез Рш Ро ..., Р„, и обРатно, заключаем, что векторы рш Арш ..., А' ~па лннейно-независимы. Точно так же ли~г-1 нейно-независимыми будут и векторы уш А'ре, ..., А Ре Обозначим через Р„подпространство, натянутое на векторы Рм Ры ..., Р„, (или, что то же самое, на вектоРы Ре, АРО, ...
3-1 ..., А ре14 через Р„подпространство, натянутое на векторы Рю, Р1 ° °, р,, через Я„и Я„их ортогональные дополнения. Тогда Р, П 6„ = 0 и Р„ П Я„ = О. Действительно, нз условий (Рг Рт) = 0 при 1 чь у' и (р1, р;) чь О, следует, что в Р„ не существует ни одно~о вектора, кроме нулевого, ортогонального ко всем векторам из Р„ н в Р„ не существует ни одного вектора, кроме нулевого. ортогонального ко всем векторзм из Р„. При обрыве алгорифма на г-и шаге возможны четыре случая. 1. п„=р„=0 (двусторонний обрыв а лго рифма). В этом случае У)„=Р„(А)РО= О, но в силУ линейной независимости вектоРов ро Аро А' 'ре ни при каком полиноме м(г) ниже г-й степени невозможно м (А)РО = О.
Следовательно, полинам Р„(1) есть минимальный полипом, аннулирующий вектор р. Так же устанавливается, что р„(1) есть минимальный полипом, аннулирующий вектор ре (по отношению к матрице А'). Подпространство Р„будет инвариантным относительно А подпространством, именно циклическим подпространством, порожденным вектором пе. Подпространство Р„будет инвариантным относительно А'.
Соответственно Я, будет инвариантным для А, Я.— инвариантным для А'. Размерности подпространств Р„и Р„одинаковы, следовательно сумма размерностей Р„и 1,"„равна размерности всего пространства и, так как Р„ПЯ„=О, получаем, что все пространство есть прям ая сумма ив вари анти ык(относительно А) поди ро стр анств Р„и 1;),. Таким же образом, все пространство есть прямая сумма ннвариантных (Относительно А') подпространств Р и <;1 . Итак. в случае двустороннего обрыва алгорнфм дает минимальный аннУлиРУющий вектоРы Ра и Р полипом. ПРи этом оказы- 416 (гл. Т| МЕТОД МИНИМАЛЬНЪ|Х ИТЕРАЦИЙ вается возможным разложение пространства в прямую сумму двух инвариантных подпространств, из которых одно циклическое.
2. р„= О, р„+ О (односторонний обрыв). В этом слу- чае р„(1) будет минимальным аннулирующим полиномом для рэ, но не будет минимальным аннулирующим полиномом для р,. Подпро- странство Р„ не будет инвариантным для А' н Я„ не будет инва- риантным для А. Хотя по-прежнему гс = Р„ + (;|„ но это разложение не является разло|кением в прямую сумму инварнантных подпро- . странств.
Аналогичный результат имеет место в случае 3. р„ Рь О, р„ = О. В последнем случае 4 Р„ФО,Р,ЦИО, но (р„,р„)= — О (тупиковый обрыв], ал- горифм как бы заходит в тупик, так как в результате проведения алгорифма мы не получаем ни какого-либо делителя характеристи- ческого полинома, ни инвариантного подпространства. Можно показать, что односторонние и тупиковые обрывы алго- рнфма являются исключительными и их можно избежать посредством надлежащего выбора начальных векторов ре и р,. Именно, векторыр, и р, всегда можно выбрать так, что в результате проведения ал- горифма будет определен минимальный полипом матр|щы А и кано- нический базис циклического подпространства, порожденного на- чальным вектором, В случае двустороннего обрыва всегда можно осуществить до- стройку полученных систем векторов Ре...,, Р, | и Ро .
. ° Р до биортогональных базисов пространства. Достройка делается со- вершенно аналогично тому, как это делается в методе минимальных итераций. и 65. Метод А-минимальных итераций Предположим, что матрица А положительно определена. Тогда, как мы видели (теорема 1!.19), любая система линейно-независимых векторов может быть подвергнута процессу А-ортогонализации. Если процесс А-ортогонализации провести для системы векторов |Уэ, АВ, ..., А" '|ущ мы пРидем к методУ А-минимальных и~еРаций. Этот метод может быть применен для решения полной проблемы собственных значений, аналогично описанному выше методу минимальных итераций.
В применении же к решению системы уравнений с матрицей А метод А-минимальных итераций оказывается более удобным. Действительно, пустытш ..., д„ , полученный в процессе А-ортогонализации базис. Если решение системы (1) 417 мвтод л-минимальных итвгаций й 65) искать в виде Х= ~~', ащ, е-е (2) то из уравнения и 1 ,У, а;А4;=Р получим для коэффициентов ае явные формулы а =— (А41, де) Дадим формулы для вычисления обратной матрицы. Условия А-ортогональности векторов де, ..., 17„, могут быть записаны в матричной форме с;)'АЯ = Л, (4) где (г — матрица со столбцами 49, ..., ди 1, Л=((де, Ае)9), ... (и -1 А17и 1)).
Из формулы (4) непосредственно следует, что А =ОЛ '1;) . (5) Легко видеть, что система А-ортогональных (сопряженных) векторов строится по трехчленным рекуррентным соотношениям 41+1 = Арю — 7в71 — 61171 1. 17 = Ае)е — 7979 (6) где (А17,, Аде) (А17,, Аде) (Ад,, 41) (АЯФ А4,,) (Ад,, Ав~ ) (Адь 41) ( 71-1 91-1) ( 91-1 41-1) (7) где е)1 (Г) полиномы, удовлетворяюшие рекуррентным соотношениям 99= 1. 41(г) = ~ — те 49+10) = И вЂ” 71)%(г) — М-1И) (р) Полиномы ре (г) будут, очевидно, удовлетворять соотношениям ортогональности г) (Ц г)е (1) Г геее1® = 6 (1 ~ 7) 27 Зав.
9?Е. Д. К, Фаддеев и В. Н. Фаддеева Этот процесс построения векторов е)1 может оборваться только если некоторый вектор д„окажется нулевым. Как правило, это происходит при г = и. Преждевременный обрыв свидетельствует о линейной зависимости пос,тедовательных итераций де, Ади,, А 49 т. е. о том, что минимальный аннулируюший вектор 49 полипом не совпадает с характеристическим. В силу построения % = Чг (А) Че. 1гл. ш 418 МЕТОД МИНИМАЛЬНЫХ ИТЕРАЦИЙ гле Г-'(С) весовая функция для полиномов рг(г) в методе минимальных итераций. Векторы до, ..., д„ г обладают рядом свойств, аналогичных свойствам вектороз'ро, ...., р„,. В частности, корни полиномов до(Г), ..., д„,(Г), д„(1) вещественны и разделяются; векторы до...,, д;, составляют А-ортогональный базис подпространства Г;1Ь натянутого на векторы до, Ауо...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
