2.2.2 DK 法 -- Durand の解釈

代数方程式

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

の根を $\xi_1$, $\cdots$, $\xi_n$ とすると

$$p(x)=(x-\xi_1)\cdots(x-\xi_n),$$

$$p'(\xi_i)=\prod_{j\ne i}(\xi_{i}-\xi_{j}) =(\xi_i-\xi_1)\cdots(\xi_i-\xi_{i-1}) (\xi_i-\xi_{i+1})\cdots(\xi_i-\xi_{n}).$$ (2.3)

Newton 法では現在の近似値 $x^{(k)}$ から次の近似値 $x^{(k+1)}$ を求めるには

$$x^{(k+1)}=x^{(k)}-\frac{p(x^{(k})}{p'(x^{(k)})}$$ (2.4)

とする。ここで導関数の計算をしないで済ませるために、この分母を (2.3) で代用することを考える。 つまり $x^{(k)}$ が $\xi_i$ の近似値だと考えて $p'(x^{(k)})$ を $p' (\xi_i)$ で置き換えるわけである。各根 $\xi_i$ に対する 近似値 $x_i^{(k)}$ が $i=1$, $\cdots$, $n$ について全部そろっているとし て、(2.4) の代わりに

$$x_i^{(k+1)}=x_i^{(k)}-\frac{p(x_i^{(k)})} {\dsp\prod_{j\ne i}\left(x_i^{(k)}-x_j^{(k)}\right)}.$$ (2.5)

を用いる。

Durand は (2.5) の収束性を示し、最終的に $2$ 乗収束 になることを証明した。 $\qedsymbol$

$\xi_1$, $\cdots$, $\xi_n$ がすべて相異なり、$x_i^{(k)}$ が $\xi_i$ に十分近いとして、 $\eps_i^{(k)}:= x_i^{(k)}-\xi_i$ とおけば、

$$\eps_i^{(k+1)} = \eps_i^{(k)} \left[ 1-\frac{\prod_{j\ne i}(x_i^{(k)}-\xi_j)} {\prod_{j\ne i}(x_i^{(k)}-x_j^{(k)})} \right]$$

$$= \eps_{i}^{(k)} \left[ 1-\prod_{j\ne i} \left( 1+\frac{\eps_j^{(k)}}{x_i^{(k)}-x_{j}^{(k)}} \right) \right]$$

$2$ 次の項 $\eps_j^{(k)}\cdot\eps_{\ell}^{(k)}$ を無視すると

$$\eps_{i}^{(k)}\kinji -\eps_{i}^{(k)}\sum_{j\ne i}\frac{\eps_j^{(k)}} {x_i^{(k)}-x_j^{(k)}}.$$

$$\vert x_i^{(k)}-x_j^{(k)}\vert\ge \frac{1}{C}$$   $$\mbox{($C$ は $i$, $j$, $k$ によらない)}$$

とすれば

$$\left\vert \eps_i^{(k+1)} \right\vert \le C\left\vert\eps_{i}^{(k)}\right\vert\cdot \sum_{j\ne i}\left\vert\eps_j^{(k)}\right\vert.$$

これは $2$ 乗収束を意味するが、さらに詳しくみると

証明. (そんなに簡単ではない。一松 [19] の §20 や、 山本・北川 [22] を参照。) $\qedsymbol$ $\qedsymbol$