Aitkenの加速法(Aitken's delta-squared process)とは、数列 $s_n$ の連続する 3 項から $t_n=s_n-\frac{(\Delta s_n)^2}{\Delta^2s_n}$ を作り、同じ極限により速く近づく数列を得る方法のことである。誤差が等比数列 $c\lambda^n$($c\ne0$、$\lambda\ne0,1$)なら $t_n$ は極限に等しく、誤差の比 $e_{n+1}/e_n$ が $1$ 以外の値に収束するなら $t_n$ の誤差と $s_n$ の誤差の比は $0$ に収束する。比が $1$ に近づく数列では加速されるとは限らない。不動点反復に組み込んだ Steffensen の方法は、$g$ が $C^2$ 級で $g'(x^*)\ne1$ なら不動点の近くから 2 次収束し、変換は Shanks 変換の最初の段にあたる。
前提知識: 等比数列, 非線形方程式の数値解法, Taylorの定理
Aitkenの加速法(Aitken's delta-squared process)は、数列 $s_0,s_1,s_2,\dots$ の連続する 3 項から
$$
t_n=s_n-\frac{(s_{n+1}-s_n)^2}{s_{n+2}-2s_{n+1}+s_n}
$$
を作り、もとの数列より速く同じ極限に近づく数列 $t_n$ を得る方法である。Aitken の $\Delta^2$ 法 ともいう。誤差がほぼ等比数列のように減る数列(非線形方程式の数値解法 の不動点反復や、交代級数の部分和)に効く。
考え方は単純である。誤差 $s_n-\sigma$ がちょうど $c\lambda^n$ なら、3 つの式 $s_{n+k}=\sigma+c\lambda^{n+k}$($k=0,1,2$)から未知数 $\sigma,c,\lambda$ を消去でき、その答えが $t_n$ である。誤差が等比数列に近いだけなら $t_n$ は $\sigma$ に一致しないが、誤差の比が $1$ 以外の値に収束していれば、$t_n$ の誤差と $s_n$ の誤差の比は $0$ に収束する(thm-ait-main)。
この記事では、加速の定理(thm-ait-main)、$t_n$ がちょうど極限になる数列の決定(thm-ait-kernel)、誤差が 2 つの等比数列の和のときの誤差の式(prop-ait-two)、不動点反復に組み込んだ Steffensen の方法の 2 次収束(thm-ait-steffensen)、Shanks 変換・$\varepsilon$ 算法との関係(prop-ait-epsilon)を証明する。補間の Aitken の算法(Neville–Aitken の算法)は別のもので、この記事では扱わない。
数列は実数列とする。前進差分を $\Delta s_n:=s_{n+1}-s_n$、$\Delta^2s_n:=\Delta s_{n+1}-\Delta s_n=s_{n+2}-2s_{n+1}+s_n$ で定める。
数列 $(s_n)$ について、$\Delta^2s_n\ne0$ となる $n$ で
$$
t_n:=s_n-\frac{(\Delta s_n)^2}{\Delta^2s_n}
$$
と定める。数列 $(s_n)$ から $(t_n)$ を作ることを Aitken の加速法(Aitken の $\Delta^2$ 法)という。$(t_n)$ にもう一度この変換を施すことを繰り返すものを、反復 Aitken 法 という。
$s_0,\dots,s_m$ から $t_0,\dots,t_{m-2}$ が作れる。
$(s_n)$ が $\sigma$ に収束し、$e_n:=s_n-\sigma$ がある $n$ から先で $0$ にならず、
$$
\rho_n:=\frac{e_{n+1}}{e_n}\to\rho\qquad(n\to\infty)
$$
となるとき、$\rho$ を 誤差の比の極限 という。$0< \lvert\rho\rvert<1$ のとき $(s_n)$ は 一次収束する(linearly convergent)という。$\rho=1$ のときは収束が等比数列より遅く、対数的に収束する ということがある。
$(s_n)$ が収束するので $\lvert\rho\rvert\le1$ である($\lvert\rho\rvert>1$ なら $\lvert e_n\rvert$ はある番号から先で増えていく)。$\rho=-1$ の場合も含めて、$\rho\ne1$ でありさえすれば加速の定理が使える。
使える条件は次のとおりである。
| 量 | 式・値 | 条件 | 根拠 |
|---|---|---|---|
| Aitken の変換 | $t_n=s_n-\dfrac{(\Delta s_n)^2}{\Delta^2s_n}=\dfrac{s_ns_{n+2}-s_{n+1}^2}{\Delta^2s_n}$ | $\Delta^2s_n\ne0$ | lem-ait-forms |
| 誤差 | $t_n-\sigma=\dfrac{e_ne_{n+2}-e_{n+1}^2}{\Delta^2s_n}=e_n\dfrac{\rho_n\rho_{n+1}-\rho_n^2}{\rho_n\rho_{n+1}-2\rho_n+1}$ | $e_n,e_{n+1}\ne0$ | lem-ait-forms |
| 加速 | $(t_n-\sigma)/e_n\to0$ | $\rho_n\to\rho\ne1$ | thm-ait-main |
| 厳密になる数列 | $t_n=\sigma$(すべての $n$) $\iff$ $s_n=\sigma+c\lambda^n$ | $c\ne0$、$\lambda\ne0,1$ | thm-ait-kernel |
| 2 項の誤差 | $t_n-\sigma=\dfrac{ab(\lambda-\mu)^2\lambda^n\mu^n}{a(1-\lambda)^2\lambda^n+b(1-\mu)^2\mu^n}$ | $e_n=a\lambda^n+b\mu^n$ | prop-ait-two |
| Steffensen の方法 | $x_{k+1}=x_k-\dfrac{(g(x_k)-x_k)^2}{g(g(x_k))-2g(x_k)+x_k}$、$\lvert e_{k+1}\rvert\le C e_k^2$ | $g\in C^2$、$g'(x^*)\ne1$ | thm-ait-steffensen |
| $\varepsilon$ 算法 | $\varepsilon_2^{(n)}=t_n$ | $\Delta s_n,\Delta s_{n+1},\Delta^2s_n\ne0$ | prop-ait-epsilon |
$\Delta^2s_n\ne0$ とし、$\sigma$ を任意の数、$e_k:=s_k-\sigma$ とする。
1. $D:=\Delta^2s_n=s_{n+2}-2s_{n+1}+s_n$ とおく。$s_nD-(s_{n+1}-s_n)^2=s_ns_{n+2}-2s_ns_{n+1}+s_n^2-s_{n+1}^2+2s_ns_{n+1}-s_n^2=s_ns_{n+2}-s_{n+1}^2$ である。同様に $s_{n+2}D-(s_{n+2}-s_{n+1})^2=s_{n+2}^2-2s_{n+1}s_{n+2}+s_ns_{n+2}-s_{n+2}^2+2s_{n+1}s_{n+2}-s_{n+1}^2=s_ns_{n+2}-s_{n+1}^2$ である。
2. $s_k=\sigma+e_k$ を代入すると $\Delta s_k=\Delta e_k$、$\Delta^2s_n=\Delta^2e_n$ なので、1 を数列 $(e_k)$ に当てはめて $t_n-\sigma=e_n-\frac{(\Delta e_n)^2}{\Delta^2e_n}=\frac{e_ne_{n+2}-e_{n+1}^2}{\Delta^2s_n}$ である。
3. $e_{n+1}=\rho_ne_n$、$e_{n+2}=\rho_n\rho_{n+1}e_n$ である。よって $\Delta s_n=e_{n+1}-e_n=e_n(\rho_n-1)$、$\Delta^2s_n=e_n(\rho_n\rho_{n+1}-2\rho_n+1)$、$e_ne_{n+2}-e_{n+1}^2=e_n^2(\rho_n\rho_{n+1}-\rho_n^2)$ で、2 に代入すればよい。$\square$
$(s_n)$ は $\sigma$ に収束し、ある $N_0$ から先で $e_n=s_n-\sigma\ne0$、かつ $\rho_n=e_{n+1}/e_n\to\rho$ で $\rho\ne1$ とする。このとき、ある $N$ から先で $\Delta^2s_n\ne0$ であり、
$$
\lim_{n\to\infty}\frac{t_n-\sigma}{s_n-\sigma}=0
$$
である。特に $t_n\to\sigma$ である。
$n\ge N_0$ では lem-ait-forms の 3 が使える。分母の因子 $\rho_n\rho_{n+1}-2\rho_n+1$ は $n\to\infty$ で $\rho^2-2\rho+1=(\rho-1)^2$ に収束し、$\rho\ne1$ だからこれは $0$ でない。よってある $N\ge N_0$ から先でこの因子は $0$ でなく、$e_n\ne0$ と合わせて $\Delta^2s_n=e_n(\rho_n\rho_{n+1}-2\rho_n+1)\ne0$ である。$n\ge N$ で
$$
\frac{t_n-\sigma}{e_n}=\frac{\rho_n\rho_{n+1}-\rho_n^2}{\rho_n\rho_{n+1}-2\rho_n+1}
$$
で、分子は $\rho^2-\rho^2=0$ に、分母は $(\rho-1)^2\ne0$ に収束するから、比は $0$ に収束する。$e_n\to0$ なので $t_n-\sigma=e_n\cdot\frac{t_n-\sigma}{e_n}\to0$ である。$\square$
$\lvert\rho\rvert<1$ の場合の主張は DLMF §3.9(iii) の式 (3.9.7)・(3.9.8) にある。上の証明は $\rho=-1$ でも通る(ex-ait-leibniz)。定理は誤差の比の極限だけを述べ、有限の $n$ での大きさは述べない。誤差の形が分かれば減り方も分かる(prop-ait-two)。
すべての $n\ge0$ で $\Delta^2s_n\ne0$ とし、$\sigma$ を数とする。すべての $n$ で $t_n=\sigma$ となるのは、$c\ne0$、$\lambda\ne0,1$ があって $s_n=\sigma+c\lambda^n$($n\ge0$)となるとき、かつそのときに限る。
$e_n:=s_n-\sigma$ とおく。
($\Leftarrow$)$e_n=c\lambda^n$ なら $e_ne_{n+2}-e_{n+1}^2=c^2\lambda^{2n+2}-c^2\lambda^{2n+2}=0$ で、lem-ait-forms の 2 から $t_n=\sigma$ である。このとき $\Delta^2s_n=c\lambda^n(\lambda-1)^2\ne0$ であることも分かる。
($\Rightarrow$)lem-ait-forms の 2 から、すべての $n$ で $e_ne_{n+2}=e_{n+1}^2$ である。ある $n$ で $e_n=0$ なら、$e_{n+1}^2=0$ から $e_{n+1}=0$、$n+1$ での式 $e_{n+1}e_{n+3}=e_{n+2}^2$ から $e_{n+2}=0$ となり、$\Delta^2s_n=e_{n+2}-2e_{n+1}+e_n=0$ に反する。よってすべての $e_n\ne0$ で、$e_{n+2}/e_{n+1}=e_{n+1}/e_n$ が成り立つ。比は $n$ によらない定数 $\lambda:=e_1/e_0\ne0$ で、$e_n=e_0\lambda^n$ である。$c:=e_0\ne0$ とおく。$\lambda=1$ なら $\Delta^2s_0=c(\lambda-1)^2=0$ となるので $\lambda\ne1$ である。$\square$
$\lvert\lambda\rvert\ge1$ のとき $s_n$ は発散するが、それでも $t_n=\sigma$ である。たとえば $s_n=\sum_{k=0}^n2^k=2^{n+1}-1=-1+2\cdot2^n$ では、すべての $n$ で $t_n=-1=\frac1{1-2}$ となる。$\sigma$ は等比級数の和の公式を形式的に当てはめた値である。
$s_n=\sigma+a\lambda^n+b\mu^n$($a,b\ne0$、$\lambda\ne\mu$)とする。$\Delta^2s_n\ne0$ となる $n$ で
$$
t_n-\sigma=\frac{ab(\lambda-\mu)^2\lambda^n\mu^n}{a(1-\lambda)^2\lambda^n+b(1-\mu)^2\mu^n}
$$
である。特に $0< \lvert\mu\rvert< \lvert\lambda\rvert$、$\lambda\ne1$ なら、$n\to\infty$ で $t_n-\sigma=\dfrac{b(\lambda-\mu)^2}{(1-\lambda)^2}\mu^n\bigl(1+o(1)\bigr)$ である。
$e_n=a\lambda^n+b\mu^n$ について
$$
e_ne_{n+2}-e_{n+1}^2=ab\lambda^n\mu^n(\mu^2+\lambda^2)-2ab\lambda^{n+1}\mu^{n+1}=ab(\lambda-\mu)^2\lambda^n\mu^n
$$
($a^2\lambda^{2n+2}$ と $b^2\mu^{2n+2}$ の項は打ち消し合う)、$\Delta^2s_n=a\lambda^n(\lambda-1)^2+b\mu^n(\mu-1)^2$ である。lem-ait-forms の 2 に代入すれば式を得る。後半は、分母を $a(1-\lambda)^2\lambda^n$ で割ると $1+\frac{b(1-\mu)^2}{a(1-\lambda)^2}(\mu/\lambda)^n\to1$ となることから従う。$\square$
$s_n$ の誤差は $a\lambda^n$ の速さで減るが、$t_n$ の誤差は $\mu^n$ の速さで減る。いちばん遅い等比の成分が取り除かれ、次の成分が残る。反復 Aitken 法は、これを繰り返して次々に成分を取り除こうとするものである。
不動点反復 $x_{k+1}=g(x_k)$ の 3 項 $x_k,g(x_k),g(g(x_k))$ に Aitken の変換を施し、その値から反復をやり直すのが Steffensen の方法である。
$g$ を区間上の関数とし、$x^*$ を不動点とする。
$$
\Phi(x):=x-\frac{(g(x)-x)^2}{g(g(x))-2g(x)+x}
$$
(分母が $0$ でない $x$ で)とし、$\Phi(x^*):=x^*$ と定める。$x_{k+1}=\Phi(x_k)$ による反復を Steffensen の方法 という。
1 回の反復で $g$ を 2 回評価し、導関数は使わない。$\Phi(x_k)$ は、3 項 $x_k,g(x_k),g(g(x_k))$ の数列に def-ait-process の $t_0$ を当てはめたものである。
$\eta>0$ とし、$g$ は $J_0:=[x^*-\eta,x^*+\eta]$ で $C^2$ 級、$g(x^*)=x^*$、$\lambda:=g'(x^*)\ne1$ とする。このとき $\delta\in(0,\eta]$ と $C>0$ があって、$\lvert x-x^*\rvert\le\delta$ なら $\Phi(x)$ が定義され
$$
\lvert\Phi(x)-x^*\rvert\le C\lvert x-x^*\rvert^2
$$
である。さらに $C\delta\le\frac12$ となるように $\delta$ をとり直せば、$\lvert x_0-x^*\rvert\le\delta$ からの反復 $x_{k+1}=\Phi(x_k)$ は $x^*$ に収束し、$\lvert x_{k+1}-x^*\rvert\le C\lvert x_k-x^*\rvert^2$ を満たす。
$K:=\frac12\max_{J_0}\lvert g''\rvert$、$A:=\lvert\lambda\rvert+K\eta$ とおく。Taylorの定理 により、$\lvert h\rvert\le\eta$ なら
$$
g(x^*+h)=x^*+\lambda h+r(h),\qquad\lvert r(h)\rvert\le Kh^2
$$
である。$\delta\in(0,\eta]$ を、$A\delta\le\eta$ かつ $K(\lvert\lambda-2\rvert+A^2)\delta\le\frac12(\lambda-1)^2$ となるようにとる($\lambda\ne1$ より右辺は正)。
$x=x^*+e$、$0< \lvert e\rvert\le\delta$ とする。$u:=g(x)-x^*=\lambda e+r_1$($r_1:=r(e)$)について $\lvert u\rvert\le(\lvert\lambda\rvert+K\lvert e\rvert)\lvert e\rvert\le A\lvert e\rvert\le\eta$ なので、$g(g(x))=x^*+\lambda u+r_2$($r_2:=r(u)$、$\lvert r_2\rvert\le Ku^2\le KA^2e^2$)である。$N:=(g(x)-x)^2$、$D:=g(g(x))-2g(x)+x$ とおくと
$$
N=\bigl((\lambda-1)e+r_1\bigr)^2,\qquad D=(\lambda-2)u+e+r_2=(\lambda-1)^2e+(\lambda-2)r_1+r_2
$$
である。展開すると
$$
eD-N=-\lambda er_1+er_2-r_1^2
$$
で、$(\lambda-1)^2e^2$ の項と $e r_1$ の項の一部が打ち消し合う。よって
$$
\lvert eD-N\rvert\le\bigl(\lvert\lambda\rvert K+KA^2+K^2\eta\bigr)\lvert e\rvert^3
$$
である($r_1^2\le K^2e^4\le K^2\eta\lvert e\rvert^3$ を使った)。一方 $\lvert(\lambda-2)r_1+r_2\rvert\le K(\lvert\lambda-2\rvert+A^2)e^2\le\frac12(\lambda-1)^2\lvert e\rvert$ なので $\lvert D\rvert\ge\frac12(\lambda-1)^2\lvert e\rvert>0$ である。したがって $\Phi(x)$ は定義され、
$$
\lvert\Phi(x)-x^*\rvert=\left\lvert e-\frac ND\right\rvert=\frac{\lvert eD-N\rvert}{\lvert D\rvert}\le C e^2,\qquad C:=\frac{2(\lvert\lambda\rvert K+KA^2+K^2\eta)}{(\lambda-1)^2}
$$
である。$e=0$ では両辺が $0$ である。
$C\delta\le\frac12$ なら、$\lvert x_k-x^*\rvert\le\delta$ のとき $\lvert x_{k+1}-x^*\rvert\le C\delta\lvert x_k-x^*\rvert\le\frac12\lvert x_k-x^*\rvert\le\delta$ である。帰納法ですべての $x_k$ が $[x^*-\delta,x^*+\delta]$ にあり、$\lvert x_k-x^*\rvert\le2^{-k}\delta\to0$ である。$\square$
不動点反復そのものは $\lvert\lambda\rvert>1$ では($x_k$ がちょうど $x^*$ に当たる場合を除き)収束しないが(非線形方程式の数値解法 の命題「不動点での傾きによる判定」)、Steffensen の方法は $\lvert\lambda\rvert>1$ でも $\lambda\ne1$ なら近くから 2 次収束する。
$\varepsilon_{-1}^{(n)}:=0$、$\varepsilon_0^{(n)}:=s_n$、
$$
\varepsilon_{m+1}^{(n)}:=\varepsilon_{m-1}^{(n+1)}+\frac1{\varepsilon_m^{(n+1)}-\varepsilon_m^{(n)}}
$$
と定める(Wynn の $\varepsilon$ 算法)。$\Delta s_n,\Delta s_{n+1},\Delta^2s_n$ がどれも $0$ でなければ、$\varepsilon_2^{(n)}$ が定義されて $\varepsilon_2^{(n)}=t_n$ である。また、Hankel 行列式 $H_2(s_n):=\begin{vmatrix}s_n&s_{n+1}\\ s_{n+1}&s_{n+2}\end{vmatrix}$ について $t_n=H_2(s_n)/\Delta^2s_n$ である。
$\varepsilon_1^{(n)}=0+\frac1{s_{n+1}-s_n}=\frac1{\Delta s_n}$ である。$\frac1{\Delta s_{n+1}}-\frac1{\Delta s_n}=-\frac{\Delta^2s_n}{\Delta s_n\Delta s_{n+1}}\ne0$ なので
$$
\varepsilon_2^{(n)}=s_{n+1}-\frac{\Delta s_n\Delta s_{n+1}}{\Delta^2s_n}
$$
である。これから $t_n$ を引くと $\Delta s_n-\frac{\Delta s_n\Delta s_{n+1}-(\Delta s_n)^2}{\Delta^2s_n}=\Delta s_n-\frac{\Delta s_n\Delta^2s_n}{\Delta^2s_n}=0$ である。後半は $H_2(s_n)=s_ns_{n+2}-s_{n+1}^2$ と lem-ait-forms の 1 による。$\square$
一般の $k$ では、$t_{n,2k}:=H_{k+1}(s_n)/H_k(\Delta^2s_n)$($H_m$ は $m$ 次の Hankel 行列式)を Shanks 変換 といい、$t_{n,2k}=\varepsilon_{2k}^{(n)}$ が成り立つ。Aitken の加速法は $k=1$ の場合である。$s_n$ が冪級数の部分和なら、$t_{n,2k}$ は Padé近似 の $[(n+k)/k]$ 型の値に一致する(いずれも DLMF §3.9(iv)、式 (3.9.9)–(3.9.11)。この記事では $k=1$ の場合だけを証明した)。
数列 $s_0,\dots,s_m$ を加速する手順は次のとおりである。
$s_n:=\sum_{k=0}^n\frac{(-1)^k}{2k+1}$ は $\sigma=\frac\pi4$ に収束するが、誤差はおよそ $\frac1{4n}$ で、非常に遅い(交代級数)。誤差の比が $-1$ に収束することを示し、$s_0,\dots,s_8$ を加速する。
答え:$e_n=s_n-\frac\pi4=(-1)^nr_n$、$r_n:=\int_0^1\frac{x^{2n+2}}{1+x^2}dx>0$ と書け、$0\le1-\frac{r_{n+1}}{r_n}\le\frac4{2n+5}$ なので、$\rho_n=e_{n+1}/e_n=-r_{n+1}/r_n\to-1$ である。
$\frac1{2k+1}=\int_0^1x^{2k}dx$ と、$0\le x< 1$ での $\sum_{k\ge n+1}(-1)^kx^{2k}=\frac{(-1)^{n+1}x^{2n+2}}{1+x^2}$(部分和の絶対値は $1$ 以下なので、項別積分してよい)から $\frac\pi4-s_n=(-1)^{n+1}r_n$ である。$r_n+r_{n+1}=\int_0^1x^{2n+2}dx=\frac1{2n+3}$ で、$0\le r_n-r_{n+1}=\int_0^1x^{2n+2}\frac{1-x^2}{1+x^2}dx\le\int_0^1x^{2n+2}(1-x^2)dx=\frac2{(2n+3)(2n+5)}$ である。$r_{n+1}\le r_n$ から $2r_n\ge\frac1{2n+3}$ なので、$1-\frac{r_{n+1}}{r_n}\le\frac2{(2n+3)(2n+5)}\cdot2(2n+3)=\frac4{2n+5}$ である。
| 値 | $s_8$ | $t_6$(1 回) | 2 回 | 3 回 | 4 回 |
|---|---|---|---|---|---|
| 誤差 | $2.77\times10^{-2}$ | $1.20\times10^{-4}$ | $2.55\times10^{-6}$ | $1.44\times10^{-7}$ | $1.51\times10^{-8}$ |
「$m$ 回」は反復 Aitken 法で $m$ 回変換したあとの、最後の項の誤差である。同じ 9 項を使う $s_8$ と比べて、1 回の変換で誤差は約 $230$ 分の $1$ になる。反復した場合の改善は thm-ait-main の範囲外で、この表の数値が示すだけである。
$x_{n+1}=\cos x_n$、$x_0=1$ とする。不動点は $x^*\approx0.7390851332$ である。
答え:$x_n\ne x^*$ で $\rho_n\to-\sin x^*\approx-0.6736$ なので、thm-ait-main が使える。
$\cos$ は $[0,1]$ を $[\cos1,1]\subset[0,1]$ に写し、そこで $\lvert\cos'\rvert\le\sin1< 1$ なので、非線形方程式の数値解法 の定理「不動点反復の収束」により $x_n\to x^*$ である。$\cos$ は $[0,1]$ で単射なので、$x_0\ne x^*$ からすべての $x_n\ne x^*$ である。平均値の定理 で $e_{n+1}=-\sin(\xi_n)e_n$($\xi_n$ は $x_n$ と $x^*$ の間)だから、$\rho_n\to-\sin x^*$ である。
| $n=2$ | $n=4$ | $n=6$ | $n=8$ | |
|---|---|---|---|---|
| $x_n$ の誤差 | $1.18\times10^{-1}$ | $5.44\times10^{-2}$ | $2.49\times10^{-2}$ | $1.13\times10^{-2}$ |
| $t_{n-2}$ の誤差 | — | $-2.18\times10^{-3}$ | $-4.49\times10^{-4}$ | $-9.29\times10^{-5}$ |
$t_{n-2}$ は $x_{n-2},x_{n-1},x_n$ から作るので、同じ列は同じ $\cos$ の評価の回数で比べている。Steffensen の方法($x_0=1$)の誤差は $k=1,2,3,4$ 回目で $-1.11\times10^{-2}$、$-1.82\times10^{-5}$、$-4.91\times10^{-11}$、$-3.58\times10^{-22}$ である。$k$ 回目までの $\cos$ の評価は $2k$ 回で、6 回の評価で誤差 $5\times10^{-11}$ に達する。$\lvert e_{k+1}\rvert/e_k^2$ は $0.1487$ 前後でほぼ一定で、thm-ait-steffensen の 2 次収束のとおりである。
$s_n=1+0.9^n+0.5^n$ に Aitken の変換を施す。
答え:prop-ait-two で $a=b=1$、$\lambda=0.9$、$\mu=0.5$ とすると、$t_n-1\approx\frac{(0.9-0.5)^2}{(1-0.9)^2}0.5^n=16\cdot0.5^n$ である。
| $n$ | $10$ | $20$ | $30$ |
|---|---|---|---|
| $s_n-1$ | $0.3497$ | $0.1216$ | $0.04239$ |
| $t_n-1$ | $1.46\times10^{-2}$ | $1.53\times10^{-5}$ | $1.49\times10^{-8}$ |
| $(t_n-1)/0.5^n$ | $14.95$ | $15.997$ | $16.000$ |
誤差の減る速さは $0.9^n$ から $0.5^n$ に変わるが、係数 $16$ は大きい。$\lambda$ が $1$ に近いほど係数 $\frac{(\lambda-\mu)^2}{(1-\lambda)^2}$ は大きくなる。
倍精度の浮動小数点数で、ex-ait-cos の $x_{40},x_{41},x_{42}$ から $t_{40}$ を 2 つの形で計算する。
答え:このとき $\Delta^2x_{40}\approx1.0\times10^{-7}$ である。定義の形 $s_n-(\Delta s_n)^2/\Delta^2s_n$ の誤差は丸めの単位の程度(約 $10^{-16}$)だが、$(s_ns_{n+2}-s_{n+1}^2)/\Delta^2s_n$ の誤差は約 $10^{-10}$ である。
後者は、ほぼ等しい 2 数 $s_ns_{n+2}$ と $s_{n+1}^2$ の差を小さい $\Delta^2s_n$ で割るので、桁落ちが拡大される。前者では、小さい補正 $(\Delta s_n)^2/\Delta^2s_n$ を $s_n$ に足すので、補正の相対誤差が大きくても全体への影響は小さい。
各行は 1 つの仮定だけを外す。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $\rho\ne1$(thm-ait-main) | $s_n=\frac1{n+1}$、$\sigma=0$、$\rho_n=\frac{n+1}{n+2}\to1$ | $(t_n-\sigma)/e_n\to0$:比は $\frac12$ に収束する |
| 比 $\rho_n$ が収束する(thm-ait-main) | $s_n=\frac{2+(-1)^n}{2^n}$、$\sigma=0$ | $(t_n-\sigma)/e_n\to0$:比は $\frac8{33}$ と $\frac87$ を交互にとる |
| $g'(x^*)\ne1$(thm-ait-steffensen) | $g(x)=x-x^3$、$x^*=0$ | 2 次収束 $\lvert e_{k+1}\rvert\le Ce_k^2$:$e_{k+1}/e_k\to\frac23$ |
表の 3 行の反例で、それぞれの結論が実際に成り立たないことを確かめる。
1 行目:$e_n=\frac1{n+1}\ne0$、$\Delta s_n=-\frac1{(n+1)(n+2)}$、$\Delta^2s_n=\frac2{(n+1)(n+2)(n+3)}\ne0$ なので $t_n=\frac1{n+1}-\frac{(n+1)(n+2)(n+3)}{2(n+1)^2(n+2)^2}=\frac{2(n+2)-(n+3)}{2(n+1)(n+2)}=\frac1{2(n+2)}$ で、$\frac{t_n-0}{e_n}=\frac{n+1}{2(n+2)}\to\frac12\ne0$ である。
2 行目:$e_n\ne0$ で、$\rho_n$ は $n$ が偶数なら $\frac16$、奇数なら $\frac32$ で、どちらも $1$ でない。$n$ が偶数で $c:=2^{-n}$ とすると $s_n,s_{n+1},s_{n+2}=3c,\frac c2,\frac{3c}4$ で、lem-ait-forms の 1 から $t_n=\frac{\frac94c^2-\frac14c^2}{3c-c+\frac34c}=\frac{8c}{11}$、$t_n/e_n=\frac8{33}$ である。$n$ が奇数なら $s_n,s_{n+1},s_{n+2}=c,\frac{3c}2,\frac c4$ で $t_n=\frac{\frac14c^2-\frac94c^2}{c-3c+\frac14c}=\frac{8c}7$、$t_n/e_n=\frac87$ である。比は $0$ に収束しない。
3 行目:$g$ は多項式で $C^2$ 級、$g(0)=0$、$g'(0)=1$ である。$g(x)-x=-x^3$、$g(g(x))-2g(x)+x=x^3-(x-x^3)^3=x^5(3-3x^2+x^4)$ なので $\Phi(x)=x-\frac{x^6}{x^5(3-3x^2+x^4)}=\frac{x(1-x^2)(2-x^2)}{3-3x^2+x^4}$ で、$\Phi(x)/x\to\frac23$ である。よって $\delta\in(0,1)$ があって、$0< \lvert x\rvert\le\delta$ なら $0< \Phi(x)/x\le\frac34$ である。$0< \lvert x_0\rvert\le\delta$ から始めると、帰納法で $0< \lvert x_k\rvert\le(\frac34)^k\delta$ となって $x_k\to0$ で、$e_{k+1}/e_k=\Phi(x_k)/x_k\to\frac23$ である。$\lvert e_{k+1}\rvert\le Ce_k^2$ なら $\lvert e_{k+1}/e_k\rvert\le C\lvert e_k\rvert\to0$ となるはずなので、2 次収束しない。
| 誤り | 正しくは | なぜ |
|---|---|---|
| どんな収束列でも速くなる | 誤差の比が $1$ 以外に収束するときに速くなる。比が $1$ に近づく遅い列には効かないことがある | thm-ait-main、反例の表の 1 行目 |
| $(s_ns_{n+2}-s_{n+1}^2)/\Delta^2s_n$ の形で計算する | 定義の形 $s_n-(\Delta s_n)^2/\Delta^2s_n$ で計算する | ex-ait-rounding |
| 加速した値は誤差が小さいと保証される | 保証されるのは $n\to\infty$ での比 $(t_n-\sigma)/e_n\to0$ だけ。有限の $n$ での大きさは言わない | ex-ait-two の係数 $16$ |
| 反復 Aitken 法も同じ定理で正当化される | thm-ait-main は 1 回の変換について。$(t_n)$ の誤差の比が収束するかは別に確かめる | ex-ait-leibniz |
| Steffensen の方法は重根でも 2 次収束する | $g'(x^*)=1$ では 2 次収束しない | 反例の表の 3 行目 |
数値積分 の Romberg 積分は、誤差の展開の冪($h^2,h^4,\dots$)が前もって分かっているときに、それを消すように組み合わせる。Aitken の加速法は、誤差の比 $\lambda$ を前もって知らなくてよく、連続する 3 項に $\sigma+c\lambda^n$ の形の数列を当てはめて $\lambda$ と $\sigma$ を同時に求める点が異なる(thm-ait-kernel)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する