ベアストゥ法
ベアストゥ法とは、一般的な多項式の実根・虚根の全てを求めることができる数値計算法です。ベアストゥ法は、多項式から２次の多項式で因数分解し、次数を順次下げることで全ての根を求めていきます。
次のような一般的な $n$ 次の多項式について、
$$a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_1x+a_0=0 -①$$
以下のように２次式で除算します。
$$(b_{n-2}x^{n-2}+\cdots+b_1x+b_0)(x^2+px+q)+fx+g=0 -②$$
剰余 $fx+g$ が０になるような $p$、$q$ を見つけることができれば、①の根を求める問題は、次の２つの多項式の根を求める問題に帰着します。
$$b_{n-2}x^{n-2}+\cdots+b_1x+b_0=0 -③$$$$x^2+px+q=0 -④$$
④は解の公式を使って根を求めることができます。一方、③が高次の多項式の場合は、この手順を繰り返し、次数を下げていきます。
剰余を０にする手順
剰余 $fx+g$ を０にするような $p$、$q$ を求める手順を説明します。②を展開すると、各係数は①と等しくなるため、
$a_n=b_{n-2}$
$a_{n-1}=b_{n-3}+pb_{n-2}$
$a_{n-2}=b_{n-4}+pb_{n-3}+qb_{n-2}$
・・・・
$a_2=b_0+pb_1+qb_2$
$a_1=pb_0+qb_1+f$
$a_0=qb_0+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$$
n=4 の場合の計算例
$n=4$ の場合の②は、
$$(b_2x^2+b_1x+b_0)(x^2+px+q)+fx+g=0$$
これと①と同じ次数同士の係数を比べると、
$a_4=b_2 -(1)$
$a_3=pb_2+b_1 -(2)$
$a_2=qb_2+pb_1+b_0 -(3)$
$a_1=pb_0+qb_1+f -(4)$
$a_0=qb_0+g -(5)$
(1)～(3) から $b_0\sim b_2$ を求めると、
$b_2=a_4$
$b_1=a_3-a_4p$
$b_0=a_2-a_4q-a_3p+a_4p^2$
これより (4)と(5) から $f$ と $g$ を求めると、
$$f=a_1-a_2p-a_3q+2a_4pq+a_3p^2+a_4p^3$$$$g=a_0-a_2q+a_4q^2+a_3pq-a_4p^2q$$
このように、$f$ と $g$ は $p$ と $q$ の関数であり、次にこれらの根を求めます。
$$f(p,q)=0$$$$g(p,q)=0$$
根を求める
$f(p,q)$ と $g(p,q)$ の根をニュートン法を使って解きます。適当な点（$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$$
右辺の２次の項を無視し、左辺を０、および、
$$\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=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}} -⑥$$
⑤と⑥を繰り返すことにより（$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$
