Brian Warehouse

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

先讓我們來(lái)驗(yàn)證下這個(gè)巧妙的方法準(zhǔn)確性，來(lái)算下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
...

可見，隨著迭代次數(shù)的增加，運(yùn)算值會(huì)愈發(fā)接近真實(shí)值。很神奇的算法，可是怎么來(lái)的呢? 查了下wikipedia和wolfram，原來(lái)算法的名字叫Newton’s Iteration (牛頓迭代法)。

下面是數(shù)理介紹，不喜歡數(shù)學(xué)的言下之意也就是絕大部分人可以略過(guò)了。

簡(jiǎn)單推導(dǎo)

假設(shè)DE>f(x)DE>是關(guān)于DE>XDE>的函數(shù):

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

簡(jiǎn)化等式得到:

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

如果DE>fDE>函數(shù)在閉區(qū)間DE>[a,b]DE>內(nèi)連續(xù)，必存在一點(diǎn)DE>xDE>使得DE>f(x) = cDE>，DE>cDE>是函數(shù)DE>fDE>在閉區(qū)間DE>[a,b]DE>內(nèi)的一點(diǎn)

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

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

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

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

DE>f'(X) = 2XDE>

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

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

化簡(jiǎn)即得到我們最初提到的那個(gè)求平方根的神奇公式了:

用泰勒公式推導(dǎo)

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

僅保留等式右邊前兩項(xiàng):

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

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

轉(zhuǎn)化為: