迭代精化

形式陈述 ​

考虑可逆系统 $Ax=b$。先在因子精度 $u_f$ 中计算带主元的近似分解，并用同一组因子得到初值 ${\hat{x}}_0$。迭代精化在第 $k$ 轮执行三步：

$$r_k=b-A{\hat{x}}_k,$$$$A{d}_k=r_k,$$$${\hat{x}}_{k+1}={\hat{x}}_k+d_k.$$

第二步不重新分解 $A$，而是复用已有的LU 因子公理库Gaussian 消元与 LU 分解Gaussian elimination · LU factorization · PA equals LU把 Gaussian 消元保存为可复用的带置换 LU 分解，再用三角求解处理一个或多个右端。做两次三角求解。输入包括 $A,b$、可复用因子、残差精度、更新精度、容差和最大轮数；输出应包含精化后的解、残差与后向误差历史、轮数和退出状态。

精确算术下，若 $x_{\ast }$ 是真解，则

$$r_k=A(x_{\ast }-{\hat{x}}_k),$$

所以精确解出校正方程会一次得到全部误差。实际因子只近似 $A$，可把一次校正视为应用近似逆 $B$：

$$e_{k+1}=x_{\ast }-{\hat{x}}_{k+1}\approx (I-BA)e_k.$$

若在相关范数中 $\Vert I-BA\Vert <1$，误差便收缩；矩阵条件性、主元增长和低精度因子误差共同决定这项条件。

残差必须在足以看见当前误差的精度 $u_r$ 中计算。若 $A{\hat{x}}_k$ 与 $b$ 已在低精度中舍入成相同值，低精度残差会错误地变成零，校正过程随即停住。采用更高精度乘加或扩展累加器计算 $b-A{\hat{x}}_k$，再把残差转换到因子求解所需精度，能把低位信息重新送入校正方程。

一种常见的混合精度配置是在低精度 $u_f$ 中分解和求解校正，在工作精度 $u$ 中保存并更新解，在更高精度 $u_r$ 中计算残差。忽略维数与增长因子常数时，基本精化的典型充分区间是

$$\kappa (A)u_f<1.$$

达到的平台还受 $u$ 和 $\kappa (A)u_r$ 控制。这些是解释路线，不是脱离主元、缩放和误差模型的硬阈值；即使不等式成立，溢出或不稳定因子仍会失败，不成立时也可能在特定右端上偶然改善。

每轮可用尺度化 normwise 后向误差

$${\eta }_k=\frac{\Vert r_k{\Vert }_{\mathrm{\infty }}}{\Vert A{\Vert }_{\mathrm{\infty }}\Vert {\hat{x}}_k{\Vert }_{\mathrm{\infty }}+\Vert b{\Vert }_{\mathrm{\infty }}}$$

作停止指标，并同时检查 $\Vert d_k\Vert$ 相对于 $\Vert {\hat{x}}_k\Vert$ 的大小。若 ${\eta }_k$ 达到容差且一次显式高精度残差复核一致，可正常结束；若残差连续数轮不降、校正量增长、因子求解失败、出现非有限值或达到最大轮数，应返回停滞或失败，而不是继续重复同一校正。

稠密问题只做一次约 $O(n^3)$ 的 LU 分解；每轮残差矩阵—向量乘与两次三角求解均为 $O(n^2)$。稀疏问题的每轮成本由 $\mathrm{nnz}(A)$、三角因子填充和访存决定。每轮重新分解会抹掉精化相对于重新求解的成本优势，也改变了本页分析的固定近似逆。

直觉 ​

低精度直接解先给出一张大体正确的地图，高精度残差再指出当前解代回原方程后还差多少。已有 LU 因子把这份方程空间里的缺口翻译成解空间中的校正；只要翻译虽粗但方向可靠，连续几轮就能把误差压到工作精度允许的平台。

关键不是“再解一次同一问题”，而是分工：昂贵分解只做一次，残差用更细的尺子观察，校正仍用便宜因子完成。若观察尺和初始求解同样粗，算法可能看不见自己最需要修正的低位。

例子与边界 ​

取五阶 Hilbert 矩阵

$$(H_5{)}_{ij}=\frac{1}{i+j-1},1\le i,j\le 5,$$

令真解 $x_{\ast }=(1,1,1,1,1{)}^{\mathsf{T}}$，并以 binary64 计算 $b=H_5{x}_{\ast }$。先把 $H_5,b$ 转为 binary32，做一次带部分主元的 LU 分解并求初值；随后仍用这组 binary32 因子求校正，但在 binary64 中计算残差和更新。一次可复查运行得到：

精化轮数 $k$	$|b-H_5{\hat{x}}_k{|}_{\mathrm{\infty }}/|b{|}_{\mathrm{\infty }}$	$|{\hat{x}}_k-x_{\ast }{|}_{\mathrm{\infty }}/|x_{\ast }{|}_{\mathrm{\infty }}$
0	$5.13\times {10}^{-8}$	$8.14\times {10}^{-3}$
1	$2.21\times {10}^{-11}$	$2.00\times {10}^{-6}$
2	$1.28\times {10}^{-14}$	$4.75\times {10}^{-10}$
3	$9.72\times {10}^{-17}$	$1.80\times {10}^{-11}$
4	$9.72\times {10}^{-17}$	$2.40\times {10}^{-11}$

${\kappa }_2(H_5)\approx 4.77\times {10}^5$，所以初始相对残差只有约 $5\times {10}^{-8}$ 时，前向误差仍达到 $8\times {10}^{-3}$；两者的差距来自问题敏感性。前三轮复用同一低精度因子便恢复了许多数字。第四轮残差已经停在 binary64 平台，前向误差反而略有回升，说明达到平台后应停止，不能把更多轮数当成更多精度。

这个历史与对角小残差反例承担不同任务：它跟踪同一个近似解怎样被实际校正，并同时显示残差与前向误差；数字会随具体 BLAS/LAPACK 实现略有末位差异，但精度分工和停滞判断可直接复现。

若 $A$ 过于病态，使低精度因子不能提供收缩方向，校正可能缓慢、振荡或发散。此时盲目提高轮数无效；可以提高因子精度、改善缩放与主元策略，或把低精度因子作为预条件器改用更强的内层迭代，但那已超出基本精化的固定三角校正。

推论与应用 ​

残差与误差估计公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。解释为什么停止必须使用尺度化后向误差，线性系统条件数公理库线性方程组的条件数与扰动Conditioning of linear systems · Matrix condition number把一般问题条件性具体化为可逆线性系统的右端、系数矩阵与联合扰动界。再把它转换成可能的前向误差。LAPACK 驱动还会结合倒条件估计和逐分量误差界；只返回一个小 residual 会遗漏用户最关心的解精度。

混合精度硬件让低精度分解具有更高吞吐，但数据转换、残差高精度累加和因子复用次数都要计入总成本。只有整体时间或能耗下降、且最终误差满足工作精度目标时，低精度主体才构成有效优化。

参考资料

• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 12.
• James Demmel et al., “Error Bounds from Extra-Precise Iterative Refinement,” ACM Transactions on Mathematical Software 32(2), 2006.
• LAPACK Users’ Guide, Further Details: Error Bounds for Linear Equations.