QR-алгоритм

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

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

Общее описание метода

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

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

Математическое описание

Известно, что произвольная квадратная матрица может быть представлена в виде произведения унитарной (в вещественном случае ортогональной) и верхней треугольной матриц. Такое разложение называется QR-разложением.

Пусть [math]\displaystyle{ A_0 = A }[/math] — исходная матрица. Для [math]\displaystyle{ k = 1, 2, \ldots }[/math] выполняется QR-разложение:

• [math]\displaystyle{ A_{k-1} = Q_kR_k }[/math], где [math]\displaystyle{ Q_k }[/math] — унитарная (ортогональная) матрица, [math]\displaystyle{ R_k }[/math] — верхняя треугольная матрица, и затем найденные матрицы перемножаются в обратном порядке:
• [math]\displaystyle{ A_k = R_kQ_k }[/math].

Поскольку [math]\displaystyle{ A_k = R_kQ_k = Q_k^{*}A_{k-1}Q_k }[/math], то матрицы [math]\displaystyle{ A_k }[/math] и [math]\displaystyle{ A_{k-1} }[/math] унитарно подобны для любого [math]\displaystyle{ k }[/math]. Поэтому матрицы [math]\displaystyle{ A_1, A_2, \ldots }[/math] унитарно подобны исходной матрице [math]\displaystyle{ A }[/math] и имеют те же собственные значения.