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

Л„). Тогда ]Щг ]]5 ~]]г ) шахг1/]уехг]. Если положить Я = [хы... х ], то ]Щг.]]Я г]]г < п шахг1/]уехг], т. е. число обусловленности такой матрицы Я не более чем в и раз превышает минимальное возможное значение. Доказательство этого утверждения можно найти в [69]. 4,4. Алгоритмы для несимметричной проблемы собственных значений 165 В главе 4 руководства для пользователей ЬАРАСК'а дан обзор чисел обусловленности для спектральных задач; в него включены, в частности, собственные векторы, инвариантные надпространства и собственные значения, соответствующие указанному инвариантному подпространству; см. также [161, 237].

Алгоритмы, вычисляющие эти числа обусловленности, реализованы ВАРАСК-подпрограммами аттила и вхтиеп; они могут быть активированы и вызовом программ-драйверов вяеечх и вяеевх. 4.4. Алгоритмы для несимметричной проблемы собственных значений Мы придем к нашему окончательному алгоритму, а именно хессенбергову С4К- алгоритму со сдвигами, отправляясь от более простых методов. Для простоты изложения, будем считать, что матрица А вещественна. Нашим первым и простейшим алгоритмом будет степенной метод (разд.

4.4.1). Он способен находить лишь собственное значение матрицы А, имеющее наибольший модуль, и соответствующий собственный вектор. Чтобы определить другие собственные значения и собственные векторы, степенной метод применяется к матрице (А — а1) ' для некоторого сдвига и. Этот алгоритм называется обратной итерацией (рвзд.

4.4.2); заметим, что собственным значением с наибольшим модулем матрицы (А — в1) 1 является число 1/(Л, — а), где Л, — собственное значение матрицы А, ближайшее к в. Поэтому, выбирая и, мы можем управлять тем, какие собственные значения будут вычисляться. Другое улучшение степенного метода позволит нам одновременно вычислять целое инвариантное подпространство, а не только отдельный собственный вектор; соответствующий алгоритм называется ортогональной итерацией (разд. 4.4.3).

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

(В разделе 4.4.7 показано, как упрощается верхняя форма Хессенберга для симметричной проблемы собственных значений и при вычислении БНП.) 4.4.1. Степенной метод Алгоритм 4.1. Степенной метод: длл заданного вектора хв выполнить ите- рации 1=0 гереа1 у;ь1 = Ах; 166 Глава 4. Несимметричная проблема собственных значений х,+г = уеч.г/~]уны]]г (приближенпый собственный вектор) Лц.~ — — хг+гйхньг (приближеннве собственное значение) т г=г+1 пока .метод не сойдется Применим этот алгоритм вначале к очень простому случаю, когда А = сйай(ЛН..., Л„), причем ]Лг] > ]Лг] » .

]Л„]. В этом случае собственными векторами будут столбцы ег единичной матрицы. Заметим, что вектор х; может быть записан и как х; = А'хв/~]А'хв]]г, так как множители 1/]~уг+г]]г лишь масштабируют хвы к единичной длине, но не меняют его направления. Имеем бл] сгЛ' сг ьг 12 (лг) А'хв — = А' 4,(л )* с„Л'„ А; = 1ЯЛЯ ') 1ЯЛЯ ~) = ЯЛ'Я ', 4 рвз так как все пары Я ~ . Я можно удалить из произведения.

Окончательно полу- чаем 6 сг ег (ла)г =с Л',й где сделано предположение ~д ~ О. Поскольку все дроби Л /Лг меньше 1 по абсолютной величине, вектор А'хв становится все более параллелен вектору ем а потому вектор х, = А'хв/~]Агхв]~г все более и более приближается к хеы т. е. к собственному вектору, соответствующему старшему собственному значению Лг. Скорость сходимости зависит от того, насколько малы отношения )Лг/Лг ) > > ]Л„/Лг]: чем они меныпе, тем сходимость быстрее. Поскольку векторы х; сходятся к хеы числа Л; = хг Ах, сходятся к старшему собственному значению л. В исследовании сходимости степенного метода было сделано несколько предположений, и прежде всего, о том, что матрица А диагоцальная. Переходя к более общему случаю, будем считать, что А = ЗЛЯ ' — днагонвлизуемая матрица, причем Л = 61ай(Лы..., Л„) и собственные значения занумерованы так, что ]Л1] > ]Лг] » ° )Л„].

Обозначив через з; соответствующие нормиРованные 1]]вг]]г = 1) собственные вектоРы, положим Я = [зг,..., в„] 1в пРедыдущем анализе мы имели Я = 1). Это позволяет написать хв = Я1Я ~хв) = ЯЯН..., с„]т). Из равенства А = ЗЛЯ ' следует, что 4.4. Алгоритмы длн несимметричной проблемы собственных значений 167 4.4.2. Обратная итерация Мы преодолеем только что указанные недостатки, применяя степенной метод не к А, а к матрице (А — о1) ', где число и называется сдвигом.

