Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 50
Текст из файла (страница 50)
Можно действовать-и иначе, возвращая сдвиг обратно после каждого шага ДК-алгоритма (это,правда, в несколько другом контексте, демонстрируется формулами (6.3,18)). Тогда все матрицы А» будут иметь те же самые собственные значения. Предыдущее обсужпение основывалось на предположении вещественности как матрицы А, так и ее минимального собственного значения. Предположим теперь что А по-прежнему вещественна, но что собственное значение Х„невешественно.
Тогда использование в качестве параметров сдвига величин а„н, которые остаются вещественными, не представляется осо- (~) бенно удачным, поскольку при этом не может аппроксимироваться чисто мнимая часть Хн. Вспомним, однако,что собственные значения расположенных в правом нижнем углу 2 Х 2-подматриц матриц А а, генерируемых ДЛ- алгоритмом без сдвигов, сходятся к паре собственных значений Лн и Х„ = л „. Поэтому вполне естественно использовать собственные значения этих 2 Х2-подматрнц в качестве параметров сдвига. Рассмотрим первый шаг такого алгоритма в, применении к матрице А,, Пусть й, и Ар =А, — соб. ственные значения 2 Х 2-подматрицы, составляющей правый нижний угол матрицы А1. Используя схему с возвратом сдвигов, получаем формулы А, — /с,1= 0,Я,, А2 =А,Д, +~с,1, Аа — й~1= 0Фэ, АЭ ~102 ~2~.
(6.3.18) Так как 1с, и ~с, невещественны, то матрицы А,, А~, (г„Д~, Я1 и Я1 будут, вообще говоря, невещественными. Отсюда следует, что эти шаги 0Я-алго- ритма необходимо выполнять в комплексной арифметике. Интересно,од- нако, что матрица Аэ оказывается вещественной (см. упражнение 6.3.10). Хотя мы здесь не будем вдаваться в детали, тем не менее имеется возмож- ность осуществлять переход от А1 к Аз в полностью вещественной арифме- тике. Эта процедура называется ЯК-алгоритмом с двойным сдвигом. Стратегию двойного сдвига с использованием собственных значений правой нижней 2 Х 2-подматриць| можно рекомендовать и в случае вещест- венных собственных значений. При таком выборе сдвигов, как и при сдвиге на элемент (п,н), скорость сходимости обычно оказывается по крайней мере квадратичной.
После того как собственные значения найдены, остается вычислить соб- ственные векторы. Это может быть сделано по аналогии с предыдущим разделом, но используя в данном случае матрицу Хессенберга. Действил тельно, пусть А — матрица Хессенберга, полученная из исходной матрицы А, 207 л и Л вЂ” приближенное собственное значение.
Решим теперь систему линейных уравнений (А — и)х = с], (6.3.19) где вектор правой части й выбран некоторым подходящим образом. Условия, при которых решение (6.3.19) будет приемлемым приближением к собственному вектору, можно получить, как и в предыдущем разделе, разлагая й по собственным векторам матрицы А. Вычислив вектор х, мы еще должны преобразовать его в собственный вектор самой матрицы А. л Если А =РАР, то, как и в предыдущем разделе, вектор у =Р х будет.
приближенным собственным вектором матрицы А. Мы теперь кратко просуммируем основные моменты обсуждения ДК- алгоритма. Чтобы метод был эффективен, нужно сначала привести исходную матрицу к форме Хессенберга и затем применить к полученной матрице основной (Ж-алгоритм, включающий сдвиги.
Собственные значения определяются последовательно одно за другим (или по два — в случае комплексно-сопряженной пары), причем для нахождения следующих собственных значений итерируется матрица меньшего размера. При надлежащей реализации Д1с-алгоритм является в настоящее время лучшим универсальным методом для несимметричных матриц, которые целиком умещаются в оперативной памяти ЭВМ. Мы здесь не имели возможности остановиться на всех деталях, необходимых для такой реализации, а ограничились только изложением основных моментов алгоритма. В дополнительных замечаниях к этому разделу приведены ссыпки на литературу для дальнейшего чтения.
ф?="",гприт,":. составляет также привлекательную альтернативу методу последовательностей Штурма в случае симметричных трехдиагональных матриц, особенно если требуется найти все собственные значения. Для трехдиагональных матриц алгоритм значительно упрощается, а так как симметричные матрицы имеют только вещественные собственные значения, то использование сдвигов не приводит к возникновению невещественных чисел. Кроме того, в симметричном случае скорость сходимости обычно оказывается выше.
Дополнительные замечеиия и ссылки 6.3 ЕЯ-алгоритм был предложен Рутнсхаузером в 1958 г. 11Я-алгоритм был опубликован независимо Френсисом [90] и Кублановской [34] Впоследствии Уилкинсон продолжил разработку и анализ этих алгоритмов; исключительно ботатый материал, включающий доказательство теорем 6.3.1 и 6.3.2, содержится в его книге [84]. Дальнейшее обсуждение ДЯ-алгоритма есть в [78]; в этой книге, в частности, рассматривается версия с неявными сдвигами, а также связь ДЯ-алгоритма с излагаемыми в следующем разделе степенным методом, методом обратных степеней и методом отношений Рзлея.
По-видимому, наилучший имеющийся в настоящее время набор программ содержится в пекете Еирасх (см. [9, 73] ). Вариантом ЕЛ-алгоритме для симметричных положительно определенных матриц т является ЕЕ -алгоритм, использующий разложение Холецкого. Основная схема алгоритме состоит в разложении А = А, в произведение Е,Е,, вычислении А, = 1.,1,, т разложении А, в произведение Е,Е, и т.д. Т л существует интересная связь между 1.6 - и ДЯ-алгоритмами. если А1 н Аз (1 = 1, 2,...) — матрицы, генерируемые соответственно ьб - и ОЯ-алгоритмами, то Аь+! = Т = Аза+!.
Распространение ДЯ-алгоритма на обобщенную проблему собственных значений было сделано Моулером и Стыоартом [48] (см. также [87]). Этот метод известен как Д2-алгоритм. Аналогичное распространение ЕЯ-алгоритма — 7.2-алгоритм принадлежит Кауфману [27]. УПРАЖНЕНИЯ б. 3 6.3.1. Пусть В и С вЂ” матрицы размера и х и. Покажите, что матрицы ВС н СВ подобны ') . 6.3.2.
Покажите, что матрица А=[ ] не допускает ЕЯ-разложения, и, следовательно, к ней не применим ЕЯ-алгоритм. Покажите, что хотя матрица ,4-[ ] имеет ЛЯ-разложение, матрица А, в (6.3 4) такого разложения не имеет, и, следовательно, в зтом случае нельзя использовать ЕЯ-алгоритм. 6.3.3. Проверьте, что если вектор н, определен как в (6.3.10), то матрица А (2) в (6.3.11) действительно имеет указанную там форму. 6.3.4. Покажите, что если А и  — вещественные ортогональные матрицы размера и Х и, то матрица АВ также является ортогональной. После этого покажите, что Т если каждый из векторов в,.
удовлетворяет условию иуч,. = 1, то матрица О в (6.3.13) ортогональна. 6.3.5. Выполните ДЯ-разложение матрицы 2 — 1 1 А= 2 3 1 1 — 1 2 6.3.6. Проделав подробные выкладки, убедитесь, что артогональные преобразования подобия Р, = 7 — 2взв, гДе вектоРы и(опрепелены как в разделе 6.2, приводят Т несимметричную матрицуА к форме Хессенберга (6.3.16). 6.3.7. Покажите, что если единственные отличные от нуля внедиагональные алименты матрицы Р; находятся в позициях (1+ 1, 1) и (1, 1+ 1), то произведение Р, ...Р„ является матрицей Хессенберга. 6.3.8. Покажите, что если Д вЂ” матрица Хессенберга, а Я вЂ” верхняя треугольная, то произведение ЯД есть матрица Хессенберга.
6.3.9. Пусть А — ленточная матрица. Покажите, что как 1.Я-алгоритм„так и ()Я- алгоритм сохраняют ширину ленты матрицы А. 6.3.10. Пусть А, — вещественная матрица, а х, и 1с, = )с — комплексные постоянные. Покажите, что матрица А,, определенная в (6.3.18) „вещественна. 6.4. Методы для больших разреженных матриц Метод Хаусхолдера и ДА-алгоритм, описанные в предыдущем разделе„ имеют первостепенное значение, если матрица А помещается в оперативной памяти, не является сильно разреженной, разве что ленточной, и требуется ) Приведите контрпример. — Примеч ред.
14. Дж. Ортега найти все или много собственных значений. Напротив, в случае очень больших разреженных матриц, для которых нужно определить только несколько собственных значений,, указанные методы не оказываются особенно полезными. Проблемы такого рода часто возникают как в уравнениях с частными производными, так и в других областях. Вот характерный пример такой задачи: имеется матрица размера 5000 Х 5000, в каждой строке которой содержится порядка десяти отличных от нуля элементов, и требуется найти только несколько, можетбыть,четыре илн пять, собственных значений. Для такой задачи.
предыдущие методы совершенно не подходят. Классическим методом, который иногда оказывается полезным для больших разреженных систем, хотя также страдает серьезными недостатками, является стеленной мет0д. Предположим, что собственные значения Х,,..., Х„матрицы А вещественны и удовлетворяют условию ~Х,~> ~Х,~>... > !Х„1.
При заданном векторе хр рассмотрим последовательность х(,+1 = Ах», й = О. 1,... (6.4.2) Анализ поведения последовательности векторов (хь) можно провести точно так же, как в случае демографической задачи из раздела 6.1. Предположим для простоты, что матрица А имеет п линейно независимых собственных векторов ч,,..., ч„, соответствующих собственным значениям Х,,... ..., Х„. Разложим хр по этим собственным векторам; хр =с,ч, +...
+с„г„. Пусть с ~ Ф О, тогда, как и в (6.1.20), хь с~ Л~ у~ + ст Х~ у~ + .. ° + сд Хд уд = ь ь Х~ с~%! +Сэ ч2 +... +Си чи (6.4.3) (6.4.4) откуда видно, что векторы хь стремятся по направлению к собственному вектору ч,. Модули же векторов х„будут при этом либо стремиться к нулю, если 1Л, ! < 1, либо неограниченно расти, если 1Л,! > 1. Поэтому векторы х» нуждаются в нормировке, и процедура нормировки даст нам также приближения к собственному значению Х,. Существует много способов выбора нормируюших множителей. Одна из удобных модификаций алгоритма (6.4.2) определяется формулами л х~,=Ахь 1, 1=1,2,..., л х» = хь(оь, lг = 1, 2,..., (6.4.5) л где о» вЂ” максимальная по модулю координата вектора хь. В этом случае можно показать, что о~,-+Х, и хь-+с~, при й- (6.4.6) 210 и в силу (6.4.1) все множители (Х;!Х~)" (ю'=2,..., и) стремятся к нулю при 1с .
Следовательно, Х, "х~- с,ч, лри /с-+ Последнее соотношение говорит, что последовательность (х„) сходится к некоторому вектору, пропорциональному собственному вектору ч,. Основным достоинством степенного метода является то, что векторы хъ получаются только с помощью умножения матрицы на вектор (плюс некоторая работа по вычислению нормирующих множителей); никаких преобразований самой матрицы А при этом не требуется.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
