next up previous contents
Next: A.5 Strum の方法 Up: A.4 Bairstow Hitchcock の方法 Previous: A.4 Bairstow Hitchcock の方法

A.4.0.0.1 一松による説明

$\displaystyle x^n+a_1 x^{n-1}+\cdots+a_{n-1}x+a_n=0
$

の二次の因数 $ x^2-px-q$ を求めよう。商を $ x^{n-2}+b_1 x^{n-3}+\cdots
+b_{n-2}$, 剰余を $ b_{n-1}x+b_n$ とおくと、

$\displaystyle b_1=a_1+p,\quad
b_2=a_2+p b_1+q,\quad
b_{k}=a_k+p b_{k-1}+q b_{k-2}$   $\displaystyle \mbox{($k=3,4,\cdots,n-1,n$)}$

という漸化式で $ \{b_k\}$ が計算できる。次に $ \{c_k\}$

$\displaystyle c_1=b_1+p,\quad
c_2=b_2+p c_1+q,\quad
c_{k}=b_k+p c_{k-1}+q c_{k-2}$   $\displaystyle \mbox{($k=3,4,\cdots,n-1,n$)}$

という漸化式で計算すると、

$\displaystyle \frac{\rd b_k}{\rd p}=c_{k-1},\quad
\frac{\rd b_k}{\rd q}=c_{k-2}
$

となることが示される。解くべき方程式は

$\displaystyle b_{n}(p,q)=0,\quad b_{n-1}(p,q)=0
$

であるから、
      $\displaystyle b_n+c_{n-1}\Delta p+c_{n-2}\Delta q=0$
      $\displaystyle b_{n-1}+c_{n-2}\Delta p+c_{n-3}\Delta q=0$

$\displaystyle p_{\nu+1}=p_{\nu}+\frac{b_n c_{n-3}-b_{n-1}c_{n-2}}
{(c_{n-2})^2-...
...\nu+1}=q_{\nu}+\frac{b_{n-1}c_{n-1}-b_{n}c_{n-2}}
{(c_{n-2})^2-c_{n-1}c_{n-3}}
$

という反復を行う。 初期値には $ p_0=q_0=0$ が使われるが、これを Bairstow 法とよぶ。除法を次 数の低い方から進める変形を Hitchcock 法と呼ぶ。

一松 [13] から
「Bairstow 法は、これまで、実係数の代数方程式の複素根を、実数計算だけで 求めるのに便利な方法として、広く使われてきた。実係数なら複素根は必ず共 役複素数の対になって現れ、実2次因子の根になるからである。しかし機械的に これを使って失敗した例が多い。その多くは、Newton 法には大域的収束性が保 証されないのに、適当な初期値からいい加減に始めた場合である。 特に虚数部が小さい根 $ \alpha\pm i\beta$ があると、あたかも $ \alpha$ に 実根があるかのように見え、他の実根 $ \gamma$ と合わせた 2 次因子 $ (x-\alpha)(x-\gamma)$ の近似が計算されかねない。ある段階に進むと、 $ x=\alpha$ の付近に実根がないため、分母が 0 近くなって、収束しかかった 反復列が大きく飛ぶという現象を生ずる。これを防ぐための手法もいろいろ 研究されている。筆者のささやかな経験では、根の分布を調べて十分よい 初期値から始めることにし、複素数のよい計算体系が利用できる場合には、 複素数の1変数の Newton 法を使うようにした方が無難と思う。」


next up previous contents
Next: A.5 Strum の方法 Up: A.4 Bairstow Hitchcock の方法 Previous: A.4 Bairstow Hitchcock の方法
Masashi Katsurada
平成21年7月9日