有限机器中的数
数学上的实数可能需要无限位数字才能表示。计算机格式只能存储有限位,因此即使是简短计算也可能混合两种不同的偏差来源:数据在表示时可能改变,此后的每次运算也可能将结果舍入。为了理解答案,必须说明哪个问题是精确的,以及哪些运算是近似的。
以下例子采用舍入到最近值;正好处于中间时,选择有效数字最后一位为偶数的可表示值。这是针对所述格式的理想化规则;实际软件还涉及精度、中间运算、下溢、上溢和特殊值的选择。下文分析不保证每个编程环境都以同样方式计算表达式。
表示与局部舍入模型
基数为 β、精度为 p 的规格化浮点数形如
±(d0.d1⋯dp−1)ββe,1≤d0<β,0≤dj<β,其中各数字和指数是整数,指数在格式允许的范围内。零另行表示。固定 e 时,相邻有效数字的间距为 βe−p+1。
间距随数量级改变。有限指数范围还导致上溢;系统对极小的数可能使用次正规数。边界情况很重要,但下述简单相对误差模型不能自动涵盖它们。
采用舍入到最近值时,单位舍入误差为 u=21β1−p。对基本运算 ∘,若其精确结果有定义且处于正规范围,舍入模型为
fl(a∘b)=(a∘b)(1+δ),∣δ∣≤u.该模型把计算出的运算与对所提供操作数作精确运算的结果比较。如果操作数已经近似其他量,还须另行计算它们的误差。当精确结果为零时,相对表达式需要单独理解;在通常模型中,精确零被表示为零。
若非零实数 z 的舍入结果处于正规范围,且没有上溢或下溢使估计失效,则
fl(z)=z(1+δ),∣δ∣≤u=21β1−p.
取 e 使 βe≤∣z∣<βe+1。在这个数量级区间内,可表示数的间距为 βe−p+1,舍入到最近值至多把 z 移动半个间距,即 21βe−p+1。由于 ∣z∣≥βe,相对改变至多为 21βe−p+1/βe=21β1−p=u。
基数为二、p=3 时,1 与 2 之间的正规数为 1、1.25、1.5、1.75,且 u=1/8。1.125 正好位于 1.002 与 1.012 中间;中点取偶规则将它舍入为 1.002=1。相对误差为 (1−1.125)/1.125=−1/9,其绝对值不超过 u。下一个数 1.25 可被精确表示,误差为零。u 是正规舍入的最坏情况保证,并不是每个数的实际误差。
快速检查
(在基数二、p=3 的格式中,将 1.375 按最近值、中点取偶规则舍入。求相对舍入误差,并与 u 比较。)
解答 · 答案
1.375 正好位于 1.012=1.25 和 1.102=1.5 中间。后者末位为偶,故舍入为 1.5。相对误差为 (1.5−1.375)/1.375=1/11<1/8=u。
前向误差、后向误差与条件性
设问题把数据 d 映为精确结果 F(d),算法返回 y。前向误差为 y−F(d);当 ∥F(d)∥ 非零时,除以它可得相对前向误差。后向误差则问:输入至少需要改变多少,才能使 y=F(d+Δd) 精确成立?其数值取决于哪些数据允许扰动及如何衡量扰动。
后向误差小说明答案解的是邻近问题;它本身并不说明邻近问题的答案也相近。
设 A 非奇异且固定,b=0,且只允许扰动 b。对计算解 x,残差为 r=b−Ax,使 x 精确成立的右端项改变唯一,为 Δb=−r,相对大小为 ∥r∥/∥b∥。在诱导范数下,精确解 x 满足
∥x∥∥x−x∥≤∥A∥∥A−1∥∥b∥∥r∥.
由 Ax=b−r 得 Δb=−r;A 可逆,所以这是唯一选择。其次,x−x=A−1r 给出 ∥x−x∥≤∥A−1∥∥r∥,而 ∥b∥=∥Ax∥≤∥A∥∥x∥ 给出 ∥x∥≥∥b∥/∥A∥。把前一个界除以后一个界,即得所述不等式。
因此在此扰动模型下,即使后向误差很小,也可能被很大的条件数放大。若同时允许扰动 A,后向误差的定义和数值便会改变;上述残差比不自动等于更宽模型中的最小值。
看到 ∥r∥/∥b∥ 很小,就接受 x,是很诱人的做法。但上面的命题表明,x 的相对误差仍可能达到该残差比的 ∥A∥∥A−1∥ 倍。判断答案是否可靠,要同时看残差和问题的条件性。
快速检查
(对 A=diag(1,10−6)、b=(1,10−6)T 和 x=(1,0)T,求残差、精确解,以及只允许改变 b 时以无穷范数衡量的后向误差。)
解答 · 答案
r=(0,10−6)T,x=(1,1)T。唯一允许的改变是 Δb=−r,故相对后向误差为 ∥r∥∞/∥b∥∞=10−6;但相对无穷范数前向误差为一。
若有限维赋范空间之间的映射 F 在非零点 d 可微且 F(d)=0,则局部相对条件数为 ∥DF(d)∥∥d∥/∥F(d)∥,其中使用诱导算子范数。
条件性属于问题本身。 它衡量精确输入的微小改变使精确输出发生多大变化。它描述一阶敏感性,依赖输入、范数及允许的扰动;它不是算法造成的误差。
对标量减法 F(a,b)=a−b=0,设 a=a(1+δa)、b=b(1+δb),且 ∣δa∣,∣δb∣≤u。即使随后精确计算两者的差,也有
∣a−b∣∣(a−b)−(a−b)∣≤u∣a−b∣∣a∣+∣b∣.
相减得 (a−b)−(a−b)=aδa−bδb,其绝对值至多为 u(∣a∣+∣b∣)。再除以 ∣a−b∣ 即可。
当 a 与 b 很接近时,右侧的比值可能很大。这是减法对输入相对扰动的敏感性,并不意味着对两个已存储操作数执行减法时,该运算本身必然产生很大的相对舍入误差。消去会暴露已有误差;辨认其来源需要追踪整个计算过程。
消去与代数等价公式
考虑舍入到三位有效数字的十进制运算。精确输入 a=1234 和 b=1233 均舍入为 1230。精确相减存储值所得为零,原始输入之差却为一。损失发生在输入舍入时;其后的存储值相减是精确的。最终答案多打印几位并不能恢复原始数据中已经丢失的数字。
快速检查
(在三位有效数字十进制运算中,先分别舍入 a=1234 和 b=1233,然后相减。求计算差和精确差。此例是否说明两个存储操作数相减不准确?)
解答 · 答案
两个输入都舍入为 1230,故计算差为零,原始差为一。两个存储值的减法是精确的;偏差由输入舍入造成。
两个非常接近的数相减后,结果失去全部有效数字,此时减法本身通常是精确的。出错的是更早的步骤:操作数在舍入或计算时已带有误差。减法的敏感性界说明了这些早先的误差为何变得可见,却没有指出是哪一步运算造成了它们。
公式也可能在计算内部产生类似困难。对 x>0,以下两个表达式在实数运算中相等:
x2+1−x=x2+1+x1.
x 很大时,第一个表达式相减的两个正数非常接近;第二个避免了相减。
反例模式
代数上相等的公式可以算出不同的值
命题:在实数运算中相等的两个表达式,在浮点运算中也返回同一个值。在 IEEE 754 binary64 舍入到最近值的运算中,取可精确表示的输入 x=108,并分别计算各基本运算。此时 x2=1016 精确成立,而 fl(x2+1)=1016:增量落在该处相邻 binary64 数的中点,取偶选择 1016。直接公式 x2+1−x 于是得到 108−108=0,尽管精确值为正且约等于 5×10−9。在此例中,有理化公式给出有用的非零近似。此比较假设所示运算顺序,且没有融合运算或编译器重新组合;它不能证明有理化公式对所有 x 都安全,因为 x2 本身可能上溢。
在每步分别舍入的 binary64 运算中,(1016+(−1016))+1=1,但 1016+((−1016)+1)=0。在第二个表达式中,−1016+1 不可表示:1016 附近的数相隔 2,而 −1016 与 −1016+2 之间的平局取偶选择有效数字为偶的 −1016,所以内层和被舍入回 −1016。两种括号的精确实数和都是一。因此运算顺序是算法规格的一部分。
稳定性属于算法
非正式地说,对于指定问题和输入模型,如果算法的计算结果是某个邻近输入的精确答案,并且相对于数据的扰动有受控的小上界,就称算法后向稳定。“邻近”必须通过范数、允许的扰动以及依赖精度和问题规模的界来说明。
稳定性定理可能只在特定输入和中间值范围条件下成立。稳定性并不意味着每个计算数字都准确:病态问题可能放大很小的后向误差;反之,条件良好的问题也可能被不稳定算法算坏。
设 sn=i=1∑nxi 从可表示的输入出发,令 s1=x1 后按给定次序逐次相加,n≥2;每个非零精确运算 sk−1+xk 都满足同一 u 的相对舍入模型,并且没有上溢或下溢。若 (n−1)u<1,则
∣sn−sn∣≤γn−1i=1∑n∣xi∣,γk=1−kuku.此外 sn=i∑(xi+Δxi),其中 ∣Δxi∣≤γn−1∣xi∣。
展开递推式:每个 xi 都乘上至多 n−1 个因子 1+δj 的乘积。对 k≤n−1,此乘积与一之差的绝对值至多为 (1+u)k−1≤ku/(1−ku)。三角不等式给出上述界。精确为零的中间和没有舍入误差,可单独处理。同一展开也将 sn 写为 i∑(xi+Δxi),这是关于求和输入的逐分量后向误差结论。
证明透视
把每个误差记到输入上
每次加法带来一个因子 1+δj,所以把递推展开后,x1 和 x2 各乘上 n−1 个这样的因子,x3 乘上 n−2 个,xn 只乘上一个。这种记账方式才是关键想法:误差记在输入上而不是部分和上,于是自然得到 xi+Δxi 这种后向形式。舍入模型(连同范围假设)每次加法用一次;(n−1)u<1 只是使 γn−1 有限。前向界随后只需三角不等式,而因为它含有 ∑∣xi∣,精确和中的抵消在其中看不出来。
上式是绝对前向误差界。若真实和相比 ∑∣xi∣ 很接近零,该界可能允许很大的相对误差;它不能保证有消去的求和仍保留准确数字。
快速检查
(在逐次求和的舍入模型下,写出四个数的绝对误差界,并解释为何它不一定给出小的相对误差界。)
解答 · 答案
若 3u<1 且满足所述范围条件,界为 γ3i=1∑4∣xi∣,其中 γ3=3u/(1−3u)。精确和相对于各项绝对值之和可以任意小,故除以精确和的绝对值可能得到很大的界;精确和为零时,相对误差甚至无定义。
1 的相邻浮点数及其不对称性
假设。 采用规格化二进制格式,精度 p≥2(含首位),指数 0 与 −1 均可用,舍入方式为就近舍入、平局取偶。不考虑范围限制,以下内容不涉及次正规数或溢出。
在此格式中,1 的后继是 1+21−p,前驱是 1−2−p。1 下方的间隙是上方间隙的一半。
区间 [1,2) 内的数形如 1.b1b2…bp−1×20。最后一位小数位改变一个单位,数值改变 21−p,所以 1 之后的下一个数是 1+21−p。
区间 [1/2,1) 内的数形如 1.b1…bp−1×2−1,间距为 21−p⋅2−1=2−p。其中最大者的有效数字各位全为 1,即 1−2−p。所以 1 下方的间隙为 2−p,是上方间隙的一半。
本文记 ε间隙=21−p 为 1 上方的间隙。它与单位舍入误差 u=2−p 不同,后者是前者的一半。不同作者用“机器精度”(machine epsilon)指这两个量中的任意一个,因此使用前必须明确定义。
把函数库中名为“epsilon”的常数当作单位舍入误差 u 使用,会使本文每个估计中的误差界加倍。代入数值前,先确认来源所指的是 1 上方的间隙(21−p),还是相对舍入误差的上界(2−p)。
对 binary64,p=53。1 的相邻数为 1−2−53 与 1+2−52,且 u=2−53。
1 上方的中点是 1+2−53。一个候选是 1,其有效数字末位为 0(偶);另一个是 1+2−52,末位为 1(奇)。平局取偶选 1。1 下方的中点是 1−2−54,候选为 1−2−53(53 个 1,奇)与 1(偶),结果仍为 1。下方的平局点距 1 只有 2−54,是上方平局点距离的一半。
上述平局针对的是对一个给定的精确实数进行舍入。在运算中,操作数本身已是浮点数,只有每次运算的精确结果会被舍入。由于 2−53 可表示,fl(1+2−53)=1。因此从左到右计算 (1+2−53)+2−53 得到 1,尽管 1+2−52 本身可以表示。
快速检查
(取 p=4,求 1 的相邻浮点数和 u,并将精确中点 1+1/16 和 1−1/32 舍入。)
解答 · 答案
前驱为 1−2−4=15/16=1.1112×2−1,后继为 1+2−3=9/8=1.0012,u=1/16。精确数 1+1/16 是 1 与 9/8 的中点。1.0002 为偶,1.0012 为奇,所以它舍入为 1。精确数 1−1/32 是 15/16(有效数字 1.1112,奇)与 1 的中点,同样舍入为 1。