数值线代 II · 特征值迭代、移位与残差证据

本页问题：一个向量已经几乎满足特征方程，它对应哪一个特征值？另一段程序把矩阵变得近乎对角，哪些量真的得到了保留？

前置：SVD、QR与后向误差、正交投影、矩阵乘法和浮点舍入。先算清二维方向的竞争，再执行四维矩阵的移位与缩减。

1. 特征对、完整分解与精确表示

特征方程是

实对称矩阵有正交分解 \(A=Q\Lambda Q^T\)。一般实矩阵的特征值可以为复数，特征向量也未必构成一组基。例如

只有一个线性无关的特征向量。因此，一个通用算法不能承诺把所有实矩阵都变成实对角矩阵。

更合适的目标是Schur分解：复数域中 \(A=QTQ^*\)，其中 \(Q\) 酉、\(T\) 上三角；实数域中可取实正交 \(Q\)，但 \(T\) 允许沿对角出现 \(2\times2\) 块。这些块容纳共轭复特征值。LAPACK的分阶段说明也将Schur向量与最终特征向量的计算分开。

为什么常用迭代？因为我们希望在给定成本内得到可靠的近似，并能检查误差。Abel–Ruffini定理排除了五次及以上一般多项式的通用根式公式，并没有排除所有计算模型中的有限步精确表示。代数数可以用多项式及隔离区间等方式表示，特殊矩阵也可以有闭式谱。不能从“没有根式公式”推出“任何精确算法都不可能”。

数值计算通常也不先展开特征多项式再求根：改变矩阵元素和改变多项式系数是不同的扰动模型，后者可能引入不必要的敏感性。保留矩阵结构和正交变换，才方便给计算过程解释误差。

2. Rayleigh商与残差：哪些结论可以直接证明

对非零 \(x\)，Rayleigh商为

取 \(\|x\|_2=1\)，定义 \(r=Ax-\rho x\)。对一般矩阵也有

反过来，任何满足该特征方程的扰动都必须满足 \(\|\Delta A\|_2\ge\|r\|_2\)。因此残差给出了保持这个向量和估计值不变时，最小的非结构矩阵扰动。这里允许任意矩阵扰动，没有要求它仍对称、稀疏或保持物理约束。

若 \(A\) 正规，可用酉基展开

因为 \(\sum_j|c_j|^2=1\)，立即得到

要证明方向接近某一个 \(u_i\)，则需当前估计与其余谱的距离

若该量严格为正，且目标方向是一个单独的特征方向，

这不是把分母随手替换成固定谱隙。\(\operatorname{gap}_i=\min_{j\ne i}|\lambda_j-\lambda_i|\) 以真特征值为中心；当前的 \(\rho\) 可能还没有足够接近它。

实验只对明确的正规矩阵和唯一的目标方向给出该上界。重根、最近谱点打平或复谱没有相应实方向时留空；非正规矩阵仍可计算残差，却不能借用上述酉展开。紧簇中的单个方向可能敏感，而整个簇对应的子空间仍稳定，这是LAPACK误差分析特别区分的两件事。

3. 幂法：竞争的是模长，起点也有决定权

先设 \(A\) 可对角化，并将起点写成

反复乘矩阵得到 \(A^kx_0=\sum_j c_j\lambda_j^kv_j\)。若

则除以 \(c_1\lambda_1^k\) 后，其余系数按 \((\lambda_j/\lambda_1)^k\) 衰减。每轮归一化只改变长度，保留这场方向竞争。

对二维实对称矩阵，在正交特征基中写 \(x_k=\cos\theta_k\,v_1+\sin\theta_k\,v_2\)，就有精确关系

于是“小模长比”对应快收敛，“接近1”对应慢收敛。但要逐项检查条件：

• 若 \(c_1=0\)，精确算术中永远不会产生该方向。不要靠机器舍入“救活”一个本来没有投影的初值，再说理论不需要这一条件。
• 最大的是模长。\(\operatorname{diag}(-3,2)\) 的主方向对应 \(-3\)；向量可能每轮变号，但一维子空间仍可收敛。
• \(\operatorname{diag}(2,-2)\) 的模长打平，一般起点会持续摆动。重复特征值还可能使单个方向根本不唯一。
• 非正规矩阵的展开系数需要用左特征向量理解；右特征向量不正交时，前期行为还会受基的条件数影响。

实验同时保留按规则预期的目标和当前Rayleigh估计最近的谱点。它们不一致时，不能只换一个标签掩盖初值或目标选择的问题。

4. 固定移位反幂法：改变谱的相对大小

选定 \(\mu\notin\sigma(A)\)，解

这里写逆矩阵是理解符号，实际运行解线性系统。每个原特征方向仍保留，其特征值变成 \(1/(\lambda_j-\mu)\)。若最近谱点 \(\lambda_i\) 唯一，且初值在该方向上的系数不为零，就有竞争因子

