3 任意次数の反復関数

3.1 単純積分型

反復関数$F_n(x)$が$n$次収束であるための必要条件は

$$F_n(\alpha)=\alpha,F_n'(\alpha)=F_n''(\alpha)=\cdots=F_n^{(n-1)}(\alpha)=0$$

であるから、単純に

$$F_n(x)=\alpha+\int_{\alpha}^{x}f(x)^{n-1}dx$$

とすれば上の条件は満たされる。しかしこれでは求めるべき$\alpha$が反復関数の中に入っており、役に立たないように見える。ところが、ここで

$$F_n(x)=\alpha+h\int_{\alpha}^{x}f(x)^{n-1}dx$$ (3.39)

のように書くと、$h$の値をうまく選ぶことで$\alpha$を消せることがある。例えば $f(x)=x^2-c,n=2$とすると、

$$\begin{eqnarray*} F_2(x)&=&\alpha+h\int_{\alpha}^{x}(x^2-c)dx \\ &=&h\left(\frac{x^3}{3}-cx\right)+\alpha\left(1+\frac{2ch}{3}\right) \end{eqnarray*}$$

であるから、$h=-3/2c$とすることで

$$F_2(x)=\frac{3cx-x^3}{2c}$$

という反復関数が得られる。

この方法は簡単であるが、$f(x)^{n-1}$の不定積分が求まり、かつ$\alpha$が消える必要があるので、一般的な用途には向かない。また、他の方法とは違って、$\alpha$の重解度が高いほど収束次数が高くなるのが特徴である。

3.2 有理関数型

Householderは$n$次の収束を示す反復関数

$$F_n(x)=x+(n-1)\frac{(1/f(x))^{(n-2)}}{(1/f(x))^{(n-1)}}$$ (3.40)

を与えている²。ここで

$$\begin{eqnarray*} \left(\frac{1}{f(x)}\right)'&=&-\frac{f'(x)}{f(x)^2}, \\ \lef... ...c{6f(x)f'(x)f''(x)-6f'(x)^3-f(x)^2f'''(x)}{f(x)^4}, \\ &\vdots& \end{eqnarray*}$$

であるから、$n=2$とすれば

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

となってNewton法が得られ、$n=3$とすれば

$$\begin{eqnarray*} F_3(x)&=&x-2\cdot\frac{f'(x)}{f(x)^2}\cdot\frac{f(x)^3}{2f'(x)^2-f(x)f''(x)} \\ &=&x-\frac{2f(x)f'(x)}{2f'(x)^2-f(x)f''(x)} \end{eqnarray*}$$

となってHalley法が得られる。$n=4$の場合には

$$F_4(x)=x-\frac{f(x)f'(x)^2-\frac{1}{2}f(x)^2f''(x)}{f'(x)^3-f(x)f'(x)f''(x)+\frac{1}{6}f(x)^2f'''(x)}$$ (3.41)

という反復関数が得られる。

具体的に$f(x)=x^2-c$とおいて有理関数型の4次までの反復関数を求めると、

$$\begin{eqnarray*} F_2(x)&=&x-\frac{x^2-c}{2x}=\frac{x^2+c}{2x}, \\ F_3(x)&=&x-\... ...}{(x^2-c) \cdot 2x \cdot 2-8x^3} =\frac{x^4+6cx^2+c^2}{4x^3+4cx} \end{eqnarray*}$$

となる。このことから一般に$n$次収束の反復関数は

$$F_n(x) = \left(\sum_{k=0}^{\infty}{n \choose 2k}c^{k}x^{n-2k}\right) \bigg/\left(\sum_{k=0}^{\infty}{n \choose 2k+1}c^{k}x^{n-2k-1}\right)$$ (3.42)

となることが予想され、具体的に $x=(1+\varepsilon )\sqrt{c}$ を代入すれば証明できる。より一般的に$f(x)=x^r-c$とした場合、

$$\begin{eqnarray*} F_2(x)&=&x\cdot\frac{(r-1)x^r+c}{rx^{r}}, \\ F_3(x)&=&x\cdot\... ...)cx^r+(r^2-1)c^2} {(r^2+3r+2)x^{2r}+(4r^2-4)cx^r+(r^2-3r+2)c^2} \end{eqnarray*}$$

