Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 57
Текст из файла (страница 57)
Графа «скорость в мегафлопах» регистрирует абсолютную скорость программы; в графе «время/время(матричного умножения)» показано отношение времени решения спектральной задачи порядка и к времени перемножения двух квадратных матриц того же порядка.
Мы видим, что для достаточно больших матриц вычисление (только) собственных значений симметричной матрицы примерно эквивалентно по стоимости перемножению матриц. (Напротив, для несимметричной матрицы вычисление собственных значений стоило бы, по меньшей мере, в 16 раз дороже [10].) Вычисление и собственных значений, и собственных векторов обходится в три раза дороже, чем умножение матриц. 5.3. Алгоритмы для симметричной проблемы собственных значений 249 Случайные матрицы, приведенные к трехдиагональиому виду, время по сравнению с ОС=1 16 Сй 14 12 10 0 0 100 200 300 400 600 600 700 800 900 1000 пОрядОк матрицы Геометричеокое распределениесоботвенныхзначений, матрицы приведены к трехдиагональному виду, время по сравнению с СС = 1 80 82 60 ЗО 10 СС 400 600 800 700 800 900 1000 порядок матрицы 0 0 100 2!й 300 Рис.
5.4. Скорость вычисления собственных значений и собственных векторов симметричной трехдиагоиальиой матрицы по сравнению со скоростью алгоритма «разделяй-и-властвуй». 250 Глава 5. Симметричная проблема собственных значений Случайные плотные матрицы, время по оравнению с ОС = ! 3.6 0й 0.6 0 0 100 200 300 400 600 600 700 600 900 1000 порядок матрицы Геометрическое распределение собственных значений, время по сравнению с ОС =1 4 ОС ТЯО 0.6 0 0 100 200 300 400 600 600 700 600 900 1000 порядок матрицы Рис.
0.5. Скорости вычисления собственных значений и собственных векторов симметричной плотной матрицы по сравнению со скоростью алгоритма «разделяй-и- властвуйк 251 5.4. Алгоритмы вычисления сингулярного разложения Сравним теперь относительную производительность ь)Н-итерации, бисекции в комбинации с обратной итерацией и алгоритма «разделяй-и-властвуйм На рис. 5.4 и 5.5 эти методы обозначаются соответственно символами ь)й, ВЕ (от имени ЬАРАСК-программы вввебя, реализующей бисекцию) и ВС. На графиках этих рисунков по горизонтальной оси откладывается порядок матрицы, а по вертикальной — отношение времени решения задачи соответствующим методом к времени алгоритма ВС. Поэтому самому этому алгоритму соответствует горизонтальная прямая уровня 1, а кривые, помеченные символами ВЕ и ь)Рс, показывают, насколько медленнее эти методы, чем ВС. Рис.
5.4 относится к решению трехдиагональной проблемы собственных значений, тогда как рис. 5.5 дает полное время решения для исходной плотной матрицы. Верхний график на рис. 5.5 соответствует случайным симметричным матрицам. Трехдиагональные матрицы для рис. 5.4 были получены приведением плотньгх матриц рис. 5.5 к трехдиагональной форме. Случайные матрицы этого типа в среднем имеют хорошо разделенные собственные значения, поэтому обратная итерация (почти) не требует дорогостоящей переортогонализации.
В результате, ВЕ оказывается сравнимым по производительности с ВС, тогда как ь)В. значительно медленнее; для трехдиагональных матриц высокого порядка С4й проигрывал ВС по времени подчас почти в 15 раз. Для нижних графиков использовались плотные симметричные матрицы с собственными значениями 1, .5, .25,..., 5" ". Иными словами, возле нуля находится кластер из многих собственных значений, поэтому в обратной итерации приходится производить большую работу по переортогонализации.
Как следствие, для трехдиагональных матриц ВЕ уступал ВС по времени более, чем в 70 раз. С1Н также был медленнее, чем ВС, подчас в 54 раза, что объясняется тем, что, благодаря дефляции, ПС в действительности рскоряетсл при наличии большого кластера собственных значений. Разница скоростей методов ь4Н, ВЕ и ПС на рис. 5.5 менее заметна, чем на рис. 5.4, поскольку здесь в стоимость каждого метода включены расходы на приведение матрицы к трехдиагональной форме и преобразование собственных векторов трекдиагонапьной матрицы в собственные векторы исходной плотной матрицы.
Эти общие накладные расходы составляют 0(пз) операций и помечены на рисунке символом ТВЮ. Близость кривых, соответствующих ВС и ТВВ на рис. 5.5, означает, что любое дальнейшее ускорение ПС мало изменит общую скорость алгоритма для плотных матриц. 5.4. Алгоритмы вычисления сингулирного разложении В теореме 3.3 показано, что сингулярное разложение (ВЧВ) матрицы общего вида Гу тесно связано со спектральными разложениями симметричных матриц С С, СС и ~ С, 0 . Опираясь на эту связь, можно преобразовать алгоритмы предыдущего раздела в алгоритмы вычисления ВЧВ. Это преобразование, однако, выполняется не прямолинейно, поскольку дополнительная структура, которой обладает ВЧВ, часто может быть использована для повышения эффективности и точности алгоритмов (120, 80, 67).
Все алгоритмы вычисления спектрального разложения симметричной матрицы А, за исключением метода Якоби, состоят из следующих этапов; 252 Глава 5. Симметричная проблема собственных значений 1. Матрица А приводится к трехдиагональной форме Т посредством ортогональной матрицы Щ „т. е. А = Я~ТСгг1. 2. Вычисляется спектральное разложение Т = 1ггЛ9~~, где Л вЂ” диагональная матрица собственных значений, а Яг — ортогональная матрица, столбцами которой являются собственные векторы матрицы Т. 3. Разложения этапов 1 и 2 комбинируются с тем, чтобы получить разложение А = ЯЯг)Л(ЯЩг)т.
Столбцы матрицы Я = ЯЯг суть собственные векторы матрицы А. Из аналогичных этапов состоят алгоритмы вычисления БУР матрицы общего вида О (исключением снова является метод Якоби): 1. Матрица О приводится к двухдиагональной форме В с помощью ортогональных матриц У1 и Ъ'ы т. е. О = У1В11'„1. Двухдиагональность матрицы В означает, что ненулевые элементы в ней могут располагаться только на главной диагонали и первой наддяагонали. 2. Вычисляется сингулярное разложение В = УгЕЪ~~ матрицы В.
Здесь Е— диагональная матрица сингулярных чисел, а столбцами ортогональных матриц Уг и Ъг являются соответственно левые и правые сингулярные векторы 3. Разложения этапов 1 и 2 комбинируются с тем, чтобы получить разложение О = (У1Уг)Е(У1Ъ~)». Столбцы матриц У = Пзбг и Р' = Ъ~Ъг суть соответственно левые и правые сингулярные векторы матрицы О. Приведение к двухдиагональной форме выполняется алгоритмом, описанным в рззд. 4.4.7.
Из обсуждения алгоритма в указанном разделе следует, что вычисление матрицы В стоит з из+ О(пг) флопов; только эта матрица и нужна, если требуется найти лишь сингулярные числа. При необходимости вычисления и сингулярньгх векторов еще 4пз+ 0(пг) флопов затрачиваются для вычисления матриц Уг и Ъ'м Сформулируем простую лемму, показывающую, как свести вычисление 'оЪ'й двухдиагональной матрицы В к вычислению спектрального разложения симметричной трехдиагональной матрицы Т.
Лемма 5.5. Пусть  — двухдиагональная матрица порядка и с диагональными элементами аы ..., а„и наддиагональными элементами Ьы ..., Ь„ Вычисление БУР матрицы В можно свести к вычислению собственных значений и собственных векторов силсметричной трехдиагональной матрицы следующими тремя способами: О Вт 1. Пусть А = . Обозначим через Р матрицу-перестановку (еме„+неже„«.г,...,е„,ег„1 где е; есть з'-й столбец единичной матрицы порядка 2п.
Тогда Тр, — РтАР является симметричной трехдиагональной матрицей. Индекс рз есть сокращение от рет7ес1 зйи)(1е (идеальная тасовка); действительно, умножение вектора х на Р «тасует» его компоненты подобно картам в колоде. Можно показать, что в Тр, все диагональные элементы равны нулю, а наддиагональными и поддиагональн ми элементами являются числа аы Ьг, аг, Ьг, ..., Ь„ы а„. Пусть (сгнх;)— 253 ЬА. Алгоритмы вычисления сингулярного разложения собственная пара для Тр„т. е.
Т„,х; = сггх,, причем х« — нормированный вектор. Тогда сн = хог, где ог — сингулярное число матрицы В, а Рх« = ~ ~ "' 1, где и, и и; суть соответственно левый и правый (нормированные) сингулярные векторы для В. 2. Полоз«сим Тввт = ВВ . Тогда Тлвт — симметричная трехдиагональна матрииа с диагональными элементами а + Ьы аг + Ьг, ..., а„г + 6„ г г г г г г аг; наддиагональные и поддиагональпые элементы равны агбы агЬг, ..., а„Ь,, Сингулярные числа матрицы В суть квадратные корни из собственных значений матрицы Таит „а левые сингулярные векторы для В суть собственные векторы для Тивт.
3. Полоэким Тнтн = В В. Тогда Твтв — симметричн я трехдиагональная матрица с диагональными элементами аы аг + Ьы аз + Ьг, ..., а„+ г г г г г г Ьг г, наддиагональные и поддиагоналъные элементы равны а»Ьы агЬг, ..., а„16„ы Сингулярньге числа матрицы В суть квадратные корни из собственных значений матрицы Тлтв, а правые сингулярные векторы для В суть собственные векторы для Тптв.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
