27. [M25] 此题需要结合正文中计算 log10xlog10x 的标准算法。 用 x′kx′k 表示 xkxk 基于有限精度的近似值： x(1−σ)≤10nx′0≤x(1+ϵ)x(1−σ)≤10nx′0≤x(1+ϵ) ，用 ykyk 替代公式（18）中的 (x′k−1)2(x′k−1)2，即 (x′k−1)2(1−σ)≤yk≤(x′k−1)2(1+ϵ)(x′k−1)2(1−σ)≤yk≤(x′k−1)2(1+ϵ) 并且 1≤yk<1001≤yk<100 ，这里的 σσ 和 ϵϵ 是很小的大于零的常数，表示基于有限精度的近似值的误差上界和下界。若用 log′10xlog′10x 表示计算结果，试证明 k 步之后有 log10x+2log10(1−σ)−1/2k<log′10x≤log10x+2log10(1+ϵ)log10x+2log10(1−σ)−1/2k<log′10x≤log10x+2log10(1+ϵ) 。
证明：
在此回顾一下正文中计算 log10xlog10x 的标准算法。
log10xlog10x 用二进制表示为 log10x=n.b1b2b3...=n+b1/2+b2/4+b3/8+...log10x=n.b1b2b3...=n+b1/2+b2/4+b3/8+... （17）
假设 x≥1x≥1 ，若 x < 1, 则首先计算 log101/xlog101/x。
x 的整数部分 n 满足 1≤x/10n<101≤x/10n<10 。为得到 b1,b2,...b1,b2,... 的值，我们设 x0=x/10nx0=x/10n ，对所有的 k≥1k≥1 ，
若 x2k−1<10x2k−1<10 ，则 bk=0,xk=x2k−1bk=0,xk=x2k−1 ；
若 x2k−1≥10x2k−1≥10 ，则 bk=1,xk=x2k−1/10bk=1,xk=x2k−1/10 (18)
这个过程的有效性来自如下事实：
对 k = 0, 1, 2, ...，有 1≤xk=x2k/102k(n+b1/2+...+bk/2k)<101≤xk=x2k/102k(n+b1/2+...+bk/2k)<10 ， (19)
这个事实可以用归纳法证明：当 k = 0 时，显然有 1≤x0=x/10n<101≤x0=x/10n<10 ，
k≥1k≥1 时，若 xk−1xk−1 满足条件 1≤xk−1=x2k−1/102k−1(n+b1/2+...+bk−1/2k−1)<101≤xk−1=x2k−1/102k−1(n+b1/2+...+bk−1/2k−1)<10 ，
此时 x2k−1=x2k/102k(n+b1/2+...+bk−1/2k−1)x2k−1=x2k/102k(n+b1/2+...+bk−1/2k−1) 满足 1≤x2k−1<1001≤x2k−1<100 ，
当 1≤x2k−1<101≤x2k−1<10 时，令 bk=0bk=0 ，则 xk=x2k/102k(n+b1/2+...+bk−1/2k−1+0/2k)=x2k−1xk=x2k/102k(n+b1/2+...+bk−1/2k−1+0/2k)=x2k−1 ，满足 1≤xk<101≤xk<10 ；
当 10≤x2k−1<10010≤x2k−1<100 时，令 bk=1bk=1，则 xk=x2k/102k(n+b1/2+...+bk−1/2k−1+1/2k)=x2k/102k(n+b1/2+...bk−1/2k−1)+1=x2k−1/10xk=x2k/102k(n+b1/2+...+bk−1/2k−1+1/2k)=x2k/102k(n+b1/2+...bk−1/2k−1)+1=x2k−1/10 ，仍然满足 1≤xk<101≤xk<10 。归纳证明完毕。
回到这道习题，我们有 log10x+2log10(1−σ)−1/2k<log′10x≤log10x+2log10(1+ϵ)log10x+2log10(1−σ)−1/2k<log′10x≤log10x+2log10(1+ϵ) ⇔log10x(1−σ)2/101/2k<log′10x≤log10x(1+ϵ)2⇔log10x(1−σ)2/101/2k<log′10x≤log10x(1+ϵ)2 ⇔x(1−σ)2/101/2k<x′≤x(1+ϵ)2⇔x(1−σ)2/101/2k<x′≤x(1+ϵ)2 ⇔x2k(1−σ)2k+1/10<(x′)2k≤x2k(1+ϵ)2k+1⇔x2k(1−σ)2k+1/10<(x′)2k≤x2k(1+ϵ)2k+1
由于 σ,ϵσ,ϵ 都是大于零的很小的常数，可以在这里假定 0<1−σ<1,1<1+ϵ<20<1−σ<1,1<1+ϵ<2 ， 则 x2k(1−σ)2k+1/10<x2k(1−σ)2k+1/(1−σ)=x2k(1−σ)2k+1−1x2k(1−σ)2k+1/10<x2k(1−σ)2k+1/(1−σ)=x2k(1−σ)2k+1−1 ，而 x2k(1+ϵ)2k+1>x2k(1+ϵ)2k+1/(1+ϵ)=x2k(1+ϵ)2k+1−1x2k(1+ϵ)2k+1>x2k(1+ϵ)2k+1/(1+ϵ)=x2k(1+ϵ)2k+1−1 ，因此要证明以上的不等式成立，只需证明比它们更加严格的不等式 x2k(1−σ)2k+1−1≤(x′)2k≤x2k(1+ϵ)2k+1−1x2k(1−σ)2k+1−1≤(x′)2k≤x2k(1+ϵ)2k+1−1 即可。
类似于公式（19），我们有 1≤x′k=(x′)2k/102k(n+b1/2+...+bk/2k)<101≤x′k=(x′)2k/102k(n+b1/2+...+bk/2k)<10 ，即 (x′)2k=102k(n+b1/2+...+bk/2k)x′k(x′)2k=102k(n+b1/2+...+bk/2k)x′k ，代入上面的式子就得到要证明的不等式为 x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk/2k)x′k≤x2k(1+ϵ)2k+1−1x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk/2k)x′k≤x2k(1+ϵ)2k+1−1
继续用归纳法。当 k=0k=0 时，根据题面显然有 x(1−σ)≤10nx′0≤x(1+ϵ)x(1−σ)≤10nx′0≤x(1+ϵ) ，
k≥1k≥1 时，若 x′k−1x′k−1 满足 x2k−1(1−σ)2k−1≤102k−1(n+b1/2+...+bk−1/2k−1)x′k−1≤x2k−1(1+ϵ)2k−1x2k−1(1−σ)2k−1≤102k−1(n+b1/2+...+bk−1/2k−1)x′k−1≤x2k−1(1+ϵ)2k−1 ，对上式各个部分分别取平方，得到 x2k(1−σ)2k+1−2≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2≤x2k(1+ϵ)2k+1−2x2k(1−σ)2k+1−2≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2≤x2k(1+ϵ)2k+1−2
先看左边的不等式 x2k(1−σ)2k+1−2≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2x2k(1−σ)2k+1−2≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2 ，两边同时乘以 (1−σ)(1−σ) ，且根据题面有 (x′k−1)2(1−σ)≤yk(x′k−1)2(1−σ)≤yk ，⇒x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2(1−σ)≤102k(n+b1/2+...+bk−1/2k−1)yk⇒x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2(1−σ)≤102k(n+b1/2+...+bk−1/2k−1)yk
由于 1≤yk<1001≤yk<100 ，当 yk<10yk<10 时，令 bk=0,x′k=ykbk=0,x′k=yk ，可得 x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk−1/2k−1+0/2k)yk=102k(n+b1/2+...+bk−1/2k−1+bk/2k)x′kx2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk−1/2k−1+0/2k)yk=102k(n+b1/2+...+bk−1/2k−1+bk/2k)x′k ；当 10≤yk<10010≤yk<100 时，令 bk=1,x′k=yk/10bk=1,x′k=yk/10 ，即 yk=10x′kyk=10x′k ，可得 x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk−1/2k−1)yk=102k(n+b1/2+...+bk−1/2k−1+1/2k)x′k=102k(n+b1/2+...+bk−1/2k−1+bk/2k)x′kx2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk−1/2k−1)yk=102k(n+b1/2+...+bk−1/2k−1+1/2k)x′k=102k(n+b1/2+...+bk−1/2k−1+bk/2k)x′k
。综合起来，可得 x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk/2k)x′kx2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk/2k)x′k 。
再看右边的不等式 102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2≤x2k(1+ϵ)2k+1−2102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2≤x2k(1+ϵ)2k+1−2 ，两边同时乘以 (1+ϵ)(1+ϵ)，
且根据题面有 yk≤(x′k−1)2(1+ϵ)yk≤(x′k−1)2(1+ϵ) ，可以推得102k(n+b1/2+...+bk−1/2k−1)yk≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2(1+ϵ)≤x2k(1+ϵ)2k+1−1102k(n+b1/2+...+bk−1/2k−1)yk≤102k(n+b1/2+...+bk−1/2k−1)(x′k−1)2(1+ϵ)≤x2k(1+ϵ)2k+1−1
和上面的推导类似，可得 102k(n+b1/2+...+bk/2k)x′k≤x2k(1+ϵ)2k+1−1102k(n+b1/2+...+bk/2k)x′k≤x2k(1+ϵ)2k+1−1 。结合起来，就得到了要证明的不等式 x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk/2k)x′k≤x2k(1+ϵ)2k+1−1x2k(1−σ)2k+1−1≤102k(n+b1/2+...+bk/2k)x′k≤x2k(1+ϵ)2k+1−1
。 反推回去，就证明了 log10x+2log10(1−σ)−1/2k<log′10x≤log10x+2log10(1+ϵ)log10x+2log10(1−σ)−1/2k<log′10x≤log10x+2log10(1+ϵ) 。这个式子也说明，随着 k 的增大，log′10xlog′10x 越来越接近于 log10xlog10x 。