如何通俗易懂地講解牛頓迭代法求開方？

12-27

五次及以上多項式方程沒有根式解（就是沒有像二次方程那樣的萬能公式），這個是被伽羅瓦用群論做出的最著名的結論。

但是，沒有王屠夫難道非得吃帶毛豬？工作生活中還是有諸多求解高次方程的真實需求（比如行星的軌道計算，往往就是涉及到很複雜的高次方程），這日子可怎麼過下去啊？

沒有根式解不意味著方程解不出來，數學家也提供了很多方法，牛頓迭代法就是其中一種。

1 切線是曲線的線性逼近

要講牛頓迭代法之前我們先說一個關鍵問題：切線是曲線的線性逼近。

這個是什麼意思呢？我們來看一看，下面是 $f(x)=x^2$ 的圖像：

我們隨便選一點 $f(x)$ 上的一點 $(a,f(a))$ 作它的切線：

我們在A點處放大圖像：

上圖中，紅色的線是 $f(x)$ ，黑色的是A點處的切線，可以看出放大之後切線和 $f(x)$ 非常接近了。很明顯，如果我們進一步放大圖像，A點切線就越接近 $f(x)$ 。

可以自己動手試試：

此處有互動內容，點擊此處前往操作。

因為切線是一條直線（也就是線性的），所以我們可以說，A點的切線是 $f(x)$ 的線性逼近。離A點距離越近，這種逼近的效果也就越好，也就是說，切線與曲線之間的誤差越小。所以我們可以說在A點附近，「切線 $approx f(x)$ 」。

2 牛頓-拉弗森方法的幾何直覺

牛頓迭代法又稱為牛頓-拉弗森方法，實際上是由牛頓、拉弗森（又是一個被牛頓大名掩蓋的傢伙）各自獨立提出來的。

牛頓-拉弗森方法提出來的思路就是利用切線是曲線的線性逼近這個思想。

牛頓、拉弗森們想啊，切線多簡單啊，研究起來多容易啊，既然切線可以近似於曲線，我直接研究切線的根不就成了。

然後他們觀察到這麼一個事實：

隨便找一個曲線上的A點（為什麼隨便找，根據切線是切點附近的曲線的近似，應該在根點附近找，但是很顯然我們現在還不知道根點在哪裡），做一個切線，切線的根（就是和x軸的交點）與曲線的根，還有一定的距離。牛頓、拉弗森們想，沒關係，我們從這個切線的根出發，做一根垂線，和曲線相交於B點，繼續重複剛才的工作：

之前說過，B點比之前A點更接近曲線的根點，牛頓、拉弗森們很興奮，繼續重複剛才的工作：

第四次就已經很接近曲線的根了

經過多次迭代後會越來越接近曲線的根（下圖進行了50次迭代，哪怕經過無數次迭代也只會更接近曲線的根，用數學術語來說就是，迭代收斂了）：

3 牛頓-拉弗森方法的代數解法

已知曲線方程 $f(x)$ ，我們在 $x_n$ 點做切線，求 $x_{n+1}$ ：

容易得出， $x_n$ 點的切線方程為： $f(x_n)+f$ 。

要求 $x_{n+1}$ ，即相當於求 $f(x_n)+f$ 的解，即 $f(x_n)+f$ ：

