Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 89
Текст из файла (страница 89)
После того как собственные значения опре,делены, остальные компоненты собственных векторов определяются, как мы увидим ниже, без проведения полного гармонического ана,лиза последовательности соответствующих компонент векторов хо, х,,...,х. Рассмотрим сначала случай, когда х» — — а совий, и=О, ..., М. $82] спектральный анализ последовательных итераций 549 Последовательность уа, уо .... у есть „трансформация Фурье" последовательности ха, х,, ..., х,. Нетрудно проверить, что у = ( — 1) — з!и М0 з!п 0 ж а 1 соз — ' — сов 0 гу Исследуем поведение у,а в зависимости от изменения гл прп фиксированном О. Допустимсначала, что 0=-в р, й (О) где р — целое число. В этом случае знаменатель выражения (8) обращается в нуль прц лг =р и сйп М0 = О. Следовательно, ум= О при гл + р и, как не- а1т' трудно подсчитать, ур= —,.
Таким образом, среди значений у,„ встретится единственное отличное от нуля значение ур Аналогично, если хл=агсоз0,-+ ....+а„соз0„ (!О) (1 1) где р; — целые числа, то среди значений у„, встретится г отличных от нуля значений у = —, ..., ур — — — ",—, а все остальные значения будут нулевыми. Это позволит определить как углы О,, ..., 0„(по номерам рп ..., р„), так и амплитуды а,, ..., а, (по значениям ур,, ..., ур ). у Вернемся теперь к иссле- т дованию случая 1 1 х~ =асозЫ ! ! ч ! в предположении, что 0 ~ —, р, Л' при целом р.
Пусть ° Р Р'г 0 = у(р+ т) О(т<1. (12) Рис. 13. В этом случае соз — ' — соз0 ) О при О ( лгх-а н — соз0 < О при р-+1 (а (М. Поэтому значения у будут иметь чередующиеся знаки прн лг изменяющемся от О до р. Знаки ур и ур„ совпалут, а затем снова будут чередоваться. Наибольшие абсолютные значения у будут при лг=р и гл=р+1 и при удалении лг от р будут убывать (см. рис.
13). Такое поведение последовательности ум дает возможность определить число р, а следовательно, в силу (13), и значение 0 с точностью до —. М' 550 итеглционные методы для вешения полной пвовлемы [гл. ч(п (14) (15) 0»= — „Ъ+т!), б «-;1.
При т, близком к р», слагаемое у(») будет, вообше говоря, преобладать над остальными. В частности, у ун) и у уи) Р» р» р»'-! г»е! Поэтому ур и ур +, будут одного знака, и это позволит опреде- Р» в»+! лить рн а следовательно, и 8» с точностью до — ' Однако при уточнении значения 0» укаэанным выше приемом, влияние других слагаемых у(У), у' Ф (, может быть еше слишком значительным и им нельзя пренебрегать. Ланцош предлагает, наряду с числами уж, ввести в рассмотрение числа гв» Уп» вЂ” ! 2уж+ Ут+! (16) Ясно, что г,„=г(„',)+ ... +г(»)+ ... +г(").
(17) Величина г(»), при удалении т от рн убывает значительно быстрее, чем у(»), так что пики для гж выражены отчетливее, чем для у т' Подсчитаем приближенно значение г('') при т, близких к рн Для этого предварительно заменим точную формулу для у(») более удобной приближенной формулой, справедливой при т, близких к рн Положим т =р»+ д, где») небольшое целое число. Имеем =( — 1)» —,э!пМ 5(п0.
Ув» = 2 )((» сов ' »+ ~ — сов 0» Ф ж( — 1)в» ч — »( — 1)п» гйп лт в)п8. 2 ' ' / (р»+»))л в)п 0» ~0» — р» — ') д» =( — » —. ч а»Ф в(п лт» кл»» — В' (18) После определения р можно получить уточненное значение для 0 из легко проверяемой формулы ур+ ! сов у (р + 1) + у р сов у р сов 0 Ув+! Ув При переходе к обшему случаю х„=а(совй0»+ ... +а„созл8, картинз будет несколько более сложной.
В этом случае у у(!)+ У( )+ + у(в) где у') = ( — 1)'" — гйп М0» гйп 8; в» !» 1 сов — — — сов О» М 9 82) спектрлльный лнллиз последовлтельных итерлций И! Соответственно 0«( — 1)яа«)«Г МП чт« / 1 2 1 т .,—,+ „-,+.,—,— ) ! — 1)та«М в«п ет« 1 (!9) в (⫠— д) (т« — «) + 1) (т« — «) — 1) 1 откуда следует, что гы«убывает, как — при возрастании ва !«)~в Это дает основание считать а«л«в«п ат«1 ЫЫа т«(т«+ 1) (т« — 1) а«!««в!и чт« 1 а «а р«+ р,+1 а (., !) т, (т« — 2) Отсюда е р«т« — 2 и+1 и, следовательно, ар 2 — — « р«.~- 1 (20) е ар Точность этого приближенного равенства будет удовлетворительной, если углы 0«не очень близки друг к другу.
Определив ть находим амплитуды а«по формуле а; —, . т«(т«+1)(т« — 1)гр,. (21) Однако амплитуды а; можно вычислять так же и по формулам 2е ',у в«а 1.~ "1( ~) (ур«+ ур«««! (22) Последняя формула, несколько менее точная, чем предыдущая, требует знания лишь двух соседних значений у . Ею разумно пользоваться при нахождении всех компонент собственного вектора У« после того, как соответствующее собственное значение и«вычислено. Именно, нужно вычислить векторы ур, ур+«при 1=1, ..., г р«р+ и применять формулу (22) ко всем их компонентам. При практическом проведении метода в качестве М следует брать достаточно большие числа, во всяком случае во много раз (10,20) 552 нтевлциониыя методы для гашения полной пеоялемы [гл. щм превосходящие порядок матрицы. Лля удобства вычислений следует также брать число И кратным !80.
Метод требует очень большого числа операций (несколько миллионов умножений при Ж=1080п и его осуществление возможно лишь на быстродействующих счетных устройствах. В настоящее время он был применен лишь для матриц невысокого порядка. В работе Ланцоша рассматривается вопрос о влиянии на ход процесса пары близких собственных значений и собственных значений, близких по модулю. ГЛАВА 1Х УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ Настоящая глава посвящена изложению теории и описанию вычислительных схем, так называемых универсальных алгорифи ов, в применении к задаче решения системы линейных уравнений АХ= гт илн, в подготовленном виде, Х=ВХ+6.
Под универсальным алгорифмом мы подразумеваем итерационный процесс, вообще говоря, не стационарный, осуществляемый по формулам вида ХР ~н ЛЧЮ+д<а1(д)[р ЛХ,а1~ (нли в случае подготовленной системы по формулам Х" ы =Хрп+у(а)(В) [ВХ'"1+ Π— Хоай), в котором последовательность полнпомов л (1) (или у (О) строится раз навсегда для обширного класса матриц с заданным расположением собственных значений, например, для класса симметричных матриц, все собственные значения которых расположены в известном промежутке. Характерной особенностью универсальных алгорифмов является то, что быстрота их сходимостн не зависит от порядка матрицы, а определяется лишь ее обусловленностью.
Простейшим универсальным алгорнфмом является алгорифм. в котором л1 ~(Г)=/г= сопз1. Такой алгорнфм есть не что иное, как процесс последовательных приближений, примененный к системе АХ=те, подготовленной к виду Х= (Š— )гА) Х+ /гР. Основным принципом построения универсальных алгорифмов является идея „подавления компонент". В следующем параграфе мы ее поясним в простейшем случае. 554 (гл. гх УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ 5 83. Обц(ая идея подавления компонент Пусть АХ= гч система линейных уравнений, причем известно, что все собственные значения матрицы А вещественны, положительны и различны.
Пусть далее Х некоторый исходный вектор и Х' = Х+ а (А) 1à — АХ1, где а(1) — некоторый полипом (может быть, нулевой степени). Как мы видели в гл. РП, последовательные приближения прн применении градиентных итерационных процессов в случае положительно-определенной матрицы А определяются по формуле (1), причем полинам а(С) может меняться от шага к шагу. При этом в рассмотренных выше градиентных методах коэффициенты полиномов существенно зависят как от матрицы А, так и от начального приближения, так что описанные в гл. ЧП методы не являются универсальными в смысле данного выше определения. Для построения универсальных алгорифмов исследуем формулу (1) со следующей точки зрения. Обозначим через У и Г соответствующие векторы ошибок для приближений Х и Х'.
Тогда 'г" = (Š— АЬ (А)) У = Р (А) г", а (г) = 1 — г)1 (1). где (2) Пусть Л,, ..., Л„попарно различные собственные значения матрицы А и (Уп ..., У„соответствующие им собственные векторы. Пусть 1' = а,(У, + ... + а„(/„. Тогда 1" = а,а ().,) (/, + ... +. а„д (Л„) с1„. Таким образом, при переходе от приближения Х к приближению Х' йомпоненты вектора ошибки в разложении по собственным векторам матрицы А умножаются, соответственно, на значения а(Л,), ..., У(Л„), которые естественно называть и нож и гелям и за ту ханна.
Переход от вектора Х к вектору Л" можно считать удачным, если один нли несколько множителей а.(Л,), ..., Р (Л„) очень малы, а остальные не слишком велики. „Подавив' таким образом одну или несколько компонент вектора ошибки, можно перейти к следующему шагу процесса, распорядившись им так, чтобы в нем подавлялись другие компоненты. В выборе полинома а(1) для одного шага процесса имеется широкий произвол.
Единственным условием, связывающим выбор а(Г), является требование а(0) = 1. Идеальным выбором полинома у(Г) для данной матрицы А является такой, при котором а(Л,) = ... — Е» ) =О. ибо при таком выборе ~ 83) овщля идея подлвлвния компонент 555 уже один шаг процесса приводит к точному решению. По существу к этому мы приходили в результате применения метода сопряженных градиентов. Выясним теперь критерии, которыми следует руководствоваться при выборе универсального полинома я(~), исходя из естественного предположения о том, что мы ничего не знаем о расположении собственных значений матрицы А, кроме промежутка (О. М), в котором они содержатся. Пусть на рнс.
14 изображен график п(Г). Рнс. !4. Тогда множителями затухания д(Л,), ..., д(Л„) будут ординаты графика с вбсциссами ), ..., Л„. Ясно, что затухание будет наиболее эффективным в окрестности корней полинома сг(Г), мало эффективным в окрестности точек. где п(Г) близко к + 1, и вместо затухания будет возрастание компонент в точках, где (д(()! больше 1. Так, на рис. 14 затухание сильно для собственных значений, близких к точкам а и б, а для собственных значений нз промежутка (с, д) затухание совсем не имеет места. Таким образом, на каждом шагу процесса желательно подобрать полипом 8 (г) так, чтобы он возможно теснее примыкал к оси абсцисс и чтобы ~ д(Г) ! нигде в промежутке (О, М) не превышал единицы. Ясно, что при этом наибольшую трудность будет представлять подавление компонент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
