Brian Warehouse

求n的平方根，先假設一猜測值DE>X₀ = 1DE>，然后根據以下公式求出DE>X₁DE>，再將DE>X₁DE>代入公式右邊，繼續求出DE>X₂DE>…通過有效次迭代后即可求出n的平方根，DE>X_k+1DE>

先讓我們來驗證下這個巧妙的方法準確性，來算下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 (牛頓迭代法)。

下面是數理介紹，不喜歡數學的言下之意也就是絕大部分人可以略過了。

簡單推導

假設DE>f(x)DE>是關于DE>XDE>的函數:

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

簡化等式得到:

然后利用得到的最終式進行迭代運算直至求到一個比較精確的滿意值，為什么可以用迭代法呢?理由是中值定理(Intermediate Value Theorem):

如果DE>fDE>函數在閉區間DE>[a,b]DE>內連續，必存在一點DE>xDE>使得DE>f(x) = cDE>，DE>cDE>是函數DE>fDE>在閉區間DE>[a,b]DE>內的一點

我們先猜測一DE>XDE>初始值，例如1，當然地球人都知道除了1本身之外任何數的平方根都不會是1。然后代入初始值，通過迭代運算不斷推進，逐步靠近精確值，直到得到我們主觀認為比較滿意的值為止。例如要求768的平方根，因為DE>25² = 625DE>，而DE>30² = 900DE>，我們可先代入一猜測值26，然后迭代運算，得到較精確值:27.7128。

回到我們最開始的那個”莫名其妙”的公式，我們要求的是DE>NDE>的平方根，令DE>x² = nDE>，假設一關于DE>XDE>的函數DE>f(x)DE>為:

DE>f(X) = X² - nDE>

求DE>f(X)DE>的一階導為:

DE>f'(X) = 2XDE>

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

DE>X_k+1 = X_k - (X_k² - n)/2X_kDE>

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

用泰勒公式推導

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

僅保留等式右邊前兩項:

令DE>f(X₀+ε) = 0DE>，得到:

再令DE>X₁ = X₀ + ε₀DE>，得到DE>ε₁DE>…依此類推可知:

轉化為: