秩一谱更新的久期方程与消去

更新 $\rho z{z}^{\ast }$ 只读取一个数 $z^{\ast }x$，再沿 $z$ 送回。如果某个旧特征空间中的向量与 $z$ 正交，更新对它为零，它就可以原样保留。重根空间中只可能有一个方向被这一项触及。

剩下的方向相互耦合，但其全部新谱可由一条有理曲线找出。正更新时，曲线在每两个活动极点之间从负无穷严格升到正无穷，每段恰好穿过零一次。极点是禁止代入的位置，不是待接受的根；删掉的极点则已不再是禁止位置。

图中的绿色谱点来自不变方向，蓝色空心刻度表示活动极点，红色短区间才是求根所得的包围。它们承担不同角色，不能把同一横坐标上的标记简单去重。

四阶输入只需求两个新根 ​

取

值 $1$ 的二维空间中保留 $(1,-1,0,0{)}^T/\sqrt{2}$，活动方向是 $(1,1,0,0{)}^T/\sqrt{2}$；第三坐标因 $z_3=0$ 而保留特征值 $3$。在活动基中，剩余矩阵为

于是

两根是 $\alpha =(9-\sqrt{17})/2$、$\beta =(9+\sqrt{17})/2$，完整升序谱为 $(1,\alpha ,3,\beta )$。无需信任小数，下面的有理符号已给出两个隔离区间：

两段都不跨活动极点，且曲线严格递增，所以 $\alpha \in (12/5,5/2)$、$\beta \in (13/2,33/5)$。由这些位置可安全合并成上述排序。最后核对维数为四、迹为 $1+1+3+5+\Vert z{\Vert }^2=13$；保留值与活动根之和也为 $1+3+9=13$。

消去的旧值可以与一个新根重合 ​

换成 $D=\mathrm{diag}(0,1,3)$、$z=(1,0,1{)}^T$、$\rho =2$。中间方向保留 $1$，活动矩阵为 $\left(\begin{array}{cc}2& 2\\ 2& 5\end{array}\right)$，其特征多项式是 $(x-1)(x-6)$。所以完整谱是 $(1,1,6)$。活动函数 $1+2/(0-x)+2/(3-x)$ 在 $x=1$ 有定义且为零；把所有旧值都从候选根中排除会漏掉一份重数。

若同一特征空间中的某个坐标为零，却有其他坐标不为零，应按整个分量的平方范数合并，不能按打印出的单个坐标判断这个重根空间是否完全消去。换基会改变单个分量，而 $a_j$ 不变。

方程、根数与向量来自同一个恒等式 ​

对可逆 $M$，行列式理路行列式Determinant交换含幺环上方阵的交替多线性标量不变量。的多重线性给

可以先提出 $M$，再展开 $I+a{b}^{\ast }$ 的各列：选取两个来自 $a{b}^{\ast }$ 的列就会线性相关，只有零列替换和单列替换贡献，分别为 $1$ 和 $\sum _i{a}_i{\bar{b}}_i$。取 $M=D-xI$，即得 $\det (D+\rho z{z}^{\ast }-xI)=\det (D-xI)f(x)$，这里只在 $x$ 避开极点时使用逆矩阵。

在互异且全部活动的情形，清分母后的特征多项式在 $x=d_j$ 的值为 $\rho |z_j{|}^2\prod _{i\ne j}(d_i-d_j)\ne 0$，所以没有遗漏藏在极点的根。又有

正更新时导数为正，每个内部区间两端极限为 $-\mathrm{\infty },+\mathrm{\infty }$；最后一段从 $-\mathrm{\infty }$ 升向 $1$。最左一段全为正，没有根。负更新时导数和单侧极限反向，外侧根换到最左。所有间隔都已找到一根，合计为矩阵阶数，完成无遗漏与简单性的证明。外侧有限界来自 $\Vert \rho z{z}^{\ast }{\Vert }_2=|\rho |\Vert z{\Vert }_2^2$ 和有序扰动界理路Hermitian 特征值的有序扰动界Weyl eigenvalue perturbation bound · Weyl monotonicity theorem从变分原理证明 Hermitian 特征值按序配对的绝对误差界，并在同一三阶扰动中核验尺度与谱隙。。

