2

任意の収束次数の方程式の数値解法の漸化式を導く

61
0
$$$$

皆さんこんにちは!
今回は高速収束法という話をしていこうと思います。

収束次数

まず最初に収束次数とはなにかについて話していきます。

収束次数

数列$x_n$が真の値$\alpha$に収束する時、

$$ \left| x_{n+1}-\alpha \right| \leq C\left| x_n-\alpha \right|^p ( \exists C \gt 0)$$

となるなら収束次数$p$をもつという。

いくつか例を出してみましょうか。

Newton法

$x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)}$

これは二次収束します。

ここから先では誤差を

$e_n=x_n-\alpha $

と置くことにします。

Newton法の導出
解を$\alpha$とする。

$x_n$周りのTaylorの定理より

$f(\alpha)=f(x_n)+f^{\prime}(x_n)(\alpha-x_n)+O((\alpha-x_n)^2) $

ここで

$f(\alpha)=0$

なので

$0=f(x_n)+f^{\prime}(x_n)h$

ただし

$h=\alpha-x_n$と置いた。

$h$について解くと

$h=-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)}$

よって

$h=\alpha-x_n$

なので

$\alpha=x_n-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)}$

しかし、途中で$O((\alpha-x_n)^2)$を無視して計算を進めたため左辺と右辺は正確には$=$ではありません。
なので $\alpha\rightarrow x_{n+1}$と置き換えることで
Newton法

$ x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)}$

が得られる。

Newton法が二次収束することの証明
$\alpha $周りのTaylor展開より

$f(x_n)=f(\alpha)+ f^{\prime}(\alpha)e_n+\displaystyle\frac{1}{2} f^{\prime\prime}(\xi_n)e_n^2$

ただし

$\xi_n\in(\alpha,x_n)$

である。
ここで

$f(\alpha)=0 $

なので

$f(x_n)=f^{\prime}(\alpha)e_n+\displaystyle\frac{1}{2}f^{\prime\prime}(\xi_n)e_n^2 $

同様に

$f^{\prime}(x_n)= f^{\prime}(\alpha)+f^{\prime\prime}( \eta_n )e_n$

ただし

$\eta_n\in(\alpha,x_n) $

これらをNewton法

$x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)} $

に代入する。
誤差表示にすると

$e_{n+1}=e_n-\displaystyle\frac{f(x_n)}{f^{\prime}(x_n)} $

よって

$e_{n+1}=e_n-\displaystyle\frac{f^{\prime}(\alpha)e_n+\displaystyle\frac{1}{2}f^{\prime\prime}(\xi_n)e_n^2}{f^{\prime}(\alpha)+f^{\prime\prime}(\eta_n)e_n}$

分子を整理して

$e_{n+1}=\displaystyle\frac{f^{\prime\prime}(\eta_n)e_n^2-\frac{1}{2}f^{\prime\prime}(\xi_n)e_n^2}{f^{\prime}(\alpha)+f^{\prime\prime}(\eta_n)e_n}$

したがって

$$e_{n+1}=\frac{e_n^2(f^{\prime\prime}(\eta_n)-\frac{1}{2}f^{\prime\prime}(\xi_n))}{f^{\prime}(\alpha)+f^{\prime\prime}(\eta_n)e_n}$$

ここで

$f^{\prime\prime} $は連続
$f^{\prime} \neq 0$
$e_n\rightarrow 0$

なので十分大きい$n$に対して

$$\left|f^{\prime}(\alpha)+f^{\prime\prime}(\eta_n)e_n\right| \geq \frac{1}{2}\left|f^{\prime}(\alpha)\right|$$

また

$$\left|f^{\prime\prime}(\eta_n)-\frac{1}{2}f^{\prime\prime}(\xi_n)\right| \leq M$$

となる定数$M$が存在する。

したがって

$$\left|e_{n+1}\right| \leq \frac{2M}{\left|f^{\prime}(\alpha)\right|}\left|e_n\right|^2$$

つまり

$\left|e_{n+1}\right|\leq C\left|e_n\right|^2$

となる。
よってNewton法は二次収束する。
Halley法

$$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)}$$

これは三次収束します。

Halley法の導出
解を$\alpha$とする。

$x_n$周りでのTaylor展開より

$$f(\alpha)=f(x_n)+f^{\prime}(x_n)(\alpha-x_n)+\frac{1}{2}f^{\prime\prime}(x_n)(\alpha-x_n)^2+O((\alpha-x_n)^3) $$

ここで

$$f(\alpha)=0$$

なので

$$0=f(x_n)+f^{\prime}(x_n)h+\frac{1}{2}f^{\prime\prime}(x_n)h^2$$

ただし

$$h=\alpha-x_n$$

$$f(x_n)+f^{\prime}(x_n)h+\frac{1}{2}f^{\prime\prime}(x_n)h^2=0$$

これを$h$について解けばいいので

