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

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

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

---

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

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

Данная задача является одной из важнейших задач линейной алгебры. Собственные вектора и собственные значения применяются в различных областях науки: в аналитической геометрии, при решении систем интегральных уравнений, в математической физике. Однако не существует простых алгоритмов прямого вычисления собственных значений для матриц в общем случае, поэтому данная задача на практике решается численными методами. Одним из таких методов является QR-алгоритм.

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

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

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

Суть базового QR-алгоритма заключается в итерационном приведении матрицы [math]A[/math] к некоторой подобной ей матрице [math]A_N[/math] при помощи QR-разложения. Матрица [math]A_N[/math] является правой верхней треугольной матрицей, а значит ее диагональ содержит собственные значения. В силу подобия матриц [math]A[/math] и [math]A_N[/math] их наборы собственных значений совпадают. Таким образом задача поиска собственных значений матрицы [math]A[/math] сводится к задаче выведения матрицы [math]A_N[/math] и поиска собственных значений для нее, что является тривиальной задачей.

Однако базовый QR-алгоритм может обладать очень низкой скоростью сходимости, поэтому существуют несколько способов ускорить его:

• Перед итерациями привести матрицу [math]A[/math] к подобной ей матрице [math]A_H[/math], которая будет иметь форму Хессенберга. Данный шаг позволит ускорить процесс QR-разложения
• Использовать QR-алгоритм со сдвигами

В данной статье будет рассмотрен только базовый QR-алгоритм.

1.9 Входные и выходные данные алгоритма

Входные данные: квадратная вещественная плотная матрица [math]A[/math]: [math]A \in \R^{n \times n}[/math]

Объем входных данных: [math]n^2[/math] (необходимо хранить все элементы матрицы)

Выходные данные: собственные значения матрицы [math]A[/math]

Объем выходных данных: [math]n[/math] (квадратная матрица размера [math]n \times n[/math] имеет ровно [math]n[/math] собственных значений при этом некоторые из них могут быть комплексными)