/blog/ekd123

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]）。在此不再赘述。