2 反復関数の解析と3次の反復関数

2.1 解析的に見たNewton法

Newton法を解析的に導いてみる。方程式 $f(x)=0$ についてある近似解 $x_n$ が与えられているとき、

$$f(x_n+\delta)=0$$ (2.22)

となるような$\delta$を求めるのが問題である。$f(x_n+\delta)$を$x_n$を中心にTaylor展開すると、

$$f(x_n+\delta)=f(x_n)+f'(x_n)\delta+\frac{1}{2}f''(x_n)\delta^2+\cdots$$

となるから、$\vert\delta\vert$が十分小さければ

$$f(x_n+\delta) \approx f(x_n)+f'(x_n)\delta$$ (2.23)

である。ここで $f(x_n+\delta)=0$ とおき、$f'(x_n) \ne 0$ を仮定すれば

$$\delta \approx -\frac{f(x_n)}{f'(x_n)}$$

となるので、

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ (2.24)

はより良い近似解となっていることが期待できる。つまりこの反復を繰り返せば十分な精度の近似解が求まるだろうと考えられる。

2.2 収束性

前節の漸化式の様子を見るために、反復関数

$$F(x)=x-\frac{f(x)}{f'(x)}$$ (2.25)

を調べてみよう。

$$\delta_n=x_n-\alpha$$ (2.26)

をおくと、(2.3)より

$$\alpha+\delta_{n+1}=F(\alpha+\delta_n)$$

であるから

$$\delta_{n+1}=F(\alpha+\delta_n)-\alpha$$

となり、 $F(\alpha+\delta_n)$を$\alpha$を中心にTaylor展開すれば

$$\begin{eqnarray*} \delta_{n+1}&=&F(\alpha)-\alpha+F'(\alpha)\delta_n+\frac{1}{2}... ... &=&F'(\alpha)\delta_n+\frac{1}{2}F''(\alpha)\delta_n^2+\cdots \end{eqnarray*}$$

を得る。次に

$$\begin{eqnarray*} F'(x)&=&1-\frac{f'(x)^2-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2}, \\ F''(x)&=&\frac{f'(x)^3f''(x)+f(x)(\cdots)}{f'(x)^4} \end{eqnarray*}$$

であるから

$$F'(\alpha)=0,F''(\alpha)=\frac{f''(\alpha)}{f'(\alpha)}$$

となり、

$$\delta_{n+1}=\frac{f''(\alpha)}{2f'(\alpha)}\delta_n^2+\cdots \approx\frac{f''(\alpha)}{2f'(\alpha)}\delta_n^2$$ (2.27)

を得る。この式から、Newton法は $f'(\alpha)\not\approx0$、つまり重解に近くない場合には十分良い近似解から反復を始めると2次収束となることが分かる。 $f'(\alpha)\approx0$の場合については、

$$f(x) \approx (x-\alpha)^mg(x) \qquad (m \ge 2,g(\alpha) \not\approx 0)$$ (2.28)

とおいて調べてみると、

$$f'(x) \approx (x-\alpha)^{m-1}(mg(x)+(x-\alpha)g'(x))$$

であるから、

