求根アルゴリズム
求根アルゴリズムは、与えられた関数f について、f (x ) = 0を満たす根x を得るための数値解法、もしくはアルゴリズムである。ここでは、浮動小数点数で近似される実数または複素数の根の計算について述べる。整数根、または解析解の計算は別な問題であり、ここで述べる手法との共通点は少ない（整数根についてはディオファントス方程式を参照のこと）。
f (x ) - g (x ) = 0の求根は、方程式 f (x ) = g (x )を解くことと同値である。ここで、x を方程式の未知数と呼ぶ。逆に、任意の方程式は標準形f (x ) = 0に変換できるので、方程式の求解は関数の求根と同値である。
数値的な求根アルゴリズムでは反復法を用いて、根となる極限（いわゆる極値）に収束する（と期待される）数列を生成する。数列の最初の値を初期値として、古い値と関数f から逐次新しい値を計算する。
求根アルゴリズムの性質は数値解析で研究されている。与えられた関数の性質を利用できる場合には、効率よく計算することができる。したがって、低次の1変数多項式の実根の計算方法は、一般に必ずしも微分可能でないブラックボックス型関数の複素根の計算方法とは異なる。密集した根の分離、数値誤差を考慮した正確な解の計算、収束率などについても研究されている。
主な手法
- 二分法
- 最も単純な求根アルゴリズムである。二分法はf が連続関数であり、f (a )とf (b )が異符号となるような初期値a 、b が既知であることを前提とする。安定な解法だが収束は遅く、1ステップ毎に1ビット精度が向上する。
- ニュートン法
- 初期値が根から遠い場合には必ずしも収束しないが、収束する場合は二分法より速い方法である。ニュートン法は、収束は通常2次であり、精度は1ステップ毎に2倍になる。関数f が連続な微分値を持つことを前提とする。ニュートン法は、多次元の問題に直ちに一般化できる点でも重要である。より高次の収束を示す方法はハウスホルダー法に分類される。このうち最も単純なハレー法は3次の収束を示す。
- 割線法
- ニュートン法の微分を差分で置き換えたものである。この方法は微分の計算（や存在）を必要としないが、収束は遅い（次数は1.6程度である）。未知の関数f を線形補間によって近似する場合にも用いられる。2次補間を用いるものをマラー法と呼ぶ。マラー法は割線法より収束は速い。この方法では、反復xn は複素数となることがある。これはfの逆関数を補間することで回避できる。これを逆2次補間という。収束は漸近的に割線法より速くなるが、近似値が解から遠い場合は収束が遅い。
- 挟み撃ち法
- 割線法に似ているが、前のステップで計算した2点を使う代わりに、根を挟む位置にある点を選ぶ。割線法より速く、二分法より安定している。
- ブレント法
- 二分法、割線法、逆2次補間を組み合わせた手法で、各ステップでどの手法が最も適しているかを判別し、適した手法を選択する。安定かつ高速で、広く用いられている。
多項式の求根
関数f が多項式である場合はよく研究されており、多項式の性質を活かした求根アルゴリズムが存在する。ただし、2次方程式の解ですら数値的な安定性には注意が必要である。
実根の場合は、スツルムの定理が根の位置の特定や分離に役立つ。これと区間演算をニュートン法と組み合わせた求根アルゴリズムも考えられるが、他の方法を用いるのが一般的である。
ひとつの可能性として、多項式のコンパニオン行列を作る方法が考えられる。コンパニオン行列の固有値は多項式の根と一致するので、任意の固有値解法を多項式の求根に用いることができる。例えば、絶対値の大きな根を求めるための古典的なベルヌーイ法は、根が存在する場合はコンパニオン行列に対する冪乗法に相当する。
- ラゲール法
- より複雑だが、収束は速い。単根の場合は3次の収束を示し、ニュートン法より高速である。ジェンキンズ＝トラウブ法もニュートン法より複雑だが高速である。
- ベアストウ法
- 実係数多項式の2次の因数を求めるのにニュートン法を用いる。実計算のみで実多項式の実根と複素根を求めることができる。
- デュラン＝カーナー法、アバース法
- 複素計算によりすべての根を同時に求める。デュランとカーナーによって多項式にある変形を施してからニュートン法を適用することが提案され、アバースによって初期値の与え方が示された。
- 分割円法
- 高次の多項式の根を任意の精度まで求めるのに有用である。計算量も最適に近い。
- ウィルキンソンの多項式
- 多項式の根を求める際には、高い精度が必要になる場合があることを示している。
重根の計算
多項式p (x )が重根を持つ場合、通常の求根アルゴリズムでは根の計算が困難になる。係数が明示的に与えられた1変数多項式については、以下のアルゴリズムが存在する。
アルゴリズム
- まず、p (x )が重根を持つかどうかを知る必要がある。p (x )がr に重根を持つなら、微分p(x )もr に根を持つので、p (x )とp(x )の最大公約数を計算し、最高次の係数が1となるよう定数倍したものをg (x )とする。スツルムの定理を参照のこと。g (x ) = 1なら、p (x )は重根を持たないので、他の求根アルゴリズムにより根を求めて終了する。
- p (x )が重根を持つとする。g (x )はr にp'(x )と同じ重複度の根を持ち、g (x )の次数はp (x )よりずっと小さいことに注意する。再帰的にこのルーチンを適用し（#1に戻ってp (x )をg (x )と置く）、g (x )の根を計算する。
- r が得られたので、p (x ) を(x−r)で分解し、r にあるすべての重根が除かれるまでこれを繰り返す。商から他の求根アルゴリズムにより根を求めて終了する。