SICP 1.45证明?

题目详见SICP 1.45,也可参见sarabander.github.io/si或者Structure and Interpretation of Computer Programs倒数第二个exercise。 大意是通过求f(y) = x/y^{n-1}的不动点来近似求解x的n次方根,问需要几次平均阻尼(average-damp)才能得到一个收敛的算法而不会产生震荡之类的问题。实验结果是\lfloor\log_2 n\rfloor,不过我不明白为什么。 不知道有没有相关的定理或者证明?
关注者
42
被浏览
1685

1 个回答

其实还是和牛顿法有一点点关系。

需要求解x的n次方根,那么等价于求解以下方程的零点
f(y)=y^n-x
我们看看m次的平均阻尼是个什么过程:
\frac{1}{2}(\cdots\frac{1}{2}(\frac{1}{2}(\frac{x}{y^{n-1}}+y)+y)\cdots+y)=\frac{1}{2^m}\left(\frac{x}{y^{n-1}}+(2^m-1)y\right)
也就是每次迭代,都是这样的(这里有意省略了 k+1 的下标):
y=\frac{1}{2^m}\left(\frac{x}{y_k^{n-1}}+(2^m-1)y_k\right)
这和牛顿法很像。

这是一个关于 y 的一次方程,也就是一条直线,这么写会更清楚一些:
g(y)=2^my_k^{n-1}y-x-(2^m-1)y_k^n
迭代过程,就是不断求解这条直线的零点。

这条直线呢,是经过这个点的:(y_k,y_k^n-x),也就是说,是在f(y)上的。
另一方面,这条直线的斜率,是2^my_k^{n-1},显然,随着平均阻尼过程的增加,m 增大,斜率也增大。先看个图:
中间黄色的直线是切线,牛顿法就是用的这条直线。如果直线斜率比切线斜率小,就是绿色直线的情况;如果直线斜率比切线大,就是红色直线的情况。
显然,绿色直线的情况会引起迭代过程震荡。事实上,必须保证直线的零点永远在曲线零点的同一侧(这个容易说明,只要直线斜率与切线斜率之比为常数并且小于1,那么就不能保证直线的零点永远在曲线零点的同一侧)

所以直线的斜率必须大于等于切线的斜率,也就是
2^my_k^{n-1}\ge ny^{n-1}
于是
m\ge \log_2n