$$h=\frac{-f^{\prime} \pm \sqrt{f^{\prime2}-2ff^{\prime\prime}} }{f^{\prime\prime}}$$

分子を有理化すると

$$h=\frac{2f}{-f^{\prime} \pm \sqrt{f^{\prime2}-2ff^{\prime\prime}}}$$

$$h=-\frac{f}{f^{\prime}}\frac{2}{1 \pm \sqrt{1-\frac{2ff^{\prime\prime}}{f^{\prime2}}}}$$

平方根が邪魔くさいので$\pm$$+$を選んで

$$\sqrt{1-\varepsilon}=1-\frac{1}{2}\varepsilon$$

を使って近似すると

$\varepsilon=\displaystyle\frac{2ff^{\prime\prime}}{f^{\prime2}}$とすればいいので

$$ h \approx -\frac{f}{f^{\prime}}\frac{1}{1-\frac{1}{2}\frac{ff^{\prime\prime}}{f^{\prime2}}} $$

$\alpha=x_n+h$$\alpha$$x_{n+1}$と置くと、
$x_{n+1}=x_n+h$となるので、

$$x_{n+1}=x_n-\frac{f}{f^{\prime}}\frac{1}{1-\frac{1}{2}\frac{ff^{\prime\prime}}{f^{\prime2}}} $$

これがHalley法です。

整理すると

$$x_{n+1}=x_n-\frac{2ff^{\prime}}{2f^{\prime2}-ff^{\prime\prime}}$$

Halley法が三次収束することの証明

解を$\alpha$とする。

$\alpha$周りのTaylorの定理より、
ある$\xi_n,\eta_n,\theta_n$$\alpha$$x_n$の間に存在して

$f(x_n)=f^{\prime}(\alpha)e_n+\frac{1}{2}f^{\prime\prime}(\alpha)e_n^2+\frac{1}{6}f^{\prime\prime\prime}(\xi_n)e_n^3$

同様に

$f^{\prime}(x_n)=f^{\prime}(\alpha)+f^{\prime\prime}(\alpha)e_n+\frac{1}{2}f^{\prime\prime\prime}(\eta_n)e_n^2$

さらに

$f^{\prime\prime}(x_n)=f^{\prime\prime}(\alpha)+f^{\prime\prime\prime}(\theta_n)e_n$

これらをHalley法の式

$$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)}$$

に代入すると

$$e_{n+1}=e_n-\frac{2(f^{\prime}(\alpha)e_n+\frac{1}{2}f^{\prime\prime}(\alpha)e_n^2+\frac{1}{6}f^{\prime\prime\prime}(\xi_n)e_n^3)(f^{\prime}(\alpha)+f^{\prime\prime}(\alpha)e_n+\frac{1}{2}f^{\prime\prime\prime}(\eta_n)e_n^2)}{2(f^{\prime}(\alpha)+f^{\prime\prime}(\alpha)e_n+\frac{1}{2}f^{\prime\prime\prime}(\eta_n)e_n^2)^2-(f^{\prime}(\alpha)e_n+\frac{1}{2}f^{\prime\prime}(\alpha)e_n^2+\frac{1}{6}f^{\prime\prime\prime}(\xi_n)e_n^3)(f^{\prime\prime}(\alpha)+f^{\prime\prime\prime}(\theta_n)e_n)}$$

$$e_{n+1}=e_n-e_n\frac{2f^{\prime2}(\alpha) +3f^{\prime}(\alpha)f^{\prime\prime}(\alpha)e_n +(f^{\prime\prime2}(\alpha)+\frac{1}{3}f^{\prime}(\alpha)f^{\prime\prime\prime}(\xi_n)+f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n))e_n^2 +\frac{1}{6}f^{\prime\prime}(\alpha)(2f^{\prime\prime\prime}(\xi_n)+3f^{\prime\prime\prime}(\eta_n))e_n^3 +\frac{1}{6}f^{\prime\prime\prime}(\xi_n)f^{\prime\prime\prime}(\eta_n)e_n^4} {2f^{\prime2}(\alpha)+3f^{\prime}(\alpha)f^{\prime\prime}(\alpha)e_n +(\frac{3}{2}f^{\prime\prime2}(\alpha)+2f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n)-f^{\prime}(\alpha)f^{\prime\prime\prime}(\theta_n))e_n^2 -\frac{1}{6}f^{\prime\prime}(\alpha)(f^{\prime\prime\prime}(\xi_n)-12f^{\prime\prime\prime}(\eta_n)+3f^{\prime\prime\prime}(\theta_n))e_n^3 +\frac{1}{6}(3f^{\prime\prime\prime2}(\eta_n)-f^{\prime\prime\prime}(\xi_n)f^{\prime\prime\prime}(\theta_n))e_n^4}$$

