QR 特征值算法

形式陈述 ​

QR 特征值算法输入方阵 $A$、容差和迭代上限，输出复 Schur 上三角形，或实 Schur 的 $1\times 1/2\times 2$ 准上三角块，并可选择累积 Schur 向量。它不是从头对稠密原矩阵反复做完整QR 分解公理库QR 分解QR factorization · QR decomposition · Economy-size QR把长方矩阵分解为正交列与上三角因子，并区分经济型表示、数值算法和秩亏边界。，而分为预处理、隐式迭代与 deflation 三层。

第一层用Householder 反射公理库Householder 反射Householder reflection · Householder transformation用一个向量紧凑表示酉反射，把整段向量化到单一坐标方向，并作为稳定 QR 的基本原语。构造正交或酉相似变换

$$H=Q_0^{\ast }A{Q}_0,$$

使一般矩阵 $H$ 成为上 Hessenberg 形，即 $h_{ij}=0$ 当 $i>j+1$。若 $A$ Hermitian/实对称，结构进一步缩为三对角。预处理一次需要 $\mathrm{\Theta }(n^3)$ 工作，却把之后每个隐式 QR sweep 从稠密 $\mathrm{\Theta }(n^3)$ 降到 $\mathrm{\Theta }(n^2)$；对称三对角情形还能利用更窄结构。

第二层在当前活动块上选择移位 ${\mu }_k$，形式上计算

$$H_k-{\mu }_{k}I=Q_k{R}_k,H_{k+1}=R_k{Q}_k+{\mu }_{k}I.$$

由于

$$H_{k+1}=Q_k^{\ast }{H}_k{Q}_k,$$

每一步都是相似变换，精确算术中保持全部特征值。实际 Francis 实现不显式形成完整 $Q_k$，而用隐式移位制造一个局部 bulge，再以短 Householder 或平面旋转沿矩阵追赶，恢复 Hessenberg 结构。实非对称矩阵常用双移位，使复共轭移位仍能在实算术中推进。

第三层监测次对角元。尺度化判据形如

$$|h_{i+1,i}|\le \tau (|h_{ii}|+|h_{i+1,i+1}|);$$

满足可靠的后向误差条件时把该元素置零，矩阵便分裂成两个更小活动块。复算法最终 deflate 到 $1\times 1$ 块；实算法允许 $2\times 2$ 块容纳共轭复特征值。所有块均完成 deflation、相似残差和正交性达到尺度要求时算法完成；非有限值或活动块超过迭代上限则明确报告未收敛。

Hessenberg 化与典型全部 sweep 的总工作通常为 $\mathrm{\Theta }(n^3)$，若累积 Schur 向量还要记录并应用相似变换。这里没有与输入无关的固定 sweep 数；聚集、多重或高度非正规谱会显著影响收敛与 deflation 时机。

直觉 ​

Hessenberg 预处理先把矩阵压成只比上三角多一条次对角线的形状。QR sweep 随后试图把这条次对角线逐段压小；一旦某处在问题尺度下可以视为零，就把已经分离的特征值块切下来，不再让它参与剩余计算。

移位负责告诉迭代“先靠近哪个谱点”。无移位 QR 的方向筛选速度受特征值模比控制，可能非常慢；从尾部小块估计特征值的 Wilkinson 或 Francis 移位，会把目标变成近奇异方向并显著加速局部收敛。shift、bulge chasing 和 deflation 共同构成实际算法，不能只剩教科书上的两行 $QR$ 公式。

例子与边界 ​

取实对称矩阵

$$A=\left(\begin{array}{cc}0.9975& 0.0043301\\ 0.0043301& 0.9925\end{array}\right),$$

其特征值为 $1$ 与 $0.99$。无移位 QR 的方向分离因子接近 $0.99$，次对角元衰减很慢；尾部 $2\times 2$ 块给出的 Wilkinson 移位选择更接近 $0.99$ 的特征值，在这个二维精确例子中可迅速隔离对应块。这个对照说明加速来自谱位置估计，而不是改变特征值。

基础无移位 QR 对任意矩阵都快速收敛是错误承诺。等模特征值可能阻止一维方向分离，聚集特征值会拖慢 deflation；实矩阵的共轭复对本来就应保留为 $2\times 2$ 块，不能强迫次对角元全部变成零。

非正规矩阵的边界更尖锐。一个很小的次对角元只有在相对邻近对角尺度且满足后向误差判据时才能 deflate；固定绝对 epsilon 可能过早切断强耦合。即使特征值的 Schur 计算后向稳定，个别特征值和特征向量仍可能因原问题病态而对微扰敏感，这属于条件性而非 QR 算法“算错”。

推论与应用 ​

QR factorization 是单步矩阵分解，QR eigenvalue algorithm 是由 Hessenberg 预处理、移位相似迭代和 deflation 组成的全谱流程；两者共享名字和正交变换，却不是同一个任务。对称问题先三对角化，可利用实谱和正交特征向量结构；一般问题则以Schur 形公理库Schur 分解Schur decomposition · Schur triangularization · Real Schur form用酉或正交相似变换把一般矩阵化为上三角或实准上三角形，作为浮点全谱计算的稳定结构目标。作为完成目标。

只求一个目标附近的特征向量时，固定移位逆迭代可以复用一次线性系统分解；需要所有特征值和稳定不变子空间时，QR 算法更合适。成熟 LAPACK 实现还包含多重移位、主动早期 deflation 与异常迭代处理，正文的基础公式必须在这些工程结构中理解。

参考资料

• J. G. F. Francis, “The QR Transformation, Parts I and II,” The Computer Journal 4, 1961–1962.
• Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lectures 24–29.
• LAPACK Users’ Guide, Nonsymmetric Eigenvalue Problems.