next up previous contents
Next: 2.2.5 解の精度の検証 Up: 2.2 連立法, 特に Durand-Kerner Previous: 2.2.3 復習: 根と係数の関係

2.2.4 DK 法 -- Kerner の解釈

$ X_1$, $ \cdots$, $ X_n$$ s$ 次基本対称式 ($ s$ 個の積全体の和) を $ S_s(X_1,\cdots,X_n)$ とおく:

$\displaystyle S_s(X_1,\cdots,X_n)
=\sum_{i_1<i_2<\cdots<i_s}X_{i_1}X_{i_1}\cdots X_{i_s}
=\sum_{i_1<i_2<\cdots<i_s}\prod_{j=1}^{s}X_{i_j}.
$

根と係数の関係から

(2.6) $\displaystyle f_s(\xi_1,\cdots,\xi_n):= (-1)^s S_s(\xi_1,\cdots,\xi_n)-a_{n-s}=0$   $\displaystyle \mbox{($s=1,2,\cdots,n$)}$$\displaystyle .$


\begin{jtheorem}
% latex2html id marker 637
[Kerner 1966]
Durand の反復 (\ref{e...
...立方程式
とみなして、それを Newton 法で解く反復計算に他ならない。
\end{jtheorem}

Proof. まず

$\displaystyle \xi=
\left(
\begin{array}{c}
\xi_1 \\
\xi_2 \\
\vdots\\
\xi_n
...
...(\xi_1,\cdots,\xi_n) \\
\vdots \\
f_n(\xi_1,\cdots,\xi_n)
\end{array}\right)
$

とおき、

$\displaystyle J=f'(\xi),\quad Q=(q_{is}(\xi))=J^{-1}
$

とすれば、

$\displaystyle x_i^{(k+1)}=x_i^{(k)}-\sum_{s=1}^nq_{is}(x^{(k)}) f_s(x^{(k)}),
$

ただし

$\displaystyle x^{(k)}=\left(
\begin{array}{c}
x_1^{(k)} \\
x_2^{(k)} \\
\vdots \\
x_n^{(k)}
\end{array}\right)
$

とおいた。

ところで $ S_s(\cdot)$ の定義から、$ x$ についての恒等式

$\displaystyle \prod_{i=1}^n (x-x_i^{(k)})
=x^n+\sum_{s=1}^n(-1)^s S_s(x_1^{(k)},\cdots,x_n^{(k)})x^{n-s}
$

が得られる。この式を $ x_i^{(k)}$ について偏微分して、 $ x=x_i^{(k)}$ とお くと、
  $\displaystyle -\prod_{j\ne i}\left(x_i^{k}-x_j^{(k)}\right)$ $\displaystyle =$ $\displaystyle \sum_{s=1}^n (-1)^s \frac{\rd S_s}{\rd \xi}$   (途中)

(書きかけ) 与えられた $ z_1$, $ \cdots$, $ z_n$ に対して

$\displaystyle \prod_{j=1}^n\left(x-z_j\right)=Q(x)=x^n+b_{n-1}x^{n-1}+\cdots+b_1 x+b_0
$

とおくと、
  $\displaystyle \frac{\rd Q}{\rd z_j}$ $\displaystyle =$ $\displaystyle \left(\frac{\rd b_{n-1}}{\rd z_j}\right)x^{n-1}
+\cdots+\left(\frac{\rd b_1}{\rd z_j}\right)x
+\left(\frac{\rd b_0}{\rd z_j}\right)$
    $\displaystyle =$ $\displaystyle -(x-z_1)\cdots(x-z_{j-1})(x-z_{j+1})\cdots(x-z_n).$

また根と係数の関係

$\displaystyle b_{n-k}=(-1)^{k} S_k(z_1,\cdots,z_n)
$

が成り立つ。 ここで $ x=z_i$ とおくと、 $ -Q'(z_i)\delta_{ij}$ となるから、

$\displaystyle \left(
-\frac{z_i^{n-1}}{Q'(z_i)},\cdots,-\frac{z_i}{Q'(z_i)},-\frac{1}{Q'(z_i)}
\right)
$

$ J(z)^{-1}=\left(\rd b_{n-i}/\rd z_j\right)^{-1}$ の第 $ i$ 行と 一致する。 ゆえに $ J(z)^{-1}f(z)$ の第 $ i$ 成分は
  $\displaystyle \frac{-z_i^{n-1}}{Q'(z_i)}(b_{n-1}-a_{n-1})-\cdots
-\frac{1}{Q'(z_i)}(b_0-a_0)$ $\displaystyle =$ $\displaystyle -\frac{z_i^n}{Q'(z_i)}(b_n-a_n)-\frac{z_i^{n-1}}{Q'(z_i)}(b_{n-1}-a_{n-1})
-\frac{1}{Q'(z_i)}(b_0-a_0)$
    $\displaystyle =$ $\displaystyle \frac{-Q(z_i)+P(z_i)}{Q'(z_i)}=\frac{P(z_i)}{Q'(z_i)}.$

ゆえに ... の各成分を比較して ... を得る。 $ \qedsymbol$ ARRAY(0x12b7d24) $ \qedsymbol$


\begin{jcorollary}
代数方程式の根がすべて相異なるとき、DK 法は根に十分近いところで 2 次の
収束となる。
\end{jcorollary}

Proof. Newton 法の一般的な性質である。 $ \qedsymbol$ ARRAY(0x12cc938) $ \qedsymbol$


next up previous contents
Next: 2.2.5 解の精度の検証 Up: 2.2 連立法, 特に Durand-Kerner Previous: 2.2.3 復習: 根と係数の関係
Masashi Katsurada
平成21年7月9日