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

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

这样,只要令 y=z 3 ×z 4 ,则有式(20)成立.证明完毕. □

由上述定理,可得下列算法 3(与算法 4).它检验 Y 的计算值 Y 的精度是否精确到当用 Y 代替 Y 后,也能获得
f 1 (Y)×f 2 (Y)的一个计算值 y,使得|y−f 1 (Y)×f 2 (Y)|<ε.
算法 3. AccurateEnough_Mul( {( , ) |1y ε i ≤≤ n }, ( , ,...,f xx 2 x n ), f 2 ( , ,...,xx 2 x n ),ε ).

i
1
1
1
i
Require: {( , ) | yε i i = y ,1≤≤ } n ,f 1 (x 1 ,x 2 ,…,x n ),f 2 (x 1 ,x 2 ,…,x n ),ε>0;
i
y
i
i
i ε
Ensure:返回一个 4 元组 D = (, , ,y k ε 0 enough ) .若 enough=true,则|y−f 1 (Y)×f 2 (Y)|<ε;否则,当 enough=false 时, y
k
的精度ε k 不能满足计算的要求,其精度需要提高至ε 0 .
1: ε′⇐0.1;

_
2: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, , )f ε′ ;
i
_
1
i

3: z ⇐ f ;
1 1
4: Calculate and Judge ({( , ) |1y ε ≤≤ n }, f , )ε′ ;
_

_
i
i i 2

5: z ⇐ f ;
2 2
6: ε 1 ⇐δ(ε/(2(|z 2 |+0.1)));

7: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, , )f ε ;
_
i
_
1
i
1

8: z ⇐ f ;
1
3
9: ε 2 ⇐δ(ε/(2(|z 2 |+0.1+ε 1 )));

10: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, f 2 , )ε 2 ;
i
_
_
i

11: z ⇐ f ;
4
2
12: y⇐z 3 ×z 4 ;
13: return (y,0,0,true);
算法 4. Calculate_and_Judge( {( , ) |1y ε ≤≤ n }, ( , ,...,f x x x ),ε )——这是一个内联函数,要嵌入到其他函

i
i i 1 2 n
数中.
Require: {( , ) | yε i i = y i ε ,1≤≤ } n ,f(x 1 ,x 2 ,…,x n ),ε>0;
y
i
i
i

i
Ensure:计算 AccurateEnough ({( , ) |1y ε i ≤≤ n }, , )f ε 的值.若其结果的第 4 个分量为 false,则返回该结果(4
i

元组);否则,将第 1 个分量赋给 f .

1: D ⇐ AccurateEnough ({( , ) |1≤≤ n f

y ε
i
}, , ) ε ;
i
i

2: if Fth ()D = false then

3: return D ;
4: else

5: f ⇐ Fst ( )D ; //获取 D 的第 1 个分量.变量名是由函数的第 2 个参数名与波浪号组合而成.
6: end if
(2) 除法运算

定理 2.4. 若命题 2.2 成立,并且 f 2 (Y)≠0,那么存在一个算法,对于 Y 的一个计算值 Y 与ε,或者能够判定,利用
此计算值可以获得一个值 y,使得:
|y−f 1 (Y)/f 2 (Y)|<ε (25)
成立,或者可以获得一个更为精确的计算值,使得利用此新的计算值,可以获得一个满足式(25)的 y.
证明:设 z 是|f 1 (Y)|的一个上界.类似于式(16),不难验证:对于 f i (Y)的计算值(z i ,ε i )(1≤i≤2)来说,只要满
1
足下列 3 个条件:
| z | 2 ,ε> | ε z /(z × (| z − | ε × ) ) | ε / 4,ε / | z < | ε < / 4 (26)
2 2 2 1 2 2 2 1 2
则有| z 1 /z 2 ε/2 −f 1 (Y)/f 2 (Y)|<ε.这样,只要令 y= z 1 /z 2 ε/2 ,则有式(25)成立.证明完毕. □
算法 5. AccurateEnough_Div( {( , ) |1y ε i ≤≤ n }, ( , ,...,f xx 2 x n ), f 2 ( , ,...,xx 2 x n ),ε ).

i
1
i
1
1