QR分解

QR分解是一种矩阵分解，将矩阵表示为 $A=QR$，其中 $Q$ 的列向量标准正交，而 $R$ 根据矩阵的维数为上三角矩阵或上梯形矩阵。对于实矩阵，方阵 $Q$ 是正交矩阵；对于复矩阵，它是酉矩阵。QR分解是数值线性代数的核心工具之一，它在保持欧氏长度不变的同时，将涉及一般矩阵的问题转化为涉及三角矩阵的问题。(netlib.org)

定义与形式

对于 $A\in\mathbb{R}^{m\times n}$，若 $m\ge n$，其完整QR分解具有如下形式：

其中 $Q$ 为 $m\times m$ 矩阵，$R_1$ 为 $n\times n$ 上三角矩阵。这里，$Q^T$ 表示矩阵转置，$I_m$ 是单位矩阵。将 $Q$ 分块为 $Q=[Q_1\ Q_2]$，便得到约化QR分解，也称薄QR分解或经济型QR分解：

其中 $Q_1$ 的大小为 $m\times n$。约化形式省略了重构 $A$ 时不需要的列。(netlib.org)

对于复数域上的矩阵，转置要替换为共轭转置，记作 $Q^*$。宽矩阵也存在QR分解，此时完整分解中的因子 $R$ 为上梯形矩阵：主对角线下方的元素均为零，但列数多于行数。(netlib.org)

每个满足 $m\ge n$ 的实矩阵都存在QR分解，包括秩亏矩阵。若其列向量线性无关，则要求 $R_1$ 的所有对角元素为正后，约化分解是唯一的。若无此约定，$Q_1$ 中的列与 $R_1$ 中相应的行可以同时改变符号。当 $m>n$ 时，完整矩阵 $Q$ 中其余的列并不唯一。(buttenschoen.ca)

几何解释

对于列满秩矩阵，$Q_1$ 的列向量构成 $A$ 的列向量的线性包的一组标准正交基。以 $a_j$ 和 $q_i$ 表示相应的列向量，则有

因此，$R_1$ 记录了原矩阵各列向量在这组标准正交基下的坐标。其三角结构反映了这样一个事实：原矩阵的前 $j$ 个列向量可以用前 $j$ 个基向量表示。系数满足 $r_{ij}=q_i^*a_j$，即一个内积。(buttenschoen.ca)

由此可知，$Q_1Q_1^*$ 表示到 $A$ 的列空间上的正交投影。因此，QR分解将由 $Q_1$ 表示的该空间的几何结构，与由 $R_1$ 表示的坐标关系分离开来。(buttenschoen.ca)

计算方法

格拉姆—施密特正交化通过减去向量在此前得到的标准正交向量上的投影，并将剩余向量归一化，来构造QR分解。在浮点运算中，经典格拉姆—施密特方法可能严重丧失正交性。改进的格拉姆—施密特方法重新安排了投影运算，通常表现更好，但对于要求较高的问题，仍可能需要再次正交化。(cs.cornell.edu)

**豪斯霍尔德变换**逐列消去对角线下方的元素。在实数运算中，反射矩阵可以写为

一系列这样的正交反射矩阵将 $A$ 变换为三角形式，其乘积确定 $Q$。由于具有良好的数值稳定性，豪斯霍尔德QR分解是处理稠密矩阵的标准方法。(buttenschoen.ca)

**吉文斯旋转**每次作用于两个坐标，以消去指定元素。当逐个置零的操作适合矩阵结构，或需要更新已有分解时，这种方法很有用。(cs.cornell.edu)

对于满足 $m\ge n$ 的稠密实 $m\times n$ 矩阵，若不显式构造 $Q$，豪斯霍尔德分解约需 $2mn^2-\frac23n^3$ 次浮点运算。因此，其计算复杂性为 $O(mn^2)$。实际实现通常以反射向量的形式隐式存储 $Q$；分块算法则利用矩阵与矩阵的运算，成组应用反射变换。(cs.utexas.edu)

最小二乘问题

QR分解可用于求解普通最小二乘法和线性回归所涉及的超定问题：

当矩阵列满秩时，由欧氏范数的正交不变性可得

第二项与 $x$ 无关。因此，唯一的最小化解满足三角线性方程组

可通过回代求得。残差范数为 $\|Q_2^*b\|_2$，因此无需显式构造残差向量即可计算。(netlib.org)

与求解正规方程 $A^*Ax=A^*b$ 不同，直接使用QR分解不会构造 $A^*A$。当 $A$ 列满秩时，$A^*A$ 的谱条件数满足 $\kappa_2(A^*A)=\kappa_2(A)^2$。避免条件数平方有助于防止额外的数值困难，但QR分解无法消除原问题对扰动的敏感性。(cs.cornell.edu)

选主元与数值秩

列主元QR分解引入置换矩阵 $P$：

通过重新排列各列，较强的独立方向得以优先显现。当矩阵的秩不确定时，将 $R$ 分成前部条件良好的块和后部数值较小的块，有助于估计数值秩。这一估计依赖于容差和缩放方式；普通的列主元选取并不能在所有情况下替代奇异值分解。在秩亏最小二乘问题中，通过带主元的QR分解得到的基本解不一定是最小范数解。(netlib.org)

与特征值算法的联系

QR算法反复使用QR分解来计算特征值与特征向量。其基本的无位移迭代步骤为

由于 $A_{k+1}=Q_k^*A_kQ_k$，相邻迭代矩阵之间满足矩阵相似关系，因此具有相同的特征值。实际实现会引入位移，并利用矩阵的结构形式，加快向舒尔分解的收敛。因此，分解 $A=QR$ 是迭代QR算法的基本组成步骤，而不是与该算法相同的操作。(cs.cornell.edu)