求根アルゴリズム

求根アルゴリズム（きゅうこんアルゴリズム、）は、与えられた関数 について、を満たす根 を得るための数値解法、もしくはアルゴリズムである。ここでは、浮動小数点数で近似される実数または複素数の根の計算について述べる。整数根、または解析解の計算は別な問題であり、ここで述べる手法との共通点は少ない（整数根についてはディオファントス方程式を参照のこと）。
の求根は、方程式 を解くことと同値である。ここで、 を方程式の未知数と呼ぶ。逆に、任意の方程式は標準形 に変換できるので、方程式の求解は関数の求根と同値である。
数値的な求根アルゴリズムでは反復法を用いて、根となる極限（いわゆる極値）に収束する（と期待される）数列を生成する。数列の最初の値を初期値として、古い値と関数 から逐次新しい値を計算する。
求根アルゴリズムの性質は数値解析で研究されている。与えられた関数の性質を利用できる場合には、効率よく計算することができる。したがって、低次の1変数多項式の実根の計算方法は、一般に必ずしも微分可能でないブラックボックス型関数の複素根の計算方法とは異なる。密集した根の分離、数値誤差を考慮した正確な解の計算、収束率などについても研究されている。
多項式の求根.
関数 が多項式である場合はよく研究されており、多項式の性質を活かした求根アルゴリズムが存在する。ただし、2次方程式の解ですら数値的安定性には注意が必要である。
実根の場合は、スツルムの定理が根の位置の特定や分離に役立つ。これと区間演算をニュートン法と組み合わせた求根アルゴリズムも考えられるが、他の方法を用いるのが一般的である。
ひとつの可能性として、多項式のコンパニオン行列を作る方法が考えられる。コンパニオン行列の固有値は多項式の根と一致するので、任意の固有値解法を多項式の求根に用いることができる。例えば、絶対値の大きな根を求めるための古典的なベルヌーイ法は、根が存在する場合はコンパニオン行列に対する冪乗法に相当する。
重根の計算.
多項式 が重根を持つ場合、通常の求根アルゴリズムでは根の計算が困難になる。係数が明示的に与えられた1変数多項式については、以下のアルゴリズムが存在する。