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

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

Основные авторы описания: Смирнова А.С., Киямова А.

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

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

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

Собственные значения

Задача нахождения собственных значений и собственных векторов для матрицы [math]\displaystyle{ A }[/math] заключается в поиске таких чисел [math]\displaystyle{ \lambda }[/math], которые удовлетворяют уравнению:

[math]\displaystyle{ Ax=\lambda x }[/math]

При этом, числа [math]\displaystyle{ \lambda }[/math] называются собственными значениями, а вектора [math]\displaystyle{ x }[/math] - собственными векторами

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

Суть QR-алгоритма заключается в приведении матрицы [math]\displaystyle{ A }[/math] к некоторой подобной ей матрице [math]\displaystyle{ A_N }[/math] при помощи итерационного алгоритма. Матрица [math]\displaystyle{ A_N }[/math] является правой квазитреугольной матрицей, на диагонали которой расположены блоки 1-го и/или 2-го порядка. Блоки первого порядка содержат различные вещественные значения матрицы [math]\displaystyle{ A_N }[/math], блоки второго порядка соответствуют двум комплексным сопряженным собственным значениям.

[math]\displaystyle{ 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]\displaystyle{ A }[/math] и [math]\displaystyle{ A_N }[/math] их наборы собственных значений совпадают. Таким образом задача поиска собственных значений матрицы [math]\displaystyle{ A }[/math] сводится к задаче выведения матрицы [math]\displaystyle{ A_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] собственных значений при этом некоторые из них могут быть комплексными)