QR分解

QR分解（QR Decomposition），又称QR因式分解，是将一个实矩阵或复矩阵分解为一个正交矩阵（或酉矩阵）$Q$与一个上三角矩阵$R$的乘积的矩阵分解方法。具体而言，对任意$m \times n$（$m \geq n$）的满秩实矩阵$A$，存在分解$A = QR$，其中$Q$为$m \times m$的正交矩阵（满足$Q^{\mathsf{T}}Q = I$），$R$为$m \times n$的上三角矩阵。QR分解是数值线性代数的核心工具之一，在最小二乘问题的求解、特征值计算和信号处理等领域有着广泛而深入的应用。

1. QR分解的数学定义

1.1 满秩情形

设$A \in \mathbb{R}^{m \times n}$且$\operatorname{rank}(A) = n \leq m$，则存在正交矩阵$Q \in \mathbb{R}^{m \times m}$与上三角矩阵$R \in \mathbb{R}^{m \times n}$，使得：

其中$R_1 \in \mathbb{R}^{n \times n}$是非奇异上三角矩阵。若将$Q$划分为$Q = [Q_1 \; Q_2]$，其中$Q_1 \in \mathbb{R}^{m \times n}$，则可得薄QR分解（Thin QR Decomposition）：$A = Q_1 R_1$。薄QR分解在计算上更为高效，因为$Q_1$仅保留与列空间相关的正交基，而舍弃了零空间部分。

1.2 复矩阵情形

对于复矩阵$A \in \mathbb{C}^{m \times n}$，将其分解为$A = QR$，其中$Q$为酉矩阵（满足$Q^*Q = I$），$R$为上三角矩阵。所有实数的推导均可通过将共轭转置替换转置、将正交矩阵替换为酉矩阵而自然地推广到复数域。复数域上的QR分解在量子计算和通信信号处理中尤为重要。

2. QR分解的计算方法

2.1 Gram–Schmidt正交化

经典Gram–Schmidt（CGS）过程最早由Jørgen Gram和Erhard Schmidt提出，其核心思想是对矩阵$A$的列向量逐次进行正交化与归一化。设$A = [a_1, a_2, \dots, a_n]$，算法如下：令$u_1 = a_1$，$q_1 = u_1 / \|u_1\|$；对于$k = 2, \dots, n$，计算$u_k = a_k - \sum_{i=1}^{k-1} (q_i^{\mathsf{T}} a_k) q_i$，然后$q_k = u_k / \|u_k\|$。最终$Q = [q_1, \dots, q_n]$，$R$的第$(i,j)$元若$i > j$则为零，否则为$q_i^{\mathsf{T}} a_j$。

然而，经典Gram–Schmidt过程在数值上不稳定的缺陷——由于舍入误差的累积，$Q$的列可能严重失去正交性。改进后的改进Gram–Schmidt（MGS）算法通过逐次从剩余向量中减去已正交化方向的投影，显著提升了数值稳定性，使其成为实际计算中更受青睐的选择。

2.2 Householder反射

Householder反射法由Alston Scott Householder于1958年提出，是目前最广泛使用的QR分解实现方式。其基本思想是利用Householder矩阵（初等反射矩阵）$H = I - 2vv^{\mathsf{T}} / (v^{\mathsf{T}} v)$将矩阵$A$的列逐次化为上三角形式。具体而言，第一枚Householder反射器将$A$的第一列中除首元素外的所有元素置零；随后作用于剩余子矩阵，将第二列的次对角线以下元素置零；依次类推，经过$n$步后得到上三角矩阵$R$，而全部Householder反射器的乘积构成$Q^{\mathsf{T}}$。

该方法的时间复杂度为$O(2mn^2 - \frac{2}{3}n^3)$，数值上高度稳定，且$Q$始终精确保持正交性（机器精度以内），因此成为LAPACK等主流数值线性代数库的标准实现方法。

2.3 Givens旋转

Givens旋转（又称Jacobi旋转）通过构造平面旋转矩阵来有选择地将特定位置元素化为零。一个Givens旋转矩阵$G(i, k, \theta)$仅在$(i,i)$、$(i,k)$、$(k,i)$、$(k,k)$四个位置非平凡，形如：

