后向误差分析

概述

后向误差分析（Backward Error Analysis）是由詹姆斯·威尔金森在1950–1960年代系统建立的数值分析方法论，是现代数值线性代数的核心范式。核心思想：不问"计算结果与精确解差多远"（正向误差），而问"计算结果精确地解了哪个问题"（后向误差）——即找到一个扰动输入 $A+\delta A$，使算法的浮点输出恰好是该扰动问题的精确解，然后评估扰动量 $|\delta A|/|A|$ 的大小。若后向误差与输入数据的固有不确定性相当，算法就是后向稳定的，计算结果的精度完全由问题的条件数决定，而非算法实现。

关键内容

正向 vs. 后向误差

	正向误差分析	后向误差分析
问题	计算结果离精确解多远？	计算结果精确解了哪个问题？
度量	$\|\hat x - x\|$	$\|\delta A\|/\|A\|$，使 $\hat x$ 为 $(A+\delta A)$ 的精确解
可操作性	困难：误差传播追踪复杂	容易：每步浮点误差直接归入扰动
实用性	常产生过于悲观的界	接近实际误差，给出可靠保证

方法论洞见：威尔金森在 Pilot ACE 上计算多项式零点时发现：计算得到的零点虽非原多项式的精确零点，但是某个系数微小扰动后多项式的精确零点。这一观察催生了后向误差分析的思想。

后向稳定性定义

算法 $\mathcal{A}$ 是后向稳定的（backward stable），若对输入 $A$ 的计算输出 $\hat x$，存在扰动矩阵 $\delta A$ 使得：

$\hat x$ 是扰动问题 $(A + \delta A)x = b$ 的精确解
后向误差满足：$\dfrac{|\delta A|}{|A|} \leq f(n)\,\varepsilon_{\text{mach}}$

其中 $\varepsilon_{\text{mach}}$ 是机器精度（machine epsilon，如双精度 $\approx 2.2\times 10^{-16}$），$f(n)$ 是维数 $n$ 的温和（低阶多项式）增长函数。

条件数：分离算法与问题

后向误差分析的关键贡献是清晰分离算法稳定性与问题条件性：

前向误差界（由后向误差推导）： $$\frac{|\hat x - x|}{|x|} \lesssim \kappa(A) \cdot \frac{|\delta A|}{|A|} \lesssim \kappa(A) \cdot f(n)\,\varepsilon_{\text{mach}}$$

矩阵条件数（线性方程组）：$\kappa(A) = |A|\cdot|A^{-1}|$

特征值条件数：对 $A = V\Lambda V^{-1}$，第 $i$ 个特征值的条件数为 $1/|y_i^H x_i|$（$x_i, y_i$ 为右/左特征向量）；对Hermitian 矩阵，条件数恒为1（特征值最"稳定"）。

含义： - 后向稳定算法 → 后向误差 $\sim \varepsilon_{\text{mach}}$（与机器精度同阶） - 计算结果误差 $\sim \kappa(A) \cdot \varepsilon_{\text{mach}}$ - 若误差过大，是问题"病态"（large $\kappa$），非算法"不稳定"

标志性应用

Gauss 消去法（带部分主元）：后向误差界： $$\frac{|\delta A|}{|A|} \leq 8n^3 \rho_n \varepsilon_{\text{mach}}$$ $\rho_n$ 为增长因子（growth factor）。最坏情形 $\rho_n$ 可达 $2^{n-1}$，但实际几乎总是适度大小——彻底推翻了 Hotelling（1943）关于 Gauss 消去法误差指数增长的悲观判断。

QR算法（Schur分解的计算）：通过 Householder 反射和 Givens 旋转等酉变换（保 2-范数，不放大误差）构造，具有后向稳定性——计算得到的 Schur 形式是原矩阵加小扰动的精确 Schur 形式。

带 Wilkinson 位移的对称 QR：全局收敛，三次方渐近收敛率，是计算对称特征值的黄金标准算法。

正交变换的优越性

后向误差分析揭示了为何酉/正交变换（Householder 反射、Givens 旋转）是数值稳定算法的首选构件：

$$|Qx|_2 = |x|_2 \quad \Rightarrow \quad \text{变换不放大误差}$$

条件数 $\kappa_2(Q) = 1$（最优），而一般相似变换的条件数可以任意大。这直接解释了QR算法（基于酉变换）优于 LR 算法（基于 LU 分解）的本质原因。

Wilkinson 多项式（条件性反例）

威尔金森给出了著名的病态反例：20次多项式 $$w(x) = \prod_{i=1}^{20}(x-i) = (x-1)(x-2)\cdots(x-20)$$

仅将 $x^{19}$ 系数（$-210$）扰动 $2^{-23}$，某些根就发生数量级的偏移（如根 $15,16,\ldots,20$ 变为复数对）。这不是算法问题，而是多项式求根问题的内在条件性极差——后向误差分析清晰地将责任归于问题而非算法。

历史谱系

图灵（1948）→ 冯·诺依曼/Goldstine（1947）→ 威尔金森（1963/1965）

阿兰·图灵1948年论文含后向误差的思想萌芽：他指出高斯消元的浮点输出可以被理解为某个"邻近方程组"的精确解，并引入条件数概念（N(A) = ‖A‖·‖A⁻¹‖），清晰区分了"问题固有困难"与"算法引入误差"。威尔金森在 NPL 与图灵共事期间受其深刻影响，后来将这些萌芽系统化为完整的后向误差分析框架（1963年《Rounding Errors in Algebraic Processes》，1965年《The Algebraic Eigenvalue Problem》）。

历史地位

彻底改变了数值分析的思维范式：在威尔金森之前，人们直觉地害怕大规模浮点计算；在威尔金森之后，人们学会了区分"算法不稳定"与"问题病态"，科学计算因此获得了严格的理论基础。

软件链条：理论（1965 Wilkinson书）→ 算法实现（1971 Wilkinson-Reinsch手册）→ EISPACK/LINPACK（1970s）→ LAPACK（1992至今）→ MATLAB/NumPy 的矩阵计算内核。

图灵奖引文（1970）：以一己之力"创造了我们目前关于线性代数计算机解法的全部科学知识"。

局限性

仅适用于后向稳定算法：并非所有算法都具有后向稳定性（如朴素 Gram-Schmidt 正交化）
不涉及算法效率：后向误差分析只告诉我们精度，不涉及计算复杂度
稀疏矩阵与迭代方法：主要针对稠密矩阵；迭代方法（Krylov 子空间法）的误差分析需要不同框架
非精确算术的新挑战：低精度计算（bfloat16、INT8）中，后向误差分析仍有效但需要更精细处理

来源

raw/books/矩阵分析/14_wilkinson_algebraic_eigenvalue_problem_1965.md
raw/books/数值分析/14_turing_rounding_errors.md