|
Страница 7 из 10
Сведение симметричной матрицы к трехдиагональной форме: редукции Гивенса и ХаусхолдераКак уже было сказано, оптимальная стратегия для поиска собственных значений и собственных векторов заключается в первоначальном сведении матрицы к возможно более простой форме с дальнейшем применением итерационной процедуры. Для симметричных матриц наиболее предпочтительной простейшей формой является трехдиагональная. Редукция Гивенса является модификацией метода Якоби. Вместо того, чтобы стараться все время приводить матрицу к диагональному виду, остановка в этом методе происходит, когда матрица трехдиагональна. Это позволяет процедуре завершиться за конечное число шагов в отличие от метода Якоби, требующего последовательные итерации для сходимости. Метод ГивенсаПри использовании метода Гивенса угол ротации выбирается таким, чтобы обнулить элемент, находящийся не на одном из четырех углов, т.е. не app, apq или aqq. Конкретно, матрица P23 используется для обнуления a31 (и по симметрии a13). Затем P24 используется для обнуления a41. В целом, используется последовательность P23, P24, ..., P2n; P34, ..., P3n; ...; Pn-1,nдля обнуления ak,j-1 с помощью Pjk. Метод работает, поскольку такие элементы, как a'rp и a'rq при r!=p и r!=q суть линейные комбинации старых значений arp и arq. Таким образом, если arp и arq уже нулевые, то они таковыми останутся и после ротации. Очевидно, требуется порядка n2/2 ротаций, а число умножений в алгоритме будет порядка 4n3/3, не считая тех, которые требуются для преобразования произведения трансформирующих матриц, необходимого для вычисления собственных векторов. Метод Хаусхолдера, который будет описан ниже, является таким же устойчивым, как и редукция Гивенса, но требует в 2 раза меньше операций, таким образом, метод Гивенса обычно не используется. Однако недавние исследования [6] показали, что редукция Гивенса может быть переформулирована так, чтобы повысить ее эффективность примерно в 2 раза, а также избежать вычисления квадратных корней. В результате этого "быстрый метод Гивенса" становится конкурентоспособным с методом Хаусхолдера. С другой стороны, быстрый метод должен отслеживать возможности переполнения, и переменные должны быть периодически перемасштабируемы при его использовании. Это обстоятельство говорит о том, что метод Хаусхолдера все же предпочтительнее. |