Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 98
Текст из файла (страница 98)
8, —— , —— 2(У2 — ) '. то (З) (8 + У 8 )о ()г2 + ,) ° Далее, д„(0) = 1. Положим 1 — ВГоо (Г) аао-г(Г) и найдем приближение Х„= Хо+ Ьао-г (А) (г' — АХо) Тогда У'.„= Хо — Ха, = Уо — И„, (А) А Уо = лто (А) 1'о. Следовательно, компоненты вектора У.„в разложении по собствен- ным векторам умножаются на множители яа„()ч).
Но '8' ()ч)! <т (з) 2(У'2 1) ' Итак, используя 2а итераций начального вектора, мы получили для оо ов погрешности оценку порядка (уг2 — 1) ж (0.4142), в то время как метод конформного отображения с использованием такого же числа итераций дает быстроту сходимости порядка 0~'ж (0.6558) 5 98! б09 РЕШЕНИЕ ЧАСТИЧНОЙ ПРОВЛЕМЫ 9 98. Применение идеи подавления компонент к решению частичной проблемы собственных значений Степенной метод для определения собственного вектора, принадлежащего наибольшему по модулю собственному значению, основан на тол4, что последовательность вектоРов А"Уа, пРи пРоизвольном начальном векторе Уа.
сходится по направлению к указанному собственному вектору. Действительно, компоненты собственных век~оРов (Уп ...,(У„ в разложении начального вектора У,=с,(У,+ ... +сии„ в результате л-кратного применения итерации матрицей А получают а а д мном<ители Л,..... )„,, среди которых Л, преобладает над остальными. Если нормировать процесс так, чтобы коэффициент ирн (14 оставлять равным единице, то остальные компоненты „подавляются" стремящимися к нулю множителями (Л вЂ” а~, ..., (А — а).
Эта идея „подавления" компонент может быть обобщена следующим образом. Пусть известно, что все собственные значения матрицы А, кроме одного Лн подлежащего определению, лежат на некотором ограниченном множестве т, дополнение к которому Ь есть связная область плоскости комплексной переменной г. Пусть е„(1) =1а+ ... Иоанном 14-й степени, наименее уклоняющийся от нуля на множестве й такой, что его корни, в свою очередь, лежат на множестве д. 1 Построим вектор . ТА(А) У .
Будем предполагать, что Уа еа (АД имеет ненулевую 1-ю компоненту в разложении по собственным векторам. Ясно, что 1-я компонента построенного вектора будет ирена(Л ) жней, а остальные компоненты приобретут множителей -"=1- (1 Ф 1). ., (Лг) Модули этих „множителей подавления" удовлетворяют неравенству Здесь т„= шах(тл(1)(. Известно' ), что аЕЕ !!ш т„" = е ( 4) ( 1, 4' (еа(14)( где 0(1) есть функция Грина для области Ь. Поэтому последовательность вектоРов та(А) У, т,(А) У, ...
Сходитса по напРавлению к собственному вектору, принадлежащему собственному вначению Лч 4) См. цитированную на стр. 590 книгу Г. М. Голузина, гл. ЧП. 39 зан. 974. д. к. Феддееа а в. н, Фаддеева 610 [гл. гх униавгсальные алгогиамы -л[п(х) -е] с быстротой е ' , где е сколь угодно малое число. После определения собственного векторз собственное значение Л; определяется без труда. 9 99. Применение конформного отображения к решвнию частичной проблемы собственных значений Степенной метод может быть интерпретирован также следующим образом.
Рассмотрим вектор «'(ш) =(Š— твА) ' г',. Его компоненты являются аналитическими функциями от комплексной переменной тв, 1 1 имеющими полюса в точках —,..., —, где [Л,[) [Ла!)~... лг лв ... ) [Л„/ — собственные значения матрицы А. Наименьшим по мо-, дулю полюсом будет число, обра~ное к наибольшему по модулю собственноъгу значению. Разложим вектор г'(нг) в ряд по степеням ш 1'(ш)=(Š— шА) ' Уо= Уо+шАУо+юзАаУа+ (1) 1 Радиус сходимости этого рядз будет, очевидно, равен'--- и на ~л,[ его круге сходимости будет существовать единственный простой 1 полюс —. Компоненты вектора г'(ш) будут аналитическими функлг' 1 циями, имеющими, вообще говоря, простой полюс — на границе л,, сходимости ряда (1). Для любой такой компоненты у(ш) имеем у(тв)= уа+уЛ+ уз '+ ° (2) Здесь у„есть выбранная компонента вектора А");.
Предельная формула Л,=!нп У"а' (3) а.~ уа может быть истолкована как результзт применения теоремы Квнига о коэффициентах разложения функции, имеющей единственный простой полюс на границе круга сходимости. Оценка быстроты сходнмости процесса (порядка ~-(, где Ла л,~ ' следующее по модулю собственное значение матрицы А) также следует из теоремы Кенига.
Такое рассмотрение степенного метода позволяет обобщить его в следующем направлении. Пусть и(ш) = —: — с — с,ш — сагв — ... с г а есть мероморфная в единичном круге функция, и(0)=со, «.(я)=лн 0([0! (1, причем при [ш [([а(, тв + О, а(гв) не принимает значений, равных собственным значениям матрицы А. Рассмотрим вектор (А — и(мг)Е) ' Уш Согласно формуле (б) $97 (А — и(Ф)Е) Уо=шИо (А) )о+юг(А)[ош+4(А)1ошз+ ° ° .[ $ 981 611 Решение частичной пРОБлемы где г(;(1) некоторые полиномы степени д Любая компонента вектора (А — и(ш)Е) ' будет мероморфна в единичном круге и регулярна в круге ~п>! <!0), кроме точки и>= 0, в которой она, вообще го- воря, будет иметь простой полюс, Следовательно, по теореме Канига отношения выбранных компо- нент векторов >1ь,>(А) Уа и»л(А) Уе будут стремиться к 9, а сами векторы будут сходиться по направлению к собственному вектору, принадле>кащему собственному значению )ч.
Собственное значение найдется как и(8). Быстрота сходимости процесса будет иметь по- 0 ж рядок —,1, где ~ 9ь ~ )~ 1, если внутри единичного круга нет проз'1 ' образов собственнык знзчений, кроме 9. Если же в единичном круге имеются также прообразы собственных значений матрицы А, то 0г есть наименьший из них по модулю. Лопустим теперь, что относительно собственных значений мат- рицы А известно, что все онн, кроме одного, подлежащего опре- делению, лежат на ограниченном замкнутом множестве Х, дополне- ние к которому Ь есть односвязная область.
В этом случзе в ка- честве функции и (ю) следует взять функцию, осуществляющую конформное отображение единичного круга на область Ь. По сообра- жениям, изложенным в 9 95, такой выбор функции будет наивыгод- нейшим в смысле быстроты сходимости полученного процесса. Прн проведении вычислений можно пользоваться вспомогатель- ными таблицами для коэффициентов последовзтельных полиномов г(а(1). Векторы дь(А) У„можно также строить по рекуррентным со- отношениям. Отметим также, что так как векторы Б>„(А) У, сходятся по на- правлени>о к собственному вектору матрицы А, принадлежащему определяемому собственному значению Х;, то последнее можно на- ходить как отношение компонент векторов А>1а(А) Уз и Ф„(А) У'е, (а не как образ О).
Впервые использование конформного отображения для нахождения собственных значений было предложено В. Н. Кублановской (1), (2), которая вместо функции и(ш) рассматривала функцию г(ш) = 1 = —, отображающую единичный круг на область Ь, полученную и (и>)' 1 из области Ь отображением посредством г= —. В этих работах иси следуется функция (Š— гА) >= — и(А — иЕ) полюса которой совпадают с полюсами рассмотренной выше функции А — иЕ. В работе (2) приведены таблицы коэффициентов соответствующих полиномов для ряда облзстей й. ЗАКЛЮЧЕНИЕ Значительное число ме~одов, рассмотренных нами в настоящей книге, далеко не исчерпывает всего многообразия приемов, предложенных для численного решения основных задач линейной алгебры.
Так, нами совершенно опушены методы „Монте-Карло", обоснование которых имеет более теоретико-вероятностный, чем алгебраический характер. Из многочисленных схем исключения рассмотрены лишь немногие нзиболее употребительные, описаны далеко не все итерационные процессы. Почти не рассматривалнсь схемы, приспособленные для решения задач частного вида, имеющих узкую область применения. Наконец, в книге не отражены приемы, опубликованные в самое последнее время. И хотя уже рассмотренный материал дает основание поставить вопрос о том, какие из описанных методов лолжны быть рекоменлованы для практических расчетов предпочтительнее перел другими, на этот вопрос трудно и даже невозможно дать определенный ответ, так как в различных конкретных условиях к методам должны предьявляться рззные требования.
Важнейшим из критериев оценки качества численного метода является его надежность, т. е. способность перенести в решение задачи почти всю информацию, солержащуюся в ее условии. Олнако кроме критерия належности имеются и другие, достаточно существенные. Эго — простота вычислительной схемы. Далее, и и нимзльность числа вычислительных операций; минимальная загрузка памяти лля машин с программным управлением или к о и п а к т н о с т ь з а п и с и при пользовании настольными машинами.
Часто важной оказывается возможность использования индивидуальных особенностей задачи, облегчающих ее решение ~преобладание диагональных элементов матрицы, наличие большего числа нулевых элементов и т. д.). Наконец, иногда важна приспособленность метода к серийному решению однотипных задач. Каждый заслуживающий внимания численный метод должен в той нли иной мере удовлетворять всем указанным требованиям. Но в различных конкретных условиях удельный вес каждого требования может быть различным. Даже такое, казалось бы, необходимое требование, как надежность, может отступать на задний план, например, при решении большой серии однотипных задач, не требующих значительной ~очности результата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
