|
|
| Строка 13: |
Строка 13: |
|
| |
|
| === Общее описание алгоритма === | | === Общее описание алгоритма === |
| QR-алгоритм — это численный метод в линейной алгебре, предназначенный для решения полной проблемы собственных значений, то есть отыскания всех собственных чисел и собственных векторов матрицы. Был разработан в конце 1950-х годов независимо В. Н. Кублановской и Дж. Фрэнсисом.
| |
|
| |
| ====Собственные значения====
| |
| Задача нахождения собственных значений и собственных векторов для матрицы <math>A</math> заключается в поиске таких чисел <math>\lambda</math>, которые удовлетворяют уравнению:
| |
|
| |
| <math>Ax=\lambda x</math>
| |
|
| |
| При этом, числа <math>\lambda</math> называются собственными значениями, а вектора <math>x</math> - собственными векторами
| |
|
| |
| ====Описание алгоритма====
| |
|
| |
| Суть QR-алгоритма заключается в приведении матрицы <math>A</math> к некоторой подобной ей матрице <math>A_N</math> при помощи итерационного алгоритма. Матрица <math>A_N</math> является правой квазитреугольной матрицей, на диагонали которой расположены блоки 1-го и/или 2-го порядка. Блоки первого порядка содержат различные вещественные значения матрицы <math>A_N</math>, блоки второго порядка соответствуют двум комплексным сопряженным собственным значениям.
| |
|
| |
| <math>A_N=
| |
| \begin{bmatrix}
| |
| \blacksquare& \bullet& \bullet& \cdots& \cdots& \cdots& \cdots& \cdots& \bullet\\
| |
| 0& \blacksquare& \blacksquare& \bullet& \ddots& \ddots& \ddots& \ddots& \vdots\\
| |
| 0& \blacksquare& \blacksquare& \bullet& \bullet& \ddots& \ddots& \ddots& \vdots\\
| |
| \vdots& 0& 0& \blacksquare& \bullet& \bullet& \ddots& \ddots& \vdots\\
| |
| \vdots& \ddots& 0& 0& \blacksquare& \bullet& \bullet& \ddots& \vdots\\
| |
| \vdots& \ddots& \ddots& 0& 0& \blacksquare& \blacksquare& \ddots& \vdots\\
| |
| \vdots& \ddots& \ddots& \ddots& 0& \blacksquare& \blacksquare& \ddots& \bullet\\
| |
| \vdots& \ddots& \ddots& \ddots& \ddots& \ddots& \ddots& \ddots& \bullet\\
| |
| 0& \cdots& \cdots& \cdots& \cdots& \cdots& 0& 0& \blacksquare
| |
| \end{bmatrix}</math>
| |
|
| |
| В силу подобия матриц <math>A</math> и <math>A_N</math> их наборы собственных значений совпадают. Таким образом задача поиска собственных значений матрицы <math>A</math> сводится к задаче выведения матрицы <math>A_N</math> и поиска собственных значений для нее, что является тривиальной задачей.
| |
|
| |
| ====Сходимость алгоритма====
| |
|
| |
| //Прописать условия для матрицы
| |
|
| |
|
| === Математическое описание алгоритма === | | === Математическое описание алгоритма === |
| Нахождение собственных чисел квадратной матрицы методом QR разложения
|
| Последовательный алгоритм
|
| Последовательная сложность
|
-
|
| Объём входных данных
|
[math]\displaystyle{ n^2 }[/math]
|
| Объём выходных данных
|
[math]\displaystyle{ n }[/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] собственных значений при этом некоторые из них могут быть комплексными)
Свойства алгоритма
Программная реализация алгоритма
Масштабируемость алгоритма и его реализации
Существующие реализации алгоритма