\cos\theta \& \sin\theta \\ -\sin\theta \& \cos\theta

通过串联一系列Givens旋转，可以逐步将$A$转化为上三角矩阵。Givens旋转特别适合处理稀疏矩阵和并行计算场景，因为每个旋转仅影响两行元素，易于并行化和流水线化。在FPGA和GPU加速的矩阵运算中，Givens旋转往往比Householder方法更具优势。

3. QR分解的主要应用

3.1 线性最小二乘问题

QR分解在最小二乘问题中扮演着核心角色。考虑超定线性系统$Ax \approx b$（$m > n$），其最小二乘解为极小化$\|Ax - b\|_2$的$x$。将$A = QR$代入，由于正交变换保持欧几里得范数，问题化为$\|Rx - Q^{\mathsf{T}}b\|_2$的最小化。由于$R$的上三角结构，该问题可通过回代（Back Substitution）高效求解：

与直接求解正规方程（$A^{\mathsf{T}}Ax = A^{\mathsf{T}}b$）相比，QR方法避免了$A^{\mathsf{T}}A$的条件数平方放大效应，数值稳定性显著更优。特别地，当$A$近于病态时，正规方程的精度损失可能极其严重，而QR分解则稳健得多。

3.2 特征值计算

QR算法（Francis算法，1961年）是计算稠密矩阵全部特征值最经典且最可靠的方法之一。其基本迭代为：对矩阵$A_k$进行QR分解$A_k = Q_k R_k$，然后令$A_{k+1} = R_k Q_k$。反复迭代后，$A_k$收敛于上三角形式（实Schur形式），对角元即为特征值。在实际实现中，通常先通过Householder变换将矩阵压缩为Hessenberg型以降低每步迭代的计算成本，再配合Wilkinson移位技术加速收敛。QR算法至今仍是EISPACK和LAPACK中特征值求解器的基石。

3.3 信号处理与通信

在多输入多输出（MIMO）无线通信系统中，QR分解被广泛应用于检测算法的设计。V-BLAST（Vertical-Bell Labs Layered Space-Time）架构中，接收端通过对信道矩阵进行QR分解，将多天线信号检测问题转化为逐层干扰消除：首先处理具有最高信噪比的信号层，减去其影响后再处理下一层。这种基于QR的逐次干扰消除算法在计算复杂度和检测性能之间取得了良好的平衡。此外，在自适应滤波和波束成形中，QR分解递归最小二乘（QR-RLS）算法通过直接对数据矩阵进行QR更新，避免了传统RLS算法中协方差矩阵的显式求逆，具备卓越的数值稳定性和并行化潜力。

3.4 条件数估计与秩确定

矩阵的条件数$\kappa(A) = \|A\| \cdot \|A^{-1}\|$衡量了线性系统对输入误差的敏感程度。通过QR分解并结合列选主元策略（Column Pivoting），可以同时获得矩阵的秩估计和条件数近似。列选主元QR分解（QR with Column Pivoting，即QRCP）产生分解$A \Pi = QR$，其中$\Pi$为置换矩阵，$R$的对角元按绝对值从大到小排列。若$R$的末尾若干对角元显著小于其他对角元，则可判定矩阵近似秩亏。该技术在信号处理的子空间识别和系统辨识中有着关键应用。

4. QR分解的变体与推广

4.1 广义QR分解

对于两个矩阵$A \in \mathbb{R}^{m \times n}$和$B \in \mathbb{R}^{p \times n}$（$m \geq n$，$p \geq n$），广义QR分解（GQRD）旨在将$A$和$B$同时分解为$A = QR$和$B = QTZ$的形式，其中$Q$和$T$为正交矩阵，$R$和$Z$为上三角矩阵。GQRD是广义特征值问题（$Ax = \lambda Bx$）和广义最小二乘问题（Generalized Least Squares）的基础工具。在计量经济学中，GLS估计量的高效计算往往需要借助GQRD来避免对协方差矩阵的显式构造和求逆。

4.2 符号与精确QR分解

