牛頓法怎麼理解？還有什麼其他方法進行高次方程的數值求解？

01-06

牛頓迭代法，我另外一篇文章寫過，如何通俗易懂地講解牛頓迭代法求開方？，在那篇文章中也提到牛頓迭代法本有不少問題，比如：

初值的選擇對問題的求解影響太大，可能導致求不出來、或者求解效率低
無法得知有幾個根。就算知道有幾個根，也不一定可以盡數求出
迭代過程中，你也不知道這次迭代的值和根的誤差有多大

所以說來，牛頓迭代法算不上很實用的求根方法，不過求平方根還是比較好用的（因為隨便選個初值，都會收斂，並且收斂速度還很快），這也是經常可以看到牛頓迭代法出沒的地方。

下面介紹一個更實用的求根方法。

米歇爾·羅爾（1652－1719），法國數學家，最著名的數學遺產是羅爾中值定理（數學史看多了，對這些數學英雄心生敬意，特立照於此）。

其實羅爾的數學研究重心在於多項式方程的根的求解，發明了一種我翻譯為級聯求根法的方法（英文：The Method of Cascades），這種方法的一個副產品是羅爾中值定理。

儘管羅爾中值定理是微積分很基本、很重要的定理，但是羅爾本人並不認可微積分，認為微積分是一堆錯誤的集合。鬼知道他是怎麼在沒有微積分的幫助下發明羅爾中值定理，並且發明出他的求根方法的（後面你會看到，他的求根方法完全基於微積分，當然這是現代人翻譯後的結果，他的原始手稿你一定是不想看的，最後會有，可以漲下姿勢）。

我們先來看看它求根的思想是什麼（下面都是用現代的數學語言翻譯過的）。

1 數學思想

羅爾研究的對象是形如 $f(x)=x^n+a_1x^{n-1}+cdots+a_n=0,xinmathbb{R}$ 這樣的多項式方程的根。

假如說這樣一個多項式的方程的根存在，我們怎麼求解呢？最粗暴的辦法，把定義域範圍內的每個實數拿來代入方程，看是否是多項式方程的根，這怕比大海撈針還希望渺茫。

羅爾給了一種方法，讓我們可以確定每個根的範圍。

1.1 駐點與根

假設 $f(x)$ 的所有的根為 ${x_n}=x_1,x_2,cdots$ ，有 $a,binmathbb{R}$ ，滿足 $a < min({x_n}), b > max({x_n})$ 。

一次函數的情況：

二次函數的情況：

求出駐點：

當然也可能出現 $(a,s_1)$ 或者 $(s_1,b)$ 區間內沒有根的情況。

比如這樣：

或者這樣（根有可能出現在駐點上）：

這該怎麼判斷呢？我們來複習下零點定理（其實就是介值定理的特殊情況），從幾何上看顯而易見：

根據零點定理可以判斷：

從上面的觀察來看，我們可以猜想根的上界與相鄰駐點、下界與相鄰駐點之間至多只有一個根。

我們來看看有沒有這種可能，會不會兩個根都在 $(a,s_1)$ ，或者在 $(s_1,b)$ 之間呢：

此處羅爾使用了羅爾中值定理（這就是羅爾中值定理的出處）進行了反證， $f(x)$ 很顯然符合使用羅爾中值定理的條件， $[a,b]$ 連續， $(a,b)$ 可導：

至此，我們可以得到一個結論：上界與相鄰駐點、下界與相鄰駐點之間至多只有一個根。

三次函數的情況：

求出駐點：

同樣的，通過羅爾中值定理，我們可以得到結論，相鄰駐點之間至多只有一個根。

四次函數的情況：

至此，我們總結一下：

上界與相鄰駐點、下界與相鄰駐點之間至多只有一個根
相鄰駐點之間至多只有一個根
區間內是否有根可以通過零點定理來進行判斷

根據上面結論，求函數 $f(x)$ 在 $(a,b)$ （ $a,b$ 分別為根的下界和上界）內的根,只需要求出 $f(x)$ 在 $(a,b)$ 內的所有駐點 $s_1,s_2cdots,s_n$ ，則所有根必定落在 $(a,s_1),(s_1,s_2)cdots(s_n,b)$ 內，每個區間至多有一個根，我們還可以通過零點定理來幫忙。然後我們就可以在這些區間內愉快的搜索了。

求駐點相當於求 $f$ 的根，對於多項式函數而言， $f$ 一般是比 $f(x)$ 簡單的。

拉格朗日把上面的結論表述為：

方程 $F^{(i)}(x)=0$ 根的界限是由方程 $F^{(i-1)}(x)=0$ 的根確定。
--拉格朗日

這樣求根就化成了求駐點。那麼我們可以開始了嗎？別慌，如何求根的上下界還沒交代呢。

1.2 根的上界

羅爾說的，對於多項式 $x^n+a_1x^{n-1}+...+a_n=0$ ，它的根都小於 $k+1$ ,其中 $k$ 為最大負數項的係數的絕對值（我找了半天也沒有找到證明，不過看到有別的證明可以佐證，感興趣可以參看書籍《first course in the theory of equations》21頁）。

舉個例子:

$x^5+4x^4-7x^2-40x+1$

這個式子也可以表述為:

$x^5+4x^4+0x^3-7x^2-40x+1$

