Участник:Odbaev/Нахождение собственных чисел квадратной матрицы методом QR разложения (2): различия между версиями
Odbaev (обсуждение | вклад) |
Odbaev (обсуждение | вклад) |
||
Строка 56: | Строка 56: | ||
Умножение матриц: | Умножение матриц: | ||
− | * | + | * [http://netlib.org/lapack/ LAPACK]: функция [http://www.netlib.org/lapack/explore-html/d7/d2b/dgemm_8f.html DGEMM] (последовательная реализация) |
+ | * [http://www.netlib.org/scalapack/ ScaLAPACK]: функция [http://www.netlib.org/scalapack/explore-html/d6/da2/pdgemm___8c.html PDGEMM] (параллельная реализация) | ||
= Литература = | = Литература = | ||
<references /> | <references /> |
Версия 13:22, 10 октября 2016
Основные авторы описания: О.Д.Баев, А.С.Шевелев
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В.Н. Кублановской и Дж. Фрэнсисом.
1.2 Математическое описание алгоритма
Пусть A — вещественная матрица, для которой мы хотим найти собственные числа и векторы. Положим A0=A. На k-ом шаге (начиная с k = 0) вычислим QR-разложение Ak=QkRk, где Qk — ортогональная матрица (то есть QkT = Qk−1), а Rk — верхняя треугольная матрица. Затем мы определяем Ak+1 = RkQk.
Заметим, что
- [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]
то есть все матрицы Ak являются подобными и их собственные значения равны.
Пусть все диагональные миноры матрицы A не вырождены. Тогда последовательность матриц Ak при k→∞ сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями. [1]
Для того, чтобы получить собственные векторы матрицы, нужно перемножить все матрицы Qk.
1.3 Вычислительное ядро алгоритма
Основными вычислительными ядрами алгоритма являются:
- QR-разложение
- Умножение матриц
1.4 Макроструктура алгоритма
QR-алгоритм на каждой итерации использует следующие макрооперации:
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Масштабируемость алгоритма и его реализации
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 (параллельная реализация)
3 Литература
- ↑ Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.