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

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

20: D ⇐ AccurateEnough ({( , ) |1≤≤ n z
y ε

}, , ) ε ; //z 为式(35)中对应等价表达式.
i
i
i
21: end if
2.2 举例说明
已知函数 f(x 1 ,x 2 )=sin(1000x 1 )+x 1 x 2 , Y = (,y y = ) ( , 2)π ,误差限ε=0.1 .
3
1 2

例 2.1:假设ε 1 =0.1 ,ε 2 =0.1 .这时,我们取 Y = ( ,y y = ) (3.14, 1.414) .判断由 ()f Y 能否获得一个 y,满足:
2
3
1 2
|y−f(Y)|<ε (36)
首先,平均分配误差:令 sin(1000x 1 )与 x 1 x 2 的误差限均为:
ε′=ε/2 (37)
然后,对于正弦函数来说,由算法 6 知,其自变量 1000x 1 的误差限应为ε″=ε′/2=ε/4;继而,由乘法的相关算法可推出
x 1 的精度(或误差限)应为:
6
ε″′=ε″/1000=0.1 /4 (38)

由于ε″′<ε 1 ,因此,由 Y 不能确保可以得出一个满足式(36)的 y.这样,建议 y 的精度ε 1 提高至式(38)中的值.
1

例 2.2:设ε 1 =0.1 ,ε 2 =0.1 .这时,取 Y = ( ,y y = 2 ) (3.1415927,1.414) .判断由 ()f Y 能否获得一个 y,满足式(36).
7
3
1
由例 2.1 知, y 的精度已能满足 sin(1000x 1 )的精度要求.
1
下面,我们分析ε 1 ,ε 2 是否能够满足式(37)中对 x 1 x 2 的精度要求.
+
3
+
+
由于 ε (| y + | ε ) ε + (| y + | ε ) = 0.1 × 7 (|1.414 | 0.1 ) 0.1 × 3 (| 3.1415927 | 0.1 ) = 7 0.0031417343 ε > ′ ,即计算
1 2 2 2 1 1

值不满足不等式(12),因此,由 Y 不能保证可以得出一个满足式(36)的 y.
另外,由于 ε 1 (| y + 2 | ε 2 ) ε < 2 (| y + 1 | ε 1 ) ,因此,令 ε 2 (| y + 1 ) ε < ′ / 2 ,即 ε < ε /(2 (| y× 1 | ε′ + 1 )) = 0.000079577... ,因
| ε
1
2
5
此,我们建议ε 2 =δ(0.000079577…)=0.1 .

7
例 2.3:设ε 1 =0.1 ,ε 2 =0.1 .这时,取 Y = ( ,y y = ) (3.1415927,1.41421) .由上例(即例 2.2)知:通过 ()f Y ,我们可以
5
1 2
获得一个值 y,满足式(36)中的条件.

可以验证, fY = ( ) 4.4429182..., ( )fY = 4.4428829... .从而, y = f ( )Y ε = 4.443 .它在满足 | y − f ( ) |Y < ε 的同
时,也满足不等式(36):|y−f(Y)|=|4.443−4.4428829…|=0.000117…<ε.
3 循环迭代程序的可信计算算法
对于式(3)来说,由 AccurateEnough 算法(即算法 0)可得:
定理 3.1. 存在一个算法,对于任意的ε>0,可以获得 y n 的一个计算值 y ,使得 | y − y | ε< .

n n n
证明:下面使用归纳法进行证明.
当 n=1 时,由于只是计算一个表达式的值,因此我们可以利用一些算法获得其误差可控的值.假设 n≤k 时结

论也成立,即,由算法可以获得 y 1 ,y 2 ,…,y k 任意精度的值.再设 (,y y 2 ,..., y k ) 是(y 1 ,y 2 ,…,y k )的一个计算值.这时,由
1
AccurateEnough 算法知,我们可以判断其是否足够精确,以至可以利用它获得 f k+1 (y 1 ,y 2 ,…,y k )误差可控的值.若该
值足够精确,那么意味着我们也能够获得 y k+1 =f k+1 (y 1 ,y 2 ,…,y k )给定精度的值.从而定理成立;否则,若该值不够精
确,那么利用 AccurateEnough 算法,通过提高有关值的精度,总可以找到一个计算值,使得该值足够精确,以至可
以获得 y k+1 =f k+1 (y 1 ,y 2 ,…,y k )给定精度的值.从而定理获证.证明完毕. □
根据定理 3.1,我们可得下列主算法.它计算 y n =f n (y 1 ,y 2 ,…,y n−1 )的值.
算法 11. Main( x 2 x m , , ,..., ,f f 2 f ε ).
, ,...,x
n
1
1
Require:m,{|1x i ≤≤ m } ,n,{y i |y 1 =f 1 (x 1 ,x 2 ,…,x m ),y i =f i (y 1 ,y 2 ,…,y i−1 ),2≤i≤n},ε>0;
i
Ensure: y ≈ y | , y − y | ε< ;
n n n n
1: l⇐1; //初始化
l
2: extra_precision⇐0.1 ; //初始化精度步长
3: j⇐1; //初始化