QR-алгоритм¶

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

¶Суть метода

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

1. A₀ = A (исходная матрица)
2. Aₖ = QₖRₖ (QR-разложение)
3. Aₖ₊₁ = RₖQₖ

При выполнении определённых условий последовательность матриц Aₖ сходится к верхней треугольной (или квазитреугольной для вещественных матриц с комплексными собственными значениями) матрице, на диагонали которой расположены собственные значения исходной матрицы. Собственные векторы при этом могут быть получены перемножением всех матриц Qₖ.

¶Сходимость и ускорение

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

Для ускорения сходимости применяются два основных приёма:

• Сдвиги — на каждом шаге из матрицы вычитается скалярная величина (сдвиг), приближающая одно из собственных значений. Это позволяет добиться квадратичной сходимости в общем случае и кубической для симметричных матриц. На практике наиболее эффективным считается сдвиг Уилкинсона, выбираемый на основе элементов нижнего правого угла матрицы.
• Предварительное приведение к форме Хессенберга — исходная матрица с помощью преобразований Хаусхолдера или Гивенса приводится к верхней форме Хессенберга (почти треугольной, с одной поддиагональю). Это сокращает вычислительную сложность каждой итерации с O(n³) до O(n²), где n — размерность матрицы.

¶Разновидности алгоритма

¶QR-алгоритм с неявными сдвигами

Наиболее распространённая реализация, использующая технику неявных сдвигов, которая позволяет комбинировать сдвиг и QR-разложение в одной операции без явного вычисления матрицы сдвига. Этот подход численно более устойчив и широко применяется в библиотеках линейной алгебры.

¶Двойной QR-алгоритм

Применяется для вещественных матриц с комплексными собственными значениями. Поскольку комплексные собственные значения вещественной матрицы появляются комплексно-сопряжёнными парами, двойной шаг с комплексно-сопряжёнными сдвигами позволяет оставаться в поле вещественных чисел, работая с блоками размера 2×2 на диагонали.

¶QZ-алгоритм

Обобщение QR-алгоритма для обобщённой проблемы собственных значений Ax = λBx, где A и B — матрицы. В этом случае используется разложение Шура пары матриц.

¶Вычислительная сложность и устойчивость

Для матрицы размера n×n полный QR-алгоритм с предварительным приведением к форме Хессенберга имеет вычислительную сложность порядка O(n³) операций. Алгоритм обладает хорошей численной устойчивостью благодаря использованию ортогональных преобразований, не приводящих к значительному росту ошибок округления.

¶Применение

QR-алгоритм используется в широком спектре задач:

• Механика и физика — расчёт собственных частот колебаний конструкций, анализ устойчивости динамических систем.
• Химия и квантовая механика — решение уравнения Шрёдингера, расчёт электронной структуры молекул.
• Статистика и анализ данных — метод главных компонент (PCA), спектральная кластеризация.
• Теория управления — анализ управляемости и наблюдаемости линейных систем.
• Машинное обучение — обучение нейронных сетей, анализ матриц ковариации.

¶Реализации

QR-алгоритм реализован во всех основных библиотеках численных методов: LAPACK, EISPACK, GNU Octave, MATLAB, SciPy (Python), Julia, а также входит в состав пакетов Intel MKL и OpenBLAS. В большинстве современных реализаций используется вариант с неявными сдвигами Уилкинсона и предварительным приведением к форме Хессенберга.