QR-разложение: определение и методы построения¶

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

¶Определение и свойства

Формально, для матрицы \(A\) размером \(m \times n\) (где \(m \ge n\)) QR-разложением называется пара матриц \(Q\) (\(m \times m\)) и \(R\) (\(m \times n\)), таких что \(A = QR\). Матрица \(Q\) удовлетворяет условию \(Q^T Q = I\) (ортогональность), а матрица \(R\) имеет нулевые элементы ниже главной диагонали.

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

Ключевые свойства:

• Число обусловленности матрицы \(A\) сохраняется при умножении на ортогональную матрицу \(Q\), что обеспечивает численную устойчивость алгоритмов.
• Определитель квадратной матрицы \(A\) равен произведению диагональных элементов \(R\), умноженному на \(\det(Q)\) (для вещественного случая \(\det(Q) = \pm 1\)).

¶Методы построения

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

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

Классический процесс ортогонализации Грама — Шмидта строит столбцы матрицы \(Q\) последовательно. Каждый столбец \(a_i\) исходной матрицы ортогонализуется относительно уже построенных столбцов \(q_1, \dots, q_{i-1}\), после чего нормируется. Элементы матрицы \(R\) вычисляются как скалярные произведения.

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

¶Метод отражений Хаусхолдера

Наиболее распространённый на практике метод. На каждом шаге \(k\) строится матрица отражения (Хаусхолдера) \(H_k\), которая обнуляет все элементы ниже диагонали в \(k\)-м столбце текущей матрицы. Итоговая матрица \(Q\) получается как произведение всех отражений: \(Q = H_1 H_2 \dots H_n\).

Метод Хаусхолдера отличается высокой численной устойчивостью и требует около \(\frac{4}{3} m n^2\) флопов для прямоугольных матриц. Он реализован в большинстве библиотек линейной алгебры (LAPACK, MATLAB, NumPy).

¶Метод вращений Гивенса

Метод использует двумерные вращения для обнуления отдельных элементов матрицы. Каждое вращение \(G(i, j, \theta)\) затрагивает только две строки матрицы. Этот подход требует больше вычислений (примерно \(2mn^2\) флопов), но удобен для разреженных матриц и параллельных вычислений, так как вращения легко применять независимо.

¶Применение

QR-разложение используется в следующих областях:

• Решение систем линейных уравнений: метод более устойчив, чем исключение Гаусса, особенно для плохо обусловленных матриц.
• Задача наименьших квадратов: решение задачи \(\min_x \|Ax - b\|_2\) сводится к решению треугольной системы \(Rx = Q^T b\).
• Вычисление собственных значений: QR-алгоритм — основной итерационный метод нахождения всех собственных значений симметричных и несимметричных матриц.
• Определение ранга матрицы: число ненулевых диагональных элементов \(R\) указывает на ранг матрицы.

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

Ортогональные преобразования не увеличивают норму ошибок округления, поэтому методы Хаусхолдера и Гивенса считаются обратно устойчивыми. Это означает, что вычисленное разложение соответствует точному разложению некоторой «близкой» матрицы \(A + \delta A\), где \(\|\delta A\|\) имеет порядок машинного эпсилон, умноженного на норму \(A\). Метод Грама — Шмидта в классической форме такой устойчивостью не обладает, что ограничивает его практическое применение.

¶Реализации

QR-разложение реализовано во всех основных пакетах численных вычислений: LAPACK (подпрограммы dgeqrf, dorgqr), MATLAB (функция qr), NumPy/SciPy (функции numpy.linalg.qr, scipy.linalg.qr), а также в библиотеках для работы с разреженными матрицами (SuiteSparse).

¶Источники

• Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
• Тыртышников Е. Е. Основы алгебры. — М.: Физматлит, 2017.
• Деммель Дж. Вычислительная линейная алгебра. — М.: Мир, 2001.