求根算法

在數學和電腦運算中，對於一個已知的從實數集合映射到實數集合，或者從複數集合映射到複數集合的連續函數，搜索變量使得（此時，變量稱為的根、的零點）的算法，稱為求根算法。在許多情況下，函數的零點無法被準確計算出，也無法被解析解表示；是故，求根算法在實數集合下只提供一個以浮點數表示的近似解，或者一個足夠小的解的存在區間，在複數集合下只提供一個複根的圓盤（輸出一個區間或一個圓盤等價於輸出一個根的近似值及其誤差上限）。 解方程與求的根是等價的。因此求根算法可以求解任何以連續函數定義的方程。然而，許多情況下，求根算法只能找到方程的某些根，而不能保證所有根都能找到；特別指出，算法未找到根，並不代表方程確實無根。 大多數的數值求根算法都使用疊代法，生成一個以方程的根為極限的收斂數列。它們需要一个或多个根作为疊代的初期值，嗣後每次疊代都生成一個逐步逼近根的值。由於疊代法必須在有限步內終止於某個點，這些方法都只能提供一個根的近似值，而不能提供一個精確解。许多方法是通過代入上一個疊代值來計算一個輔助方程，從而得出下一個疊代值的。此處所指的輔助方程是指為了使源方程的根是一個定點並使疊代值能更快地收斂到這些定點而設計的一個方程，因此疊代值的極限是這個輔助方程的一個定點。 求根算法的性能是數值分析的研究範疇。一种算法的效率可能大幅度取決於已知點的性質。例如，一部分算法都使用輸入函數的導數（此要求函數不但連續，而且可導），而其他算法則能用於任何一個連續函數。在一般情况下，數值算法不能保證找到一個函數的所有根，因此算法未能找到根並不能證明方程無根。然而，對於多項式，存在特定的使用代數學性質以定位根的所在區間（或複根所在的圓盤）的算法，這個區間（或圓盤）足夠小以能保證數值算法（例如牛頓法）能收斂到唯一被定位的根。