求根アルゴリズム

求根アルゴリズム（きゅうこんアルゴリズム、）は、与えられた関数 について、を満たす根 を得るための数値解法、もしくはアルゴリズムである。ここでは、浮動小数点数で近似される実数または複素数の根の計算について述べる。整数根、または解析解の計算は別な問題であり、ここで述べる手法との共通点は少ない（整数根についてはディオファントス方程式を参照のこと）。

の求根は、方程式 を解くことと同値である。ここで、 を方程式の未知数と呼ぶ。逆に、任意の方程式は標準形 に変換できるので、方程式の求解は関数の求根と同値である。

数値的な求根アルゴリズムでは反復法を用いて、根となる極限（いわゆる極値）に収束する（と期待される）数列を生成する。数列の最初の値を初期値として、古い値と関数 から逐次新しい値を計算する。

求根アルゴリズムの性質は数値解析で研究されている。与えられた関数の性質を利用できる場合には、効率よく計算することができる。したがって、低次の1変数多項式の実根の計算方法は、一般に必ずしも微分可能でないブラックボックス型関数の複素根の計算方法とは異なる。密集した根の分離、数値誤差を考慮した正確な解の計算、収束率などについても研究されている。

主な手法 二分法 最も単純な求根アルゴリズムである。二分法は が連続関数であり、 と が異符号となるような初期値 が既知であることを前提とする。a と b とが異符号であるから連続関数に対する中間値の定理により、a とｂの中間に根が存在することが言えるが、根が一つであるとは限らないことに注意する。中間に根が複数ある場合には、そのうちのどれか1つだけが求まる。この解法は安定で堅実であるが、根の近似精度の向上は反復1ステップ毎に1ビットだけであり、収束の遅いことが欠点である。関数値が異符号となる a と b が存在するかどうか、また存在する場合にそれらをどのようにして用意するかについては、また別の問題である。 ニュートン法 初期値が根から遠い場合には必ずしも収束しないが、収束する場合は二分法より速い方法である。ニュートン法は、収束は通常2次であり、精度は1ステップ毎に2倍になる。関数 が連続な微分値を持つことを前提とする。ニュートン法は、多次元の問題に対しても一般化が容易にできることも重要である森正武『数値解析』共立出版、2002年2月。ISBN 4-320-01701-3。P. Henrici, Applied and Computational Complex Analysis I, Wiley, 1974.皆本晃弥. (2005). UNIX & Information Science-5 C 言語による数値計算入門, サイエンス社.。より高次の収束を示す方法はハウスホルダー法に分類される。このうち最も単純なハレー法は3次の収束を示す。 割線法 ニュートン法の微分を差分商で置き換えたものであるWeisstein, Eric W. "Secant Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SecantMethod.html。この方法は導関数の計算（や存在）を必要としないが、収束は遅い（収束次数は1.6程度である）。未知の関数 を線形補間を用いて近似したことにあたる。それに対して2次補間を用いるものをマラー法と呼ぶ。マラー法は割線法よりも収束は速いが、反復の中で近似解 は虚数の値になり得る。このことは の逆関数を補間することで回避できる。これを逆2次補間という。マラー法は割線法よりも収束が漸近的に速いが、出発値が解から遠い場合には収束が遅くなる。

割線法と似ているが、前のステップで計算した2点を使う代わりに、根を挟む位置にある点を選ぶ。二分法よりも収束が速く、割線法よりも安定している。 ブレント法 二分法、割線法、逆2次補間を組み合わせた手法で、各ステップでどの手法が最も適しているかを判別し、適した手法を選択する。安定かつ高速で、広く用いられているBrent, R. P. Ch. 3-4 in Algorithms for Minimization Without Derivatives. Englewood Cliffs, NJ: Prentice-Hall, 1973.Weisstein, Eric W. "Brent's Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BrentsMethod.html。

多項式の求根 関数 が多項式である場合はよく研究されており、多項式の性質を活かした求根アルゴリズムが存在する。ただし、2次方程式の解ですら数値的安定性には注意が必要である安定性（日本NAGのウェブサイトより）。

実根の場合は、スツルムの定理が根の位置の特定や分離に役立つ。これと区間演算をニュートン法と組み合わせた求根アルゴリズムも考えられるが、他の方法を用いるのが一般的である。

