Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 88
Текст из файла (страница 88)
Эта операция при выполнении на быстродействующих машинах требует значительной ватраты машинного времени. Более удобными оказываются циклические якобиевы процессы и, в частности, циклические процессы с преградами. 544 итаглцнонныв матоды лля.вешания полной пговлвмы [гл. шп Таблица )ТП1. Т Опрвделение собственного вектора методом Якоби ш — 0,00003556 — 0.02812808 0.03048475 0.02809253 0.02447059 — 0.03964253 — 0.41314164 0 42857618 0.51139013 0.70710678 О. 99953524 0.99950533 0.99970055 6.9392!394 ОЛ!ООИШ 0,90360564 9.85934868 О 70710678 — О.ЕЮОгбаа — О.ЕЮО24 ОО О.ОООО4743 0.03967421 0.039 67421 — 0.13986866 — 0.10581153 — О.
71884900 1 — О 00291765 — 0.00291765 ( — 0.0%91736 — О. ОО 291736 0.40999603 0.38743715 0.38743715 0.38743715 -0.536969 1 О. 99960433 0.99960433 0.99881670 0.91079448 0,91079448 0.91079448 0.56920890 — 0.791834 — 0.02812608 — 0.02812808 — О.О23жбО3 — 0.02512806 — 0,09359923 — 0.09569928 0.133128 нли по столбцам сверху вниз и слева направо (1, 2), '(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)..., ..., ( 1, л), (2, л), ..., (л — 1, л). 3. Циклические процессы с преградами.') Промежуточное положение между классическим методом Якоби и циклическим ааннмает циклический метод с преградами. Недостатком циклического метода является то обстоятельство.
что по ходу процесса приходится анну- .1) Грегори [3[. 9) П о п, Т о м и к н н с [1[. 2. Циклические якобиевы процессы. ') При проведении циклического процесса выбирается определенная нумерация пар (П у) н аннулирование внеднагональных элементов происходит по циклам, в течение каждого из которых аннулируются по очереди элементы а!4 в порялке выбранной нумерации пар индексов. Элементарный шаг процесса ничем не отличается от элементарного шага классического метода Якоби, так что рабочими формулами остаются формулы, выведенные выше, Как указано в статье Грегори [3[, сходимость метода установлена в неопубликованной еше работе Форсайта и Хенричн.
После того, как внедиагональные элементы станут достаточно малыми, сходимость процесса становится квадратичной, в чем легко убедиться теми же рассуждениями, которые были приведены для метода Якоби. Наиболее естественной нумерацией пар является нумерация по строкам слева направо и сверху вниз, именно (1, 2), (1, 3), ..., (1, л), (2, 3), ..., (2, л), ..., (п — 1, л) э 81! НРоцессы, ОснОВАнные ИА НРименении ВРАщений 545 лирозать малые внедиагональные элементы, хотя в матрице еще присутствуют большие.
Этот недостаток устраняется введением „преград". Именно, вводится монотонно убывающая к нулю последовательность чисел а,, а, ..., и при последовательном аннулировании внедиагональных элементов пропускаются те шаги, при которых приходилось бы аннулировать элементы, меньшие чем а,. После того, как все внедиагональные элементы станут по модулю не больше ао „преграда" сдвигается — число а, заменяется на число а, и т. д. Легко устанавливается, что процесс с преградами сходится, Лействительно, „преградае а, будет перейдена не более чеч через >9(А))а' элементарных шагов, так как за каждый шаг до преодо >ения преграды а, число Ге(А) уменьшается не менее чем на а'.
>' Аналогично, через конечное число шагов будут преодолеваться последующие преграды а„аз и т. д. Так как а„— «О, то через достаточно большое число элементарных шагов все внедиагональные элементы матрицы станут сколь угодно малыми. Это и доказывает сходимость процесса. Как и прежде, при попарно различных собственных значениях, сходимость процесса будет, начиная с некоторого места, квадрзтичной.
4. Процессы Якоби с рацнональныии формулами. Элене»тарный шзг процессов этой группы отличается от элементарного шага процессов с полной релаксацией Выбором угла поворота вращения. Именно, 2»>у вместо формулы 1»299= берется формула „20 — а, а а>1 (К вЂ”.= —, ==а 2 2 (ан — агу) если !, ~ < ">> 2 — 1, ОП!4. .
'2(ан — ауу) если ~ ' !)~)>'2 — !. 2(ан - - ау>е) е О=-- При малых углах Π— О, только О всегда немного больше 69. Нетрудно проверить, что ! О, ( С ! 0 ) С ! 299 ), так что указанный выбор угла вращения обеспечивает верхнюю релаксацию. Для вычисления чисел с и з получаем рациональные формулы 1 — »в 2» с =- —,— „, з.=-- -- — „(а ( )> 2 — 1) 1-~-»е * 1+»е с = —, з = — —, (а)~ )Г2 — 1).
У"2 35 Звв. 974. Д. К. Фвллеев в В. и. Феллеевв Само преобразование вращения следует осуществлять по формулам 0 5!. Выбор пар может осу>цествляться либо циклически, либо по индексам наибольшего по модулю внедиагонального элемента. В литературе описаны и некоторые другие якобиевы процессы. 546 итвглционныв методы для гашения полной пгозлвмы [гл. чш Описанные методы почти без изменения переносятся на диагонализацию эрмитовых матриц. Вместо элементарных вращений приходится производить трансформации унитарными матрицами вида с, сз (унитарные вращения).
Условия унитарности [с !'+! !'=! ! а !'-+ ! с, !' = 1 — с,з, + е,с = О позволяют выбирать числа с,, ао са и е, в виде е, =яп Ое"', с, = соя Ое '. с, = сов Ое'", ее = яп Ое ", Здесь О, а, р, [, 3 — вещественные числа, причем а — р — у -+ О = 0 (тоб 2к). .Мы не будем здесь приводить соответствующих рабочих формул. В случае произвольной матрицы преобразованиями подобия посредством вращений привести матрицу к диагональной форме уже невозможно. Однако верна следующая теорема И. Шура. Для любой кочплексной матрицы А существует унитарная матрица У такая, что г' АУ есть верхняя треугольная матрица. Для доказательства рассмотрим матрицу А как матрицу оператора в некотором ортонормальном базисе и перейдем к новому ортонормальному базису, включающему один из собственных векторои ф 82) спвктглльный лнллиз послвдовлтвльных итвглций 54Т матрицы.
В этом новом базисе оператору будет соответствоваты матрица Ь„... Ьги О Ьча Ьви Применяя то же рассуждение к матрице (и†1)-го порядка Ь22 . ° ° Ьач ча ич Ь ... Ь получим Х, сж с,з ... с,„ )ч саз ' ' ' сан О О с„... сз„ О О с„, ... сии Продолжая процесс далее. принимая во внимание, что произведение унитарных матриц есть унитарная матрица, придем к требуемому результату. Теорема Шура дает основание предполагать, что, подбирая подходящим образом последовательность унитарных матриц вращений, можно добиться преобразованиями подобия приведения данной матрицы к треугольному виду.
Два таких процесса описаны в работах Гринштадта [1) и Лоткина 141. В первой из них предлагается аннулировать поочередно за счет подходящих унитарных вращений поддиагональные элементы Доказательство сходимости процесса отсутствует, дается только указание на экспериментальную проверку метода. Во второй работе вращения подбираются так, чтобы сумма квадратов модулей поддиагональных элементов уменьшалась на каждом шагу. Процесс оказывается довольно сложным — на каждом шагу приходится решать вспомогательное кубическое уравнение. Мы не будем описывать подробности этих процессов. й 82. Решение полной проблемы собственных значений при помощи спектрального анализа последовательных итераций Этот метод, который принадлежит Ланцошу 171, заключаетсн в следующем.
Пусть матрица А симметрична '), н ее собственные. г) Рассуждения остаются в силе и в случае, если матрица А не. симметрична, но имеет попарно различные вещественные собственные значения 35* 348 итвялционпыв мвтоды для гашения полной пвоалвмы [гл. чш значения заключены в интервале (т, Л4), Вводится матрица В= "4+т( — ', А), (;) собственные значения рн ..., р„которой принадлежат уже промежутку ( — 1, !). В случае положительно-определенной матрицы А в качестве т можно взять, например, нуль.
Вычислим последовательность векторов Хо, Х, = ВХ,, Ха = 2ВХо, — Хь, (й = 2, 3...,, Х), Пусть Хо = (у~+ 1 (2) где Е/н ..., (/„собственные векторы матрицы В, а следовательно, и матрицы Л. Тогда Х, = Т, (р,) и, + ... + Т„(. „) и„ (3) где Ть (1) = сов и агссов г. Положим оо = сов О„при О ( 8; ( и. Ясно, =совйагссовр;=совйОн так что Хо=совlгй,У,+ ...
+совй8,.0„. Т„(й,) = (4) Отсюда и любая компонента вектора Хы которую мы обозначим через хы будет иметь вид ха=а,совйй,+ ... +а„совИ„, (б) Пусть хо пт 2ят у = — +х,сов — +ха сов — + 2 Ф Ф (М вЂ” 1) пт Фкт ... +х „сов +х сов —, (т=О...,, М). (7) где ао ..., а„некоторые определенные, но заранее неизвестные нам числа (равные выбранным компонентам векторов Ун ..., У„), Ланцош предлагает определять углы Он ..., 0„(а следовательно, и собственные значения рн ..., р,), подвергая гармоническому анализу последовательность хо, х,, ..., х (для контроля следует взять также и вторую последовательность, состоящую из других компот мент итераций Хь). При этом попутно определяются и амплитуды а,, ..., а„, которые являются выбранными компонентами собственных векторов Ун ..., У„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
