next up previous contents
Next: 2.2.9 Ehrlich-Aberth 法 Up: 2.2 連立法, 特に Durand-Kerner Previous: 2.2.7 初期値の取り方の重要性

2.2.8 Aberth の初期値, DKA 法

以下に示す連立法の初期値は Aberth (1973) により提唱された。 アルゴリズム全体を DKA 法と呼ぶ。

$\displaystyle p(z)=z^n+a_{n-1}z^{n-1}+\cdots+a_0=0
$

の根を求める DK 法の初期値 $ z_j^{(0)}$ ( $ j=1,2,\cdots,n$) として、

(2.7) $\displaystyle z_j^{(0)}=-\frac{a_{n-1}}{n}+r_0 \exp \left[ \sqrt{-1} \left( \frac{2\pi(j-1)}{n}+\frac{\pi}{2n} \right) \right]$   $\displaystyle \mbox{($j=1,2,\cdots,n$)}$

ただし $ r_0$ は閉円板

$\displaystyle \overline B(-a_{n-1}/n;r_0):= \{z\in\C; \vert z+a_{n-1}/n\vert\le r_0\}
$

がすべての根を含むように選ぶ。例えば

$\displaystyle r_0=\frac{\vert a_{n-1}\vert}{n}+1+\max_{0\le i\le n-1}\vert a_i\vert.
$

$ p(z)=0$ の根は行列

$\displaystyle \left(
\begin{array}{ccccc}
0 & & & & -a_0 \\
1 & 0 & & & -a_1 \...
... \vdots \\
& & \ddots & 0 & -a_{n-2} \\
& & &1 & -a_{n-1}
\end{array}\right)
$

の固有値である。Gerschgorin の定理から、それらはすべて

$\displaystyle \vert z\vert\le 1+\max_{0\le i\le n-1}\vert a_i\vert
$

に含まれる。

また

$\displaystyle x^{(1)}_{j}+\frac{a_1}{n}
=\left(1-\frac{1}{n}\right)
\left(x^{(0...
...+\frac{a_1}{n}\right)
+O\left(\left(x^{(0)}_j+\frac{a_1}{n}\right)^{-1}\right)
$

が成り立つので、$ r_0$ が十分大きいいとき、 $ x^{(k)}_j$ ( $ j=1,2,\cdots,n$) は、 円の中心 (根の重心) $ -a_1/n$ に向かって「直進」する。 このことを「最初は$ 1$次収束」、「終盤は$ 2$次収束」と言われることもあるが、 中盤がどうなるかは分からず、収束証明になっているわけではない。


next up previous contents
Next: 2.2.9 Ehrlich-Aberth 法 Up: 2.2 連立法, 特に Durand-Kerner Previous: 2.2.7 初期値の取り方の重要性
Masashi Katsurada
平成21年7月9日