Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 80
Текст из файла (страница 80)
Теорема 74,3,') Если в методе постоянного множителя и О ( р 1, то 1нп —" = У,, )пп р (га) =- ), 12 М вЂ” гн [12 [ — 2 Доказательство. Имеем (а = (Л( — р)) а, СУ(+ (Лг — ра) аа Уг+ ... + (˄— па) а„СУ„ (а) (а) (а) причем (12, 12) =(Лг — ра)го~2 ) +(), — ра)2 а(2 ) +... +(˄— оа)га„) ч'- О. так как г)~ 2. Имеем далее (Ха, са) = О = (Л( — )ьа) аг '.+ (Л, — р.а) аьа -[- ... +() — ра) а„ (В) 2 (а) 2 (а) 2 Отсюда, поделив на аг, после перехода к пределу получим, на осно(ва ванин предыдущей леммы, Лг — Ра (В)2 (го 2 аг -+ Л, — Л,. аг 2) Хестннс н Карую [1[.
н О ( — < 1, если ( < 72 Следовательно, начиная с некоторого ьг места, 9 74) опведеление наивольшего совственного значения 493 Но <Л, — нв),1 "1 и, следовательно, 1 1Л,— Л,) иа л(ю На основании 9 13 (стр. 118) заключаем, что последовательность $ь стремится по направлению к 57,. Далее, р 6„) = р ( 5" 1 ) - р (иа) =- Л,. В качестве примера проведем описанный процесс для матрицы Здесь точными значениями являются )я=0.48, Лт=0.24, Л,=0.12, Л,=006, 57,=(1, О, 1, 1)', ЕУ,=(0, — 1, — 1, 1)'. Для применения метода постоянного множителя можно взять 7 =. 1. Имеем — О. О.
0.23999989 Мы видим, что при 7е —.--43 второе собственное значение определяется с точностью до 1 ° 10 . Собственный вектор, ему принадлежащий, определяется значительно хуже. Совсем иную картину мы имеем в методе наискорейшего спуска. Здесь последовательность |е не является сходящейся. Более того, справедлива следующая теорема, 0.22 0.02 0.12 О.! 4 0.02 0.14 0.04 — 0.06 0.12 0.04 0.28 0.08 0.14 — 0.06 0.08 0.26 .000237 10 .235470 1О .235923 10 ?35087 10 [гл. чп 494 ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ Теорема 74.4. Градиенты соседних приближений метода наискорейшего спуска ортогональны. Доказательство.
Имеем сь = АХА — р„Х„ 6ь с(= АХьл( >льл(Хьл( = А (ХА+ ив[а) — рь. ((Хь+ гль) Следовательно, ((>с(( (ь)=(АХА, "ь)+иь(А(ь, ьь) —,с>,,(Х>, (ь) — иьрь - (-'.ь Еь)= =[(+или((ь) — и р „,[((ь, (~)=О, так как Р(1сссьл) — - и (сь> Иль( — и (Есс> й 75. Решение частичной проблемы собственных значений с помощь>о полиномов Ланцоша Установленное в теореме 74.3 свойство последовзтельности градиентов приближений суженного метода постоянного множителя допускает обобщение, позволяю(цее нахолить несколько собственных значений и принадлежащих им собственных векторов с заранее фиксированным числом т собстяенных значений, подлежащих определению.
Введем следу(ощее обозначение. Через р(">, р(ь>, ..., р(„",> „обозначим первые т векторов Ланцоща, построенные нз начального вектора Х„, через р(ь>(г), р(ь>(г), ..., р(">,(() соответствующие им полиномы. Ясно, что р(,"> =Х, р(">=( . >с с .ь. Теорема 7б.1. Пусть Х, =р(ь> = а(ь>(7, + а(,">Па+... -+ а(ь>(7„ последовательность еекторое е подпространстее, катянутолс на нормированные собственные векторы (с'(, ((г ..., (7с симметричной матрицы А, соответствующие собстеенны.н значениям (ь> (ь> (>с> )с ) >г ) ) >т.
Пусть =ь -+ О, — „)-+ О, ..., — "-+О при й-ьоо. 1 ас '( Тогда, если р(">=р(У>(А)р(л> (-й вектор Ланиоша, то соответствую(иие полиномы р(ь>(г) сходятся к полиному р((() =(( — ~,)... ... (( — >.,), а векторы р(ь> сходятся по направлению к вектору(7,, Доказательство. Будем доказывать теорему по индукции. Для 1=0 утверждение справедливо, ибо (ь> а("> "л 495 Реп<ение частичной пРОБлемы Допустим, что утверждение теоремы справедливо для индексов О, 1, ..., ( — 1 и в этом предположении докажем его для индекса 1. Имеем р<а>= а<а)р(а)(Л )(У ) < п(."> р(а>(Л ) (г., +...+а(а)р(а>(Л ) У = =от»грт (Ли+1)!гЬ<, 01+... +Ьги 01+())»1+ (а) <а) Г <а) <а) <а) (а» (а> (а> (а> +Ь;»М,<У»2+ ...
+Ьну У„)= ау гр. (Л) 1)Ъ'~, где Ь(а> л. р, (л,) (а> (а) <1„.> <а> Л1 1 Р) (Л1+ 1) — Ьгу 01+ ° ., +.Ь11' ( т+ ()т, 1+ Ьт»2 )У<+2+ ... + Ьгт Уг (»> (а> <а> <а> (а) В силу индукционного предположения 1) ра (() - » р (Г) при „Г С Е, 2) Ъ')<")-» (Г,+1 при,/( Г. Докажем то же самое для у=(.
Имеем Р, () (, )Р () Р Р (), где (Арр ) р) ) (А <г(а> <г(а> ) (л (а),(а) ) л(а),<оо л ~р(а> )г< ) ) В силу индукционного предположения а)-+ ' =), (а (А(Г(, (Гг) — ((гя !ГО Далее, (! 1-2 < 1-2) (сг(-1 ГГ(-1) Р(1->1 (л() Р( — 1 (лд р,,(л,) р(,(л() ' <('> л л. ~В) 12) а — -+О в силу условия теоремы. Следовательно, ~~ 1-+О при (а) (-1 Й-+ со и потому (Г) - (Г Л,) р( , (Г) — р, (Г) ггадиинтныв итвгацнонные методы (гл. >и( Для доказательства второго утверждения нам надо установить, что коэффициенты дм -+ О при а-ьсо, если а Ф(+1.
(а) Для з)~1+2 это устанав.чивается очень просто. Именно, рн а(а> Р(а>(Л > бо( — (а> а(эг Р1 (Л(э1> ~(а > (а> (а> а .~~ (> =с( ( (з(1), и где а( > Р( >(Л,) ,(Ю 1 " 1 1 а( > ~ Р( >(Л ) ~ а(„>~ Р( (2) (а) В силу условия теоремы =„— «О прн з (Е. Докажем, что с(",> а(а> стремятся при а — + со к конечным пределам. Тем самым будет установлено, что Ьт( -+О при з (1.
(а> Для доказательства используем ортогональность вектора р(а> к векторам р,'а), ..., Р)а),. Имеем О = (р(а>, р(а>) = а(а)эр(а>(Л )р(а>(Л )+... ... + а,(>'Р11>(>,() РЮ (Л()+ а~а~,'РЮ (Л„,) р~~ (Л( „,) + +а(а>э (а>(Л )р(а>(Л )+ а(а)ар(а)(Л)РОО(Л) Поделим это равенство на аыо'р(Р»Л ) и перенесем члены, ( ('(--т) начиная с (+1-го, в другую часть равейства. Получим с(а)р(а)(),)+с(а>р(а>(Л)+ ... + с(Ур(а>() ) — (К(а>, (ч) га(а> а (а) Л. Р(а> Л ,(( > = р(а) Л ы Ра Л (э>1 (а) (а>,Л (э( Р( ( (е(> а(а) 1э Р(а) (Л ) Р(а) (Л ) (а> / (а> л а„.,/ Р, (Л(+т) (а) В силу условия теоремы (' -+О при з)~1+2 и, в силу >же (а) доказанного, р(а>()э)-+р((Л,), р(а>(Л,,)-+р,.(Л(„д)=(Л,,— Л,)... ... (Л„, — )ч> чь О. Труднее устанавливаются предельные соотношения Ьм -+ О, если (а> з (1.
Для доказательства положим 5 751 497 ввшвнив частичной пвовлвмы Система равенств (3) при э=О, ...,1 — 1 может рассматриваться как система линейных уравнений относительно коэффициентов с(".Л ..,, с(з) 11 й При стремлении и к бесконечности коэффициенты этой системы р(в) (Л,) стремятся к конечным пределам р, (Л ). В свою очередь, к конечным пределам стремятся н свободные члены системы. Именно, (л) А» -+ — р»(Л)»1), нбо р(, ) (11) р»ю(Л,) р»(Л,) р» (Лу) р, (Л,,,) р,(Л„,) (в) (а) +-+О при /~1+1. (1) Рассмотрим прелельную систему с„рз(Л1)-+ са(1)з()1)-+ +сире(Л() = — р (Ли ) с;р,(Л )+ с;р, ()а)+ ...
-+ сир,(Л() = — р,(Л;,) с„р; (Л ) + с,р;, (А») -( — ... -1- сир,, (Л ) = — р(, ()ч,,). Эта система имеет треугольную матрицу, ибо р1(Л)) =р»(Л,) = =ра()1)=... =р, 1()ч 1)=О, иее определительд=ре(Л1)р1(),,)... ...р( 1(Л)) не равен нулю.
В силу теоремы 13.1 ее решение ссь ..., сй будет предельным для сИ), .... с(Ы. 11' '''' й Итак, мы установили, что последовательность с(".), „с(1) имеет конечные пределы. Следовательно, (з) („) („) а».-1 Ьм =ей „-+О при з (1. а» ) Таким образом 1,(ю»Ц а потому векторы р(ь) сходятся к У по направлению. Теорема полностью доказана. Заметим, что в процессе доказзтельстза теоремы мы получили оценку быстроты сходимости. Именно ) в(к) л~" (в), »» ~а) 498 [гл. Тн ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ В лемме $74 было доказано, что последовательные приближения Хь, вычисленные по методу постоянного множителя при О ( Т ( 1 (, удовлетворяют условиям теоремы 75.1.
Тем самым доказано, что если Хъьг =ХА — Т(ь 6ь= АА >А(ХА)Хь О < т < д> ! и!">, ..., Р>а>, векторы Ланцоша, построенные исходя из ргь> = Х, то р~~>, ..., р>,",>, сходятся по направлению к первым (в порядке убывания собственных значений) собственным векторам, лежащим в подпространстве, порожденном начальным вектором Хю Отметим, что при вычислении векторов р!А>, ..., ргь>,, исходя из вектора Хь, приходится производить вычитание близких величин, так что указанный процесс мало пригоден для практических вычислений.
Мы это уже видели на последнем примере $74. В заключение заметим, что условиям теоремы 78.1 удовлетворяет и степенной метод. Позтому, если Хь.г1=АХА (а=О, 1...) )>!А>, ..., р!А>, векторы Ланцоша, построенные исходя из р!еь>=ХА, то ргь>, ..., р!А>, сходятся по направлению к соответствующим собственным векторам, лежащим в подпространстве, порожденном начальным вектором Хе. й 76, а-шаговый метод наискорейшего спуска По сути дела, первое приближение Х, любого градиентного метода лежит в подпространстве Р, натянутом на векторы Хз и АХ,, и о> в методе наискорейшего спуска оно осуществляет максимизацию функционала р(Х) в этол> подпространстве.
Второе приближение Ха любого градиентного метода лежит в подпространстве Р' >, натянутом !з> на Хю АХЕ, А'Хы третье в подпространстве Ри>, натянутом' на Хю АХ,, А'Хе, АтХ, и т. д. Однако уже второе приближение, даже по методу наискорейшего спуска, не будет максимизировать р(Х) в подпространстве ж >. Естественно поставить вопрос об отыскании а> вектора, осуществляющего максимизацию функционала р(Х) в подпространстве Рыь'>, натянутом на векторы Хз, АХЕ, ..., А'Хе, при заранее фиксированном числе г. Решение поставленной задачи позволит построить итерационный процесс для определения алгебраически наибольшего собственного значения симметричной матрицы и принадлежащего ему собственного вектора — так называемый з-ш >говый метод наискорейшего спуска, который заключается в следующем.
Берется начальное приближение Х,, строится вектор Х,, осуществляющий максимизацию р(Х) в подпространстве Р,, натянутом (а а>) на векторы Ха, АХа, ...„А"Ха, затем ищется вектор Ха, осуществляющий максимизацию р(Х) в подпространстве Р,, натянутом (аа>) на векторы Х,, АХ,, ..., АХ, и т. д. Прежде чем выяснить сходимость процесса, покажем, как осуществляется решение задачи о максимизации р(Х) в подпространстве Р(; ™. В этом подпРостРанстве выбиРаетсЯ какой-либо базис (га, ~',,..., 1га. Пусть Х любой вектор подпространства и пусть Х= Ьа('о+Ь>1'>+ + ЬаЪ'а причем не все Ь( равны нулю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
