数值问题与数值算法

形式陈述 ​

一个数值问题首先是带度量的映射公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。

$$F:(D,d_D)⟶(S,d_S),s=F(d),$$

其中 $d$ 是精确输入，$s$ 是问题规定的精确输出。实际机器只能接收可表示数据 $\hat{d}\in \hat{D}$，算法 $A$ 在有限步后给出 $\hat{s}=A(\hat{d})\in \hat{S}$。因此“求解 $F$”至少包含三个不同对象：问题映射 $F$、选定的算法 $A$，以及算法在具体算术、编译器和停止规则下的一次实现。问题对数据扰动的敏感性属于 $F$；算法怎样放大舍入和迭代误差属于 $A$；溢出、NaN、并行重排等现象还依赖执行环境。

最终误差 $d_S(\hat{s},F(d))$ 往往经过一条误差链产生：$d$ 到 $\hat{d}$ 的表示或测量误差；连续问题替换为有限问题的离散化误差；迭代尚未完成的误差；每步有限精度运算的舍入误差。它们未必能简单相加，因为后续算法会传播并放大先前扰动；分析必须说明所用范数、允许扰动的数据以及各极限变量。

计算成本也不只由输入规模 $n$ 决定。若输出允许误差 $\epsilon$，一个数值算法的工作量、存储量和所需精度通常应写成 $C(n,\epsilon )$；病态程度或网格参数还可能成为额外变量。精确算术中的算法正确性公理库算法正确性Algorithm correctness · Partial and total correctness所有合法执行都符合规格，并在完全正确时保证终止。仍是必要起点，但数值正确性还要求逼近误差受控、停止条件有意义，并且有限精度执行没有破坏这些结论。

直觉 ​

“解 $Ax=b$”是一项数学任务，不是一段固定程序。Gaussian 消元把矩阵化为三角系统；共轭梯度法只在特定结构下沿低维子空间逼近；两者可以解同一个问题，却有不同的适用条件、成本和有限精度行为。把问题、算法、实现分层以后，条件数为何不能评价某段代码、收敛定理为何不能自动保证计算结果可信，都会变得清楚。

同一算法也可能有不同实现。例如一个代数恒等的表达式在实数中给出同一值，在浮点运算中却因运算顺序不同而产生不同舍入路径。分析的目标不是追求抽象上的“完全精确”，而是说明在给定数据、资源和精度目标下，哪些误差不可避免，哪些误差由算法选择造成，最后能交付怎样的可信数字。

例子与边界 ​

设 $F(A,b)=A^{-1}b$，定义域只包含可逆矩阵。若 $A$ 接近奇异，输入的一点扰动就可能显著改变真解，这是问题本身的条件性；即使使用后向稳定的求解器，也不能凭空恢复数据没有携带的精度。反之，一个良态系统也可能被显式计算 $A^{-1}$ 再乘 $b$ 的不当实现弄坏。前者不能归咎于算法，后者不能用“大概收敛”掩盖。

连续积分也展示另一层差别。$F(f)={\int }_a^{b}f(x)dx$ 是数学问题；复合求积先用有限采样替代 $f$，产生离散化误差；自适应算法再用局部估计决定采样位置；浮点求和又产生舍入误差。只报告最终小数位，而不说明函数类、网格、误差度量和参考值，无法构成数值结论。

并非所有算法问题都适合强行套入连续条件数。比较排序在无 NaN 的离散全序上要求输出一个满足次序规格的排列，通常属于精确离散问题；它仍可能受错误比较器或浮点 NaN 语义影响，但这与连续映射的局部敏感性不是同一概念。

推论与应用 ​

这套分层为后续页面提供共同坐标：条件性公理库问题条件性与条件数Conditioning of a problem · Condition number度量问题真解对输入微扰的局部敏感性，并把这种固有敏感性与算法误差分开。研究 $F$，数值稳定性公理库数值稳定性Numerical stability · Backward stability以允许的小输入扰动刻画算法的有限精度行为，并与问题条件性及其他稳定性概念分开。研究 $A$，前向与后向误差公理库前向误差与后向误差Forward and backward error分别衡量计算答案离真解多远，以及它能否视为邻近输入问题的精确解。连接计算结果和邻近问题，离散化误差公理库离散化误差与截断误差Discretization error · Truncation error区分连续问题的离散缺陷与离散解的全局误差，并说明一致性为何不能单独保证收敛。解释连续模型怎样变成有限模型，残差与误差估计公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。则回答运行到何时可以停。

因此，线性方程、常微分方程和积分的基础页面只需定义数学对象及其可解性；具体算法、误差界和实现边界应留在数值分析中。这样每个完整定义只出现一次，应用页仍能通过明确链接说明它为何需要该定义。

参考资料

• Lloyd N. Trefethen, “The Definition of Numerical Analysis,” in The Princeton Companion to Mathematics, 2008.
• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 1.
• NIST Digital Library of Mathematical Functions, Chapter 3: Numerical Methods.