昨天查 mathomatic 的 MAN 时看到一个很有意思的计算平方根的方法 ( 当然不是叫你在 Excel 里 n^1/2 啦!):

求 n 的平方根，先假设一猜测值 X0 = 1，然后根据以下公式求出 X1，再将 X1 代入公式右边，继续求出 X2…通过有效次迭代后即可求出 n 的平方根，Xk+1

x_(k+1)=1/2(xk+n/(xk))

先让我们来验证下这个巧妙的方法准确性，来算下 2 的平方根 (Computed by Mathomatic)

1-> x_new = ( x_old + y/x_old )/2

                       y
            (x_old + -----)
                     x_old
#1: x_new = ---------------
                   2

1-> calculate x_old 1
Enter y: 2
Enter initial x_old: 1

 x_new = 1.5

1-> calculate x_old 2
Enter y: 2
Enter initial x_old: 1

 x_new = 1.4166666666667

1-> calculate x_old 3
Enter y: 2
Enter initial x_old: 1

 x_new = 1.4142156862745

1-> calculate x_old 10
Enter y: 2
Enter initial x_old: 1
Convergence reached after 6 iterations.

 x_new = 1.4142135623731
...

可见，随着迭代次数的增加，运算值会愈发接近真实值。很神奇的算法，可是怎么来的呢? 查了下 wikipedia 和 wolfram，原来算法的名字叫 Newton’s Iteration ( 牛顿迭代法 )。

下面是极其つまらない(boring) 的数理介绍，不喜欢数学的言下之意也就是绝大部分人可以略过了。

简单推导

假设 f(x) 是关于 X 的函数:

An illustration of one iteration of Newton's method

求出 f(x) 的一阶导，即斜率:

math

简化等式得到:

math

然后利用得到的最终式进行迭代运算直至求到一个比较精确的满意值，为什么可以用迭代法呢?理由是中值定理 (Intermediate Value Theorem):

如果 f 函数在闭区间 [a,b] 内连续，必存在一点 x 使得 f(x) = c，c 是函数 f 在闭区间 [a,b] 内的一点

我们先猜测一 X 初始值，例如 1，当然地球人都知道除了 1 本身之外任何数的平方根都不会是 1。然后代入初始值，通过迭代运算不断推进，逐步靠近精确值，直到得到我们主观认为比较满意的值为止。例如要求 768 的平方根，因为 252 = 625，而 302 = 900，我们可先代入一猜测值 26，然后迭代运算，得到较精确值:27.7128。

回到我们最开始的那个”莫名其妙”的公式，我们要求的是 N 的平方根，令 x2 = n，假设一关于 X 的函数 f(x) 为:

f(X) = X2 - n`

求 f(X) 的一阶导为:

f'(X) = 2X`

代入前面求到的最终式中:

Xk+1 = Xk - (Xk2 - n)/2Xk

化简即得到我们最初提到的那个求平方根的神奇公式了:

math

用泰勒公式推导

我之前介绍过在 The Art and Science of C 一书中有用到 泰勒公式求平方根的算法，其实牛顿迭代法也可以看作是泰勒公式 (Taylor Series) 的简化，先回顾下泰勒公式:

f(x0+epsilon)=f(x0)+f^'(x_0)epsilon+1/2f^('')(x_0)epsilon^2+....

仅保留等式右边前两项:

f(x0+epsilon) approx f(x0)+f^'(x_0)epsilon.

令 f(X0+ε) = 0，得到:

epsilon_0=-(f(x_0))/(f^'(x_0))

再令 X1 = X0 + ε0，得到 ε1…依此类推可知:

epsilon_n=-(f(x_n))/(f^'(x_n))

转化为:

x_(n+1)=x_n-(f(x_n))/(f^'(x_n))

引申

从推导来看，其实牛顿迭代法不仅可以用来求平方根，还可以求立方根，甚至更复杂的运算。

同样，我们还可以利用 C 语言来实现下那个最简单的求平方根的公式 ( 尽管我们可以直接用 sqrt() 完成 )

#include <stdio.h>
#include <math.h>

#define N 768

main() {
        float x=1;
        int i;
        for (i=1;i<=1000;i++) {  // recursion times : 1000
                x = (x + N/x)/2;
        }
        printf("The square root of %d is %f\n",N,x);
}