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

赵世忠 等:循环迭代程序的一种可信计算算法 3693

y
Require: {( , ) | yε i i = y ,1≤≤ } n ,f 1 (x 1 ,x 2 ,…,x n ),f 2 (x 1 ,x 2 ,…,x n ),f(y 1 ,y 2 ,…,y n )≠0,ε>0;
i
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: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, ,0.1)f 1 ;
i
_
_
i
2: z ⇐ 1 | f 1 | 0.1+ ;
3: ε 2 ⇐0.1;
_
i
_

4: Calculate and Judge ({( , ) |1y ε ≤≤ n }, f , )ε ;
i i 2 2
5: while (| f |≤ 2 ε× ) do;
2 2
6: ε 2 ⇐0.1×ε 2 ;
7: Calculate and Judge ({( , ) |1y ε ≤≤ n }, f , )ε ;
_
i
_

i i 2 2
8: end while
9: while (| 4 z× 1 × ε 2 | | f ×≥ 2 (| f 2 | ε 2 ) ε − × |) do
10: ε 2 ⇐0.1×ε 2 ;

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

_
_
13: Calculate and Judge ({( , ) |1y ε i i n }, , (|f δ ≤≤ 1 f 2 | / 4 ε × )) ;
i
14: y ⇐ f / f ;
1 2 ε / 2
15: return (y,0,0,true);
(3) 正弦函数

定理 2.5. 若命题 2.2 成立,那么存在一个算法,对于 Y 的一个计算值 Y 与ε,或者能够判定,利用此计算值可
以获得一个值 y,使得:
|y−sin(f(Y))|<ε (27)
成立,或者可以获得一个更为精确的计算值,使得利用此新的计算值,可以获得一个满足式(27)的 y.

证明:首先,对于误差限ε/2 来说,由假设知,我们或者可以判定,利用 Y 可以获得一个值 z,满足:
|z−f(Y)|<ε/2 (28)
或者可以获得一个更为精确的计算值,利用该计算值可以获得满足式(28)的一个 z.
若式(28)成立,则有:
| sin(z) ε/2 −sin(f(Y))|≤| sin(z) ε/2 −sin(z)|+|sin(z)−sin(f(Y))|<ε/2+|z−f(Y)|<ε (29)
这样,只要令 y= sin(z) ε/2 ,则有式(27)成立.

若式(28)不成立,那么我们可以获得一个更为精确的计算值 Y ,利用它可以获得一个新的 z,满足式(28).这
样,式(29)也成立.因此,新的 z 的函数值 sin(z) ε/2 使得式(27)成立.证明完毕. □
算法 6. AccurateEnough_Sin( {( , ) |1y ε i ≤≤ n }, ( , ,...,f x x 2 x n ),ε ).

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

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

_
i
1: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, , / 2)f ε ;
_
i
2: y ⇐ sin( )f ε /2 ;
3: return (y,0,0,true);
(4) 反正切函数
2
由于 arctan(x)′=1/(1+x )≤1,因此类似于正弦函数的算法 6,我们有下列算法 7.
算法 7. AccurateEnough_ArcTan( {( , ) |1y ε i ≤≤ n }, ( , ,...,f x x 2 x n ),ε ).

i
1
i