となり、余り規則性は見られない。$F_3(x)$はBailey法(Bailey's Method)、Hutton法(Hutton's Method)、あるいはLambert法(Lambert's Method)として知られている反復関数である。

3.3 級数型

方程式$f(x)=0$の解$\alpha$を求めるのに、Newton法では与えられた$x$に対して

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

を用いて

$$\alpha \approx x+\delta$$

と近似したが、これを級数

$$\alpha=x+\delta+\frac{a_2}{2!}\delta^2+\frac{a_3}{3!}\delta^3+\cdots$$ (3.43)

を用いて正確に表すことを考える。$f(\alpha)$を$x$中心にTaylor展開すると、

$$\begin{eqnarray*} f(\alpha)&=&f(x)+f'(x)(\alpha-x)+\frac{f''(x)}{2}(\alpha-x)^2+\cdots \end{eqnarray*}$$

となり、ここで

$$\begin{eqnarray*} \alpha-x&=&\delta+\frac{a_2}{2!}\delta^2+\frac{a_3}{3!}\delta^3+\cdots \\ (\alpha-x)^2&=&\delta^2+a_2\delta^3+\cdots \end{eqnarray*}$$

であるから、$f^{(n)}(x)$を$f_n$で表すとして、

$$f(\alpha) = f_0+f_1(\delta+\frac{a_2}{2!}\delta^2+\frac{a_3}{3!}\delta^3+\cdots)+\frac{f_2}{2!}\left(\delta^2+a_2\delta^3+\cdots\right)+\cdots$$

$$= \frac{a_2f_1+f_2}{2!}\delta^2+\frac{a_3f_1+3a_2f_2+f_3}{3!}\delta^3+\cdots$$ (3.44)

となる。$f(\alpha)=0$であるから、任意の$x$に対して上の式が成り立つように$a_n$を選ぶと、

$$a_2=-\frac{f_2}{f_1},a_3=\frac{3f_2^2-f_1f_3}{f_1^2},\cdots$$ (3.45)

となる。このとき関数

$$F=x+\delta+\frac{a_2}{2!}\delta^2+\frac{a_3}{3!}\delta^3+\cdots$$ (3.46)

は、ほとんどの$x$に対してその$x$に対応する$\alpha$を返し、有限の項で打ち切れば任意の次数の反復関数が得られる。例えば$\delta^3$までの項で打ち切ると、4次収束を示す

$$\begin{eqnarray*} F&=&x-\frac{f_0^1}{1!}\cdot\frac{1}{f_1^1}-\frac{f_0^2}{2!}\cd... ...\frac{f_0f_2}{2f_1^2}+\frac{f_0^2(3f_2^2-f_1f_3)}{6f_1^4}\right) \end{eqnarray*}$$

が得られ、この方法がNewton法やHouseholder法の自然な拡張となっていることが分かる。

ここで

$$\left(\frac{1}{f_1}\right)'=-\frac{f_2}{f_1^2},\left(\frac{f_2}{f_1^3}\right)'=-\frac{3f_2^2-f_1f_3}{f_1^4}, \cdots$$

であることに気づけば、$n$次の反復関数は

$$F_n(x)=x-\sum_{k=1}^{n-1}\frac{f_0^k}{k!}\cdot\left(-\frac{1}{f_1}D\right)^{k-1}\frac{1}{f_1}$$ (3.47)

となることが予想される。 $F_n(\alpha)=\alpha$は明らかであるので、導関数を調べる。$F_n(x)$を書き直して

$$F_n(x)=\sum_{k=0}^{n-1}\frac{f_0^k}{k!}\cdot \frac{1}{D}\left(-D\frac{1}{f_1}\right)^k$$ (3.48)

とすると、被和項の1階導関数は

