Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 83
Текст из файла (страница 83)
) '>„собственные значения матрицы А на инвариантном подпространстве, порожденном вектором Хо. Пусть р)Ю (1' = О, 1, ..., г — 1) и о)!> (1= 1,..., г — 1) числа, построенные согласна схеме деления и вычитания. Тогда Огл р(ь) =Л., >пп о(ь) =О. (8) 1.1- 1 ' с >с и со Ь и со Локазательства. Подиномы р)ь) (1) = Г!+ ... характеризуются условиями ортогональности (Аьргь) (А) Х, р!">(А) Хо) = О при 1+ТО Эти ь )с условия можно переписать в форме Лр(")(А) А'Хо, р(.")(А) А'Хо) = О. что означает, что р))ь) (1) суть полиномы Ланцоша, построенные для начального вектора Уо( ) = А 'Хо.
511 $77) АЛГОРИФМ ДЕЛЗННЯ И ВЫЧИТАНИЯ й Последовательность вектоРов А ВХьо очевидно, УдовлетвоРЯет условиям теоремы 75.1. Следовательно, имеет место предельное соотношение Вш р<й>(1) =р,(Г) =(( — Л,)... (à — Л,). й Роо Переходя к пределу в вытекающем нз (2) равенстве (й) ~ гьг гРф'(г)-Р(У "(О рг — (й-ц (,) Рг получим (ю 㫠— ЛП ... П вЂ” л,) — (г — л,)... (г — 1ч) (г — л,ь,) 1!гп р (г — л~) (г — лг) Для а!й1 получим аналогично ! > — - — — О й -э оо Рг-ь (О Теорема доказана.
Теперь перейдем к обобщению алгорифма в двух направлениях. Во-первых, распространим его на любые матрицы с вещественными различными собственными значениями и, во-вторых, введем в рассмотрение более широкий класс весовых функций, управляющих ортогонализацией. Как мы увидим ниже, рациональный выбор последовательности весовых функций может значительно ускорить сходимость процесса. Пусть (Г) 1,7,(1) — Р тй(г) — ((Г (,)... (( — 7й) (/г.= 2, 3, ...) (9) последовательность полнномов.
Каждый последующий полипом получается из предшествующего умножением на линейный двучлен. Пусть, далее, А данная матрица, собственные значения которой вещественны и различны, Х, и г'р некоторые начальные векторы. Исходя из системы векторов Хй, АХЫ .,., А" 'Х„ и системы вектоРов Гю А''г'щ ..., А'" 'г'В, постРоим системы вектоРов Р!ой!, РЮ, ..., Р<й1, и р!й( РОК ..., р<~>, биортогональных по весу ~ой(А). Мы будем предполагать, что начальные векторы Хй н 'г'з выбраны так, что пРн всех в=О, 1, ... постРоение вектоРов Р'йб ...Ря"), и Р<й>, ..., Р(А1, возможно, т. е. что процесс ортогонализации протекает при любом гг без вырождения.
Векторы р)й> вполне характеризуются выполнением следующих двух требований: 1) р! 1=Р( )(А)Х, где Р(1(г) =!+с~ ) г +... 2) (тй(А)Рг ~ Аы)о) О пРи 7' О 1 ' ' ! 1 512 итягйционные методы для гашения полной пговлемы !гл. чш Нетрудно дать явные формулы для векторов р(й) и полиномов р(йа)(~). Именно, положив щ()о ., щ(у) о т(а> ... т(а) р(й) (с)— 1 .(11) щ(>с) (й) > ''' й( — 1 где (~ой(А) А о' 1 о)' мы будем иметь ('Уй(А)Р; (А)Хо Ас Уо)=(с~а(А)А)Р( )(А)Хо У)= щ(а) щ(й> щ(а> о ''' с) ) т(й)... т(") щ(а) с ) -с- 1 = О ()'= О, 1, ..., ( — 1).
щ(а> щ(й) щ(й) м-! с-с( т(й> ... т(у) о ''' с-с (й) Ь( л>(."> ... т(а) . йс-и ' ' ' йс-В (12) Таким образом, для обеспечения невырожденного течения процесса ортогонализации на каждом шагу нужно предполо)кить, что все определители Ь( отличны от нуля. ()с'с Тогда р(,") = >з((а> (А) Х,, где (13) Отметим одно. важное для дальнейшего, свойство полиномов р(й>((). Именно, докажем справедливость тождества ))» ((а+с) = ( — 1) б) -(й> ' (а ос> (1 4) ЛЕйетантЕЛЬНО, В СИЛУ РаВЕНСтВа с(сй,(Г)=1а(~)(( — ~а+(), ИМЕЕМ тс + > = (уа (А) (А — (ай(Е) А Хо, Уо) = (й) = яа(А) А'+'Хо Уоу — 1а+гйа(А) '" Хо Уо) = т)й) Га с)ту ' (>с) Поэтому вектор >Т(У)(А) Х лишь численным множителем отли- с о чается от вектора р(.).
Этот множитель равен —, где й 1 с а(й) ч 771 Алговиам делания и 'вычитАния Отнимая в определителе т!">... т!"> о т!") ... т>!') Р(й) (г ), ! й,.1 44">." 2", ! Га„ из каждой строки предыдущую, умноженную на,га,! получим т)й) ... т)а> 1 ~ О .
4-1 т!"4Ц ... т)ййю О , ')а+ц о '' 4! — ( 1)>й,. Р>а) (4 ) и!)й4 Ц т)айн 4 — ! ''' 24 — 2 (А — 42, Е) Р>й ' ) — Р4,") = Р4>'+,')Р<."), ,<а),(!.-ц, <рецР>й:.ц 4 4 4 — 1 (15) а полипом ы р>42) (Г) — соотношениями: (4 4 ) Р4>;-.ц (г) Р<а> (4) р>!а+!>Р>а> (г) Р44а>(Г) — Р4>аоЦ(1) =",""ЦР',"',Ц(Г) ° (16) коэффициенты р(еа> и а>й> в свою очередь удовлетворяют соот- ношениям: а(424 Ц+ р(га"-и+1, = а4! >, +- р!")+ Га а(аз Ц 42+о = а(а>ргй> (17) Р4-! Эти соотношения выводятся посредством сравнения трехчленных соотношений, связывающих векторы Р(">, Р>а>, Р!">, которые полу!Е1' 4 ' 4 — 1' чаются двумя способами из двухчленных соотношений, точно так же, как это делалось выше.
Соотношения (17) позволяют последовательно вычислять коэффициенты р>аоо и афе') в порядке р<"+Ц, а>ае Ц, р!" 'Ц, а>ай'),..., р>а,н, ! "! О . ! ' ! 2 е-! а'„"','>, р>й — ','>, как только числа предыдущей строки уже вычислены. Вычислительными формулами (схема деления и вычитания со сдвигом) являются р'."Ай=а!"+)1-+р® — а!""'> — 1 +та (1=0, 1, ..., л — 1) а! )р>а> а(24Ц=— ,4 . (А+Ц ! — 1 При этом нужно считать, 'что ао'>=а(й) =В.
33 зее. 914. д. к Феддеее е в. н. Феддееее Легко устанавливается, что векторы р>а> связаны рекуррентными соотношениями: 5!4 итвглционные методы для ввшиния полной пвовлемы [гл ч(п а(й) д(йь1) <а+ и Р<-1 д(й)д(й+и 1 — 1 <19) Дла вывода этой фоРмУлы положим 1=1йь1 в пеРвом из соотношений 116). Тогда (й) ее ъ а(й) (й) ~Г ч ат) д(РЬ1) ) Р1 ( йь)) 1-1Р1 1 й 1) 1-1 1 (У),г, а<й)-<й),г, а<й)а(йь-Ц ' Рь-11 й-~1) Р( 11 й+1) 1 1-1 Теорема 77.2.
Если весовые полиномы уй 1() и начальные векторы Хь и 'г'ь выбраны так, что !) все Ь, ~ О, 2) последовательность 1й сходится к конечному пределу с. 3) при некоторой нумерации собственных значений !)ч — т)) ))ч — е() ... ) )),„— 1(, то последовательности р<") сходятся к пределам )чь( — т, а последовательности а<й) сходятся к нулю. Доказательство. Заметим прежде всего, что, при выполнении условий теоремы, ч чь)ч при != 1, ..., и — 1. Равенство же т=)ч, не исключено.
Выведем асимптотические формулы для рй+1). Для этого оценим прежде всего определитель Ь(<й). Пусть Х,=с,и,+ ... +с„<У„ У~= д,1',+ ... +б„~'„, где 01, ..., 0„— собственные векторы матрицы А, принадлежащие собственным значениям )ч, ..., ), занумерованным согласно условию 3) теоремы. Соответственно, Ъ'1, ..., !г„собственные векторы матрицы А'. Тогда т',ю=д,~й(Л,))',+ ... +д„ай!),))4, где Ь(= сФ((!Уо (г(). Начальная строка составляется из коэффициентов двучленных формул биортогонального алгорнфма, которые могут быть вычислены непосредственно или найдены прн помощи коэффициентов трехчленных формул.
Если считать, что все ~й = О, то формулы (13) в точности совпадут с формулами схемы (;)!Э, выведенными выше для положительно-определенной матрицы А. Для дальнейшего окажется полезной следующая явная формула для коэффипиента р(1). именно ф 771 515 алговием делания и вычитания Следовательно, Еб р„(Л ) Л ... 'Еб р (Л )Л Еб,у„(Л,) Л",, ... Еб, у„(Л,) Л',' Еб,~ра ().а) Ебв'Рь (Ла) )и Едарь(Л ) Л', ' Едзуь(Ла)Лв . Ебз~ь(Лв)Лз — б,~,(Л,) б,р„(Л,) ... б„р„(Л„)- Лфрь (Л,) Лглгрь (Ла) ... Л„б„~рь (Л„) М Ьр (Л„) Ч ЧЛ(Л ) Л„' Ч„9„(Л„) Л, ... Л','-' 1 Ле ° ° Лг 1 Ль...ЛВ' Воспользовавшись известной теоремой об определителе произведения двух прямоугольных матриц, получим Л, Лг-' з 4"= '~', б,~у„(Л,)... б„~р„(Л„) 1 Л ...).'' а ° ° ° тг «,(и ( ...
<зг Нетрудно видеть, что при достаточно большом й ~ р„(Л,)1>~~ь(Л,)~> ... >! р,(Л„)~ и более того, 11ш ' = О. т, (л,.) т„(л,,) Действительно, т„(Л;) (Л» — Г,) ... (Л,— Гь) ти (Л,.) " „, т„(лг ',) (л,, — г,) ... (л,, — гь) = т„(л. ' ) И, $1вь,;1 1 Выберем Ае настолько большим, чтобы прн г > йе г, ~<! л, ° )+ Лг — т где е малое число, такое, что ~, ~' +е = и ( 1., Здесь все суммы распространены на з=-1, 2, ..., п. йй Матрицу, находящуюся под знаком определителя Ь) ~, можно представить как произведение следующих двух прямоугольных матриц: 516 нтвгационныв мвтоды для гвшвнии полной пвовлимы [гл. чщ Тогда при рг -+ со.
Поэтому преобладающим слагаемым в Д~ будет то, в котором (а) а1= 1. а1=2, ..., г;=Р. Следующим по величине будет то, в котором а1=1, ге=2, ..., г( 1=1' — 1, а(=1+1. Следовательно, л,,л,'' ! Л(...л(' Д„' =Ь,, Ь( а(Л1)... Ра(Л() (а) !+О 'а("( ) (20) Эта формула верна для 1=1, 2, . должны считать До — — 1, при 1=л верна ., а — 1. При Р=О мы точная формула л, ЛГ-' ' Д( =Ь .. Ь 9а(Л) ° ° ° та(Л ) (а) (21) 1 ) ~4 Далее, д[а -11) д(а) л ...л( 1 ! О Ча(-1( '+!) 1 Л Л' ь, ... ь,р,,(л,)... та,(лг) [~-~о[ "(' ))] ь, ...
ь,т„(л) ... т,(л() Л( ... Л( 1+0 (Л() ) =(л, — р,)... (л, — р„„) 1+ О ~ "" (+" ) 1 (л() ) ч для р ( и — 1 величины (+' и ае( ~' имеют одинаковые порядки иалости, ибо г„„(л(,,) т„(л„) (л„,— р„,,) р,(л„) лг„-. та„(л() р,(л() (л, — г„) р,(л() л, — -.
При 1=я — 1 порядок малости л может быть выше почав (л ). та+~(л -) р,(л„) рядка ", если т = Л„. 'ра( ч-1) ' 517 й тт) йлгорием делания я вычитания Поэтому при 1 ( и†1 верна формула д(йей) . 1 (), — '„=(Л,— Р„,) ... ()ч — Р„,)~1-(-О~ ' (+' ~ . д(й) (22) Для ) = и верна точная формула д(й+1) — "„, =(л,— рй„)... (л„ д( (23) Отсюда получаем асимптотическне формулы для р(й+'). Именно, при Р=О. 1, ..., л — 2 д(й+й) д(й-~1) (й- 1) (+) . ( л(й) ' д(й) (Л,— („,) ... (Л„,— Рй„) 1+О(( р р„ (л, ,) л ( тй(Л(„) ) (Л) — Елей) ... (Л( — (йч.й) ~ 1+ 0 )' т,(л(„) 1 тй(л() / =Р ьл)[~ч-О[ — )-ьО [ +'.)).
(24) Для р(й",) асимптотическая формула имеет более простой вид ,!';"=р.— ь„~[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}
