计算机浮点数运算的舍入误差分析.docxVIP

计算机浮点数运算的舍入误差分析 计算机中的字数应表示为浮点形式。由于计算机浮点数中尾数的位数是有限的, 在进行科学计算的时候, 对一般实数总是要按舍入原则表示为浮点数。这样, 计算机浮点数就是该实数的近似值。因此, 我们有必要对计算机浮点数和浮点数的算术运算的舍入误差进行系统的理论分析。事实上, 这正是在科学计算中对各种数值计算方法作误差分析的基础。由算术运算的误差界限, 可以建立更复杂运算的误差界限, 因而可对各种算法的舍入误差进行分析。 1 计算机浮点系统的构成 设F表示系统的计算机浮点数全体所构成的集合, 即 F={0}∪{f∶f=±βJt∑k=1dkβ-k,0≤dk≤β,d1≠0,L≤j≤U}(1) 其中每个dk都是整数。β是计算机浮点数的基数, 当β=10时, 就是通常使用的十进制数;当β=2, 8, 16时, 分别表示二进制数、八进制数和十六进制数。本文就一般基数情形进行统一讨论。又±t∑k=1dkβ-k=±0.d1d2?dt是尾数, 自然数t是字长, 整数j是阶, 阶有固定的下限L和上限U,L和U均为正整数或零;因此,F是由四元数组 (β,t,L,U) 来描述的, 即F=F(β,t,L,U) , 称为计算机浮点数系统, 显然它是包含2 (βt-βt-1) (U-L+1) +1个数的有限集。 F中的数对称地分布在区间[-M,m]和[m,M]中, 其中 {Μ=βU(β-1)(t∑k=1β-k)=βU(1-β-t)m=β-1βL=βL-1(2) 以下将计算机浮点数简称为浮点数, 并把实数x的浮点表示为fl(x) , 若x=0时,fl(0) =0;当m≤|x|≤M时, 对舍入法有 fl(x)={0.d1d2?dt×βJ,当0≤dt+1<β/2时(0.d1d2?dt+β-t)×βJ,当dt+1≥β/2时(3) 对截断法, 有fl(x) =0.d1d2…dt×βJ。例如对二进制系统的舍入法有 fl(x)={0.d1d2?dt×2J,当dt+1=0(0.d1d2?dt+2-t)×2J,当dt+1=1(4) 截断法有fl(x) =0.d1d2…dt×2J。 两个浮点数相加或相减, 首先要对阶, 即将两数的小数点对齐, 使它的阶相等。具体做法是把阶小的浮点数的尾数右移, 每移动一位其阶就加1, 直到两浮点数的阶相等。然后相加或相减。下面, 我们将用“。”来表示加、减、乘、除四则运算中任意一种运算。在运算中, 若|a。b|>M是上溢;若0<|a。b|<m是下溢。以下我们将在不发生溢出的情况下进行讨论。 2 浮点数的间距 实数表示成浮点数之后, 我们可得到它的相对误差限, 这是进行误差分析的基础。误差分析的基本定理是:设m<|x|<M, 其中m和M由 (2) 式给出, 则有 fl(x)=x(1+δ),|δ|≤u(5) 其中u为浮点数的相对误差限 (机器精度) , 即 u={12β1-t,舍入法β1-t,截入法(6) 证明若fl(x) =0, (5) 式显然成立。现不妨假定x<0, 同理可记x>0的情形。设x∈(-βJ,-βJ-1), 故x的阶为J, 于是在该区间中的所有t位浮点数以间距βJ-t分部。 对舍入法, 有|fl(x)-x|≤12βJ-t,12βJ-t是fl(x) 的绝对误差限, 又 |fl(x)-x|≤12βJ-t=12βJ-1β1-t≤12β1-t从而|fl(x)-xx|≤12β1-t(7) 这样我们就得到对浮点数使用舍入法的相对误差限。令δ=fl(x)-xx, 由 (7) 知|δ|≤u=12β1-t, 从而有 fl(x)=x(1+δ),|δ|≤u=12β1-t(8) 对截断法, 有|fl(x) -x|≤βJ-t,βJ-t为使用截断法的绝对误差限, 因为 |fl(x)-x|≤βJ-t=βJ-1β1-t≤|x|β1-t从而有|fl(x)-xx|≤u=β1-t(9) 令δ=fl(x)-xx, 得 |fl(x) -x|=x(1+δ) , |δ|≤u=β1-t(10) 联合 (8) 和 (10) 式, 即得 (5) 式和 (6) 式, 证毕。 特别对10进制系统, (6) 式为 u={5×10-t,舍入法10×10-t,截入法 对二进制系统为 u={2-t,舍入法2×2-t,截入法 在某些情形, 为使用便利, 我们也将fl(x) 的相对误差表为 fl(x)=x1+δ,|δ|≤u(11) 3 约化法证明 由浮点数表示的特征可以导出算术运算的舍入误差。设x,y∈F,fl(x。y) 的意义是先让x,y进行运算, 运算的结果是精确的实数x。y, 再按舍入规则表示成F中的浮点数。x。y与fl(x。y) 的误差就是舍入误差。关于浮点数算术运算的舍入误差, 据 (5) 和 (6) 式得如下结论: fl(x?y)=(x?y)(1+δ),|δ|≤