Участник:Смирнова Александра/Нахождение собственных чисел квадратной матрицы методом QR разложения (3)

Нахождение собственных чисел квадратной матрицы методом QR разложения
Последовательный алгоритм
Последовательная сложность	-
Объём входных данных	[math]\displaystyle{ n^2 }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	-
Ширина ярусно-параллельной формы	-

Основные авторы описания: Смирнова А.С., Киямова А.

---

Задача нахождения собственных значений и собственных векторов для матрицы [math]\displaystyle{ A }[/math] заключается в поиске таких чисел [math]\displaystyle{ \lambda }[/math], которые удовлетворяют уравнению:

[math]\displaystyle{ Ax=\lambda x }[/math], при этом, числа [math]\displaystyle{ \lambda }[/math] называются собственными значениями, а вектора [math]\displaystyle{ x }[/math] - собственными векторами

Данная задача является одной из важнейших задач линейной алгебры. Собственные вектора и собственные значения применяются в различных областях науки: в аналитической геометрии, при решении систем интегральных уравнений, в математической физике. Однако не существует простых алгоритмов прямого вычисления собственных значений для матриц в общем случае, поэтому данная задача на практике решается численными методами. Одним из таких методов является QR-алгоритм.

Свойства и структура алгоритма

Общее описание алгоритма

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

Суть базового QR-алгоритма заключается в итерационном приведении матрицы [math]\displaystyle{ A }[/math] к некоторой подобной ей матрице [math]\displaystyle{ A_N }[/math] при помощи QR-разложения. Матрица [math]\displaystyle{ A_N }[/math] является правой верхней треугольной матрицей, а значит ее диагональ содержит собственные значения. В силу подобия матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ A_N }[/math] их наборы собственных значений совпадают. Таким образом задача поиска собственных значений матрицы [math]\displaystyle{ A }[/math] сводится к задаче выведения матрицы [math]\displaystyle{ A_N }[/math] и поиска собственных значений для нее, что является тривиальной задачей.

Однако базовый QR-алгоритм может обладать очень низкой скоростью сходимости, поэтому существуют несколько способов ускорить его:

• Перед итерациями привести матрицу [math]\displaystyle{ A }[/math] к подобной ей матрице [math]\displaystyle{ A_H }[/math], которая будет иметь форму Хессенберга. Данный шаг позволит ускорить процесс QR-разложения
• Использовать QR-алгоритм со сдвигами

В данной статье будет рассмотрен только базовый QR-алгоритм.

Математическое описание алгоритма

QR-разложение матрицы

Основой алгоритма является тот факт, что любую вещественную матрицу можно разложить на произведение двух матриц следующего вида:

[math]\displaystyle{ A=QR }[/math], где [math]\displaystyle{ Q }[/math] - ортогональная матрица ([math]\displaystyle{ Q^T=Q^{-1} }[/math]), [math]\displaystyle{ R }[/math] - верхняя треугольная матрица

Данное разложение называется QR-разложением.

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

Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы

Основная статья: Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы

Суть метода Хаусхолдера заключается в последовательном приведении матрицы [math]\displaystyle{ A }[/math] к верхней треугольной форме при помощи домножения ее на так называемые матрицы отражения. Получившаяся треугольная матрица будет искомой матрицей [math]\displaystyle{ R }[/math], а матрица [math]\displaystyle{ Q }[/math] будет равна произведению сопряженных матриц отражения.

На [math]\displaystyle{ i }[/math]-ом шаге задача [math]\displaystyle{ i }[/math]-ой матрицы отражения заключается в обнулении всех поддиагональных элементов [math]\displaystyle{ i }[/math]-го столбца матрицы [math]\displaystyle{ A }[/math] (при этом столбцы левее [math]\displaystyle{ i }[/math]-го не изменяются). Таким образом, алгоритм состоит из n шагов, на каждом из которых вычисляется очередная матрица отражения, после чего найденное отражение применяется к матрице, которая является результатом предыдущего шага.

Матрица отражения имеет вид [math]\displaystyle{ E-\frac{1}{\gamma }vv^* }[/math], где вектор [math]\displaystyle{ v }[/math] вычисляется из текущего [math]\displaystyle{ i }[/math]-го столбца матрицы при помощи использования операции скалярного произведения векторов. Данное представление матриц отражения позволяет хранить их в виде одного вектора и сводит домножение матрицы отражения на текущую матрицу к арифметическим операциям над векторами (скалярное произведение и сложение векторов).

Метод Гивенса (вращений) QR-разложения квадратной матрицы

Основная статья: Метод Гивенса (вращений) QR-разложения квадратной матрицы

Суть метода Гивенса заключается в последовательном приведении матрицы [math]\displaystyle{ A }[/math] к верхней треугольной форме при помощи домножения ее на так называемые матрицы вращения. Получившаяся треугольная матрица будет искомой матрицей [math]\displaystyle{ R }[/math], а матрица [math]\displaystyle{ Q }[/math] будет равна произведению сопряженных матриц вращения.