ここからは厳密ではないですが、証明に必要ない$e_n$のある次数の項を省略して書こうと思います。具体的には分子は$4$次以上の項を、分母は$3$次以上の項を省略します。

$$e_{n+1}=e_n\frac{(2f^{\prime2}(\alpha)+3f^{\prime}(\alpha)f^{\prime\prime}(\alpha)e_n +(\frac{3}{2}f^{\prime\prime2}(\alpha)+2f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n)-f^{\prime}(\alpha)f^{\prime\prime\prime}(\theta_n))e_n^2 )-(2f^{\prime2}(\alpha)+3f^{\prime}(\alpha)f^{\prime\prime}(\alpha)e_n+(f^{\prime\prime2}(\alpha)+\frac{1}{3}f^{\prime}(\alpha)f^{\prime\prime\prime}(\xi_n)+f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n))e_n^2 )} {2f^{\prime2}(\alpha) +3f^{\prime}(\alpha)f^{\prime\prime}(\alpha)e_n +(\frac{3}{2}f^{\prime\prime2}(\alpha)+2f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n)-f^{\prime}(\alpha)f^{\prime\prime\prime}(\theta_n))e_n^2}$$

$$e_{n+1}=e_n^3\frac{-\frac{1}{2}f^{\prime\prime2}(\alpha)-\frac{1}{3}f^{\prime}(\alpha)f^{\prime\prime\prime}(\xi_n)+f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n)-f^{\prime}(\alpha)f^{\prime\prime\prime}(\theta_n)} {2f^{\prime2}(\alpha) +3f^{\prime}(\alpha)f^{\prime\prime}(\alpha)e_n +(\frac{3}{2}f^{\prime\prime2}(\alpha)+2f^{\prime}(\alpha)f^{\prime\prime\prime}(\eta_n)-f^{\prime}(\alpha)f^{\prime\prime\prime}(\theta_n))e_n^2}$$

よって

$$e_{n+1}=Ae_n^3$$

となり

絶対値をとれば

$\left| e_{n+1} \right| \leq C\left| e_n \right|^3$

Householder法

ここからが本題です
Newton法は二次収束、Halley法は三次収束である
ではもっと高い収束次数の求根法の漸化式とはどんなものなのか説明していこうと思います。

Householder法

関数
$$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$$

Householder法の導出
$$\frac{1}{f(x)}=\frac{1}{f^{\prime}(\alpha)(x-\alpha)}+c_0+c_1(x-\alpha)+c_2(x-\alpha)^2+\cdots$$

極の位置は $x=\alpha$ である

Laurent展開より

$$g(x)=\frac{A}{x-\alpha}+c_0+c_1(x-\alpha)+c_2(x-\alpha)^2+\cdots$$

微分すると

$$g^{\prime}(x)=-\frac{A}{(x-\alpha)^2}+c_1+2c_2(x-\alpha)+\cdots$$

さらに微分していくと

$$g^{(k)}(x)=(-1)^kk!\frac{A}{(x-\alpha)^{k+1}}+O(1)$$

同様に

$$g^{(k-1)}(x)=(-1)^{k-1}(k-1)!\frac{A}{(x-\alpha)^{k}}+O(1)$$

したがって

$$\frac{g^{(k-1)}}{g^{(k)}}=\frac{(-1)^{k-1}(k-1)!\frac{A}{(x-\alpha)^{k}}+O(1)}{(-1)^kk!\frac{A}{(x-\alpha)^{k+1}}+O(1)}=\frac{-(x-\alpha)+O((x-\alpha)^{k+1})}{k+O((x-\alpha)^{k+1})}$$

$$\frac{g^{(k-1)}}{g^{(k)}}=-\frac{x-\alpha}{k}+O((x-\alpha)^{k+1})$$

$$\alpha=x+k\frac{g^{(k-1)}}{g^{(k)}}+O((x-\alpha)^{k+1})$$

$x \rightarrow x_n,\alpha \rightarrow x_{n+1}$とすると

$$x_{n+1}=x_n+k\frac{g^{(k-1)}(x_n)}{g^{(k)}(x_n)}$$

Householder法がk+1次収束することの証明
$$x_{n+1}=x_n+k\frac{g^{(k-1)}(x_n)}{g^{(k)}(x_n)}$$

にHouseholder法の導出の方で証明した$\displaystyle\alpha=x+k\frac{g^{(k-1)}}{g^{(k)}}+O((x-\alpha)^{k+1}) $を適応すると、

$\displaystyle x_n+k\frac{g^{(k-1)}}{g^{(k)}}$の項が消えて

$$e_{n+1}=O(e_n^{k+1})$$

両辺に絶対値を取れば,ある定数$C$が存在して、

$$\left|e_{n+1}\right| \leq C\left|e_n\right|^{k+1} $$

となり、示された。

証明で出たきた式の証明

最後に証明で出てきた
$\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)}$$

よって示された。

投稿日:2日前
更新日:2日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中