最大負數係數項即 $k=|-40|=40$ ，則它的根小於 $1+k=1+40=41$ ，即我們可以說 $b=41$ （ $b$ 代表根的上界）。

1.3 根的下界

知道上界之後，通過一個替換我們就可以確定根的下界。

已知 $f(x)$ 根的上界為 $e$ ，那麼如果 $x$ 為 $f(x)$ 的根的話，必定有 $e-x=z>0$ 。

那麼我們做一個替換，令 $z=e-ximplies x=e-z(z > 0)$ ，代入 $f(x)=f(e-z)implies g(z)$ 。

那麼對於 $g(z)=0$ 的根而言， $z > 0$ ，所以下界 $a=0$ ，而上界 $b$ 需要根據剛才的演算法重新算出來。

2 示例

來看一個具體的例子，下面只計算到小數點後兩位：

求 $f(x)=x^4+x^3-4x^2-3x+2$ 的根.

2.1 方程變形

根據之前的根的上界的演算法， $k=|-4|=4$ ，得到根 $x < 4+1=5$ 。則令 $x=5-z$ 。

代入 $f(x)=f(5-z)=(5-z)^4+(5-z)^3-4(5-z)^2-3(5-z)+2$ ，整理得到：

$g(z)=z^4-21z^3+161z^2-532z+637$ 。

2.2 級聯求根

對 $g(z)$ 連續求導，直到只有一次項為止。

$egin{align} z^4-21z^3+161z^2-532z+637=0quad (1) \ 4z^3-63z^2+322z+532=0quad (2) \ 12z^2-126z+322=0quad (3) \ 24z-126=0quad (4) \ end{align}$

然後我們需要從 $(4) o(1)$ 逐級求根。

雖然(1)(2)(3)(4)方程都可以通過通式求出，但是為了演示方法，我還是從(4)式開始求：

$24z-126=0implies z=-31.5$ ，這其實就是(3)的駐點：

$b$ 點太遠了，不方便畫圖，我們暫時把 $b$ 放到圖外去：

通過零點定理和二分法（二分法的效率還是很高的），很快就可以算到 $x_1=4.39,x_2=6.10$ （保留小數點後兩位），實際上就求得了(2)式的駐點。

反覆運用上述方法，求得 $g(z)$ 的根為： $z_1=7.01,z_2=6.24,z_3=3.19,z_4=4.55$ ，因為保留小數點後兩位，上述根並不精確，比如 $z_1=7.01$ ，其實精確的根應該為 $z=7$ 。

2.3 得到結果

最後將此代入： $x=5-z$

求得 $f(x)$ 的根為 $x_1=-2.01,x_2=-1.24,x_3=1.81,x_4=0.45$ 。

3 結論

羅爾的方法對連續可導的 $f(x)$ 都是適用的，並非要局限在多項式，但是，至少要 $f$ 比 $f(x)=0$ 更容易解才有意義。

最後，讓我們用羅爾研究這個問題的手稿來結束這篇文章，儘管三四百年的數學發展讓我們已經很難看出他寫的是什麼了：

牛頓法的原理就是通過迭代地求曲線的切線來逼近方程的解，如圖：

求解方程的數值解的常用方法還包括bisection method、method of false position、Secant method、Muller method、Taylor series method、Brent"s method、Languerre"s method等等。

澳村高三狗強答一發，方法比較低端，希望大神們不要鄙視

首先，我們先弄清什麼是根，在圖像上就是和x軸交叉的點，很好理解，但是代數上呢？就是當x=a時候f（x）=0

這個時候我們有了一個定理叫因式定理 https://zh.wikipedia.org/wiki/%E5%9B%A0%E5%BC%8F%E5%AE%9A%E7%90%86

維基的解釋有點高端模糊，簡單的說就是對於f(x),如果x=a是一個解，則（x-a)是一個因數（不知道怎麼翻譯，英語叫factor）然後就會成為f(x)=(x-a)Q(x), Q(X)代表另一個多項式但是係數減一（因為之前的x-a已經「拿走」了一個了）

好，假設我們有一f(x)=x^3+3x^2+4x-8

帶入x=1，發現函數等於一（這是難點，因為第一個很難確定，有一個小trick就是一定是常數項的一個因數）說明1是一個解

然後我們就要引出主角:synthetic substitution

（不會知乎上用就只好word裡面打好截圖了，畢竟還naive...)

這題可以做例題，因為是標準的格式

補充：當有一項比如上題如果沒有x的一次項的話還是要用0補充的

最後得出0的話說明是一個解，如果不是0而是一個常數let"s say k的話那k就是餘數（除數為x-a時）

這個方法不適合很高次，但是對6以下的還是比較方便的，畢竟可以不斷的把係數降下來，降到二次的時候就很簡單了

wiki:

Synthetic division

《數值分析》

牛頓迭代就是用直線/二次/三次曲線切待求零點的曲線,每次去切完,該切線的零點都更接近於原曲線零點,將該切線的零點代入下次迭代並作為切點的自變數坐標,就能不斷逼近實際零點.

非線性方程組的數值解法很多,比如CG-就是先亂猜一個差不多的解,然後看看差了多少,該往什麼方向去修正,再把修正過的結果代入下次迭代,這個在處理維數異常高的方程組的時候要比牛頓法快些.

講數值方法的書有好多啊,自己找來看看比在這裡問要有效得多……