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

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

定理 2.1. 若命题 2.1 成立,则存在算法,对于 y i ,y j 任意给定的一对计算值 (, ),( , )y ε i y ε j ,或者可以判定:

i
j
| y × i y − j y × i y j | ε< (7)
成立,或者根据这一对计算值可以给出一对新的计算值,该计算值满足式(7).
证明:令:
ε′ = ε (| y + | ε × ) (8)
i j j
ε′′ = ε (| y + | ε × ) (9)
j i i
Mul _bound = ε′ + ε ε′′ = × (| y + | ε ) ε + × (| y + | ε ) (10)
i j j j i i
则有:
| y × i y − j y × i y j | |(y − ≤ i y × i ) y + j | |(y − j y × j ) y i | ε ×≤ i | y + j | ε j | y ≤ i | ε × ′ + ε ′′ = Mul _bound (11)
这样,若:
Mul_bound<ε (12)
则式(7)成立.
若式(12)不成立,下面分两种情形来讨论:
(1) ε′>ε″
若ε′>ε″,则ε′>ε/2(否则式(12)成立).这时,令 ε = i δε j | ε+ j ))) ,并在此新的更高精度下计算 y i 新的值,
( /(2(| y
则这个新值(不依赖于 y j 的计算值而始终)满足下列不等式:
|(y − y ) y× | ε≤ /(2(| y + | ε )) y× < ε / 2 (13)
i i j j j j
如果将 y i 新的值代入式(9)后有ε″≤ε/2,则结论成立;否则,利用新的 (, )y ε ,令 ε = δε | ε+ ))) ,并
( /(2(| y
i i j i i
在此新的更高精度下计算一个 y j 新的值,则这个新值满足下列不等式:
|(y − j y j ) y× i | ε< /(2(| y + i | ε i )) y× i < ε / 2 (14)
这样,由式(11)、式(13)以及式(14)知,式(7)成立.
(2) ε′≤ε″
由于两个变量相乘具有对称性,即 x i ×x j =x j ×x i .因此,只要将式(11)改写为:
| y × y − y × y | | (y − ≤ y ) y× | | (y+ − y ) y× | ,
i j i j i i j j j i
则类似于第 1 种情形,可以获得一对新的计算值,满足式(7).证明完毕. □

定理 2.2. 若命题 2.1 成立,并且 y j ≠0,则存在算法,对于 y i ,y j 任意给定的一对计算值 (, ),( , )y ε i y ε j ,或者可以
j
i
判定:
| yy i / j ε /2 − yy j | ε< (15)

/
i
成立,或者可以给出一对新的计算值,该计算值满足式(15).
证明:下面验证,若计算值满足下面 3 个条件:
| y > | 2 ,|ε ε (| y + | ε × )/(y × (| y − | ε )) | ε < /4,ε / | y < | ε / 4 (16)
j j j i i j j j i j
则有:
| yy − i / j yy j | ε< / 2 (17)
/
i
/
从而式(15)成立: | y y i / j ε /2 − y i / y ≤ i / j ε /2 − yy j | | yy+ i / j − yy j | ε< / 2 ε + 2 / = ε .
/
|| yy
i
i
j
首先,我们有:
| y i / y − j y i / y j | | (y≤ i × y − j y × i y j )/(y × j y j ) | | (y+ i × y − j y × i y j )/(y × j y j ) | ε< 1 + ε 2 (18)
其中, ε = 1 | ε i / y j |,ε 2 | (y × i ε = j )/(y × j y j ) | .然后,由式(16)中第 1 个不等式可以推出:| y j | | y> j | ε− j > 0 .这样,由
第 2 个不等式又能够得出:ε 2 <ε/4.同时,由第 3 个不等式有ε 1 <ε/4.因此,由式(18)知,式(17)成立.
若式(16)中第 1 个不等式不成立,那么由于|y j |>0,因此,通过不停地提高精度,比如多次执行ε j =δ(ε j /10),我们
总能找到一个满足条件的计算值;同样道理,对于式(16)中第 2 个不等式,只要不停地缩小ε j 的值,则可得
到满足这个不等式的一对新的计算值;最后,若第 3 个不等式不成立,那么令 ε = δ (| y ε j | / 4) ,则有不等式成立.证
i