На каждом шаге задачей матрицы вращения является обнуление одного поддиагонального элемента. Вначале обнуляются все поддиагональные элементы 1-го столбца, затем 2-го и так далее до [math]\displaystyle{ (n-1) }[/math]-го. Таким образом, алгоритм состоит из [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] шагов на каждом из которых вычисляется очередная матрица вращения, после чего она применяется к матрице, которая является результатом предыдущего шага.

QR-алгоритм нахождения собственных чисел

Пусть матрица [math]\displaystyle{ A }[/math] - матрица, для которой мы хотим найти собственные значения. Тогда итерационный процесс строится следующим образом:

1. [math]\displaystyle{ A_0=A }[/math]
2. Пусть имеется матрица [math]\displaystyle{ A_k }[/math], тогда матрица [math]\displaystyle{ A_{k+1} }[/math] строится следующим образом:

• Строится QR-разложение: [math]\displaystyle{ A_k=Q_kR_k }[/math]
• Вычисляется [math]\displaystyle{ A_{k+1}=R_kQ_k }[/math]

Заметим, что [math]\displaystyle{ A_{k+1}=R_kQ_k={Q_{k}^{-1}}Q_kR_kQ_k={Q_{k}^{-1}}A_kQ_k={Q_{k}^{T}}A_kQ_k }[/math]

Таким образом матрицы [math]\displaystyle{ A_{k+1} }[/math] и [math]\displaystyle{ A_{k} }[/math] подобны для [math]\displaystyle{ \forall k }[/math], а значит, в силу транзитивности подобия, все матрицы [math]\displaystyle{ A_{k} }[/math] подобны матрице [math]\displaystyle{ A }[/math] и имеют одинаковый набор собственных значений.

Сходимость алгоритма

Предположим, что для [math]\displaystyle{ \forall m }[/math] выполнены следующие условия:

1. [math]\displaystyle{ A=X\Lambda X^{-1} }[/math], где [math]\displaystyle{ \Lambda =\begin{bmatrix} \Lambda_1 & 0\\ 0 & \Lambda_2 \end{bmatrix}, \Lambda_1\in\mathbb{C}^{m\times m},\Lambda_2\in\mathbb{C}^{r\times r} }[/math]

2. [math]\displaystyle{ \left | \lambda_1 \right | \geq ...\geq \left | \lambda_m \right | \gt \left | \lambda_{m+1} \right | \geq ...\geq \left | \lambda_{m+r} \right | \gt 0 }[/math], где [math]\displaystyle{ \{\lambda_1,...,\lambda_m\} = \lambda(\Lambda_1), \{\lambda_{m+1},...,\lambda_{m+r}\} = \lambda(\Lambda_2) }[/math]

3. Ведущая подматрица порядка [math]\displaystyle{ m }[/math] в [math]\displaystyle{ X^{-1} }[/math] невырождена

Тогда при [math]\displaystyle{ k \rightarrow \infty }[/math] последовательность матриц [math]\displaystyle{ A_k }[/math] сходится к матрице с верхней треугольной формой.

Таким образом, на практике необходимо выполнять итерации до тех пор пока матрица [math]\displaystyle{ A_k }[/math] не станет треугольной (также можно продолжать выполнять их пока искомая матрица не будет найдена с некоторой заранее заданной точностью [math]\displaystyle{ \varepsilon }[/math]). Если итерации закончились на шаге [math]\displaystyle{ N }[/math], то числа на диагонали матрицы [math]\displaystyle{ A_N }[/math] будут считаться собственными значениями матрицы [math]\displaystyle{ A }[/math]

Вычислительное ядро алгоритма

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

1. Вычисление QR-разложения матрицы: [math]\displaystyle{ A_k=Q_kR_k }[/math]. Существует несколько методов решения данной задачи:

• Метод Хаусхолдера (отражений)
• Метод Гивенса (вращений)

2. Перемножение двух плотных матриц: [math]\displaystyle{ A_{k+1}=R_kQ_k }[/math]

Входные и выходные данные алгоритма

Входные данные:

квадратная вещественная плотная матрица [math]\displaystyle{ A }[/math]: [math]\displaystyle{ A \in \R^{n \times n} }[/math]

Объем входных данных:

[math]\displaystyle{ n^2 }[/math] (необходимо хранить все элементы матрицы)

Выходные данные:

собственные значения матрицы [math]\displaystyle{ A }[/math]

Объем выходных данных:

[math]\displaystyle{ n }[/math] (квадратная матрица размера [math]\displaystyle{ n \times n }[/math] имеет ровно [math]\displaystyle{ n }[/math] собственных значений при этом некоторые из них могут быть комплексными)