有力な方法として、多項式に対するコンパニオン行列を作り（それをバランシング操作を加えてから）、固有値解法を用いて固有値を計算する方法がある。コンパニオン行列の固有値は多項式の根と一致するので、任意の固有値解法を多項式の求根に用いることができるJared L. Aurentz, Thomas Mach, Raf Vandebril and David S. Watkins: "Fast and Backward Stable Computation of Roots of Polynomials",SIAM Journal on Matrix Analysis and Applications, Vol.36, No.3 (2015).Jared L. Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril and David S. Watkins: "Fast and Backward Stable Computation of Roots of Polynomials, Part II: Backward Error Analysis; Companion Matrix and Companion Pencil",SIAM Journal on Matrix Analysis and Applications, Vol.39, No.3 (2018).。 絶対値の大きな根を求めるための古典的なベルヌーイ法(英語版)は、根が存在する場合はコンパニオン行列に対する冪乗法に相当する。

ラゲール法 より複雑だが、収束は速いE. N. Laguerre, Sur une m´ethode pour obtenir par approximation les racines d’une ´equation alg´ebraique qui a toutes ses racines r´eelles, Œuvre de Laguerre 1 (1898), 87–103.。単根の場合は3次の収束を示し、ニュートン法より高速である。ジェンキンズ＝トラウブ法もニュートン法より複雑だが高速であるJenkins, M. A. and Traub, J. F. (1970), A Three-Stage Variables-Shift Iteration for Polynomial Zeros and Its Relation to Generalized Rayleigh Iteration, Numer. Math. 14, 252–263.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, 1992.Ralston, A. and Rabinowitz, P. (1978), A First Course in Numerical Analysis, 2nd ed., McGraw-Hill, New York.。 ベアストウ法 実係数多項式の2次の因数を求めるのにニュートン法を用いる。実計算のみで実多項式の実根と複素根を求めることができる。 デュラン＝カーナー法、アバース法 複素計算によりすべての根を同時に求める。デュランとカーナーによって多項式にある変形を施してからニュートン法を適用することが提案され、アバースによって初期値の与え方が示された。 分割円法 高次の多項式の根を任意の精度まで求めるのに有用である。計算量も最適に近い。 ウィルキンソンの多項式 これはジェームズ・H・ウィルキンソンによって例題として提唱された根を数値的に求めるのが困難な例題の多項式である。この例は多項式の根を数値的に求める際には、高い精度を用いた計算が必要になる場合があることを示しているJ. H. Wilkinson (1963). Rounding Errors in Algebraic Processes. Englewood Cliffs, New Jersey: Prentice Hall.。

重根の計算 多項式 が重根を持つ場合、通常の求根アルゴリズムでは根の計算が困難になる。係数が明示的に与えられた1変数多項式については、以下のアルゴリズムが存在する。

アルゴリズム まず、 が重根を持つかどうかを知る必要がある。 が に重根を持つなら、微分 も に根を持つので、 と の最大公約数を計算し、最高次の係数が 1 となるよう定数倍したものを とする () 。スツルムの定理を参照のこと。 なら、 は重根を持たないので、他の求根アルゴリズムにより根を求めて終了する。 が重根を持つとする。 は に と同じ重複度の根を持ち、 の次数は より小さいことに注意する。再帰的にこのルーチンを適用し（#1に戻って を と置く）、 の根を計算する。 が得られたので、 を で分解し、 にあるすべての重根が除かれるまでこれを繰り返す。商から他の求根アルゴリズムにより根を求めて終了する。

関連項目 零点 重根 (多項式) 最大公約数 多項式 暗号論的擬似乱数生成器

より高度な内容の書籍等 伊理正夫：「数値計算：方程式の解法」、朝倉書店、ISBN 978-4-254-11362-4 (1981年12月). Victor Y. Pan: "Solving a Polynomial Equation: Some History and Recent Progress", SIAM Review, Vol.39, No.2, pp.187-220 (June, 1997). John Michael McNamee: Numerical Methods for Roots of Polynomials - Part I, Elsevier, ISBN 978-0-444-52729-5 (2007年6月4日). John Michael McNamee and Victor Y. Pan: Numerical Methods for Roots of Polynomials - Part II, Elsevier, ISBN 978-0-444-52730-1 (2013年6月19日).

脚注

出典

外部リンク GAMS: Roots of polynomials with real coefficients Numerical Recipes Homepage 非線型方程式の数値計算法