求n的平方根，先假設一猜測值X0 = 1，然后根據以下公式求出X1，再將X1代入公式右邊，繼續求出X2…通過有效次迭代后即可求出n的平方根，Xk+1

先讓我們來驗證下這個巧妙的方法準確性，來算下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的函數:

求出f(x)的一階導，即斜率:

簡化等式得到:

然后利用得到的最終式進行迭代運算直至求到一個比較精確的滿意值，為什么可以用迭代法呢?理由是中值定理(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

化簡即得到我們最初提到的那個求平方根的神奇公式了:

用泰勒公式推導

我之前介紹過在The Art and Science of C一書中有用到泰勒公式求平方根的算法，其實牛頓迭代法也可以看作是泰勒公式(Taylor Series)的簡化，先回顧下泰勒公式:

僅保留等式右邊前兩項:

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

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

轉化為:

引申

從推導來看，其實牛頓迭代法不僅可以用來求平方根，還可以求立方根，甚至更復雜的運算。

同樣，我們還可以利用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);
}