$$\begin{eqnarray*} &&\left(D\frac{f_0^k}{k!}\right)\cdot\frac{1}{D}\left(-D\frac{... ...right)^{k-1}+\frac{f_0^k}{k!}\cdot\left(-D\frac{1}{f_1}\right)^k \end{eqnarray*}$$

となるので、

$$F_n'(x)=\frac{f_0^{n-1}}{(n-1)!}\cdot\left(-D\frac{1}{f_1}\right)^{n-1}$$ (3.49)

を得る。$F_n'(x)$は因数$f^{n-1}$を持つので、$F_n(x)$の$n-1$階までの全ての導関数は$x=\alpha$において$0$となり、$F_n(x)$は$n$次収束を示すことが分かる。また、$F_n(x)$は

$$F_n(x)=\alpha+\int_{\alpha}^{x}\frac{f_0^{n-1}}{(n-1)!}\cdot\left(-D\frac{1}{f_1}\right)^{n-1}dx$$ (3.50)

と表され、従って単純積分型の拡張となっていることも分かる。

$F_n(x)$をもう少し分かりやすく

$$F_n=x-\sum_{k=1}^{n-1}\frac{f_0^k}{k!}\cdot\frac{p_{k-1}}{f_... ...}^{x}\frac{f_0^{n-1}}{(n-1)!}\cdot\frac{p_{n-1}}{f_1^{2n-2}}dx$$ (3.51)

という形で表すことを考えると、$k=1$の場合を考えて$p_0=1$であり、また

$$\begin{eqnarray*} \left(-\frac{1}{f_1}D\right)\frac{p_{k-1}}{f_1^{2k-1}} &=&\fra... ...1^{4k-1}} \\ &=&\frac{(2k-1)f_2p_{k-1}-f_1p_{k-1}'}{f_1^{2k+1}} \end{eqnarray*}$$

となるから、

$$p_n=(2n-1)f_2p_{n-1}-f_1p_{n-1}'$$ (3.52)

という漸化式が得られる。具体的に$p_n$を計算すると、

$$p_0 = 1$$

$$p_1 = f_2$$

$$p_2 = 3f_2^2-f_1f_3$$

$$p_3 = 15f_2^3-10f_1f_2f_3+f_1^2f_4$$ (3.53)

$$p_4 = 105f_2^4-105f_1f_2^2f_3+15f_1^2f_2f_4+10f_1^2f_3^2-f_1^3f_5$$

$$p_5 = 945f_2^5-1260f_1f_2^3f_3+210f_1^2f_2^2f_4+280f_1^2f_2f_3^2-21f_1^3f_2f_5-35f_1^3f_3f_4+f_1^4f_6$$

$$\vdots$$

となる。

$F(x)$は次のようにしても得られる。$f(x)$の反復関数が

$$F(x)=x-f(x)\varphi_1(x)$$ (3.54)

という形をしていると仮定する。 $F(\alpha)=\alpha$は当然満たしているので、$x=\alpha$における導関数の値が$0$という条件を要求すると、まず

$$\begin{eqnarray*} F'(x)=1-f'(x)\varphi_1(x)-f(x)\varphi_1'(x) \end{eqnarray*}$$

であるから、$F'(\alpha)=0$とおけば

$$\varphi_1(\alpha)=\frac{1}{f'(\alpha)}$$

となる。この式から一般に$\varphi_1(x)$は

$$\varphi_1(x)=\frac{1}{f'(x)}+f(x)\varphi_2(x)$$

の形で表せることが分かり、$F(x)$は

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

となる。同様にして

$$F''(\alpha)=\frac{f''(\alpha)}{f'(\alpha)}-2f'(\alpha)^2\varphi_2(\alpha)$$

であるから、$F''(\alpha)=0$を満たす一般の$\varphi_2(x)$は

$$\varphi_2(x)=\frac{f''(x)}{2f'(x)^3}+f(x)\varphi_3(x)$$

で表され、$F(x)$は

$$F(x)=x-\frac{f(x)}{f'(x)}-\frac{f(x)^2f''(x)}{2f'(x)^3}-f(x)^3\varphi_3(x)$$ (3.56)

となる。この計算を続けると

$$F(x)=x-\frac{f_0}{f_1}-\frac{f_0^2f_2}{2f_1^3}-\frac{f_0^3(3f_2^2-f_1f_3)}{6f_1^5}-\cdots$$ (3.57)

が得られ、先程と同じ反復関数となる。

さて、具体的に$f(x)=x^r-c$とすると、 $p_n=a_nx^{b_n}$として、

$$\begin{eqnarray*} p_n&=&(2n-1)r(r-1)x^{r-2}a_{n-1}x^{b_{n-1}}-rx^{r-1}a_{n-1}b_{... ...^{b_{n-1}-1} \\ &=&r((2n-1)(r-1)-b_{n-1})a_{n-1}x^{b_{n-1}+d-2} \end{eqnarray*}$$

となるので、

$$\begin{eqnarray*} a_n&=&r((2n-1)(r-1)-b_{n-1})a_{n-1} \\ b_n&=&b_{n-1}+r-2 \end{eqnarray*}$$

を得る。これを解けば

$$a_n = \prod_{k=1}^{n}r((k+1)r-1)$$ (3.58)

$$b_n = n(r-2)$$ (3.59)

となるので、積分型の$F_{n+1}(x)$は

$$\begin{eqnarray*} F_{n+1}(x)&=&\alpha+\int_{\alpha}^{x}\frac{(x^r-c)^n}{n!}\cdot... ...{a_n}{r^{2n}n!}\int_{\alpha}^{x}\left(1-\frac{c}{x^r}\right)^ndx \end{eqnarray*}$$

となることが分かる。