$$\delta_{n+1} = \delta_n-\frac{f(x_n)}{f'(x_n)}$$

$$\approx \delta_n-\frac{(x_n-\alpha)g(x_n)}{mg(x_n)+(x_n-\alpha)g'(x_n)}$$

$$= \delta_n-\frac{g(x_n)}{mg(x_n)+g'(x_n)\delta_n}\delta_n$$

$$\approx \left(1-\frac{1}{m}\right)\delta_n$$ (2.29)

となり、かなり遅い収束であることが分かる。

上の議論で重要なのは、反復関数$F(x)$が十分素直な場合に$\delta_n$が漸化式

$$\delta_{n+1}=F'(\alpha)\delta_n+\frac{1}{2}F''(\alpha)\delta_n^2+\cdots$$ (2.30)

で与えられるということである。つまり、もし$F(x)$が

$$F'(\alpha)=F''(\alpha)=\cdots=F^{(r-1)}(\alpha)=0, \quad 0<\vert F^{(r)}(\alpha)\vert<\infty$$ (2.31)

を満たせば

$$\delta_{n+1}=F^{(r)}(\alpha)\delta_n^r+\cdots \approx F^{(r)}(\alpha)\delta_n^r$$ (2.32)

であり、$r$次収束となることが分かるのである。

2.3 Householder法

Newton法の場合は1次の項で展開を打ち切ったが、これを2次の項まで展開するとより高い次数の収束を示すと考えられる。そこで

$$0 \approx f(x_n)+f'(x_n)\delta+\frac{f''(x_n)}{2}\delta^2$$ (2.33)

とおけば、

$$\begin{eqnarray*} \delta&\approx&\frac {-f'(x_n)\pm\sqrt{f'(x_n)^2-2f(x_n)f''(x... ...n)}\left( 1\pm\sqrt{1-\frac{2f(x_n)f''(x_n)}{f'(x_n)^2}}\right) \end{eqnarray*}$$

となる。 $f(x_n) \approx 0$であることを考えて、$\vert\delta\vert$が小さくなる様に複号は$+$を選び、また根号を一般の二項定理を用いて開けば、

$$\begin{eqnarray*} \delta&\approx&-\frac{f'(x_n)}{f''(x_n)} \left(\frac{f(x_n)f'... ...f(x_n)}{f'(x_n)}\left(1+\frac{f(x_n)f''(x_n)}{2f'(x_n)^2}\right) \end{eqnarray*}$$

となる。よって反復関数

$$F(x)=x-\frac{f(x)}{f'(x)}\left(1+\frac{f(x)f''(x)}{2f'(x)^2}\right)$$ (2.34)

が得られる。ここで $F'(\alpha)=F''(\alpha)=0$であり、また

$$F'''(\alpha)=3\left(\frac{f''(\alpha)}{f'(\alpha)}\right)^2-\frac{f'''(\alpha)}{f'(\alpha)}$$ (2.35)

であるから、$\alpha$が重解に近くなければ3次収束となる。この反復関数を用いる方法をHouseholder法(Householder's Method)という。

2.4 Halley法

2次の項で展開を打ち切った場合、次のようにすればHouseholder法とは違う3次収束をする反復関数が得られる。まず

$$\begin{eqnarray*} 0&\approx&f(x_n)+f'(x_n)\delta+\frac{f''(x_n)}{2}\delta^2 \\ &=&f(x_n)+\delta\left(f'(x_n)+\frac{f''(x_n)}{2}\delta\right) \end{eqnarray*}$$

と変形すれば、

$$\delta \approx -\frac{f(x_n)}{f'(x_n)+\frac{1}{2}f''(x_n)\delta}$$ (2.36)

となる。ここで右辺の$\delta$をNewton法から考えて

$$\delta=-\frac{f(x_n)}{f'(x_n)}$$

で置き換えると、

$$\delta \approx -\frac{2f(x_n)f'(x_n)}{2f'(x_n)^2-f(x_n)f''(x_n)}$$

となり、反復関数

$$F(x)=x-\frac{2f(x)f'(x)}{2f'(x)^2-f(x)f''(x)}$$ (2.37)

が得られる。ここで $F'(\alpha)=F''(\alpha)=0$であり、また

$$F'''(\alpha)=\frac{3}{2}\left(\frac{f''(\alpha)}{f'(\alpha)}\right)^2-\frac{f'''(\alpha)}{f'(\alpha)}$$ (2.38)

であるから、$\alpha$が重解に近くなければ3次収束となる。この反復関数を用いる方法をHalley法(Halley's Method)という。

Householder法はHalley法からも導くことができる。(2.16)から

$$\begin{eqnarray*} F(x)&=&x-\frac{f(x)}{f'(x)-f(x)f''(x)/2f'(x)} \\ &=&x-\frac{f(x)}{f'(x)}\left(1-\frac{f(x)f''(x)}{2f'(x)^2}\right)^{-1} \end{eqnarray*}$$

となり、一般の二項定理を用いて

$$\begin{eqnarray*} F(x)&=&x-\frac{f(x)}{f'(x)}\left(1+\frac{f(x)f''(x)}{2f'(x)^2}... ...x&x-\frac{f(x)}{f'(x)}\left(1+\frac{f(x)f''(x)}{2f'(x)^2}\right) \end{eqnarray*}$$

が得られる。