QR-разложение матрицы: алгоритмы и применение¶

QR-разложение матрицы — это представление матрицы \(A\) в виде произведения ортогональной (унитарной в комплексном случае) матрицы \(Q\) и верхнетреугольной матрицы \(R\). Для вещественной матрицы размера \(m \times n\) (\(m \ge n\)) разложение записывается как \(A = QR\), где \(Q\) имеет размер \(m \times m\) (полное разложение) или \(m \times n\) (экономное разложение), а \(R\) — размер \(m \times n\) или \(n \times n\) соответственно. QR-разложение является фундаментальным инструментом вычислительной линейной алгебры и используется для решения систем линейных уравнений, задач наименьших квадратов и вычисления собственных значений.

¶История

Идея разложения матрицы на ортогональный и треугольный множители восходит к работам Карла Фридриха Гаусса начала XIX века, который применял ортогональные преобразования при решении задач геодезии. Однако систематическое изучение и алгоритмизация QR-разложения связаны с именем Джона Тодда (John Todd) и его коллег, работавших в 1950-х годах в Калифорнийском технологическом институте. Название «QR» закрепилось в литературе после публикаций Альстона Хаусхолдера (Alston Householder) в 1958 году, который предложил эффективный метод приведения матрицы к верхнетреугольному виду с помощью отражений. В 1960-х годах Джин Голуб (Gene Golub) и Чарльз Ван Лоан (Charles Van Loan) систематизировали алгоритмы и распространили их применение на задачи наименьших квадратов и вычисление сингулярных значений.

¶Основные алгоритмы

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

¶Метод Грама — Шмидта

Классический процесс ортогонализации Грама — Шмидта строит ортонормированный базис столбцов матрицы \(A\) последовательно. Каждый следующий столбец \(a_i\) проектируется на подпространство, порождённое предыдущими ортонормированными векторами, и полученная невязка нормируется. Коэффициенты проекций образуют элементы матрицы \(R\). Модифицированный вариант метода Грама — Шмидта (MGS) пересчитывает остаточные векторы на каждом шаге, что значительно повышает численную устойчивость. Вычислительная сложность метода составляет \(O(mn^2)\) операций, однако классическая версия чувствительна к потере ортогональности при плохо обусловленных матрицах.

¶Отражения Хаусхолдера

Метод Хаусхолдера основан на применении последовательности ортогональных преобразований — отражений (матриц Хаусхолдера) вида \(H = I - 2vv^T / (v^T v)\), где \(v\) — вектор отражения. Каждое преобразование обнуляет все элементы текущего столбца ниже диагонали, не нарушая уже полученную структуру. После \(n\) шагов матрица приводится к верхнетреугольному виду \(R\), а произведение всех отражений даёт матрицу \(Q\). Метод Хаусхолдера считается наиболее численно устойчивым и требует \(O(mn^2)\) операций, при этом он эффективно использует кэш-память современных процессоров.

¶Вращения Гивенса

Метод вращений Гивенса использует плоские повороты — ортогональные матрицы, обнуляющие один элемент за раз. Каждое вращение действует на пару строк матрицы и требует вычисления синуса и косинуса угла поворота. Алгоритм применяется, когда необходимо сохранить разреженность матрицы или выполнять обнуление элементов в определённом порядке. Вычислительная сложность выше, чем у метода Хаусхолдера (примерно в два раза), но вращения удобны для параллельных вычислений и работы с ленточными матрицами.

¶Применение

QR-разложение лежит в основе многих вычислительных методов.

¶Решение систем линейных уравнений

Для квадратной невырожденной матрицы \(A\) система \(Ax = b\) решается в два шага: сначала находится \(y = Q^T b\), затем решается верхнетреугольная система \(Rx = y\) обратной подстановкой. Такой подход обеспечивает высокую численную устойчивость и часто используется в пакетах линейной алгебры вместо метода Гаусса.

¶Метод наименьших квадратов

В переопределённых системах (\(m > n\)) QR-разложение позволяет найти псевдорешение, минимизирующее норму невязки \(\|Ax - b\|_2\). Благодаря ортогональности матрицы \(Q\) норма невязки сохраняется, и задача сводится к решению верхнетреугольной системы из \(n\) уравнений. Этот метод применяется в регрессионном анализе, обработке сигналов и геодезии.

¶Вычисление собственных значений

QR-алгоритм (итерационный метод QR) — основной способ вычисления всех собственных значений плотной матрицы. На каждой итерации выполняется QR-разложение текущей матрицы и перемножение множителей в обратном порядке: \(A_{k+1} = R_k Q_k\). Последовательность матриц сходится к верхней квазитреугольной форме (форме Шура), диагональ которой содержит собственные значения. Метод был предложен в 1961 году Джоном Фрэнсисом (John Francis) и Верой Кубановской (Вера Кубановская) независимо друг от друга.

¶Другие области

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

¶Численная устойчивость и реализация

Все три алгоритма являются численно устойчивыми в смысле обратного анализа ошибок: вычисленное разложение \(\tilde{Q}\tilde{R}\) точно соответствует некоторой матрице \(A + E\), где \(\|E\| \le c \varepsilon \|A\|\), а \(c\) — небольшая константа, зависящая от размерности и алгоритма. Наилучшей устойчивостью обладает метод Хаусхолдера. Современные реализации (LAPACK, MATLAB, NumPy) используют блочные версии алгоритмов, которые повышают эффективность за счёт работы с подматрицами и уменьшения числа обращений к памяти.

¶Источники

• Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
• Тыртышников Е. Е. Основы вычислительной (численной) линейной алгебры. — М.: Физматлит, 2017.
• Golub G. H., Van Loan C. F. Matrix Computations. — 4th ed. — Johns Hopkins University Press, 2013.
• Higham N. J. Accuracy and Stability of Numerical Algorithms. — 2nd ed. — SIAM, 2002.