QR 特征值算法

形式陈述 ​

QR 特征值算法输入方阵 $A$、容差和迭代上限，计算其特征值理路特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。，其输出接口是Schur 分解理路Schur 分解Schur decomposition · Schur triangularization · Real Schur form用酉或正交相似变换把一般矩阵化为上三角或实准上三角形，作为浮点全谱计算的稳定结构目标。：复 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$ 成为上 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$，形式上计算

由于

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

第三层监测次对角元。一个常见的相邻对角尺度测试形如

它只是代表性的局部测试；实际判据还应考虑活动块尺度、零对角元与下溢的安全处理。满足可靠的后向误差条件时把该元素置零，矩阵便分裂成两个更小活动块。复算法最终 deflate 到 $1\times 1$ 块；实算法允许 $2\times 2$ 块容纳共轭复特征值。所有块均完成 deflation、相似残差和正交性达到尺度要求时算法完成；非有限值或活动块超过迭代上限则明确报告未收敛。

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