求根アルゴリズム

求根アルゴリズム（きゅうこんアルゴリズム、英: root-finding algorithm）は、与えられた関数 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 が連続な微分値を持つことを前提とする。ニュートン法は、多次元の問題に直ちに一般化できる点でも重要である^[1][2][3][4]。より高次の収束を示す方法はハウスホルダー法に分類される。このうち最も単純なハレー法は3次の収束を示す。

割線法

ニュートン法の微分を差分で置き換えたものである^[4][5]。この方法は微分の計算（や存在）を必要としないが、収束は遅い（次数は1.6程度である）^[4]。未知の関数 f を線形補間によって近似する場合にも用いられる。2次補間を用いるものをマラー法と呼ぶ。マラー法は割線法より収束は速いが、マラー法では反復 x_n が複素数になり得る。これは f の逆関数を補間することで回避できる。これを逆2次補間という。収束は漸近的に割線法より速くなるが、近似値が解から遠い場合は収束が遅い。

(挟み撃ち法)（英語版）

割線法に似ているが、前のステップで計算した2点を使う代わりに、根を挟む位置にある点を選ぶ。割線法より収束が速く、二分法より安定している。

ブレント法

二分法、割線法、逆2次補間を組み合わせた手法で、各ステップでどの手法が最も適しているかを判別し、適した手法を選択する。安定かつ高速で、広く用いられている^[6][7]。

(ステフェンセン法)（英語版）

多項式の求根

関数 f が多項式である場合はよく研究されており、多項式の性質を活かした求根アルゴリズムが存在する。ただし、2次方程式の解ですら数値的安定性には注意が必要である^[8]。

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

ひとつの可能性として、多項式のコンパニオン行列を作る方法が考えられる。コンパニオン行列の固有値は多項式の根と一致するので、任意の固有値解法を多項式の求根に用いることができる^[1]。例えば、絶対値の大きな根を求めるための古典的なベルヌーイ法は、根が存在する場合はコンパニオン行列に対する冪乗法に相当する。

ラゲール法

より複雑だが、収束は速い^[9][3]。単根の場合は3次の収束を示し、ニュートン法より高速である。ジェンキンズ＝トラウブ法もニュートン法より複雑だが高速である^[10][11][12]。

ベアストウ法

実係数多項式の2次の因数を求めるのにニュートン法を用いる。実計算のみで実多項式の実根と複素根を求めることができる。

デュラン＝カーナー法、アバース法

複素計算によりすべての根を同時に求める。デュランとカーナーによって多項式にある変形を施してからニュートン法を適用することが提案され、アバースによって初期値の与え方が示された^[1]。

分割円法

高次の多項式の根を任意の精度まで求めるのに有用である。計算量も最適に近い。

ウィルキンソンの多項式

ジェームズ・H・ウィルキンソンによって提唱された多項式である。これは多項式の根を求める際には、高い精度が必要になる場合があることを示す例である^[13]。

重根の計算

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

アルゴリズム

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

関連項目

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

より高度な内容の書籍等

• 伊理正夫：「数値計算 - 方程式の解法」、朝倉書店、(ISBN 978-4-254113624) (1981年12月）。
• J.M. McNamee: Numerical Methods for Roots of Polynomials - Part I, Elsevier, (2007年6月4日）.
• J.M. McNamee and Victor Pan: Numerical Methods for Roots of Polynomials - Part II, Elsevier, (2013年6月19日）.

脚注

[脚注の使い方]

出典

1. ^ ^{a b c} 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月。ISBN (4-7819-1038-6)。 
2. ^ ^{a b} 森正武『数値解析』共立出版、2002年2月。(ISBN 4-320-01701-3)。
3. ^ ^{a b} P. Henrici, Applied and Computational Complex Analysis I, Wiley, 1974.
4. ^ ^{a b c} 皆本晃弥. (2005). UNIX & Information Science-5 C 言語による数値計算入門, サイエンス社.
5. ^ Weisstein, Eric W. "Secant Method." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/SecantMethod.html
6. ^ Brent, R. P. Ch. 3-4 in Algorithms for Minimization Without Derivatives. Englewood Cliffs, NJ: Prentice-Hall, 1973.
7. ^ Weisstein, Eric W. "Brent's Method." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BrentsMethod.html
8. ^ 安定性（日本NAGのウェブサイトより）
9. ^ 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.
10. ^ 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.
11. ^ 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.
12. ^ Ralston, A. and Rabinowitz, P. (1978), A First Course in Numerical Analysis, 2nd ed., McGraw-Hill, New York.
13. ^ J. H. Wilkinson (1963). Rounding Errors in Algebraic Processes. Englewood Cliffs, New Jersey: Prentice Hall.

外部リンク

• GAMS: Roots of polynomials with real coefficients
• Numerical Recipes Homepage
• 非線型方程式の数値計算法