$x_{n+1}=x_{n}-{frac {f(x_{n})}{f$ 。

4 牛頓-拉弗森方法是否總是收斂（總是可以求得足夠近似的根）？

牛頓-拉弗森方法源於直覺，這種直覺本身有一定程度的合理性。

我們來看看收斂的充分條件：

若 $f$ 二階可導，那麼在待求的零點 $x$ 周圍存在一個區域，只要起始點 $x_0$ 位於這個鄰近區域內，那麼牛頓-拉弗森方法必定收斂。

也就是說，在這個區域內，用切線代替曲線這個直覺是合理的。但是，因為我們不知道根點到底在哪裡，所以起始點 $x_0$ 選擇就不一定在這個區域內，那麼這個直覺就不可靠了。

4.1 駐點

起始點不幸選擇了駐點，從幾何上看切線根本沒有根。

從代數上看， $x_{n+1}=x_{n}-{frac {f(x_{n})}{f$ 沒有意義。

4.2 越來越遠離的不收斂

下面是 $f(x)=x^{frac{1}{3}}$ 的曲線，不論怎麼選擇起始點，越迭代就越遠離根點：

從代數上看， $x_{n+1}=x_{n}-{frac {f(x_{n})}{f$ ，就是說下一個點比上一個點更遠離根點。

此處根點很顯然是0點，而 $f$ 是不存在的。

4.3 循環震蕩的不收斂

還有一種更酸爽的不收斂，就是不斷的循環震蕩。

比如下面是 $f(x)=|x|^{frac{1}{2}}$ 的曲線：

很漂亮的圖像吧。從代數上看就是 $x_{n+1}=-x_n$ 造成的。

由於選擇的起始點不對，造成這種循環的情況其實還挺多，在很多曲線的某些點都會出現這種情況。

此處根點也是0點，而 $f$ 是不存在的。但是不一定 $f$ 不存在就無法用牛頓-拉弗森方法求解，比如 $f(x)=|x|^{frac{2}{3}}$ 依然可以用牛頓-拉弗森方法：

這是因為之前說的收斂判斷條件只是充分條件。

4.4 不能完整求出所有的根

比如 $f(x)=x^4-2x^2+x$ 這種有多個根的函數，因為選擇的起始點，只能求到附近的根：

也可能想求附近的根，由於選擇的起始點不對，結果求到遠處的根：

4.5 自己動手試試

通過按鈕可以切換函數，拖動「起始點」也會有驚喜：

此處有互動內容，點擊此處前往操作。

4.6 總結

應用牛頓-拉弗森方法，要注意以下問題：

函數在整個定義域內最好是二階可導的
起始點對求根計算影響重大，可以增加一些別的判斷手段進行試錯

5 牛頓-拉弗森方法的應用

比如求平方根： $x^2=78$ ，可以轉為求 $x^2-78=0$ 這個方程的根，就可以用牛頓-拉弗森方法求。求平方根用牛頓-拉弗森方法是安全的，沒有我之前說的那麼多坑。不過我看了有一些工程師寫的代碼，就有點濫用牛頓-拉弗森方法了，沒有從數學角度進行更多的考慮。

數學的魅力就在於，哪怕18世紀就證明了五次及以上多項式方程沒有根式解，隨著時間的發展，這個證明並不會被推翻，不像技術一樣會日新月異。所以牛頓-拉弗森方法仍然在計算機學科中被廣泛使用。

只是試試.純憑印象.錯誤請指正.
----
1,求方程f(x)=0的根即求曲線y=f(x)與y=0的交點的橫坐標.
2,牛頓法:
也就是從估計點x0出發,以y=f(x0)+f"(x0)(x-x0)作為對y=f(x)的估計,求得根x1.
x1=x0-f(x0)/f"(x0)
依次迭代.
3,關於"以y=f(x0)+f"(x0)(x-x0)對y=f(x)近似的解釋"
也就是對曲線y=f(x),那麼使用經過(x0,f(x0))點的其切線,進行近似.
顯然該切線的斜率等於曲線的斜率k=f"(x0),
那麼該切線的方程為y=f"(x0)(x-x0)+f(x0).
(這裡是牛頓法的核心,也就是使用切線對曲線進行近似)
4,對於求開方
也就是求x^2=a的解
這裡f(x)=x^2-a,f"(x)=2x.
所以利用上式:
以y=2x0(x-x0)+x0^2,則其根為
x1=x0-(x0^2-a)/2x0=(x0+a/x0)/2
5,例子
x^2=2.
x0=2,
x1=(2+0.5)/2=1.4998
x2=(x1+1/x1)/2=1.4167
x3=1.4142
...

Talk is cheap，show me the code.

我覺得吧，不能做無用的重複，這裡已經有一個非常詳盡的說法了，而且有一個很棒的gif，一看就明白。
求牛頓開方法的演算法及其原理，此演算法能開任...

/** * @param x a double * @return the square root of x */ public double sqrt(double x) { double eps = 1e-12; double t = x; while (Math.abs(t - x/t) &> eps * t) { t = (t + x / t) / 2.0; } return t; }

以上是java實現。這裡詳細解釋一下while循環里的邏輯。參考 @馬同學的原理，我們上來就把x作為根，進入迭代。

這時，曲線f(x) = t^2 - x 上對應的點為(x, t^2 - x), 過這個點切線的斜率為2t
如果我們把這一步迭代根的逼近距離(下圖橫軸紅色表示，借用 @馬同學的圖)設為d, 那麼結合1我們有： 2t = (t^2 - x) / d
所以 d = (t - x/t)2, 這一步迭代後根坐標為(t - d, 0)，即(t + x/t)/2
判斷精度，如果精度滿足跳出迭代，如果不滿足，重複step1.

還有個有意思的，lz可以看看牛頓法解最優化問題。最後形式很像：

def squareRoot(x, eplison): """x 需要求開根號的數值 eplison 誤差值 a 需要求開方的值 f(x) = x^2 - a f(x)的一次導 f"(x) = 2x 牛頓拉復生法求開方 Xn+1 = Xn - f(xn)/f"(Xn) 即 Xn+1 = Xn - Xn的偏差值/Xn的一次導 Xn 為第N次迭代後開方的猜想值 """ assert x &>= 0, u"x 必須不是一個負數 " + str(x) assert eplison &> 0, u"偏差值必須大於零 " + str(eplison)


    x = float(x)

    guess = x #x開根號後的猜想值，初始為x的本身

#猜想值的2次方與 x本身的偏差值，如果誤差小於eplison誤差值，則guees為x的開方猜想值 diff = guess ** 2 - x ctr = 1 print "guess: %f diff: %f ctr: %d" %(guess,diff, ctr) while abs(diff) &> eplison and ctr &<= 100: guess = guess - diff/(2*guess) diff = guess**2 - x ctr += 1 print "guess: %f diff: %f ctr:%d" % (guess, diff, ctr) print "guess: %f iteration: %d" %(guess, ctr) squareRoot(10, 0.01) guess: 10.000000 diff: 90.000000 ctr: 1 guess: 5.500000 diff: 20.250000 ctr:2 guess: 3.659091 diff: 3.388946 ctr:3 guess: 3.196005 diff: 0.214448 ctr:4 guess: 3.162456 diff: 0.001126 ctr:5 guess: 3.162456 iteration: 5

這裡是Java實現：

public class Sqrt { public static void main(String[] args) { System.out.println(sqrt(2)); }

static double sqrt(double C) { if (C &< 0) return Double.NaN; double err = 1E-15; double cur = C; while (Math.abs(C - cur * cur) &> err) cur = (cur + C / cur) / 2; return cur; } }

二維平面，三維時空是人類締造出來的一種形象認知方式，既然是人為締造肯定在一定範圍內是可行的。但是突破這個範圍就不行了，所以在現有形象認知下是無法想像的，必須借用新的工具方式才能描述更高維。

舉例說下，人類基礎認知的變化是加減+-，但是翻倍呢發明了乘法，反之除法。這是日常生活中對變化的基本認知，是不是所有呢?肯定不是，一個因素自身相乘呢，發明了平方，反之開方，更高維的立方，四方等等，反之同理，這些都是變化，但在日常生活中是不形象的，也不容易想像。但這些只是冰山一角，變化的更基本方式是大量的無限迭代，高中學過等差等比數數列應該明白，數列千奇百怪，你可以理解為積分和微分，大量的現有因子在迭代下變化成為下一個因子（熵），就像你理解的現有情況下一秒變化成下一秒的情況，當然這個因子量巨大，而且迭代方式千奇百怪，這也就是為什麼未來不可準確預測，但是一些情況如果我們掌握了基本的現有因子和迭代方式，未來又可以模糊預測，但是準確的來說無限迭代是混沌··

通俗嗎形象嗎滿意嗎