Дж. Деммель - Вычислительная линейная алгебра, страница 39

Если р = 1, то и метод, и его анализ таковы же, как в случае степенного метода. При р > 1 имеем арап(Я,ч.1) = арап(Уч.1) = арап(АЯ;), поэтому арап(Я;) = арап(А'Яо) = врал(5Л'5 'Уо). Заметим, что 5Л'5 ~Ев = 501ая(Л'„...,Л„')5 1Яо 5-'г.. = Л'5 р (л„/л )й Поскольку ~-~-~ > 1, если у < р, и Ла < 1 при у > р, получаем л ! л Р рхр 5 — т Π— ~ (и-р) хр (Л„/Лр)' где блок гг; сходится к нулю со скоростью (Лрч.1/Лр)', а блок $'; к нулю не стремится. Действительно, если блок Ъо имеет полный ранг (это обобщение предположения из разд.

4.4.1 о том, что б1 ф 0), то и все блоки )~. имеют полный ранг. Запишем матрицу из собственных векторов так: 5 = [вы..., в„] = [5„"хР 5 ~ Р~], т. е. 5р — — [вы ..,, вр]. Тогда имеем 5Л'5 'Яо = Л„'5 [й,* ] = Л„'(5р1; + 5рИгв). Отсюда арап(Е;) = врал(5Л'5 'Яо) = арап(5р(г, + 5 Иг,) ~ арап(5„(с), т.е. подпространство арап(Я;) сходится к арап(5рЪ;) = врал(5р), а это есть инвариантное подпространство, натянутое на первые р собственных векторов. Мы получили требуемый результат. ЯК-разложение используется в методе для того, чтобы векторы, образующие базис надпространства арап(А'Яо), сохраняли линейную независимость, несмотря на наличие округлений. Заметим, что если в итерациях этого алгоритма следить лишь за первыми р столбцами матриц Ун где р < р, то они будут теми же самыми, что и при итерировании только первых р столбцов матрицы Яо, а не р столбцов, как в первом случае.

Иными словами, ортогональная итерация по существу происходит одновременно для всех значений р = 1, 2,..., р. Поэтому, если модули всех собственных значений попарно различны, то из проведенного выше анализа сходимости вытекает, что линейная оболочка первых р столбцов матрицы Я; при любом р < р сходится к арап(вв,..., и„-). 170 Глава 4. Несимметричная проблема собственных значений Итак, исследуя ортогональную итерацию, можно положить р = п и Ео = 1.

Приводимая ниже теорема показывает, что при определенных предположениях с помощью ортогональной итерации можно вычислять форму Шура матрицы А. Теорема 4.8. Пусть ортогональная итерация с р = п и Яо = 1 применяется к матрице А. Ясли все собственные значения матрицы имеют попарно различные модули и все главные подматрицы 5(1: 1, 1: у) невырозкденньц то матрицы А, = оРАгч сходятся к верхней форме Шура матрицы А, т. е.

к верхней треугольной матрице, на диагонали которой расположены собственные значения. Они упорядочены по убыванию абсолютных величин. Набросок доказательства. Предположение о невырожденности матриц Я(1: 1,1: у) для всех у обеспечивает невырожденность блока 1'о, требуемую предыдущим анализом. Геометрически это условие означает, что ни один вектор из инвариантного надпространства врал(зг,..., з,) не ортогонален к подпространству грел(еы..., е ), натянутому на первые з столбцов матрицы Ео = 1.

Заметим теперь, что Е, — квадратная ортогональная матрица, поэтому матрицы А и А, = л,'АЯ; подобны. Положим Я; = [гмлг,], где гм состоит из р столбцов. Тогда А, = л; Асг = ~ ттА т. ' 2~ м г~ га Поскольку подпространство грал(г ы) сходится к инвариантному надпространству матрицы А, врап(АЯм) сходится к тому же самому надпространству, а ЯгтгАЯм сходится к ЯгтгЯм = О. Учитывая, что сказанное справедливо для каждого р < п, заключаем, что все полдиагональные элементы матрицы А, стремятся к нулю.

Таким образом, А; сходится к верхней треугольной матрице, т.е. к форме Шура. О В действительности, нз этого анализа видно, что подматрица Яг;АЕН = т А,(р+ 1: п,1: р) должна сходиться к нулю со скоростью ~Лрч ~/Лр~'. Поэтому Лр будет предельным значением элемента (р, р) в Ан а сходимость будет происходить со скоростью шах()Л ч.г/Лр(', (Лр/Л ~)г).

Пример 4.5. Характер сходимости ортогональной итерации иллюстрируется численным экспериментом, в котором мы взяли Л = сйак(1, 2,6,30) и случайную матрицу Я (с числом обусловленности 20), сформировали матрицу А = 5 Л Я ' и провели с ней 19 итераций метода при р = 4. Рис. 4.3 и 4.4 показывают, как сходится алгоритм. На рис. 4.3 даны графики ошибок )А;(р, р) — Лр! в вычисляемых собственных значениях (сплошные линии) и приближений шах((Лрч.~/Лр(', )Лр/Лр г!') (пунктирные линии). В полулогарифмической шкале графики обеих величин по существу представляют собой прямые линии с одинаковым угловым коэффициентом. Это означает, что сами величины суть функции вида у = с т', где с и т — некоторые константы, причем т (значение углового коэффициента на графиках) для них одно и то же.

