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

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

Основные авторы описания: О.Д.Баев, А.С.Шевелев

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

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

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

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

Пусть 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.

Заметим, что

[math] 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, [/math]

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

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

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

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

Основными вычислительными ядрами алгоритма являются:

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

1.4 Макроструктура алгоритма

QR-алгоритм на каждой итерации использует следующие макрооперации:

1. QR-разложение
   • Метод Гивенса (вращений)
   • Метод Хаусхолдера (отражений)
2. Умножение матриц

1.5 Схема реализации последовательного алгоритма

QR-алгоритм является итерационным.

На каждой итерации k:

1. Строится QR-разложение матрицы [math] A_k = Q_k R_k [/math]
2. Получается матрица [math] A_{k+1} = R_k Q_k [/math], используемая на следующей итерации

Алгоритм выполняется до сходимости матрицы к треугольному виду.

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

Входные данные: плотная квадратная матрица [math]A[/math] (элементы [math]a_{ij}[/math]).

Объём входных данных: [math]n^2[/math].

Выходные данные: собственные числа матрицы [math]A[/math].

Объём выходных данных: [math]n[/math].

2 Программная реализация алгоритма

2.2 Существующие реализации алгоритма

Полный алгоритм:

• LAPACK: функция DGEEV (последовательная реализация)
• ScaLAPACK: функция PDHSEQR (параллельная реализация)
• ALGLIB: реализация алгоритма для различных языков программирования
• Python NumPy: функции linalg.eig, linalg.eigvals
• C++ Eigen: Eigenvalues модуль

QR-разложение:

• LAPACK: функция DGEQRF (последовательная реализация)
• ScaLAPACK: функция PDGEQRF (параллельная реализация)
• MATLAB: функция qr
• Mathematica: функция QRDecomposition
• ALGLIB: реализация QR-разложения для различных языков программирования
• Python NumPy: функция linalg.qr
• C++ Eigen: QR модуль

Умножение матриц:

• LAPACK: функция DGEMM (последовательная реализация)
• ScaLAPACK: функция PDGEMM (параллельная реализация)
• MATLAB: функции mtimes, *
• Mathematica: функция Dot
• Python NumPy: функция numpy.dot