所以移位靠近目标可以加速。但“靠近”与“正好等于”不同：\(\mu\) 恰为特征值时，线性系统奇异。实验保留这个停止原因，不把失败替换成默认移位。

大问题上固定移位通常允许复用一次LU分解；本页二维求解器逐次显式执行，目的是展示实际消元、主元和求解残差，不能把它的运行时间直接当成库实现的性能比较。

靠近目标时移位矩阵会病态，这并不自动让反幂法失去用途：放大最大的方向正是算法想提取的方向。但仍要记录线性求解误差，而不是从“方向有利”推断每一个返回值都可靠。ALAFF的原始教学推导将这两层分别说明。

5. Rayleigh商迭代：二维模型里能直接看见三次项

现在每轮更新移位 \(\mu_k=\rho(x_k)\)，再解移位系统。对二维实对称矩阵，仍在正交特征基中写 \(x=\cos\theta\,v_1+\sin\theta\,v_2\)。于是

以及

当两分母都不为零时，新向量的系数比满足

靠近 \(v_1\) 时，角度每轮变为原来三次量级；负号只说明在目标方向两侧交替。这给出了“三次局部收敛”的具体来源，不是对所有起点、所有矩阵或所有浮点运行的承诺。\(\theta=\pi/4\) 时两个方向打平，也不在吸引目标的局部邻域。

实际程序需要先判断残差，再决定是否继续解几乎奇异的系统。本实验的状态分开表示：

• 浮点运算得到零残差；
• 相对残差低于明示的浮点停止阈值；
• 移位系统出现零主元，无法继续；
• 迭代预算用尽；
• 幂法的矩阵乘积变成零向量。

前两项都不称作实数数学中的“精确收敛”。在非正规例子中，Rayleigh移位还可能落到一个真特征值上，而当前向量并不是特征向量；此时奇异移位是真失败，不能被小矩阵的漂亮轨迹遮住。

6. QR迭代：对整个基做相似变换

对当前矩阵作 \(A_k=Q_kR_k\)，然后令 \(A_{k+1}=R_kQ_k\)。由于 \(Q_k\) 正交，

若 \(Z_k=Q_0Q_1\cdots Q_{k-1}\)，则精确算术中

因此谱得到保留。再把相似关系与分解关系相乘，可以看到累计的 \(Z_k\) 也与对 \(A_0^k\) 进行QR分解、逐次正交化整组基有关。这就是QR与同时迭代的联系；“暗中在做幂法”仍需要谱模长分离和初始旗标不退化等收敛条件。

对对称矩阵，接近对角化可以帮助读出实特征值。对一般实矩阵，只能期待合适的实Schur块，不能承诺所有非对角元都趋于0。旋转矩阵

的特征值为 \(\pm i\)，本来就没有实特征方向；保留一个实 \(2\times2\) 块不是失败。

浮点实验每轮都保存完整的 \(A_k\) 和累计 \(Z_k\)，并分别报告

三者回答不同的问题：基还正交吗、相似关系偏离多少、当前基与变换后的矩阵是否共同解释原矩阵。对角线尚未收敛时，只把它称为“对角估计”，不直接当成已验收的特征值。

7. 有限步结构化与反复迭代各做什么

稠密一般矩阵通常先通过正交相似变换化为上Hessenberg形；实对称情形可以化为三对角形。先消去大量无关位置，可以让之后的迭代更便宜。

这并不与前面的精确表示讨论矛盾：Hessenberg化本身是有限次消元，通常没有完成本征求解。之后还需移位、迭代、缩减和回代。

实际库使用结构化QR/QL、隐式移位及其他算法组合。本页四维模型明确使用显式Givens QR：每次平面旋转都可单独检查，

它适合学习相似变换的机制，却没有实现大型库的隐式追赶与缓存优化。每次分解的 \(Q\)、\(R\)、旋转参数和实际工作矩阵都保留，不能只画一条预设衰减曲线代替算法。

8. Wilkinson移位与缩减：加速也需要记下修改量

移位QR执行

它仍是正交相似变换。对实对称三对角矩阵，Wilkinson策略在末尾 \(2\times2\) 主块中选靠近右下角的特征值。若主块是 \(\begin{pmatrix}a&b\\b&d\end{pmatrix}\)，令 \(\delta=(a-d)/2\)，可用避免不必要相消的形式

\(b=0\) 时直接取 \(\mu=d\)。这里只求一个局部块的谱，用它帮助更大的活动块分离。

若整个问题本来只有 \(2\times2\)，该移位已经取得全矩阵的一个本征值；它的极快消去不能用来证明一般渐近收敛阶。因此下面使用四维链。

