皆さんこんにちは!
今回は高速収束法という話をしていこうと思います。
まず最初に収束次数とはなにかについて話していきます。
数列$x_n$が真の値$\alpha$に収束する時、
$$ \left| x_{n+1}-\alpha \right| \leq C\left| x_n-\alpha \right|^p ( \exists C \gt 0)$$
となるなら収束次数$p$をもつという。
いくつか例を出してみましょうか。
$x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)}$
これは二次収束します。
ここから先では誤差を
$e_n=x_n-\alpha $
と置くことにします。
$$x_{n+1}=x_n-\frac{2f(x_n)f^{\prime}(x_n)}{2(f^{\prime}(x_n))^2-f(x_n)f^{\prime\prime}(x_n)}$$
これは三次収束します。
ここからが本題です
Newton法は二次収束、Halley法は三次収束である
ではもっと高い収束次数の求根法の漸化式とはどんなものなのか説明していこうと思います。
関数
$$f: \mathbb{R} \rightarrow \mathbb{R} $$
が$k+1$回微分可能とする。
単純根
$f(\alpha)=0, f^{\prime}(\alpha) \neq 0$
を持つとき
$$g(x)=\frac{1}{f(x)}$$
と置くと
次の反復法
$$x_{n+1}=x_n+k\frac{g^{(k-1)}(x_n)}{g^{(k)}(x_n)}$$
または
$$x_{n+1}=x_n-\frac{f}{f^{\prime}}(1+A_1+A_2+ \cdots +A_{k-1})^{-1}$$
ただし、
$$A_i=\frac{f^{(i+1)}}{(i+1)!}(\frac{f}{f^{\prime}})^i$$
最後に証明で出てきた
$\displaystyle\frac{1}{f(x)}=\frac{1}{f^{\prime}(\alpha)(x-\alpha)}+c_0+c_1(x-\alpha)+c_2(x-\alpha)^2+\cdots$
を証明しておきましょうか。
$f(z)$を$z=\alpha$で零点をもち、$f^{\prime}(z)$が$z=\alpha$で非ゼロ値をとる正則関数とすると
$$f(z)=\sum_{n=1}^{\infty}\frac{f^{(n)}(\alpha)}{n!}(z-\alpha)^n$$
Laurent展開の定義より
$$g(z)=\sum_{n=-\infty}^{\infty}c_n(z-\alpha)^n$$
ただし、
$\displaystyle c_n=\frac{1}{2\pi i }\oint_C\frac{g(\xi)}{(\xi-\alpha)^{n+1}}d\xi$
$\displaystyle g\rightarrow\frac{1}{f}$とすると
$$\frac{1}{f(z)}=\sum_{n=-\infty}^{\infty}c_n(z-\alpha)^n$$
$\displaystyle c_n=\frac{1}{2\pi i }\oint_C\frac{1}{f(\xi)(\xi-\alpha)^{n+1}}d\xi$
$$ c_{-1}=\frac{1}{2\pi i}\oint_C\frac{1}{f(\xi)}d\xi=\frac{1}{2\pi i}\oint_C\frac{1}{\sum_{n=1}^{\infty}\frac{f^{(n)}(\alpha)}{n!}(\xi-\alpha)^n}d\xi=\frac{1}{2\pi i}\oint_C\frac{(\sum_{n=1}^{\infty}\frac{f^{(n)}(\alpha)}{n!}(\xi-\alpha)^{n-1})^{-1}}{\xi-\alpha}d\xi$$
$$c_{-1}= \lim_{\xi \to \alpha} (\sum_{n=1}^{\infty}\frac{f^{(n)}(\alpha)}{n!}(z-\alpha)^{n-1})^{-1}=\frac{1}{f^{\prime}(\alpha)}$$
よって示された。