Page 22 - 《软件学报》2020年第12期

3688 Journal of Software 软件学报 Vol.31, No.12, December 2020

2 向后精度分析

本节讨论函数求值的反问题:已知 f(x 1 ,x 2 ,…,x n )是关于 n 个变元的函数, y 是实数 y i 满足精度ε i (>0)的近似
i
i

值,即 | y − i y i | ε< i (1≤≤ ) n ,而 y 是 (,f yy 2 ,..., y n ) 的一个计算值.对于任意的一个误差限ε(>0),如何判断|y−f(y 1 ,
1
y 2 ,…,y n )|<ε是否成立?若不成立,需要提高哪些 y 的精度?即缩小哪些ε i ?并且如何缩小?
i
比如,已知函数 f(x 1 ,x 2 )=sin(1000x 1 )+x 1 x 2 与自变量值 Y = (, )y y = ( , 2)π .虽然我们可以获得 f(y 1 ,y 2 )任意精
1 2
度的值,但是在计算过程中,我们并没有使用到真正的 y 1 与 y 2 .因为它们均是无理数,即,我们只是使用了它们的
近似值.反过来,任给类似的一对近似值,我们能够判断其是否足够精确,以至利用它们可以获得函数误差可控
的值(参见第 2.2 节).
2.1 算 法

设 f 是一个算术表达式,它的准确值是一个实数.我们用 f 或 (, )f ε 以及 f ε 来表示 f 的计算值,其中,后二者
分别说明 | f − | f < ε 与| f ε −f|<ε.这时,ε>0 代表运算时的误差限(有时也称作精度).若 f>0,定义函数δ(f)={0.1 |
n

n
0.1 ≤f<0.1 n−1 ,n∈Z},例如,δ(0.5)=0.1,δ(0.00234)=0.001.最后,设 D 是一个四元组,我们用函数 Fst (),D Snd ( )D ,

Thd D ( )
(),Fth D 分别获取它的第 1~第 4 个分量.
对于一个算术表达式,假设可以获得其任意精度的值.而对于两个常数(位数有限的实数,下同)的和、差或乘
积,也可以获得准确值.

根据这些定义与假设,我们给出主算法(算法 0).它检验 Y(Y 代表(y 1 ,y 2 ,…,y n ),下同)的计算值 Y 的精度是否精

确到当用 Y 代替 Y 后,也能获得 f(Y)的一个计算值 y,使得|y−f(Y)|<ε.
算法 0. AccurateEnough( {( , ) |1y ε ≤≤ n }, ( , ,...,f x x x ),ε ).

i
i i 1 2 n
Require: {( , ) | yε = y ,1≤≤ } n ,f(x 1 ,x 2 ,…,x n ),ε>0;
y
i
i i i i i ε
Ensure:返回一个 4 元组 D = (, , ,y k ε 0 enough ) .若 enough=true,则|y−f(y 1 ,y 2 ,…,y n )|<ε;否则,当 enough=false 时,
y 的精度ε k 不能满足计算的要求,其精度需要提高至ε 0 .
k
1: if f 是算术表达式(可以包含π与 e),或若干常数与若干变元的和,或变元与常数相乘或相除,或两个变元
相乘或相除 then

2: D ⇐ Sub 1_ AccurateEnough ({( , ) |1y ε i ≤≤ n }, ( , ,...,f x x 2 x n ), )ε ;

i
1
i
3: else if f = f × 1 2 , f f 1 / f ,sin( ),arctan( ),lnf 1 f 1 ( ),f 1 e 之一 then
1 f

4: D ⇐ Sub 2_ AccurateEnough ({( , ) |1y ε i ≤≤ n }, ( , ,...,f x x 2 x n ), )ε ;

i
i
1
5: else if f =− , f 1 n f , f 1 2 f 或公式 (34)中之一 then
1 ∑ i = 1 i
6: D ⇐ Sub 3_ AccurateEnough ({( , ) |1y ε i ≤≤ n }, ( , ,...,f x x 2 x n ), )ε ;
i

1
i
7: end if

8: return D ;
这个主算法调用了 3 个子算法 Sub1_,Sub2_,Sub3_AccurateEnough,分别代表递归计算的“出口”算法、利用
特定子算法进行的计算以及利用公式进行的递归计算.由于它们与上述主算法拥有相同的输入(require)、输出

(ensure)以及返回(return D )项,因此为了节省篇幅,在后面的算法中,将省去此 3 项内容.
2.1.1 “出口”子算法
如果 f 不含变元,即它是一个算术表达式,那么由假设,算法直接返回它的计算值.如果 f 表示为若干常数与
变元的和,那么若对应自变量计算值的误差的和小于预先设定的误差限,则返回和的结果;否则,平均分配误差,
并返回误差最大者的下标.如果 f 等于一个变元乘以或除以一个常数,那么若对应计算值的精度与此常数的积
或商的值小于预先设定的误差限,则返回它们的值;否则,在精度为“对应计算值的精度与常数的商或积”的前提
下,重新计算对应计算值.
命题 2.1. 已知 y i ,y j 是两个未知实数,ε>0.存在算法,可以获得 y i ,y j 任意精度的计算值.