魔法书1.1补充:平方根算法的论证

Ma Kai posted @ Jun 18, 2016 05:24:32 PM in 编程 with tags SICP , 432 阅读

SICP 1.1 节「程序设计的基本元素」给出了一个计算平方根的算法,原书并没有给出证明,大概是因为不太适合书的主题,我在此写这个证明只是为了补充书上所缺,满足自己的强迫症,如有错误请指出!

证明

数学表达如下:

对于任意实数 [tex]b>0[/tex],数列 [tex]a_n[/tex] 的递推公式是 [tex]a_{n+1}=\frac{a_{n}+b/a_{n}}{2}[/tex],且[tex]a_1=1[/tex],那么当 n 充分大时,[tex]a_n[/tex] 可以无限接近 [tex]\sqrt{b}[/tex]。下面给出证明。

由 [tex]a_{n+1}-a_{n}=\frac{b-a_n^2}{2a_n}[/tex] 可知,当 [tex]a_n<\sqrt{b}[/tex] 时,数列 [tex]a_n[/tex] 是严格递增的;当 [tex]a_n>\sqrt{b}[/tex] 时,数列 [tex]a_n[/tex] 是严格递减的。容易知道,当 b > 1 时,数列 [tex]a_n[/tex] 严格递增且有上界;当 b = 1 时,无疑 [tex]a_n=1[/tex] 恒成立;当 b < 1 时,数列 [tex]a_n[/tex] 严格递减且有下界。因此确信数列 [tex]a_n[/tex] 收敛且存在极限,记作 [tex]a[/tex]。

递推式两边取极限得:[tex]a=\frac{a+\frac{b}{a}}{2}[/tex]

整理即得:[tex]a=\sqrt{b}[/tex]

也就是,当 n 充分大时,[tex]a_n[/tex] 可以无限接近 [tex]\sqrt{b}[/tex]。

注记

我一开始认为 [tex]a_1[/tex] 是可以选取任意正数的,后来计算一番发现,存在特定的组合 [tex]a_1[/tex] 和 [tex]b[/tex],使得数列不收敛。如当 [tex]{a_1}^2=\frac{\sqrt{2}+1}{3}b[/tex] 时,[tex]a_3 = a_1[/tex],此时所有奇数项相等,所有偶数项相等,数列围绕 [tex]\sqrt{b}[/tex] 摆动而不收敛。尽管在计算机上存在浮点数舍入误差,不一定能产生预期的效果,但是只有当[tex]a_1=1[/tex]时才能在数学上严格证明出对于所有正数 [tex]b[/tex] 都一定能求出算数平方根的近似值。

实际上迭代算平方根的方法很多,比如说还可以由 [tex]c^2-1=b-1[/tex] 得到 [tex]c_{n+1}=\frac{b-1}{c_n+1}+1[/tex],可以证明该数列的极限也是 [tex]\sqrt{b}[/tex](选取恰当的 [tex]c_1[/tex])。在此不再赘述。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter