|
Страница 3 из 10
Диагонализация матрицыИспользуя тот факт, что матрица XL обратна к XR, из предыдущих формул получаем: XR-1AXR = diag(l1,...,lN).Это является частным случаем преобразования подобия матрицы A: A -> Z-1AZдля некоторой трансформирующей матрицы Z. Основную роль в вычислениях собственных значений играют именно преобразования подобия, поскольку они их не меняют. Это легко доказывается: det|Z-1AZ - l1| = det|Z-1(A - l1)Z| = det|Z| det|A - l1| det|Z|-1 = det|A - l1|.Видно, что матрица с набором собственных векторов, удовлетворяющим свойству полноты (к таким относятся все нормальные матрицы и "большинство" случаев ненормальных матриц), может быть диагонализирована преобразованием подобия, трансформирующей матрицей которого является матрица, столбцы которой содержат координаты правых собственных векторов; строки же обратной к ней матрицы будут образовывать координаты левых собственных векторов. Для действительных симметричных матриц собственные векторы действительны и ортонормальны, таким образом, трансформирующая матрица является ортогональной. При этом преобразование подобия является ортогональным преобразованием: A -> ZTAZ.Хотя действительные несимметричные матрицы и могут быть диагонализированы "почти во всех" случаях, трансформирующая матрица не обязательно будет действительной. Однако выходит так, что "почти" всю работу в этом случае делает также действительное преобразование подобия. Оно может привести матрицу к системе малых блоков (2 x 2), расположенных по диагонали; все остальные элементы будут нулевыми. Каждый из блоков размера (2 x 2) соответствует комплексно - сопряженной паре собственных чисел. Эта идея будет эксплуатироваться в алгоритмах, помещеных ниже. Главная стратегия почти всех современных методов расчета собственных векторов и собственных значений заключается в том, что матрица A приводится к диагональной формы посредством цепочки преобразований подобия: A -> P1-1AP1 -> P2-1P1-1AP1P2 -> P3-1P2-1P1-1AP1P2P3 и т.д.Если эта цепочка приводит в конце концов к диагональной форме, то матрица правых собственных векторов XR будет представлять из себя произведение матриц: XR = P1P2P3...Иногда не требуется проводить подобное преобразование до диагональной формы. Например, если нас интересуют только собственные значения, а не собственные вектора, то достаточно привести A к треугольному виду, при котором нулями являются все элементы над диагональю или под ней. В этом случае диагональные элементы преобразованной матрицы уже будут собственными значениями. Имеется два существенно различных подхода к осуществлению указанной стратегии. Часто они хорошо работают в комбинации друг с другом, так что большинство современных методов используют оба из их. Первый подход заключается в построении индивидуальных матриц Pi как явных "элементарных" трансформаторов, расчитанных на специфические задачи, например, для обнуления конкретного внедиагонального элемента (преобразование Якоби) или целого столбца или строки (преобразования Хаусхолдера). В общем случае конечная цепочка подобных преобразований диагонализировать матрицу не может. Имеется выбор: либо использовать конечное число трансформаций для прохода большей части пути к диагонализации (например, приведя к трехдиагональной или Гессенберговской форме), а затем завершить операцию на второй стадии с помощью алгоритмов, которые будут указаны ниже. Либо итерациями свести внедиагональные элементы к пренебрежимо малым. Последний подход концептуально является простейшим и будет обсуждаться в следующем разделе, однако при N больших ~10 он является примерно в 5 раз менее эффективен. Другой подход, называемый методами факторизации, более тонкий. Предположим, матрица A может быть разложена в произведение правого FR и левого FL факторов. Тогда A = FLFR, или, что эквивалентно, FL-1A = FR.Если мы перемножим эти факторы в обратном порядке и используем вышенаписанное тождество, то будем иметь FRFL = FL-1AFL,что сразу распознается как преобразование подобия матрицы A с трансформирующей матрицей FL. Эту идею использует метод QR-разложения матрицы. Методы факторизации также не дают сходимость за конечное число шагов. Но лучшие из них сходятся быстро и надежно, и при использовании хорошего начального состояния матрицы, первично преобразованной элементарными операциями, являются главным выбором. |