动机
数值答案由有限数据及有限次运算得到。推导精确公式后,我们仍须问:输入如何表示?运算每一步的舍入会有什么影响?条件描述数学问题对数据扰动的敏感度;稳定性则描述算法引入的误差。两者是不同的问题。
表示与误差
以 β 为底、保留 t 位有效数字的归一化非零浮点数可写作
±(d0.d1⋯dt−1)ββe,1≤d0<β,0≤di<β.
指数范围有限。实际机器亦有零,还可能有次正规数、无穷大和特殊值;此简化模型并非完整的机器规格。数的量级愈大,相邻可表示数的间距亦愈大。
十进制保留三位有效数字、取最接近值时,1.234 舍入为 1.23,而 1234 舍入为 1230。两个绝对误差 0.004 与 4 相差一千倍,相对误差却都约为 3.2×10−3,低于下文定义的单位舍入误差 21⋅10−2。
定义 1.1.3
(绝对误差、相对误差与单位舍入误差)
精确值 x 与近似值 x 的绝对误差为 ∣x−x∣;若 x=0,相对误差为 ∣x−x∣/∣x∣。接近零时,绝对误差更有意义,因相对误差在零处没有定义。远离溢出与下溢时,取最近值可用标准模型
fl(x)=x(1+δ),∣δ∣≤u=21β1−t.
这是一次舍入的界,并不代表整个多步计算的相对误差也不超过 u;下溢时亦未必适用。
问题的敏感度
设 f 在 x=0 可微,且 f(x)=0。对小扰动 Δx,微分给出一阶近似
∣f(x)∣∣f(x+Δx)−f(x)∣≈f(x)xf′(x)∣x∣∣Δx∣.系数 κf(x)=∣xf′(x)/f(x)∣ 是局部相对条件数。
它依赖问题、输入和误差尺度,并非任意大扰动的统一保证。若输出为零,应改用合适的绝对误差尺度。
概念视角几何
条件数是对数坐标下的斜率
记 X=log∣x∣、Y=log∣f(x)∣。在 f 可微且不为零之处,链式法则给出 dY/dX=xf′(x)/f(x),所以 κf(x)=∣dY/dX∣。在一阶近似下,相对变化就是对数之差,因此相对误差与这个斜率天然配对。对 x,双对数图是斜率为 1/2 的直线;对 x−1,在 x=1 附近斜率无界,那里 log∣f∣→−∞。
对 f(x)=x、x>0,条件数为 1/2,故小的相对输入变化约产生一半大小的相对输出变化。相反,f(x)=x−1 的条件数 ∣x/(x−1)∣ 在 x 趋近 1 时无界。若输入已经舍入,改写减法也不能找回失去的数据。
消去与稳定公式
当 x 很小且为正时,g(x)=1+x−1 是两个相近数的差,可能暴露操作数已有的舍入误差。有理化得到完全相等的公式
g(x)=1+x+1x,
它避免相近数相减。
在每步均舍入至四位有效十进制数的模型中,取 x=0.0001,1+x 舍入为 1.000,第一公式得到零;第二公式的分母舍入为 2.000,结果为 0.00005000,接近精确值 0.00004999875…。实际硬件的运算规则可能不同。
消去本身并不必然产生误差:若两个操作数均精确表示,相减本身也可能精确。危险是小差值凸显原有误差。残差小亦不能单独保证病态问题的答案准确。
前向及后向误差
定义 1.1.7
(前向误差、后向误差与后向稳定性)
对数据 d、精确答案 F(d) 和计算答案 y,前向误差比较 y 与 F(d);后向误差寻找使 y=F(d+Δd) 的小数据扰动。后向稳定算法的答案是附近数据的精确解,“附近”相对于指定的数据度量而言。
后向稳定性配合良好条件,才可得到有用的前向误差界;单靠其中一项,并不能在所有情况下保证准确。
设 x>0,并设算法返回 y=x+Δx,其中 x+Δx≥0。则
x∣y−x∣=1+Δx/x+1∣Δx∣/x.特别地,若 ∣Δx∣/x≤ε≤1,相对前向误差至多为 ε/(1+1−ε);当 ε 很小时,此值约为 ε/2。
记 r=Δx/x,则 r≥−1,且 y/x=1+r。于是
1+r−1=1+r+1∣(1+r)−1∣=1+r+1∣r∣.若 ∣r∣≤ε≤1,分子至多为 ε,分母至少为 1+1−ε,即得所述界。恒等式同时展示了一阶近似忽略的部分:因子 1/(1+r+1) 只在 r=0 时等于 1/2。
因子 1/2 正是平方根的条件数。这是一般规律的缩影:在一阶意义下,前向误差至多为条件数乘以后向误差。
误差累积与运算次序
即使每个运算各自只有小相对误差,多步运算也会累积误差。若 n 次运算各贡献因子 1+δi,其中 ∣δi∣≤u,则因子之积与一之差至多为 (1+u)n−1;当 nu 很小,此值约为 nu。这是该乘积的最坏情况界,不能直接当成包含加法及消去的任意算法之误差界。
例如用三位有效十进制数求 1+0.004+0.004。先加两个小数得 0.008,再加 1 并舍入得 1.01;逐一加到 1,每一步均舍入至 1.00。两者都不等于精确和 1.008,但次序改变了损失。长和中把量级相近的数分组可能有帮助,效果仍依赖符号及数据,没有一种次序可消除所有误差。精确的数学和与次序无关,浮点计算过程则不然。
分析计算时应分别记下精确问题、实际存储的数据、运算及舍入模型,以及输出误差尺度,从而把建模误差与表示误差、算法误差区分开来。增加位数有助减少舍入,却不能修正错误的测量或模型,也不改变问题本身的条件数。
扰动区间与测量
假设温度计读数 x=100,已知绝对不确定度不超过 0.1,相对输入不确定度至多为 10−3。对倒数 f(x)=1/x,单调性给出严格输出区间 [1/100.1,1/99.9]。条件数 1 则只预测小扰动下相对输出不确定度约为 10−3。区间包含非线性余项,可提供具体保证;条件数提供局部估计。两者回答的问题不同。
有多个输入时,条件数需要指定共同扰动尺度。对减法 s(a,b)=a−b,若 ∣Δa∣≤ε∣a∣ 且 ∣Δb∣≤ε∣b∣,三角不等式给出
∣Δs∣=∣Δa−Δb∣≤ε(∣a∣+∣b∣).
当 a=b,相对输出误差至多为 ε(∣a∣+∣b∣)/∣a−b∣。两数相近时此界可能很大,它描述独立扰动两个操作数的敏感度;把它们的差看成一个已知输入则是另一问题。必须说明数据是什么,才能有意义地谈条件。
例如 a=1.0001、b=1.0000,各有独立的 0.00005 绝对不确定度时,真差可介于零与 0.0002 之间,而名义差为 0.0001,所以绝对不确定度是名义差的 100%。若以真差为分母,相对误差可以任意大;真差为零时则没有定义。后续减法多保留数位,不能重建未知真值;如果操作数本来精确且精确存储,就没有这个测量不确定度。
舍入界的推导
在指数范围不受限制的理想归一化模型中,设实数 x=0,而 fl(x) 是与 x 最接近的浮点数。则 fl(x)=x(1+δ),其中 ∣δ∣≤u=21β1−t。
在区间 [βe,βe+1) 内,相邻数间距为 βe−t+1。舍入至最近值的绝对误差不超过半个间距;由于区间内的数至少为 βe,相对误差不超过 21β1−t。这证明正数的一次舍入界,负数由对称性得到。在边界附近间距改变,但所述理想模型的同一界仍成立。两个最近值等距时须指定选择规则;任选其一仍符合此界。
指数范围有限时,模型在极端值处须额外处理:溢出没有附近的有限归一化数,次正规数的间距固定,并不与量级成比例。故基于 ∣δ∣≤u 的证明须排除这些情况或另行处理。
反例模式
次正规数打破相对误差界
断言:指数范围内的每个非零实数,舍入后的相对误差都不超过 u。在 IEEE binary64 中,u=2−53≈1.1×10−16,最小的正次正规数是 2−1074,而零附近的次正规数间距为 2−1074。实数 x=3⋅2−1075 恰好位于 2−1074 与 2−1073 的正中,取偶舍入选出 2−1073。相对误差为
3⋅2−10752−1073−3⋅2−1075=34−3=31,是 u 的 1015 倍以上。补救正是命题中已有的假设:相对误差界只对归一化结果成立。在次正规范围内,改为成立的是绝对误差界 ∣fl(x)−x∣≤2−1075,即固定间距的一半。
二次方程根的表示
当 a=0 且 b2−4ac≥0,二次方程 ax2+bx+c=0 有实根。若直接计算两个分子 −b±b2−4ac,其中一个可能是相近数之差而损失准确度。例如 a=1、b=−10000、c=1,小根为 (10000−99999996)/2,相减消去大部分前导数位。两根之积为 c/a=1,因此先用相加的分子计算大根,再取其倒数得到小根。精确算术中两种方法相同;浮点计算中后者避免了这次消去。
一般而言,当 b=0,可令 q=−21(b+sign(b)b2−4ac),在 q=0 时计算 q/a 和 c/q。b=0、q=0、重根及非实根等特殊情况须另行处理。形成判别式时仍可能溢出或严重消去;接近重根时,根本身对系数变化十分敏感,改写算法不能消除所有困难。
如何理解显示的数位
计算程序显示 1.4142135623,并不证明每个数位都正确。可信的报告需要误差界、配合敏感度数据的已验证残差,或其他有理据的误差估计。先验证区间再按所需位数舍入,比没有依据地列出长小数更可靠。两个算法的答案高度一致是有用证据,但若它们共用有偏差的输入或不稳定步骤,一致仍不是证明。
不同误差来源应分开追踪。若模型使用测量参数,数值结果可能准确地对应那些参数,而参数本身仍偏离现实。减少算术误差的细化实验不能消除模型或测量误差;误差分析的目的,是判断哪一项不确定度主导结论及结论所能支持的精度。
总结
数值分析首先确定数据及误差尺度。浮点模型界定每次正常舍入;条件衡量数学映射对数据的敏感度。后向误差问解的是哪个附近问题,前向误差则衡量答案的差距。误差模型的假设成立时,对条件良好的问题使用后向稳定算法,通常可得到小前向误差。
即使代数上完全等价的改写也须放在情境中判断。有理化避免相近数相减,却可能在其他步骤造成溢出;高精度计算也可能准确地解了记录错误的数据。一份有用的结果报告应说明数据尺度、可能受扰动的量,以及有多少位数受到证据支持,而非混淆存储精度与测量的确定性。
练习
快速检查
(求 f(x)=1/x(x=0)的相对条件数并解释。)
计算 xf′(x)/f(x)。
解答 · 答案
f′(x)=−1/x2,故条件数为 1:小相对扰动产生约同样大小的相对输出变化。
快速检查
(用每步舍入至三位有效十进制数,计算 (100+0.4)−100 和 100+(0.4−100)。结果说明了什么?)
解答 · 答案
前者的和舍入为 100,结果为 0;后者括号为 −99.6,结果为 0.4。浮点加法不遵守实数加法的结合律。
快速检查
(为大正数 x 改写 x2+1−x,避免相近数相减。)
同乘及同除以 x2+1+x。
解答 · 答案
乘以共轭式得到 1/(x2+1+x)。实现时仍须防止极大 x 的 x2 溢出。
快速检查
(正量的测量值为 10,绝对不确定度至多 0.01。用区间界定其平方,并与条件数的一阶估计比较;解释为何区间的结论较强。)
解答 · 答案
输入落于 [9.99,10.01],故平方落于 [99.8001,100.2001]。名义输出为 100,最大绝对偏差是 0.2001。f(x)=x2 的相对条件数为 2;相对输入不确定度 0.001 预测相对输出不确定度约 0.002,即绝对变化约 0.2。区间包括二次项,提供严格界而非仅为一阶估计。