Участник:Odbaev/Нахождение собственных чисел квадратной матрицы методом QR разложения (2): различия между версиями
Odbaev (обсуждение | вклад) |
Odbaev (обсуждение | вклад) |
||
Строка 41: | Строка 41: | ||
Полный алгоритм: | Полный алгоритм: | ||
* [http://netlib.org/lapack/ LAPACK]: функция [http://www.netlib.org/lapack/double/dgeev.f DGEEV] (последовательная реализация для двойной точности) | * [http://netlib.org/lapack/ LAPACK]: функция [http://www.netlib.org/lapack/double/dgeev.f DGEEV] (последовательная реализация для двойной точности) | ||
− | * [http://alglib.sources.ru ALGLIB]: реализация [http://alglib.sources.ru/ | + | * [http://alglib.sources.ru ALGLIB]: реализация [http://alglib.sources.ru/eigen/nonsymmetric/nonsymmetricevd.php алгоритма] для различных языков программирования |
* [http://www.numpy.org Python NumPy]: функции [https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eig.html linalg.eig], [https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eigvals.html linalg.eigvals ] | * [http://www.numpy.org Python NumPy]: функции [https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eig.html linalg.eig], [https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eigvals.html linalg.eigvals ] | ||
Версия 22:52, 9 октября 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 (последовательная реализация для двойной точности)
- ALGLIB: реализация алгоритма для различных языков программирования
- Python NumPy: функции linalg.eig, linalg.eigvals
QR-разложение:
- LAPACK: функция DGEQRF (последовательная реализация для двойной точности)
- ScaLAPACK: функция PDGEQRF (параллельная реализация для двойной точности)
- MATLAB: функция qr
- Mathematica: функция QRDecomposition
- ALGLIB: реализация QR-разложения для различных языков программирования
- Python NumPy: функция linalg.qr
- C++ Eigen: QR модуль
Умножение матриц:
3 Литература
- ↑ Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.