Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 81
Текст из файла (страница 81)
Сопоставим вектору Хвектор Харифметического пространства йи+ ) с компонентами Ьа, Ь>, ..., Ь,. Тогда (Х, Х)= ~~ с(уЬ(Ь =(СХ, Х) г-о,;-О а (АХ, Х) = ~ г(, Ь;Ь, =(ОХ, Х), (=а,>=о (2) где Очевидно, что матрица С поло>кительно определена. Таким образом, наша задача свелась к максимизации функционала (ВХ, Х) (СХ, Л) (4) в пространстве >(("' Искомый максимум )а(а) получается как наибольший корень уравнения (Р— Сг(=0, а реализующий его вектор определяется из системы линейных однородных уравнений (Π— (а(а)С) Х=- О. Соответствующий ему вектор Х, получается затем из разложения (1). Таким образом, наша задача сводится к решению частичной обобщенной проблемы собственных значений для матрицы а+1-го порядка. Если за базис взять векторы Х,, АХ,, ..., АаХа, то Решение задачи сильно >прощается, если в подпространстве Ре( (а-Н) взять какой-либо ортогональный базис. Очень удобным для этой 32а ~ 76! а-шлговый метод наискогвйшвго спгскл 499 [гл чп 500 гглдивнтныв итвглционныв методы с; =(рн ру) с,.=О в ~ г; сн=(ро р;).
н потому (6) Лалее Нвд =(Аро р ), так что г(; =0 при [М вЂ” у[) 1; в(вв=(Арвч р;)=х;(ро р;); (7) с(гв-в = 4-вв = ~г (Рг-в Рв-в). Таким образом, [в — с(! = «о(ро Ро) — Г(Уо Ро) йг(ро Ро) Вт(Р« Ро) «в (Рь Рд Г(рв Рв) О Вв(Рп Рг) ° ° ° О ° «в(Рв Рв) Г(рв Рв) ! «о(ро Ро) — Г(ро Ро) вв (Ро Ро) (Рп Рг) «г(рг Рв) — Г(рг Рт) Рв(рм Рв)" ... «,(Р., Р,) — С(рв, Рв) ! О [ибо р;(р; и р;,) =(ро р;)! — й, О ... О О «, — Г Вв .
О О =(Ро Ро)(рв Рв) ° ° (Рв Рв) О О О = (врв„(1) (6) где ев =( — 1)'~'(ро, ро)... (р,, р,), а рв+,(с) есть (з 1-1)-й полипом Ланцоша. Итак, значение [вго1 максимума [в (Х) в подпространстве Р1«+ 1 есть наибольший корень (а+1)-го полинома Ланцоша р,в,(1). Обратимся теперь к определению вектора, реализу ющего этот максимум. Координаты Ьо, Ь,, ..., Ь, этого вектора (относительно базиса р„, р,, ..., Р,) определяются из системы линейных однородных уравнений [«о(ро Ро) р(1 (Ро Ро)! Ьо+ огв (Ро Ро) Ьв = О [вв (Ро Ро) Ьо+ [ив (Рв Рд) [в( > (Рв Рв)! Ьв+го (Рв Рв) Ьа = 0 (д) 'рв(рв о р в) Ьв в+(а — [в(о))(р„рв)Ь«= О. в) К аруш [1!. цели оказывается базис ро, р,, ..., р„ состоящий .из первых (з + 1) векторов Ланцоша '). В этом случае $76] г-шлговый метод нлискогвйшвго спускА 50! Сделав подстановку <)< = Ь',.
(Ри Рг) ' и принимая во внимание, что р, = ' -' †, получим для опреде- (Р, Рд (Р<-) Рг-д пения Ь' систему (по — р(о) ) во+ п~ = 0 й,<),',+(и,— р(о)1<);+б,,'=0 РА,+(а,— р<о)) Ь„'=О. Положим ( „<о)) Тогда Ь = <)(о) — о'. =р (р<о)) (р(о) и т ь~ о ь~ — ~р<о) и тр (р(о)~ я гр (г(о)) р (р(о)ь и т. д. Из предпоследнего уравнения получим р,~~ ( <о)) Последнее уравнение окажется удовлетворенным, так как Р.~ (В<о)) = О. Итак. Ь<='' ~ (<=О, ..., л) ( <о)1 (Рь Рд и вектор Х,, реализующий максимум.
дается формулой тсч Р (о<о)) Х,= ~~ — ' — р<. Л ) (Ро Р() <-1 (10) где векторы р<о), р<ь), ..., Р<л) суть векторы Ланцоша, построенные исходя из вектора р<ол)=Хо по рекуррентным соотношениям метода минимальных итераций; р(а) — наибольший корень полинома Ланцоша р<л), (г). Выведенные формулы позволяют придать следующую форму в-шаговому методу наискорейшего спуска. За начальное приближение берется произвольный вектор Хо.
После того как построен вектор Хю строится вектор Хло, по формуле й (ю Р< (в ) < ) алло — <Ю <) )~ Р) (11) <=о~р< ' Р< [гл. чп 502 гвадивнтныв итагациониыа мвтоды Теорема 76.7. Пусть последовательность векторов Хо, Х,, Х„, ... строится так, что Х„реализует максимум (АХ, Х) (Х, Х) в подпространстее, натянутом на векторы Хь АХ„,, ..., АХ„,. Тогда отношения ' сходятся к наив (АХь, Хь) (Хю Хь) большему собстеенному значению матриць( А з инвариантном подпространстэе, порожденном зектором Хо, а векторы Х„сходятся по направлению к принадлежащему этому собственному значению собственному вектору. Доказательство. Пусть г = го размерность инвариантного подпространства, порожденного вектором Хо, >,) >и)...
) >„— собственные значения матрицы А на этом подпространстве, Уо У,...., Уг соответствующие нормированные собственные векторы. Тогда Хо=-а~ У,-[-а У + ... +-а, (.Г„. (о> (о> (о> Все коэффициенты а(( >, аз( >, ..., а( > отличны от нуля, и без нарушения (о> общности их можно считать положительными. Далее, через г„обозначим размерность инвариантного надпро- странства, порожденного вектором Хь. Так как каждый последующий вектор Хь содержится в инвариантном подпространстве, порожденном предществующим вектором Хь,, то гонг, ...
~~гь)~... Рассмотрим прежде всего вырожденный случай, когда при неко- тором )з окажется г„( з+ !. Тогда подпространство, натянутое на векторы Х„, АХ„, ..., А"Х„, само будет инвариантиым (если гь(з+ 1, то среди перечисленных векторов будут линейно-зави- (АХ, Х) симые) и вектор Хь+,, на котором реализуется максимум в этом подпространстве, окажется собственным вектором матрицы А. На следующем шаге подпространство, натянутое на векторы Хь+,, АХ„,, ..., А'Х„, будет одномерным, так что процесс стабилизи- руется.
В дальнейшем мы покажем, что так полученный собственный вектор будет пропорционален У,, и тем самым для вырожденного случая теорема будет доказана. Обратимся теперь к рассмотрению одного невырожденного шага процесса. Пусть Х„= а П,-[- аа (.(о+ ... + а„и„, (ь> (ь> (ь> р(ь>, (=О, ..., з, э+1 — векторы Ланцоща, построенные исходя из вектора Х, р((ь>(Г) — соответствующие полиномы, >ь(ь> нх наиболь- щие корни.
Как мы видели выше. >ь, „есть максимум (ь> (АХ, Х) в подпространстве, натянутом на векторы Хь, АХь, .... А'Х„, кото- рый мы раньше обоаначали через р(ь>, так что (! 2) э 761 я-шАГОВый метод ЯАискОРейшеГО спускА 503 Согласно формуле (11) (А) (А) В свою очередь, (А) — п(А)Р(А) ()ч) Ц + ... + О(А)Р(А) (), ) Ц . Следовательно, (13) Ха ы — — а, (7, + ...
+ а„(7„ (А~ю) (Аэц где (А) ( (А) т (А)(А А (А+() (А) Ът Р( 0 + тР( ~ г) (А),„(А) ( А) (АЭП (А) т Р (РА цР1 ( Г) (А) (А) (А) Г (А) ) (А) (А ) Сделаем некоторые выводы из построенных формул. Так как корни полиномов Ланцоша разделяются, мы имеем )А(") ( )А(А) ( ... ( ((А(АА)()А(А),~(Л,, так что (А(А)( и )А строго больше всех корней полиномов Р(А) (Г).
Следовательно, Ат(А) ) О. Мы предположили, что а(') ~ О. Поэтому а(') ~ О, ..., а',"+') ь О, так что инвариантное подпространство, порожденное вектором ХА~(, включает собственный вектор 1('О принадлежащий собственному значению ), Следовательно, если для ХА~( имеет место выроя(денный случай, то на следующем шаге в подпространстве, натянутом на векторы Хаен АХ„,, ... ..., А Х„,, (оно будет инварнантным!), максимум отношения 8 будет достигаться именно на собственном векторе У(.
Теперь остается рассмотреть процесс, протекающий без вырождения. Прежде всего заметим, что )А(Хз) < "(Х)) < ° ° ° ("( так что существует Вш р (ХА) = и. А-ь со Положим х,=!х,Яь(,"~и,+ ... +ь'„)и„'~. (14). Так же как при доказательстве теоремы 74.1, прежде всего докажем, что один из коэффициентов Ь~ -+ 1, а остальные коэффициенты Ь(ю-+О, 1~7. С этой целью снова рассмотрим отношение 1АА= (( м А =ьт ) 1),( — р(ха)1 + ...
+ьГ) () — р(ха)) ()б) (гл. )<!г 504 гвадиентные итвплционнь>в методы В наших обозначениях Р(1) (1 а<ь)) (Г а< ">) Р<1) (() (16) здесь а<за> =р. (ха). я<!ь>= р,(р<а>), Р<">(<) — второй полипом ланцоша. подставим в (16) г=>2(ха~,)=и<";>,. Ясно, что Р(">(>2<а>,)) О, ибо р<ь>, при з ) 1 больше обоих корней полинома р<ь>(Г). Поэтому пг<1.) ( (>2<2> о(1>) (>2(ь> о(ь))— ='(р(Х..„) — рЯ,)Ц;(Ха„) — р(Р<2))) (17> О!сюда следует, что <><">-ьО, так как первый множитель правой ча.!и неравенства (17) стремится к нулю, а второй ограничен. Из равенства (16) заключаем, что ()(">'[)ч — )2(Хь)>з-+0 при всех 1=1, 2, ..., г.
Из множителей ()ч — >2(Ха)) стРемитьсЯ к нУлю может не более чем один, все же (>< не могут стремиться к нулю, (ь) нбз,чР~(><! > =1. Поэтому р(Х„)-+), при некотором определенном у, 1=1 а все <>! при 1 + 7' стремятся к нулю и <>у -+ 1. ш) (й) 2 Таким образом, векторы Х„сходятся по направлению к У.. С .тается доказать, что ( = 1.
Если допустнть, что ) ) 1, мы получим, что (>< > а(> 1 ! — = — -+О при н-ьос. а<Ю л<Р) Но, с другой стороны, а<ье'> (а> Л)<2> ! 1 1 а<!' !> а<."> М<л> .! 1 д<(ь> 1 Покажем, что — ~ !. Действительно, м® Р<ь)(„(а> )Р(ь)(1 ) (Р Р( ) 5 761 в-шлговый мвтод нлисковвйшвго списка 505 Но )ь1Ы, = )л(Хь~,) (Лр так что Л больше всех корней (в+1)-го полииома Ланцоша при любом )г и подавно больше всех корней полиномов р1р1(Г). Так как, кроме того.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
