QR-разложение матриц

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

История

Идея разложения матрицы на ортогональную и треугольную части восходит к работам немецкого математика Карла Фридриха Гаусса (начало XIX века), который использовал метод ортогонализации при решении задач астрономии и геодезии. Однако современное название и систематическое применение QR-разложение получило в середине XX века, с развитием численных методов и появлением компьютеров. В 1950-х годах американский математик Джон Тодд и его коллеги предложили алгоритмы, основанные на QR-декомпозиции, для решения задач наименьших квадратов. В 1961 году австралийский математик Джон Г. Ф. Фрэнсис независимо разработал QR-алгоритм для вычисления собственных значений, который стал одним из наиболее эффективных методов в этой области. В Советском Союзе значительный вклад в теорию и практику QR-разложения внесли работы В. Н. Кублановской, В. В. Воеводина и других учёных.

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

Пусть A — матрица размером \( m \times n \) (где \( m \ge n \)) с действительными или комплексными элементами. QR-разложением называется представление:

\[ \mathbf{A} = \mathbf{Q} \mathbf{R} \]

где:

• Q — матрица размером \( m \times m \) (или \( m \times n \) в «экономной» форме), столбцы которой образуют ортонормированный базис (то есть \( \mathbf{Q}^T \mathbf{Q} = \mathbf{I} \) для действительных матриц или \( \mathbf{Q}^* \mathbf{Q} = \mathbf{I} \) для комплексных);
• R — матрица размером \( m \times n \) (или \( n \times n \) в экономной форме), которая является верхнетреугольной (все элементы ниже главной диагонали равны нулю).

Свойства

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

Методы вычисления

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

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

Классический метод ортогонализации Грама — Шмидта (и его модифицированная версия) последовательно строит ортонормированный базис столбцов матрицы A. Столбцы Q получаются ортогонализацией столбцов A, а элементы R — коэффициенты разложения. Модифицированный метод Грама — Шмидта (MGS) численно более устойчив, чем классический, но всё же уступает по точности другим методам.

Преобразования Хаусхолдера (отражения)

Наиболее распространённый метод в вычислительной практике. Основан на применении к матрице A последовательности ортогональных преобразований — отражений Хаусхолдера. Каждое отражение обнуляет все элементы ниже диагонали в текущем столбце. Матрица Q не строится явно, а представляется в виде произведения отражений, что экономит память и время. Этот метод обладает высокой численной устойчивостью.

Вращения Гивенса (вращения)

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

Виды QR-разложения

Полное и экономное разложение

• Полное разложение: Q — квадратная матрица \( m \times m \), R — прямоугольная \( m \times n \). Нижние \( m-n \) строк R состоят из нулей.
• Экономное разложение (thin QR): Q — матрица \( m \times n \) с ортонормированными столбцами, R — квадратная верхнетреугольная \( n \times n \). Используется, когда \( m \gg n \), так как требует меньше памяти.

QR-разложение с перестановками

В некоторых случаях (например, для вырожденных или плохо обусловленных матриц) применяется QR-разложение с перестановками столбцов (QRP). В этом случае A P = Q R, где P — матрица перестановок. Это позволяет улучшить численную устойчивость и выделить линейно независимые столбцы.

Применение

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

Для квадратной системы A x = b с невырожденной матрицей A решение сводится к последовательному решению двух систем:

1. Q y = b (откуда y = Q\(^T\) b);
2. R x = y (решается обратной подстановкой, так как R — верхнетреугольная).

Этот метод устойчивее, чем метод Гаусса, особенно для плохо обусловленных матриц.

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

Для переопределённых систем (\( m > n \)) задача минимизации \( \| \mathbf{A} \mathbf{x} - \mathbf{b} \|_2 \) решается с помощью QR-разложения. Решение x находится из системы R x = Q\(^T\) b, где Q и R — экономное разложение. Этот подход используется в регрессионном анализе, обработке сигналов и геодезии.

Вычисление собственных значений (QR-алгоритм)

QR-алгоритм — итерационный метод для нахождения всех собственных значений квадратной матрицы. На каждом шаге выполняется QR-разложение текущей матрицы, а затем перемножение R и Q в обратном порядке. Со временем матрица сходится к верхней треугольной форме (или к блочно-диагональной), на диагонали которой находятся собственные значения. Модификации алгоритма (с предварительным приведением к форме Хессенберга, сдвигами) являются основой большинства современных программных библиотек для вычисления собственных значений.

Сингулярное разложение (SVD)

QR-разложение используется как вспомогательный шаг при вычислении сингулярного разложения матриц. Например, в алгоритме Голуба — Райнша.

Другие применения

• Решение задач линейного программирования.
• Обработка изображений и сжатие данных.
• В машинном обучении: в методах главных компонент (PCA) и регрессии.
• В квантовой механике и теории управления.

Пример

Рассмотрим матрицу:

\[ \mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix} \]

Её QR-разложение (экономное, с помощью метода Грама — Шмидта) даёт:

\[ \mathbf{Q} = \begin{pmatrix} \frac{1}{\sqrt{3}} & 0 \\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} \end{pmatrix}, \quad \mathbf{R} = \begin{pmatrix} \sqrt{3} & 2\sqrt{3} \\ 0 & \sqrt{2} \end{pmatrix} \]

Проверка: \(\mathbf{Q} \mathbf{R} = \mathbf{A}\).

Реализация в программном обеспечении

QR-разложение реализовано во всех основных системах компьютерной математики и библиотеках:

• MATLAB: функция qr.
• Python (NumPy/SciPy): numpy.linalg.qr, scipy.linalg.qr.
• Julia: qr.
• R: qr.
• LAPACK: подпрограммы xGEQRF, xORGQR и другие.

Критика и ограничения

• Для очень больших и разреженных матриц QR-разложение может быть менее эффективным, чем итерационные методы (например, метод сопряжённых градиентов).
• Метод Грама — Шмидта в классической форме численно неустойчив; требуется использование модифицированной версии.
• Для матриц с высокой степенью вырожденности QR-разложение может давать неточные результаты без использования перестановок.

Интересные факты

• QR-алгоритм для вычисления собственных значений был независимо открыт в 1961 году Джоном Фрэнсисом (Великобритания) и Верой Кублановской (СССР). В советской литературе он долгое время назывался «алгоритмом Кублановской — Фрэнсиса».
• QR-разложение лежит в основе алгоритма «сдвига» для ускорения сходимости QR-алгоритма.
• В некоторых приложениях (например, в телекоммуникациях) используется «разложение по сингулярным числам» (SVD), которое может быть получено из QR-разложения.