求根演算法

在數學和電腦運算中，對於一個已知的從實數集合對映到實數集合，或者從複數集合對映到複數集合的連續函數$f(x)$，搜尋變數$x$使得$f(x)=0$（此時，變數$x$稱為$f(x)=0$的根、$f(x)$的零點）的演算法，稱為求根演算法。在許多情況下，函數的零點無法被準確計算出，也無法被解析解表示；是故，求根演算法在實數集合下只提供一個以浮點數表示的近似解，或者一個足夠小的解的存在區間，在複數集合下只提供一個複根的圓盤（輸出一個區間或一個圓盤等價於輸出一個根的近似值及其誤差上限）。

解方程式$f(x)=g(x)$與求$f(x)-g(x)$的根是等價的。因此求根演算法可以求解任何以連續函數定義的方程式。然而，許多情況下，求根演算法只能找到方程式的某些根，而不能保證所有根都能找到；特別指出，演算法未找到根，並不代表方程式確實無根。

大多數的數值求根演算法都使用疊代法，生成一個以方程式的根為極限的收斂數列。它們需要一個或多個根作為疊代的初期值，嗣後每次疊代都生成一個逐步逼近根的值。由於疊代法必須在有限步內終止於某個點，這些方法都只能提供一個根的近似值，而不能提供一個精確解。 許多方法是通過代入上一個疊代值來計算一個輔助方程式，從而得出下一個疊代值的。此處所指的輔助方程式是指為了使源方程式的根是一個定點並使疊代值能更快地收斂到這些定點而設計的一個方程式，因此疊代值的極限是這個輔助方程式的一個定點。

求根演算法的效能是數值分析的研究範疇。一種演算法的效率可能大幅度取決於已知點的性質。例如，一部分演算法都使用輸入函數的導數（此要求函數不但連續，而且可導），而其他演算法則能用於任何一個連續函數。在一般情況下，數值演算法不能保證找到一個函數的所有根，因此演算法未能找到根並不能證明方程式無根。然而，對於多項式，存在特定的使用代數學性質以定位根的所在區間（或複根所在的圓盤）的演算法，這個區間（或圓盤）足夠小以能保證數值演算法（例如牛頓法）能收斂到唯一被定位的根。

包圍法

包圍法是指通過疊代確定根的所在區間，並逐漸縮小其區間長度的演算法。當區間變得足夠小時，則認為根已經被找到。一般地，包圍法以介值定理為基礎，且能夠求出根的絕對誤差上限；而當函數是一個多項式時，還有其它基於施圖姆定理或笛卡兒符號法則的方法，能夠在一個區間內求出精確的根。

二分法

最簡單的求根演算法為二分法︰令$f(x)$為一個連續函數，且已知存在區間$[a,b]$滿足$f(a)$和$f(b)$符號互異。令$c=(a+b)/2$（區間的中點），則$f(a)$和$f(c)$或$f(c)$和$f(b)$中，必恰有一者符號互異，並將已知根所在區間的長度縮短為一半。對被縮短的區間重複上述步驟，直到找到根。

縱二分法具有強健性，但其只能求得區間內的一個且只有一位精度的解。此外在合適的條件下，亦存在其他能更快求得精確解的方法。

盈不足術法

盈不足術法與二分法相似。異處在於，盈不足術以方式計算出疊代點，

$c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.$

盈不足術法也類似於割線法。異處在於，盈不足術法不保留前兩次疊代點，而是在根的兩側各保留一點。 盈不足術法能以較二分法更快的速度求根，且不會如割線法一樣發散（不收斂）；但在一些簡單實現的情形中可能因為捨入誤差而無法收斂。

Ridders法是盈不足術法的一個變形。其使用區間中點的函數值，構造出一個具有相同零點的函數，再用盈不足術法求解之。這個方法維持了一定的強健性外，亦使演算法更快收斂。

插值法

許多求根演算法通過插值來實現。即，使用上一步計算出的根的多個近似值，藉助一個以插值法求出的低次多項式，以逼近一個函數。然後計算多項式的根，並用其作新的函數的根的近似值，重複此流程。

兩個函數值可利用插值法求得一個一次多項式，即以一條直線逼近一個函數圖像。此乃割線法及盈不足術法的基礎。進而，三個函數值可求得一個二次函數，即以一條拋物線逼近一個函數圖像。此即Muller法。

疊代法

雖然所有求根演算法都通過疊代，但一個疊代的求根演算法，通常使用一種特定的疊代類型，包括定義一個輔助函數，應用上一步計算出的根的近似值，求得新的近似值。輔助函數到逹一個定點（到逹所需的精度），即新疊代的近似值充分接近上一個疊代值時，疊代停止。

牛頓法（及類似的以導數為基礎的方法）

牛頓法假定函數$f$的導數是連續的。如果起始點距離根太遠，牛頓法可能不收斂。然而，其若收斂，速度將較二分法快，且通常為二次收斂。牛頓法也是一種重要的演算法，因為它能容易地推廣到高維問題。類似牛頓法且有更高次的收斂性的演算法為Householder法。具有三次收斂性的Householder法是Halley法。

割線法

將牛頓法中的導數替換為一個差分式，即得到割線法。 這種方法的優點在於不需要計算導數，但其代價是收斂速度較慢（收斂次數約為1.6）。把割線法推廣到高維的演算法是Broyden法。

逆插值法

對函數$f$進行逆插值，能夠避免插值法中出現複數。這種方法稱為逆二次插值法。其收斂速度漸近快於割線法；但當疊代離根較遠時，逆二次插值法往往表現不佳。

演算法組合

Brent法

Brent法是二分法，割線法同逆二次插值法的組合。在每一次疊代，Brent法會決定此三者中何種的效果最好，然後使用該種方法執行一次疊代。此法快捷並強健，故甚流行。

參見

• Broyden法
• 求根演算法列表
• 重複度
• 最大公因式
• Graeffe法
• 密碼學安全偽隨機數生成器，一個特別設計的無法以求根演算法求解的函數組。
• 多項式方程組，用求根演算法求解多變數問題。
• MPSolve
• GNU科學庫

參考文獻

腳註

來源

• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. Chapter 9. Root Finding and Nonlinear Sets of Equations. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007 [2017-08-18]. ISBN 978-0-521-88068-8. （原始內容存檔於2011-08-11）. 

外部連結

• GAMS: Roots of polynomials with real coefficients （頁面存檔備份，存於網際網路檔案館）
• Free online polynomial root finder for both real and complex coefficients （頁面存檔備份，存於網際網路檔案館）
• Kehagias, Spyros: RealRoots, a free App for iPhone, iPod Touch and iPad to compare Sturm's method and VAS https://itunes.apple.com/gr/app/realroots/id483609988?mt=8 （頁面存檔備份，存於網際網路檔案館）