若 $\mu$ 是活动根，对应向量可取 $y=(D_{\mathrm{a}\mathrm{c}\mathrm{t}}-\mu I{)}^{-1}w$，因为

它非零，归一化后再通过活动基和 $Q$ 回到原坐标。靠近极点时逆差值很大，浮点实现需要缩放并核验原矩阵残差与向量正交性，不能由这个精确公式自动推出算法稳定。

括根、求值误差与近似消去 ​

在每个无极点的区间中使用二分法理路二分求根法Bisection method以端点异号区间为不变量，给出可验证误差界、对数成本和有限精度停止条件。，正更新时按 $f(c)<0$ 保留右半段，按 $f(c)>0$ 保留左半段；负更新时相反。遇到精确零就记录该根。宽度小于 $2\epsilon$ 时，中点的绝对位置误差至多 $\epsilon$。二分负责缩短已有区间，本页的单调和极限负责证明每段只有一根。

用向外舍入区间算术理路验证数值计算与区间算术Verified numerics · Validated numerics · Interval arithmetic用向外舍入的区间运算构造包含真实结果的可检查外包络，并分辨可靠包含与界的紧致程度。计算 $f(c)$ 时，只有整个结果区间为正或为负，才能作相应删除；若包含零，应提高精度、改选切点或保留当前区间。不能把含极点的区间交给连续二分，也不能把普通小数恰好打印成零当作精确根。

若为了数值消去而把 $z$ 改成 $\tilde{z}$，那已换成邻近矩阵。设 $e=z-\tilde{z}$，则

故其二范数和 Frobenius 范数都不超过 $2\Vert \tilde{z}{\Vert }_2\Vert e{\Vert }_2+\Vert e{\Vert }_2^2$，再乘 $|\rho |$ 才是本次删分量的扰动预算。合并仅仅接近的极点也要加上 $D$ 的改动。只有被精确证明为零或相等的输入，才允许不记误差地消去。

证书基线的工作量与停止责任 ​

已给稠密 $Q$ 时，计算 $z=Q^{\ast }v$ 需 $O(n^2)$ 算术操作。若旧谱已排序，按相等值分组并计算各组平方范数需 $O(n)$；否则先排序，比较成本为 $O(n\log n)$。每组只需储存一个活动方向及其正交补的表示；若还要显式写出全部补基，必须另计这些基向量的形成和输出成本，不能把它混入线性扫描。

剩下 $r$ 个活动极点时，一次 $f(c)$ 求值要累加 $r$ 项，成本为 $O(r)$。严格极限保证在每个活动间隔内能找到异号的有限端点，但极点本身不能求值；应从内部逐步靠近端点直到符号得到认证。外侧也须先用有限谱界找到包围，并检查有限端点是否恰为根。这段初始括根工作可能因根极接近极点而耗费额外精度和次数，不包含在下面的二分轮数中。

已有第 $j$ 个可靠括区，宽度为 $w_j$，要使中点误差至多 $\epsilon >0$，再二分至多

轮。因此全部根的这一阶段需 $O(r\sum _{j=1}^r(1+L_j))$ 算术操作。存储各根区间和活动数据为 $O(n+r)$，不含原来的稠密 $Q$。有理运算的分子分母位数会增长，区间符号认证也可能提高精度；这些位成本不能当成固定字长常数。

只要谱区间已达到宽度要求，求谱任务即可结束。若另外要求特征向量，活动坐标公式对全部 $r$ 个根需要 $O(r^2)$ 次求差和除法；返回原坐标、形成保留方向、检查单位长度与原矩阵残差还须另计。直接对每个新向量乘稠密 $Q$ 或 $B$ 各需 $O(n^2)$，全部 $r$ 个新向量便可达到 $O(n^{2}r)$。只给出根的小数或很小的久期残差，不能冒充已经完成了这些向量验收。