求根法

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

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

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

最簡單的求根算法為二分法︰令

為一個連續函數，且已知存在區間

滿足

和

符號互異。令

（區間的中點），則

和

或

和

中，必恰有一者符號互異，並將已知根所在區間的長度縮短為一半。對被縮短的區間重複上述步驟，直到找到根。

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

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

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

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

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

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

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

牛頓法假定函數

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

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

對函數

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