在一些符号计算和密码学场景中，需要精确（无舍入误差）的QR分解。通过使用整数高斯消去和有理数算术，可以在整数环或代数数域上构造精确的QR分解。这类方法在计算代数几何和数论中偶有应用，但因计算成本极高，通常仅在$m$和$n$均较小的情形下才可行。此外，利用Python的SymPy或Mathematica等符号计算工具，可以演示QR分解在精确算术下的代数性质，为教学和理论分析提供便利。

4.3 分块QR分解

为适应现代计算机的内存层次结构（缓存、主存、磁盘三级存储），分块QR分解（Block QR Decomposition）将矩阵划分为若干子块，逐块进行QR分解和更新。分块算法大幅提高了计算的数据局部性，减少了内存带宽的瓶颈效应。在分布式计算框架中（如ScaLAPACK和Elemental），分块QR分解是实现大规模分布式矩阵运算的关键技术。典型的做法是将$A$分块为$A = [A_{11} \; A_{12}; A_{21} \; A_{22}]$，先对左块进行QR分解，再通过正交变换更新右块，如此递归即可实现高效的并行QR分解。

5. 数值稳定性与精度分析

QR分解的数值稳定性是决定其实际可用性的核心指标。Householder反射法被公认为后向稳定的——即计算得到的$\hat{Q}$和$\hat{R}$满足$\|A - \hat{Q}\hat{R}\| = O(\varepsilon) \|A\|$，其中$\varepsilon$为机器精度。改进Gram–Schmidt方法虽不如Householder方法稳定，但已接近后向稳定的水平，且在某些特定架构上可能具有速度优势。Givens旋转的稳定性介于二者之间，但其优势在于可以独立地对行对进行操作。总的来说，在绝大多数实际工程应用中，Householder反射法是默认的首选方案。

值得注意的是，即使QR分解本身是稳定的，将其用于求解最小二乘问题时，结果的误差依然受制于矩阵的条件数$\kappa(A)$。如果$\kappa(A)$极大（即矩阵病态），则任何数值方法都无法避免解的巨大相对误差——这是问题的固有属性，而非算法的缺陷。在实践中，QR分解结合截断奇异值分解（Truncated SVD）或Tikhonov正则化，可以有效缓解病态问题的难度。

6. 历史与发展

QR分解的思想渊源可以追溯到Gram–Schmidt正交化过程（1883年由Gram发表，1907年由Schmidt完善），但"QR分解"这一名称和系统理论框架直到20世纪50年代末至60年代初才真正成形。1961年，J. G. F. Francis独立发表了将QR分解用于特征值计算的QR算法，同时Vera Kublanovskaya也独立提出了类似的思想。Householder反射法发表于1958年，Givens旋转的历史则可追溯到Jacobi在1846年关于对称矩阵对角化的开创性工作。随着20世纪70年代LAPACK和EISPACK等数值库的推广，QR分解成为科学计算的标准标配工具。

进入21世纪，QR分解的研究持续向大规模计算和新型计算架构延伸。在GPU和TPU上实现的高通量QR分解支撑着现代机器学习的部分底层运算；量子QR分解的理论框架也在量子算法领域受到关注。作为一个历经半个多世纪考验的经典算法，QR分解凭借其理论优雅性、数值稳定性和应用广泛性，始终是计算数学的基石之一。

7. 参考文献

• Golub, G. H., \& Van Loan, C. F. (2013). *Matrix Computations* (4th ed.). Johns Hopkins University Press.
• Trefethen, L. N., \& Bau, D. (1997). *Numerical Linear Algebra*. SIAM.
• Francis, J. G. F. (1961). The QR transformation: A unitary analogue to the LR transformation. *The Computer Journal*, 4(3), 265–271.
• Householder, A. S. (1958). Unitary triangularization of a nonsymmetric matrix. *Journal of the ACM*, 5(4), 339–342.
• Stewart, G. W. (1998). *Matrix Algorithms, Volume I: Basic Decompositions*. SIAM.
• Demmel, J. W. (1997). *Applied Numerical Linear Algebra*. SIAM.