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

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

y
Require: {( , ) | yε i i = y ,1≤≤ } n ,f(x 1 ,x 2 ,…,x n ),ε>0;
i
i
i
i ε
Ensure:返回一个 4 元组 D = (, , ,y k ε 0 enough ) .若 enough=true,则|y−arctan(f(y 1 ,y 2 ,…,y n ))|<ε;否则,当 enough=
false 时, y 的精度ε k 不能满足计算的要求,其精度需要提高至ε 0 .
k
1: Calculate and Judge ({( , ) |1y ε i i ≤≤ n }, , / 2)f ε ;
_
i
_
2: y ⇐ arctan( )f ε /2 ;
3: return (y,0,0,true);
(5) 自然对数函数

定理 2.6. 若命题 2.2 成立,并且 f(Y)>0,那么存在一个算法,对于 Y 的一个计算值 Y 与ε,或者能够判定,利用
此计算值可以获得一个值 y,使得:
|y−ln(f(Y))|<ε (30)
成立,或者可以获得一个更为精确的计算值,使得利用此新的计算值,可以获得一个满足式(30)的 y.
证明:首先,由拉格朗日中值定理,在 z 与 f(Y)之间存在一个 c,使得|ln(z)−ln(f(Y))|=|(z−f(Y))/c|.
已知不等式组:
|z−f(Y)|<ε′,z>2ε′≤(z−ε′)ε (31)
其中,ε′=ε.
若式(31)成立,则有| ln(z) ε/2 −ln(f(Y))|≤| ln(z) ε/2 −ln(z)|+|ln(z)−ln(f(Y))|<ε/2+|(z−f(Y))/c|<ε/2+ε′/(z−ε′)≤ε.
这时,只要令 y= ln(z) ε/2 ,则有式(30)成立.
n
否则,若式(31)不成立,则令ε′=0.1 ε(n∈ ).这时,由 f(Y)>0 与假设知:只要 n 足够大,总可以获得一个计算值

(, )Y ε′ 以及对应的 z,使得式(31)成立.这样,新获得的 z 的函数值 ln(z) ε/2 能够满足式(30).证明完毕. □
算法 8. AccurateEnough_Ln( {( , ) |1y ε ≤≤ n }, ( , ,...,f x x x ),ε ).

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

_
2: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, , )f ε′ ;
i
_
i
3: while (| f |≤ 2ε′ ∨ 2ε (| f − | ε′ ′ ) )ε > do
4: ε′⇐0.1ε′;
i

_
5: Calculate and Judge ({( , ) |1y ε i ≤≤ n }, , )f ε′ ;
_
i
6: end while
7: y ⇐ ln( )f ε /2 ;
8: return (y,0,0,true);
(6) 指数函数

定理 2.7. 若命题 2.2 成立,那么存在一个算法,对于 Y 的一个计算值 Y 与ε,或者能够判定,利用此计算值可
以获得一个值 y,使得:
|y−e f(Y) |<ε (32)
成立,或者可以获得一个更为精确的计算值,使得利用此新的计算值,可以获得一个满足式(32)的 y.
证明:已知不等式:
|z−f(Y)|<ε′ (33)
()
其中, ε min{0.1, ( /(2( eδ′ = ε fY 0.1 0.1+ 0.2 + 0.2)))} .
z
z
z
z
z
若式(33)成立,则有| e ε/2 −e f(Y) |≤| e ε/2 −e |+|e −e f(Y) |<ε/2+|e −e f(Y) |.由拉格朗日定理,在 z 与 f(Y)之间存在一个
z
c
z
c,使得|e −e f(Y) |=|(z−f(Y))e |≤|(y−f(Y))e z+0.1 |<ε′( e z+0.1 0.2 +0.2)<ε/2.这时,只要令 y= e ε/2 ,则有式(32)成立.