3.3 QR 方法

对应教材 3.3.1–3.3.3、定理 3.2、习题 9–12。老师课堂未讲，本节按教材补齐，标“教材有、课堂未讲”。 主线：Householder 正交变换 → QR 分解 → 基本 QR 迭代 → 拟上三角化 → 双步位移 QR。

3.3.1 QR 分解

定理 3.2：设 $A\in\mathbb R^{n\times n}$ 非奇异，则存在正交矩阵 $Q$ 和上三角矩阵 $R$（对角元为正），使 $$A=QR,$$ 且分解唯一。

构造（Householder）：对 $A$ 的每一列，用 Householder 矩阵 $H_r=I-2u_ru_r^{\mathrm T}/(u_r^{\mathrm T}u_r)$ 把该列对角线以下元素消为零： $$H_{n-1}\cdots H_2H_1A=R, \qquad Q=H_1H_2\cdots H_{n-1}.$$ $H_r$ 对称正交，$H_r^{-1}=H_r^{\mathrm T}=H_r$。

基本 QR 迭代： $$A_k=Q_kR_k,\qquad A_{k+1}=R_kQ_k=Q_k^{\mathrm T}A_kQ_k.$$ 每个 $A_{k+1}$ 与 $A_k$ 正交相似，特征值不变。若 $A$ 实对称，$A_k$ 收敛到对角矩阵，对角元即特征值；若 $A$ 一般实矩阵，$A_k$ 本质上收敛到分块上三角矩阵，一阶块给实特征值、二阶块给复共轭特征值。

3.3.2 拟上三角化

先用 Householder 相似变换把 $A$ 化为拟上三角矩阵（上 Hessenberg）： $$a_{ij}=0\quad(i\gt j+1).$$ 变换为 $A^{(r+1)}=H_rA^{(r)}H_r$，其中 $H_r$ 只作用在第 $r+1,\dots,n$ 行/列，消去第 $r$ 列第 $r+2$ 行以下的元素。最终 $$A^{(n-1)}=P^{\mathrm T}AP, \qquad P=H_1H_2\cdots H_{n-2}$$ 正交，且与 $A$ 相似。若 $A$ 实对称，拟上三角化后就是三对角矩阵。这样 QR 迭代的每步计算量从 $O(n^3)$ 降到 $O(n^2)$。

3.3.3 带双步位移的 QR 方法

为加速收敛，取两个位移 $s,t$（通常取当前右下 $2\times2$ 块的特征值），构造 $$M=(A_k-sI)(A_k-tI),$$ 对 $M$ 作 QR 分解 $M=QR$，再令 $$A_{k+1}=Q^{\mathrm T}A_kQ.$$ 这就是双步位移 QR；它一次推进两步，且保持实运算（复共轭特征值成对处理）。实际算法还包括：

• 先用 Householder 化拟上三角；
• 对右下角块做“压缩”（deflation），把已收敛的特征值分离出去；
• 用 Givens/Householder 实现 $M$ 的 QR 分解，避免显式形成 $M$。

3.3.4 习题（教材习题 9–12）