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