QR-алгоритм

QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В. Н. Кублановской и Дж. Фрэнсисом (англ.).


Алгоритм[ | ]

Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A0=A. На k-м шаге (начиная с k = 0) вычислим QR-разложение Ak=QkRk, где Qk — ортогональная матрица (то есть QkT = Qk−1), а Rk — верхняя треугольная матрица. Затем мы определяем Ak+1 = RkQk.

Заметим, что

то есть все матрицы Ak являются подобными, то есть их собственные значения равны.

Пусть все диагональные миноры матрицы A не вырождены. Тогда последовательность матриц Ak при сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями.[1]

Для того, чтобы получить собственные векторы матрицы, нужно перемножить все матрицы Qk.

Алгоритм считается вычислительно устойчивым, т. к. производится ортогональными преобразованиями подобия.

Доказательство для симметричной положительно определённой матрицы[ | ]

Будем считать, что собственные числа положительно-определённой матрицы A упорядочены по убыванию:

Пусть

а S — матрица, составленная из собственных векторов матрицы A. Тогда, матрица A может быть записана в виде спектрального разложения

Найдём выражение для степеней исходной матрицы через матрицы Qk и Rk. С одной стороны, по определению QR-алгоритма:

Применяя это соотношение рекурсивно, получим:

Введя следующие обозначения:

получим

С другой стороны:

Приравнивая правые части последних двух формул, получим:

Предположим, что существует LU-разложение матрицы ST:

тогда

Умножим справа на обратную к U матрицу, а затем — на обратную к Λk:

Можно показать, что

При без ограничения общности можно считать, что на диагонали матрицы L стоят единицы, поэтому

Обозначим

причём матрица Pk является верхнетреугольной, как произведение верхнетреугольных и диагональных матриц.

Таким образом, мы доказали, что

.

Из единственности QR-разложения следует, что если произведение ортогональной и треугольной матрицы сходится к ортогональной матрице, то треугольная матрица сходится к единичной матрице. Из сказанного следует, что

То есть матрицы Sk сходятся к матрице собственных векторов матрицы A.

Так как

то

Переходя к пределу, получим:

Итак, мы доказали, что QR-алгоритм позволяет решить полную проблему собственных значений для симметричной положительно-определённой матрицы.

Реализация QR-алгоритма[ | ]

При определенных условиях последовательность матриц сходится к треугольной матрице, разложению Шура матрицы . В этом случае собственные числа треугольной матрицы располагаются на ее диагонали, и задача нахождения собственных чисел считается решенной. В тестах на сходимость не практично требовать точных нулей в нулевой части матрицы, но можно воспользоваться теоремой Гершгорина о кругах[en], задающей пределы ошибок.

В исходном состоянии матрицы (без дополнительных преобразований) стоимость итераций относительно высока. Стоимость алгоритма можно уменьшить, сначала приведя матрицу к форме верхней матрицы Хессенберга (стоимость получения которой методом, основанном на преобразовании Хаусхолдера, оценивается как арифметических операций), и затем используя конечную последовательность ортогональных преобразований подобия. Данный алгоритм чем-то похож на двухсторонюю QR-декомпозицию. (В обычной QR-декомпозиции матрица отражений Хаусхолдера умножается на исходную только слева, тогда как в случае использования формы Хессенберга матрица отражений умножается на исходную и слева, и справа.) Нахождение QR-декомпозиции верхней матрицы Хессенберга оценивается как арифметических операций. Из-за того, что форма матрицы Хессенберга почти верхнетреугольная (у неё только один поддиагональный элемент не равен нулю), удается сразу снизить число итераций требуемых для схождения QR-алгоритма.

В случае, если исходная матрица симметричная, верхняя матрица Хессенберга также симметричная и поэтому является трехдиагональной. Этим же свойством обладает вся последовательность матриц . В этом случае стоимость процедуры оценивается как арифметических операций с использованием метода, основанного на преобразовании Хаусхолдера. Нахождение QR-разложения симметричной трехдиагональной матрицы оценивается как операций.

Скорость сходимости зависит от степени разделения собственных чисел, и в практической реализации в явном или неявном виде используюся «сдвиги» для усиления разделения собственных чисел и для ускорения сходимости. В типичном виде для симметричных матриц QR-алгоритм точно находит одно собственное число (уменьшая размерность матрицы) за одну или две итерации, что делает этот подход как эффективным, так и надежным.

Реализация QR-алгоритма в неявном виде[ | ]

В современной вычислительной практике QR-алгоритм реализуется с использованием его неявной версии, что упрощает добавление множественных «сдвигов». Исходно матрица приводится к форме верхней матрицы Хессенберга , так же как и в явной версии. Затем, на каждом шаге первая колонка преобразуется через малоразмерное преобразование подобия Хаусхолдера к первой колонке (или ), где — это полином степени , который определяет стратегию «сдвигов» (обычно , где и — это два собственных числа остаточной подматрицы размера 2×2, это так называемый неявный двойной сдвиг). Затем последовательные преобразования Хаусхолдера размерности производятся с целью вернуть рабочую матрицу к форме верхней матрицы Хессенберга.

Примечания[ | ]

  1. Численные методы / Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. — 3-е изд. — М: БИНОМ, Лаборатория знаний, 2004. — С. 321. — 636 с. — ISBN 5-94774-175-X.

Ссылки[ | ]