Именно таким было предсказание нашего анализа. Аналогично, на рис. 4.4 приведены графики для йА;(р + 1: п,1: р)сг (сплошные линии) и приближений )Л ~~/Лр)' (пунктирные линии). Эти гра- 4.4. Алгоритмы для несимметричной проблемы собственных значений 171 Сходимость Х(2)= 6 Сходимость Х(1)= 30 10 10 10 10 10 10 10 10 10-10 5 10 15 20 0 5 10 16 20 Сходимость Х(3) 2 Сходимость й(4)= 1 10 10 10 1О 1О 1О 10 10 10 6 10 15 20 10 О 5 10 16 20 Рис.

4.3. Сходимость диагональных элементов в ортогональной итерации. Сходимость формм Шура (2:4, 1:1) 10 10 10 10 10 10 10 10 1а 10 10 0 6 10 16 20 Сходимость формы Шура (4:4, 1:3) 0 10 10 10 Б 10 1Б 20 Рис. 4.4. Сходимость к форме Шура в ортогональной итерации. 10 0 10 0 10 О 10 10 Сходимость формы Шура (3:4, 1:2) 10 1О!е 0 5 10 16 20 172 Глава 4. Несимметричная проблема собственных значений фики тоже хорошо согласуются.

Приведем для сопоставления матрицы Ао и Аш.. — 4.0123 — 5.8157 — 5.8415 — 10.558 10 — 70.844 14.984 1.8143 —.55754 2.0000 —.25894 4.9533 10 г 1.0000 10 'г 10-23 10-29 Этот пример и аналогичные ему могут быть решены с помощью Ма11аЬ- программы, помещенной в НОМЕРАСЕ/Мас1аЬ/цг1гег.ш. О Пример 4.6. Чтобы понять роль предположения о невырожденности матриц Я(1: у, 1: у) в теореме 4.8, рассмотрим диагональную матрицу А, собственные значения которой не упорядочены на диагонали по убыванию модулей. Тогда ортогональная итерация дает Я; = Йаб(х1) (диагональная матрица с диагональными элементами х1) и А; = А для всех 2, так что собственные значения не переупорядочиваются по убыванию модулей.

Покажем теперь, почему необходимо предположение о том, что собственные значения имеют различные модули. Предположим, что А — ортогональная матрица, тогда все собственные значения имеют один н тот же модуль 1. Снова матрицы А; по существу не меняются в алгоритме. (Строки и столбцы могут умножаться на — 1.) 4.4.4. (4К-итерация Наша следующая цель — так модифицировать ортогональную итерацию, чтобы она допускала сдвиги и обращение матрицы, как в разд. 4.4.2. Это повысит эффективность метода и позволит устранить предположение о том, что модули собственных значений различны.

Оно было необходимо в теореме 4.8 для обоснования сходимости. Алгоритм 4.4. ЯК-ггтерацияг для заданной матрицьА Ао выполнять итерации 1=0 гереас Вычислить разложение А, = Я;Вг ЯЛ-разложение) А,чы — — В;Яг 1=2+1 пока метод не сойдется Поскольку А,».г — — ВЩ, = ЯТАГАН;)Я, = ЯА'АЯАз матрицы А;» г и А; ортогонально подобны. Мы утверждаем, что матрица А,, вычисляемая в ЯК-итерации, совпадает с матрицей оТАЯ», неявно вычисляемой в ортогональной итерации.

Лемма 4.3. Пусть А; — матрица, вычисляемая в алгоритме 4.4. Тогда А, = ЛТАЯн где Яг — матрица, вычисляемая в ортогональной итерации (алгориптм ».з), исходя из оо = 7. Таким образом, если все собственные значенил имеют различные модули, то матрицы А; сходятсл к форме Шура. А=А =[ А, = [ 3.5488 2.3595 8.9953 1.9227 30.000 6.

7607 1.5452 7.3360 15.593 8.5775 24.526 14.596 27.599 21.483 55.667 39.717 — 32.557 6.0000 1.1086 10 9 3.3769 10 4.4. Алгоритмы дли несимметричной проблемы собственных значений 173 Доказательство. Применим рассуждение по индукции. Пусть А; = Я~АУ,. Согласно алгоритму 4.3, АЯ, = У;+1Вг ьы где Л;~.1 и Вьы — соответственно ортогональная и верхнетреугольная матрицы. Но тогда ЕТАЯ; = У~(Я,+~В,+1) есть произведение ортогональной матрицы Ч = Я~Я;~1 и верхнетреугольной матРицы В = Вс.ы — — Ят АЯ,.

Это пРоизведение должно быть ЯК- разложением матрицы А; = ЯВ, поскольку ЯВ-разложение определено единственным образом (с точностью до умножения столбцов в Я и строк в В на — 1). Теперь имеем ят ~Ах, 1хт ~х ~ратх ) В 1гт~ Именно таким образом цВ-итерация отображает А; в Аььы Следовательно, Ятч,АЯ;+1 = А,+ы что и требовалось. Многочисленные примеры, иллюстрирующие сходимость Я11-итерации, можно активировать с помощью Ма11аЬ-программы, о которой говорится в вопросе 4.15.

Из предыдущего анализа мы знаем, что скорость сходимости определяется отношениями собственных значений. Для ускорения сходимости применим сдвиги и обращение. Алгоритм 4.5. ЯВ-итерация со сдвигом: длл заданной матрицы Ао выполнять итерации 1=О тереа1 Выбрать сдвиг о; вблизи некоторого собственного значения матрицы А Вычислить разложение А; — о;1 = ЯгВ< ЩВ-разложение) А;~1 = В;ч, + о;1 1=1+1 пока метод не сойдется Лемма 4.4. Матрицы А; и Аг~ы ортогонально подобньь Доказательство.