WikiSort.ru - Не сортированное

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

Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A₀=A. На k-ом шаге (начиная с k = 0) вычислим QR-разложение A_k=Q_kR_k, где Q_k — ортогональная матрица (то есть Q_k^T = Q_k⁻¹), а R_k — верхняя треугольная матрица. Затем мы определяем A_k+1 = R_kQ_k.

Заметим, что

${\displaystyle A_{k+1}=R_{k}Q_{k}=Q_{k}^{-1}Q_{k}R_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k}=Q_{k}^{T}A_{k}Q_{k},}$

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

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

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

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

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

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

${\displaystyle \lambda _{1}>\lambda _{2}>...>\lambda _{n}>0.}$

Пусть

${\displaystyle \Lambda =\mathrm {diag} \left(\lambda _{1},...,\lambda _{n}\right),}$

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

${\displaystyle A=S\Lambda S^{T}.}$

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

${\displaystyle A^{k}=A_{1}^{k}=\left(Q_{1}R_{1}\right)^{k}=Q_{1}\left(R_{1}Q_{1}\right)^{k-1}R_{1}=Q_{1}A_{2}^{k-1}R_{1}.}$

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

${\displaystyle A^{k}=Q_{1}\cdot ...\cdot Q_{k}\cdot R_{k}\cdot ...\cdot R_{1}}$

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

${\displaystyle S_{k}=Q_{1}\cdot ...\cdot Q_{k},}$

${\displaystyle T_{k}=R_{k}\cdot ...\cdot R_{1},}$

получим

${\displaystyle A^{k}=S_{k}T_{k}.}$

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

${\displaystyle A^{k}=S\Lambda ^{k}S^{T}.}$

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

${\displaystyle S\Lambda ^{k}S^{T}=S_{k}T_{k}.}$

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

${\displaystyle S^{T}=LU,}$

тогда

${\displaystyle S\Lambda ^{k}LU=S_{k}T_{k}.}$

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

${\displaystyle S\Lambda ^{k}L=S_{k}T_{k}U^{-1},}$

${\displaystyle S\Lambda ^{k}L\Lambda ^{-k}=S_{k}T_{k}U^{-1}\Lambda ^{-k}.}$

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

${\displaystyle \Lambda ^{k}L\Lambda ^{-k}\to \mathrm {diag} \left(l_{11},...,l_{nn}\right)=L^{\prime }}$

при ${\displaystyle k\to \infty ,}$ без ограничения общности можно считать, что на диагонали матрицы L стоят единицы, поэтому

${\displaystyle S_{k}T_{k}U^{-1}\Lambda ^{-k}\to S.}$

Обозначим

${\displaystyle P_{k}=T_{k}U^{-1}\Lambda ^{-k},}$

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

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

${\displaystyle S_{k}P_{k}\to S}$ .

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

${\displaystyle S_{k}=Q_{1}\cdot ...\cdot Q_{k}\to S.}$

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

Так как

${\displaystyle A_{k+1}=Q_{k}^{T}A_{k}Q_{k}=...=\left(Q_{k}^{T}\cdot ...\cdot Q_{1}^{T}\right)A_{1}\left(Q_{1}\cdot ...\cdot Q_{k}\right)=\left(Q_{1}\cdot ...\cdot Q_{k}\right)^{T}A\left(Q_{1}\cdot ...\cdot Q_{k}\right),}$

то

${\displaystyle A_{k+1}=S_{k}^{T}AS_{k}.}$

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

${\displaystyle \lim _{k\to \infty }A_{k}=\lim _{k\to \infty }A_{k+1}=S^{T}AS=S^{T}S\Lambda S^{T}S=\Lambda .}$

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

Реализация QR алгоритма

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

В исходном состоянии матрицы (без дополнительных преобразований) стоимость итераций относительно высока. Стоимость алгоритма можно уменьшить сначала приведя матрицу ${\displaystyle A}$ к форме верхней матрицы Хессенберга (стоимость получения которой оценивается как ${\displaystyle {10 \over 3}n^{3}+O(n^{2})}$ арифметических операций используя метод основанный на преобразовании Хаусхолдера), и используюя конечную последовательность ортогональных преобразований подобия. Данный алгоритм чем-то похож на двухсторонюю QR декомпозицию. (В обычной QR декомпозиции, матрица отражений Хаусхолдера перемножается только слева, когда в случае использования формы Хессенберга матрица отражений перемножается и слева и справа.) Нахождение QR декомпозиции верхенй матрицы Хессенберга оценивается как ${\displaystyle 6n^{2}+O(n)}$ арифметических операций. Из за того что, форма матрицы Хессенберга почти верхне-треугольная (у неё только один под-диагональный элемент не равен нулю), удается сразу снизить число итераций требуемых для схождения QR алгоритма.

В случае если исходная матрица симметричная, верхняя матрица Хессенберга так-же симметричная и поэтому является трех-диагональной. Этим же свойством обладает вся последовательность матриц ${\displaystyle A_{k}}$ . В этом случае стоимость процедуры оценивается как ${\displaystyle {4 \over 3}n^{3}+O(n^{2})}$ арифметических операций с использованием метода основанного на преобразовании Хаусхолдера. Нахождение QR декомпозиции симметричной трехдиагональной матрицы оценивается как ${\displaystyle O(n)}$ операций.

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

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

В современной вычислительной практике QR алгоритм проводится используя его неявную версию, что делает проще добавление множественных "сдвигов". Исходно матрица приводится к форме верхней матрицы Хессенберга ${\displaystyle A_{0}=QAQ^{T}}$ так же как и в явной версии. Затем, на каждом шаге, первая колонка ${\displaystyle A_{k}}$ преобразуется через мало-размерное преобразование подобия Хаусхолдера к первой колонке ${\displaystyle p(A_{k})}$ (или ${\displaystyle p(A_{k})e_{1}}$ ), где ${\displaystyle p(A_{k})}$ , это полином степени ${\displaystyle r}$ , который определяет стратегию "сдвигов" (обычно ${\displaystyle p(x)=(x-\lambda )(x-{\bar {\lambda }})}$ , где ${\displaystyle \lambda }$ и ${\displaystyle {\bar {\lambda }}}$ это два собственных числа остаточной подматрицы ${\displaystyle A_{k}}$ размера 2 x 2, это так называемый неявный двойной сдвиг). Затем последовательные преобразования Хаусхолдера размерности ${\displaystyle r+1}$ производятся с целью вернуть рабочую матрицу ${\displaystyle A_{k}}$ к форме верхней матрицы Хессенберга.

Примечания

Ссылки

• Заметки Питера Олвера о ортогональных базисах и QR-алгоритме (англ.)