2.2.8 Aberth の初期値, DKA 法

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

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

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

$$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] \mbox{($j=1,2,\cdots,n$)}$$ (2.7)

ただし $r_0$ は閉円板

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

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

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

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

$$\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 の定理から、それらはすべて

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

に含まれる。

また

$$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$次収束」と言われることもあるが、 中盤がどうなるかは分からず、収束証明になっているわけではない。