Это позволит нам получить сходимость не к Лд, а к собственному значению, ближайшему к и. Такой метод называется обратной итерацией, или обращенным степенным методом. Алгоритм 4.2. Обратная итераддияд для заданного вектора хо выполнять итерации д=О гереад уыьд = (А оГ) хд хдед — — удч.д/)(уд+д 'бз Лд+д = хд+ Ахд~ьд т д=д+1 пока метод не сойдется (приближенный собственный вектор) (приближенное собственное значение) Для анализа сходимости отметим, что из А = ЯЛ5 ' следует А — о1 = Я(Л вЂ” о1)Я ', откуда (А — а1) ' = Я(Л вЂ” о1) дЯ '. Таким образом, матрица (А — аХ) ' имеет те же собственные векторы вд, что и А, а соответствующие собственные значения равны ЯЛ вЂ” о1) ')" = (Л вЂ” о) '. Те же рассуждения, что и выше, показывают, что х; должен сходиться к собственному вектору для собственного значения с наибольшим модулем.

Более подробно, предположим, что число )Ль — а! меньше всех прочих (Лд — о~, тогда собственным значением с наибольшим модулем для матрицы (А — оХ) д будет число (Ль — о) '. Как Как и прежде, вектор в квадратных скобках сходится к ед, поэтому век гор А*хо становится все более параллелен вектору Бед — — вд, т. е. собственному вектору для Лд. Следовательно, Лд = хд Ахд сходится к вд Авд — — гд Лдгд — — Лд. т т т Небольшим изъяном метода является предположение (д ~ О, т.е. вектор хо не должен принадлежать инвариантному надпространству градд(вг,..., г„). Это предположение с очень большой вероятностью выполняется при случайном выборе хо. Крупными же недостатками следует считать: сходимость только к собственному значению с наибольшим модулем и соответствующему собственному вектору; зависимость скорости этой сходимости от величины ~Лг/Лд~, которая может быть близка к 1, что влечет за собой очень медленную сходимость.

В действительности, если для вещественной матрицы А собственное значение с наибольшим модулем является комплексным, то имеется пара сопряженных комплексных собственных значений Лд и Лг с таким модулем: )Лд! = (Лг!. В этом случае проведенный выше анализ не работает вовсе. В предельной ситуации ортогональной матрицы все собственные значения имеют один и тот же модуль 1. С помощью программы, помещенной на НОМЕРАОЕ/Маг)аЬ/родчегр!оаш, можно получить графическое представление сходимости степенного метода.

168 Глава 4. Несимметричная проблема собственных значений и выше, введем запись хо = Яф,...,6„] и предположим, что сь ~ О. Тогда 6 сг 8,(Л, — о)- б„(˄— о) (А — о1) 'хо = (Я(Л вЂ” о1) 'Я )Я Ь. (Ль:а) =ЫЛЛ вЂ” и) гЯ Еа (Л~ -а) 4.4.3. Ортогональная итерация Еще одно улучшение метода позволит нам получить одновременную сходимость к р-мерному инвариантному подпространству (где р ) 1), а не только к отдельному собственному вектору. Оно называется ортпогональной итерацией (а иногда также итерированием надпространства или одновременной итерацией). Алгоритм 4.3.

Ортогональная итерац ят пусть Во — матрица размера пхр с ортпонормированнмми столбцами. Вьтолняются итперации т=О тереа1 1;„= Агг Вычислить разложение 1; тт —— Е,.ттН1.ты используя алгоритм Хг (Сдп'-разложение) (линейн я оболочка столбцов матрицы Яг ы даетп приближенное У вектора в квадратных скобках 1 является и-й компонентой. Так как все дроби (Ль — о)/(Лт — и) меньше единицы по абсолютной величине, то этот вектор сходится к еь, а потому вектор (А — о1) *хо становится все более параллелен вектору Яел = зы т.е.

собственному вектору, ассоциированному с Лы Как и прежде, числа Л, = х~Ах, сходятся к Лы Преимущество обратной итерации по сравнению со степенным методом состоит в ее способности сходиться к любому собственному значению (тому, что ближе всех к сдвигу о). Выбирая о вблизи нужного собственного значения, можно добиться очень быстрой сходимости. Таким образом, в отличие от исходного степенного метода, здесь мы не ограничены возможной близостью других собственных значений.

Метод особенно эффективен, когда уже имеется хорошее приближение к собственному значению и требуется лишь найти соответствующий собственный вектор (такова ситуация, например, в равд. 5.3.4). Позднее мы укажем, как выбирать о, не зная собственных значений: ведь именно эти значения мы хотим вычислить прежде всего! 4.4. Алгоритмы Лля несимметричной проблемы собственных значений 169 инвариантное надпространство для А) 1=1+1 пока метод не сойдется Приведем неформальный анализ этого метода. Предположим, что [Лр~ > [Лрч.1 [.