也不能无条件说Wilkinson策略始终三次收敛。已有原始研究给出严格二次收敛的情形；本页不把有限运行曲线当作普适定理。Leite、Saldanha与Tomei的结果说明了这个边界。

缩减将足够小的尾部耦合设为0，把已分离的本征值从活动问题中移出。这是有记录的近似修改。理想三对角结构中，删掉一对对称元素 \(e\) 引入

实验更谨慎地检查尾行与尾列的全部连接，将实际删掉的矩阵逐项保存。阈值明确按相邻对角元的尺度与机器精度设置，每次删除的范数以及累计预算另列；相似误差中还含浮点运算误差，不能说它完全等于缩减预算。

9. 四维近邻链：参考谱可以独立推出来

考虑

它可以代表一个只有近邻耦合的四自由度线性模型。令 \(v_j=\sin(j\theta)\)，并取边界 \(v_0=v_5=0\)。由正弦加法公式，

因此 \(\theta=k\pi/5\)，\(k=1,2,3,4\)，给出全部特征值。记 \(\phi=(1+\sqrt5)/2\)，升序参考谱为

这样，参考答案没有借用另一个迭代算法。本页同时改变 \(c\)、\(b\) 和共同尺度，并运行两种QR策略。

重点观察三个边界：

• \(b=0\)：矩阵已经对角，重复特征值不妨碍报告谱，却不支持唯一的单个方向。
• \(c=0\)：谱成正负对，最大模长打平。无移位过程可能持续无法完成缩减，不能因为数值有限就显示“已收敛”。
• 很小的 \(b\)：特征值聚集，算法残差和单个向量精度必须分开；还应检查缩减阈值与输入尺度的关系。

把矩阵同时乘 \(10^s\) 后，原始残差和特征值也乘该尺度，适当归一化的量应基本保持。这比只看“有多少个零”更有解释力。

10. 非正规矩阵：一个很小的扰动可以搬动谱

取

特征值一直是2和1，但当 \(\gamma\) 很大时，两条右特征方向越来越接近平行。

对给定复数 \(z\)，矩阵离“以 \(z\) 为特征值”的矩阵集合有多远？在不限制扰动结构的谱范数下，答案是

下界来自 \((A-zI)v=-Ev\)：对单位 \(v\)，左边的范数至少为最小奇异值。取达到最小值的右奇异向量 \(v\)，再构造

就达到下界。于是“小残差”可以理解为：\(z\) 是某个邻近矩阵的特征值，而不一定已经接近原谱。

本实验只展示实轴上的伪谱截面，没有把一条曲线冒充整个复平面区域。它逐点计算最小奇异值，给出实际向量和扰动，并核对扰动后的特征方程。

一个可以手算的例子是 \(z=3/2\)。当 \(\gamma\ge0\)，

原谱距离始终为 \(1/2\)，但右式随 \(\gamma\) 增大而变小。第二个表达式避免了大数相减，适合计算。\(\gamma=0\) 时矩阵正规，最小奇异值恰等于到谱的距离；这是同一个实验中的对照。

11. 四道迁移题与完整答案

题一：为什么没有起始投影时，幂法可能给出另一个正确特征对？

对 \(A=\operatorname{diag}(3,1)\)，分别取 \(x_0=(1,1)^T\) 与 \(x_0=(0,1)^T\)。写出第 \(k\) 次乘法前的向量，解释小残差能否证明找到了最大模特征值。

题二：从系数比推出Rayleigh商迭代的三次关系

设对称矩阵有两个不同特征值，当前单位向量的系数为 \(\cos\theta\) 和 \(\sin\theta\)。推导 \(\tan\theta_{\rm new}=-\tan^3\theta\)，并说明 \(\theta=0\) 与 \(\theta=\pi/4\) 为什么需要单独处理。

题三：一次缩减究竟修改了多少矩阵？

将实对称矩阵中的一对耦合 \(A_{ij}=A_{ji}=e\) 设为0，其余元素不动。求修改矩阵的谱范数和Frobenius范数，并解释为什么应记录修改量。

题四：用一个向量证明“远离原谱也可以小残差”

对 \(A_\gamma\) 与 \(z=3/2\)，说明最小奇异值表达式怎样给出一个实际矩阵扰动；为什么 \(\gamma=0\) 是有用的对照？

12. 把停止规则带进更大的问题

完成本页后，应该能先回答“要找哪一个谱点或子空间”，再选择算法；能区分原始残差、相对残差、方向误差、谱估计与实际输入扰动；能解释为什么缩减和浮点停止需要记录，为什么非正规问题需要额外的敏感性信息。

下一讲进入Krylov子空间、CG与GMRES。那里不能显式保存完整大矩阵的分解，但“每个结果对应什么残差、满足哪些条件”的阅读习惯仍然保留。需要回顾范数与后向误差时，返回数值线代 I。