Участник:Odbaev/Нахождение собственных чисел квадратной матрицы методом QR разложения (2): различия между версиями
Строка 43: | Строка 43: | ||
На каждой итерации <math style="vertical-align:0%"> k </math>: | На каждой итерации <math style="vertical-align:0%"> k </math>: | ||
− | # Строится QR-разложение матрицы <math | + | # Строится QR-разложение матрицы <math> A_k = Q_k R_k </math> |
− | # Получается матрица <math | + | # Получается матрица <math> A_{k+1} = R_k Q_k </math>, используемая на следующей итерации |
− | Алгоритм выполняется до сходимости матрицы <math | + | Алгоритм выполняется до сходимости матрицы <math> A_k</math> к треугольному виду. |
Версия 16:13, 28 октября 2016
Нахождение собственных чисел квадратной матрицы методом QR разложения | |
Последовательный алгоритм | |
Последовательная сложность | [math]N * O(n^3)[/math] |
Объём входных данных | [math]n^2[/math] |
Объём выходных данных | [math]n[/math] |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | [math]N*(12n-15)[/math] |
Ширина ярусно-параллельной формы | [math]O(n^2)[/math] |
Основные авторы описания: О.Д.Баев, А.С.Шевелев
Содержание
- 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 Математическое описание алгоритма
Пусть [math]A[/math] — вещественная квадратная матрица, для которой мы хотим найти собственные числа и векторы. Положим [math]A_0 = A[/math]. На k-ом шаге (начиная с k = 0) вычислим QR-разложение [math]A_k = Q_k R_k[/math], где [math]Q_k[/math] — ортогональная матрица (то есть [math]Q_k^{T} = Q_k^{-1}[/math]), а [math]R_k[/math] — верхняя треугольная матрица. Затем мы определяем [math]A_{k+1} = R_k Q_k[/math].
Заметим, что
- [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]
то есть все матрицы [math]A_k[/math] являются подобными и их собственные значения равны.
Пусть все диагональные миноры матрицы [math]A[/math] не вырождены. Тогда последовательность матриц [math]A_k[/math] при [math]k \rightarrow \infty[/math] сходится по форме к клеточному правому треугольному виду, соответствующему клеткам с одинаковыми по модулю собственными значениями. [1]
Для того, чтобы получить собственные векторы матрицы, нужно перемножить все матрицы [math]Q_k[/math].
1.3 Вычислительное ядро алгоритма
Основными вычислительными ядрами алгоритма являются:
- QR-разложение
- Умножение матриц
1.4 Макроструктура алгоритма
QR-алгоритм на каждой итерации использует следующие макрооперации:
1.5 Схема реализации последовательного алгоритма
QR-алгоритм является итерационным.
На каждой итерации [math] k [/math]:
- Строится QR-разложение матрицы [math] A_k = Q_k R_k [/math]
- Получается матрица [math] A_{k+1} = R_k Q_k [/math], используемая на следующей итерации
Алгоритм выполняется до сходимости матрицы [math] A_k[/math] к треугольному виду.
Псевдокод алгоритма:
algorithm QR is input: Matrix A output: Eigenvalues of the matrix A repeat Q, R ← QR_factorization(A) A ← R×Q until convergence return diag(A)
1.6 Последовательная сложность алгоритма
Пусть дана матрица [math] A \in \mathbb{R}^{n \times n}[/math]. До момента приведения матрицы к треугольной форме произведено [math]N[/math] итераций алгоритма. На каждой итерации алгоритма производится три действия: QR-разложение, перемножение матриц и проверка, является ли матрица треугольной.
Распишем последовательную сложность каждого действия:
- QR-разложение:
- Перемножение матриц - [math]n^3[/math] операций[4].
- Проверка, имеет ли матрица треугольную форму - [math]\frac{n^2 - n}{2}[/math] операций.
Таким образом, на каждой итерации последовательный алгоритм выполняет [math]O(n^3)[/math] операций. Для всего алгоритма потребуется выполнить [math]N * O(n^3)[/math] операций.
1.7 Информационный граф
На Рисунке 1 изображен макрограф описываемого QR-алгоритма, представляющего собой последовательность итераций алгоритма. На рисунке 2 представлен граф, на котором более подробно отображено содержимое каждой итерации. Информационные графы QR-разложения и матричного умножения представлены в соответствующих статьях.
1.8 Ресурс параллелизма алгоритма
Базовый алгоритм является итерационным и выполняется последовательно. Возможность распараллеливания алгоритма предоставляется при реализации операций таких, как QR-разложение, перемножение матриц и проверка, имеет ли матрица треугольную форму.
Рассчитаем параллельную сложность для каждой из указанных операций:
- QR-разложение:
- Перемножение матриц - [math]n[/math][4].
- Проверка, имеет ли матрица треугольную форму - [math]1[/math].
Результирующая параллельная сложность одной итерации [math]12n-15[/math] (для метода вращений). А всего алгоритма из [math]N[/math] итераций - [math]N*(12n-15)[/math].
1.9 Входные и выходные данные алгоритма
Входные данные: плотная квадратная матрица [math]A[/math] размера [math]n[/math].
Объём входных данных: [math]n^2[/math].
Выходные данные: [math]n[/math] собственных чисел матрицы [math]A[/math].
Объём выходных данных: [math]n[/math].
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 (параллельная реализация)
- MATLAB: функции mtimes, *
- Mathematica: функция Dot
- Python NumPy: функция numpy.dot
3 Литература
- ↑ Бахвалов Н.С., Жидков Н.П., Кобельков. Г.М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
- ↑ 2,0 2,1 Метод Гивенса (вращений) QR-разложения квадратной матрицы
- ↑ 3,0 3,1 Метод Хаусхолдера (отражений) QR-разложения квадратной матрицы
- ↑ 4,0 4,1 Перемножение плотных неособенных матриц