ベアストゥ法とは

/数値計算

ベアストゥ法

ベアストゥ法とは、一般的な多項式の実根・虚根の全てを求めることができる数値計算法です。ベアストゥ法は、多項式から2次の多項式で因数分解し、次数を順次下げることで全ての根を求めていきます。

次のような一般的な $n$ 次の多項式について、

$$a_0x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n=0  -①$$

以下のように2次式で除算します。

$$(b_0x^{n-2}+\cdots+b_{n-3}x+b_{n-2})(x^2+px+q)+fx+g=0  -②$$

剰余($fx+g$)が0になるような $p$、$q$ を見つけることができれば、①の根を求める問題は、次の2つの多項式の根を求める問題に帰着します。

$$b_0x^{n-2}+\cdots+b_{n-3}x+b_{n-2}=0  -③$$$$x^2+px+q=0  -④$$

④は解の公式を使って根を求めることができます。一方、③が高次の多項式の場合は、この手順を繰り返し、次数を下げていきます。

剰余を0にする手順

②を展開すると、各係数は①と等しくなるため、

$a_0=b_0$
$a_1=b_0p+b_1$
$a_2=b_2+b_1p+b_0q$
・・・・
$a_{n-2}=b_{n-2}+b_{n-3}p+b_{n-4}q$
$a_{n-1}=b_{n-2}p+b_{n-3}q+f$
$a_n=b_{n-2}q+g$

$a_0\sim a_n$ は既知であるため、これらより $b_0\sim b_{n-2}$ を求めると、$f$ と $g$ は $p$、$q$ の関数として表すことができます。

$$f=f(p,q)$$$$g=g(p,q)$$

従って、$f$ と $g$ の根 $\alpha$、$\beta$ を求める問題に帰着します。

$$f(\alpha,\beta)=0$$$$g(\alpha,\beta)=0$$

根を求める

これをニュートン法を使って解きます。適当な点($p_1$、$q_1$)を始点として、テイラー展開すると、

$$f(p_2,q_2)=f(p_1,q_1)+(p_2-p_1)\frac{\partial f}{\partial p}+(q_2-q_1)\frac{\partial f}{\partial q}+\cdots$$$$g(p_2,q_2)=g(p_1,q_1)+(p_2-p_1)\frac{\partial g}{\partial p}+(q_2-q_1)\frac{\partial g}{\partial q}+\cdots$$

右辺の2次の項を無視し、左辺を0と置いて解くと、

$$p_2=p_1-\frac{g’f(p_1,q_1)-f’g(p_1,q_1)}{\dot{f}g’-f’\dot{g}}  -⑤$$$$q_2=q_1+\frac{\dot{g}f(p_1,q_1)-\dot{f}g(p_1,q_1)}{\dot{f}g’-f’\dot{g}}  -⑥$$$$\dot{f}\equiv\frac{\partial f}{\partial p}  ,  f’\equiv\frac{\partial f}{\partial q}$$$$\dot{g}\equiv\frac{\partial g}{\partial p}  ,  g’\equiv\frac{\partial g}{\partial q}$$

⑤と⑥を繰り返すことにより($p_2$、$q_2$)$\cdots$($p_n$、$q_n$)を計算し、変化量が許容誤差範囲 $\epsilon$ 未満になれば、($p_n$、$q_n$)を根と考えます。

$|p_n-p_{n-1}|\lt\epsilon$ かつ、$|q_n-q_{n-1}|\lt\epsilon$
ならば、
$\alpha=p_n$ 、$\beta=q_n$

 

応用数学
情報理論、暗号理論、機械学習、金融工学、ゲーム理論
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

タイトルとURLをコピーしました