QR分解

1. QR分解的定义

1.1 定义

设 $A$ 为 $m\times n$ 矩阵（$m\ge n$），若 $A$ 可以分解为：

$A=QR$

其中 $Q$ 为 $m\times n$ 矩阵，其列向量构成标准正交组（$Q^{T}Q=I_n$），$R$ 为 $n\times n$ 上三角矩阵，则称为 $A$ 的 QR 分解（瘦型 QR 分解）。

完全型 QR 分解：$A=QRP$，其中 $Q$ 为 $m\times m$ 正交矩阵，$R$ 为 $m\times n$ 上梯形矩阵。

1.2 存在条件

定理：若 $A$ 的列向量线性无关（$r(A)=n$），则 $A$ 的 QR 分解存在。

1.3 唯一性

当 $R$ 的对角线元素为正时，QR 分解唯一。

2. Gram-Schmidt 方法

2.1 方法

对 $A$ 的列向量 ${\mathbf{a}}_1,{\mathbf{a}}_2,\dots ,{\mathbf{a}}_n$ 进行施密特正交化：

${\mathbf{q}}_1=\frac{{\mathbf{a}}_1}{\Vert {\mathbf{a}}_1\Vert }$

${\tilde{\mathbf{q}}}_k={\mathbf{a}}_k-{\sum }_{j=1}^{k-1}({\mathbf{a}}_k,{\mathbf{q}}_j){\mathbf{q}}_j,{\mathbf{q}}_k=\frac{{\tilde{\mathbf{q}}}_k}{\Vert {\tilde{\mathbf{q}}}_k\Vert }$

则 $Q=({\mathbf{q}}_1,{\mathbf{q}}_2,\dots ,{\mathbf{q}}_n)$，$R=Q^{T}A$。

$R$ 的元素：$r_{ij}={\mathbf{q}}_i^T{\mathbf{a}}_j$（$i\le j$），$r_{ij}=0$（$i>j$）。

2.2 示例

对 $A=\left(\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right)$ 进行 QR 分解。

${\mathbf{a}}_1=(1,1,1{)}^T$，${\mathbf{a}}_2=(1,2,3{)}^T$

${\mathbf{q}}_1=\frac{1}{\sqrt{3}}(1,1,1{)}^T$

${\tilde{\mathbf{q}}}_2=(1,2,3{)}^T-\frac{6}{3}(1,1,1{)}^T=(-1,0,1{)}^T$

${\mathbf{q}}_2=\frac{1}{\sqrt{2}}(-1,0,1{)}^T$

$Q=\left(\begin{array}{cc}1/\sqrt{3}& -1/\sqrt{2}\\ 1/\sqrt{3}& 0\\ 1/\sqrt{3}& 1/\sqrt{2}\end{array}\right)$

$R=Q^{T}A=\left(\begin{array}{cc}\sqrt{3}& 2\sqrt{3}\\ 0& \sqrt{2}\end{array}\right)$

2.3 Gram-Schmidt 方法的数值问题

经典 Gram-Schmidt 方法在数值计算中可能不稳定（舍入误差累积）。改进的 Gram-Schmidt 方法（MGS）更稳定。

改进的 Gram-Schmidt：在每一步中，立即用已正交化的向量消去后续向量中的分量。

3. Householder 变换方法

3.1 Householder 变换

Householder 矩阵（初等反射矩阵）定义为：

$H=I-2\frac{\mathbf{v}{\mathbf{v}}^T}{{\mathbf{v}}^T\mathbf{v}}$

其中 $\mathbf{v}$ 为非零向量。

3.2 性质

1. $H$ 是对称矩阵：$H^T=H$
2. $H$ 是正交矩阵：$H^{T}H=I$
3. $H$ 是对合的：$H^2=I$
4. $|H|=-1$
5. 几何意义：$H\mathbf{x}$ 是 $\mathbf{x}$ 关于超平面 ${\mathbf{v}}^T\mathbf{x}=0$ 的反射

3.3 构造 Householder 变换

给定向量 $\mathbf{x}$，要使 $H\mathbf{x}=\alpha {\mathbf{e}}_1$：

$\mathbf{v}=\mathbf{x}-\alpha {\mathbf{e}}_1$

其中 $\alpha =-\text{sign}(x_1)\Vert \mathbf{x}\Vert$（选择符号以避免相消）。

3.4 QR 分解的 Householder 方法

步骤：

1. 构造 $H_1$ 使 $H_{1}A$ 的第一列除第一个元素外全为零
2. 对 $H_{1}A$ 的右下子矩阵重复上述过程
3. 最终 $H_{n-1}\cdots H_2{H}_{1}A=R$（上三角）
4. $Q=H_1{H}_2\cdots H_{n-1}$

3.5 示例

对 $A=\left(\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right)$ 用 Householder 方法进行 QR 分解。

第一列 ${\mathbf{a}}_1=(1,1,1{)}^T$，$\Vert {\mathbf{a}}_1\Vert =\sqrt{3}$

$\mathbf{v}=(1,1,1{)}^T-(-\sqrt{3},0,0{)}^T=(1+\sqrt{3},1,1{)}^T$

$H_1=I-2\frac{\mathbf{v}{\mathbf{v}}^T}{{\mathbf{v}}^T\mathbf{v}}$

$H_{1}A$ 的第一列变为 $(-\sqrt{3},0,0{)}^T$，对第二列做相应变换。

4. Givens 旋转方法

4.1 Givens 旋转

Givens 旋转矩阵 $G(i,j,\theta )$ 在 $i,j$ 平面上做旋转：

$G=\left(\begin{array}{ccccc}1& & & & \\ & \cos \theta & & -\sin \theta & \\ & & 1& & \\ & \sin \theta & & \cos \theta & \\ & & & & 1\end{array}\right)$

4.2 特点

• Givens 旋转只改变两个分量
• 适合稀疏矩阵（只消去特定元素）
• 可以并行化

4.3 与 Householder 的比较

5. QR 分解的应用

5.1 解最小二乘问题

$\min \Vert Ax-b{\Vert }^2$：$A=QR$，$x=R^{-1}{Q}^{T}b$

5.2 QR 算法求特征值

迭代格式：$A_k=Q_k{R}_k$，$A_{k+1}=R_k{Q}_k$

$A_k$ 收敛于上三角矩阵（Schur 形），对角线元素为特征值。

5.3 解线性方程组

$Ax=b$：$QRx=b$，$Rx=Q^{T}b$

5.4 矩阵的列空间

$Q$ 的前 $r$ 列构成 $A$ 的列空间的标准正交基。