|
求根アルゴリズムは、与えられた関数''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次補間を用いるものをマラー法と呼ぶ。マラー法は割線法より収束は速い。この方法では、反復''x''''n'' は複素数となることがある。これは''f''の逆関数を補間することで回避できる。これを逆2次補間という。収束は漸近的に割線法より速くなるが、近似値が解から遠い場合は収束が遅い。 ; : 割線法に似ているが、前のステップで計算した2点を使う代わりに、根を挟む位置にある点を選ぶ。割線法より速く、二分法より安定している。 ; ブレント法 : 二分法、割線法、逆2次補間を組み合わせた手法で、各ステップでどの手法が最も適しているかを判別し、適した手法を選択する。安定かつ高速で、広く用いられている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「求根アルゴリズム」の詳細全文を読む スポンサード リンク
|