Apéryの加速法5：Apéryの加速法

はじめに

　この記事では 前回の記事 に引き続きApéryの加速法について解説していきます。
　さて 前回の記事 では多項式係数の連分数
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc\qquad \l(\begin{array}{ll} \deg a_n\leq d\\ \deg b_n=2d \end{array}\r)$$
に対し、多項式$r_n$によるBauer-Muir変換
$$x=a_0+r_0-\frac{d_0}{a_1+r_1}\p \K^\infty_{n=2}\frac{b_{n-1}d_{n-1}/d_{n-2}}{a_n+r_n-r_{n-2}d_{n-1}/d_{n-2}}$$
の収束速度が
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
の次数$d'$に応じて$O(1/n^{2d-d'})$あるいは$O(1/n^{2d-d'-2})$だけ速くなる、ということについて解説しました。
　そして今回の記事ではこのような加速を無数に繰り返すことで指数関数的な加速を構成する手法ことApéryの加速法について解説していきます。

反復Bauer-Muir変換

　まずはBauer-Muir変換の反復法について考えていきましょう。

概要

　やることとしては単純で多項式係数の連分数
$$\frac{p_n}{q_n}=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc\p\frac{b_n}{a_n}$$
に対し
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
の次数を十分小さくするような多項式$r_n$を取り
\begin{align} \frac{p'_n}{q'_n} &=\frac{p_n+r_np_{n-1}}{q_n+r_nq_{n-1}}\\ &=a'_0+\frac{b'_1}{a'_1}\p\frac{b'_2}{a'_2}\p\cc\p\frac{b'_n}{a'_n} \end{align}
とおき、これに対しまた
$$d'_n=r'_n(a'_{n+1}+r'_{n+1})-b'_{n+1}$$
の次数を十分小さくするような多項式$r'_n$を取り
\begin{align} \frac{p''_n}{q''_n} &=\frac{p'_n+r'_np'_{n-1}}{q'_n+r'_nq'_{n-1}}\\ &=a''_0+\frac{b''_1}{a''_1}\p\frac{b''_2}{a''_2}\p\cc\p\frac{b''_n}{a''_n} \end{align}
とおき...、といった具合に
\begin{align} \frac{p^{(k)}_n}{q^{(k)}_n} &=\frac{p^{(k-1)}_n+r^{(k-1)}_np^{(k-1)}_{n-1}}{q^{(k-1)}_n+r^{(k-1)}_nq^{(k-1)}_{n-1}}\\ &=a^{(k)}_0+\frac{b^{(k)}_1}{a^{(k)}_1}\p\frac{b^{(k)}_2}{a^{(k)}_2}\p\cc\p\frac{b^{(k)}_n}{a^{(k)}_n}\\ d^{(k)}_n&=r^{(k)}_n(a^{(k)}_{n+1}+r^{(k)}_{n+1})-b^{(k)}_{n+1} \end{align}
という数列の組
$$p^{(k)}_n,q^{(k)}_n,a^{(k)}_n,b^{(k)}_n,r^{(k)}_n,d^{(k)}_n$$
を構成していく、というだけではあります。

問題点

　しかし上のような構成だと、Bauer-Muirの変換公式から$n\geq2$において
\begin{align} a^{(k+1)}_n&=a^{(k)}_n+r^{(k)}_n-r^{(k)}_{n-2}\frac{d^{(k)}_{n-1}}{d^{(k)}_{n-2}}\\ b^{(k+1)}_n&=b^{(k)}_{n-1}\frac{d^{(k)}_{n-1}}{d^{(k)}_{n-2}} \end{align}
が成り立つことに注意すると、例えば$d^{(k)}_n$が常に$n$に依らない定数となるとき
$$b^{(k)}_n=b^{(0)}_{n-k}\qquad(n>k)$$
のように$b^{(k)}_n$の値がズレていったり、また$d^{(k)}_n$が$n$についての定数でない多項式となるとき$a^{(k+1)}_n,b^{(k+1)}_n$が多項式とならないことがあったり、という不都合が生じるため$p^{(k)}_n,q^{(k)}_n$の取り方には一工夫加える必要あります。

反復Bauer-Muir変換

　具体的には$p^{(k)}_n,q^{(k)}_n$の取り方を少しズラしたり適当な因子を掛けたりすることで次のように構成される数列について今後は考察していきます。

　このとき Bauer-Muirの変換公式 から$p^{(k)}_n,q^{(k)}_n$は次の漸化式を満たすことがわかるのでした。

連分数表示

　特に ベルヌーイの公式 や Bauer-Muirの変換公式 に注意すると、$q^{(k)}_0\neq0$が成り立つような$k$に対し$p^{(k)}_n/q^{(k)}_n$および$p^{(k+1)}_n/q^{(k+1)}_n$は次のように連分数展開できることがわかります。

　なお一般に$q^{(k)}_m\neq0$なる$m$に対し
$$\frac{p^{(k)}_n}{q^{(k)}_n} =\frac{p^{(k)}_m}{q^{(k)}_m}+\frac{(p^{(k)}_{m+1}q^{(k)}_m-p^{(k)}_mq^{(k)}_{m+1})/(q^{(k)}_m)^2}{q^{(k)}_{m+1}/q^{(k)}_m}\p\frac{b^{(k)}_{m+2}}{a^{(k)}_{m+2}}\p\cc\p\frac{b^{(k)}_n}{a^{(k)}_n}$$
という連分数表示をすることはできます。

補足

$a^{(k)}_1$の多項式表示について

　ちなみに$a^{(k)}_n,b^{(k)}_n,r^{(k)}_n,d^{(k)}_n\quad(n\geq2)$を規定する多項式をそれぞれ$a_k(n),b_k(n),r_k(n),d_k(n)$とおいたとき、一般に$a^{(k)}_1=a_k(1)$が成り立つとは限りませんが、次のような状況においては$a^{(k)}_1=a_k(1)$となることがわかります。

　この事実は実際に連分数表示を求めるときに計算が非常に楽になるのでよく覚えておきましょう。
　またこれは超幾何級数由来の連分数
$$\sum^\infty_{n=1}A_n =\frac{g(1)A_1}{g(1)}\p\K^\infty_{n=2}\frac{-f(n)g(n-1)}{f(n)+g(n)}\qquad \l(\frac{A_n}{A_{n-1}}=\frac{f(n)}{g(n)}\r)$$
においては$f(1)=0$である場合に相当することに注意しましょう。
　さらに$g(0)=0$である場合は
\begin{align} \l(\sum^\infty_{n=0}A_n\r)^{-1} &=\l(\frac{A_0}1\m\frac{f(1)}{f(1)+g(1)}\p\K^\infty_{n=2}\frac{-f(n)g(n-1)}{f(n)+g(n)}\r)^{-1}\\ &=\frac1{A_0}\l(1-\frac{f(1)}{f(1)+g(1)}\p\K^\infty_{n=2}\frac{f(n)g(n-1)}{f(n)+g(n)}\r) \end{align}
という連分数を考えることで上手くいくことも覚えておきましょう。

$p^{(k)}_n/q^{(k)}_n$の級数表示について

　また連分数の性質から
$$\frac{p^{(k)}_n}{q^{(k)}_n}-\frac{p^{(k)}_{n-1}}{q^{(k)}_{n-1}} =\frac{(q^{(k)}_0)^2b^{(k)}_1}{q^{(k)}_nq^{(k)}_{n-1}}\prod^n_{j=2}(-b^{(k)}_j)$$
が成り立つので、上の$q^{(k)}_0,b^{(k)}_1$から次のような級数表示が得られることにも覚えておくといいかもしれません。

Apéryの加速法

　さて 初回の記事 でも紹介したようにApéryの加速法とは、反復Bauer-Muir変換によって得られた数列$p^{(k)}_n,q^{(k)}_n$に対し
$$P_n=p^{(n)}_n,\quad Q_n=q^{(n)}_n$$
とおくことで、これも多項式係数の連分数
$$\frac{P_n}{Q_n}=A_0+\frac{B_1}{A_1}\p\frac{B_2}{A_2}\p\cc\p\frac{B_n}{A_n}$$
を定め、さらに指数関数的な加速
$$x-\frac{P_n}{Q_n}\sim\frac1{C^n}\l(x-\frac{p^{(0)}_n}{q^{(0)}_n}\r)$$
が得られる、ということを主張するものでした。
　ということで以下ではこの主張の詳細について考察していきましょう。

収束性について

　まず$P_n/Q_n$の収束性について簡単に考察しておきましょう。
　いま$b^{(k)}_n,d^{(k)}_n$の次数が$k$に依らず一定であるとすると、 前回の記事 の結果からある整数$D$およびある$n$に依らない定数$c_k$が存在して
$$\l|x-\frac{p^{(k)}_n}{q^{(k)}_n}\r|\leq\frac{c_k}{n^{Dk}}\c\frac{(\b/\a)^n}{n^\nu}$$
のように評価できるので、$P_n/Q_n$についても
$$\l|x-\frac{P_n}{Q_n}\r|\leq\frac{c_n}{n^{Dn}}\c\frac{(\b/\a)^n}{n^\nu}$$
が成り立ち、これが$0$に収束するのは直感的に正しいと思えます(具体的に証明できるのかは不明)。
　特にこのことから$P_n/Q_n$によって$O(1/n^n)$程度の加速が得られそうに見えますが、この$c_k$が$k$に応じて意外と大きくなるのか、実際には指数関数$O(1/C^n)$程度の加速に収まるようです。
　ここら辺の説明がどのように正当化できるのかが個人的によくわかってないのであまり釈然としませんが、とりあえず$P_n/Q_n\to x$が成り立つことは認めるものとして話を進めていくこととしましょう。

補足

　なお、これは完全に経験則の話になりますが、$t^{(k)}_n$を規定する有理関数$t_k(x)$が$x\geq k$において不連続であるときには$P_n/Q_n\to x$が成立せず、逆に$t_k(x)$が$x\geq k$において連続であれば$P_n/Q_n\to x$が成り立つような印象があります(まだ計算例が全然揃っていないので普通に反例はあるかもしれません)。これも一体何なんでしょうね。

漸化式について

　次に$P_n,Q_n$が満たす漸化式について考えていきましょう。
　いま$P_n,Q_n$は$p^{(k)}_n,q^{(k)}_n$を次のように並べたときの対角線を渡るような数列として定めていたのでした。

　ただこのような経路において漸化式を直接考えるのはやや難しいので、代わりに各$p^{(k)}_n$に至るのに次のような経路を辿ることにしましょう。

　このとき次の漸化式が成り立ちます。

　つまり上の表を

という階段状に渡る数列
$$\wh P_{2n}=p^{(n)}_n,\quad\wh P_{2n+1}=p^{(n)}_{n+1}$$
を考えると、これは
\begin{alignat}{3} \wh P_{2n} &=T^{(n-1)}_nR^{(n-1)}_n\wh P_{2n-1}&&+T^{(n-1)}_nb^{(n-1)}_{n+1}\wh P_{2n-2}\\ \wh P_{2n+1} &=t^{(n-1)}_{n+1}R^{(n-1)}_{n+1}\wh P_{2n}&&-T^{(n-1)}_{n+1}d^{(n-1)}_{n+1}\wh P_{2n-1} \end{alignat}
という漸化式を満たすことがわかり、特にこの係数を少し調整することで次のような事実が得られます。

　そしてこのとき
$$\frac{\P_0}{\Q_0}=\frac{a^{(0)}_0}1,\quad \frac{\P_1-\P_0\Q_1}{\Q_1}=\frac{b^{(0)}_1}{a^{(0)}_1}$$
であることに注意すると以下の連分数表示が得られます。
　ただし連分数の偶数項と奇数項を明示的に表すため
$$\K^\infty_{n=1}\frac{b_n}{a_n} =\K^\infty_{n=1}\l(\frac{b_{2n-1}}{a_{2n-1}}\p\frac{b_{2n}}{a_{2n}}\r)$$
という記法を用いるものとします(この記法は一般的ではありません)。

　そしてこれに連分数の 縮約公式
$$\K^\infty_{n=1}\frac{b_n}{a_n} =\frac{b_1a_2}{b_2+a_1a_2} \p\K^\infty_{n=2}\frac{-b_{2n-2}b_{2n-1}a_{2n}/a_{2n-2}}{b_{2n}+a_{2n-1}a_{2n}+b_{2n-1}a_{2n}/a_{2n-2}}$$
を適用することで
$$P_n=\P_{2n},\quad Q_n=\Q_{2n}$$
の満たす漸化式と連分数表示は以下のように求まることがわかります。

　特に$a_n^{(k)},b_n^{(k)},r_n^{(k)},t^{(k)}_n$の一般項を求めることができていれば、特にそれらが$n,k$についての有理関数として表せていれば、これは有理関数係数の連分数を定めることとなります。
　そしてそのとき Birkhoff-Adamsの定理 などによって$x-P_n/Q_n$の収束速度を求めてみると、実際に指数関数的な加速が生じていることが観測される、というのがApéryの加速法の一連の流れとなります。

おまけ：下側の階段について

　ちなみに上では$\P_n,\Q_n$を対角線の上側を通る階段に沿って$p^{(k)}_n,q^{(k)}_n$を渡る数列として取っていましたが、対角線の下側を通る階段

に沿った数列を考えることで次のような連分数も得られます。
　なお実用上は上階段の方が若干汎用性は高いですが、下階段を用いた方が綺麗な表示が得られることもあるので場合に応じて上手く使い分けるようにしましょう。

　またこれに縮約公式を用いることで$P_n,Q_n$に関する漸化式が次のような形に求まります。

　なおこの公式は公式2と全く同じ連分数を与えるのでお好みの方をお使いください。

Apéry双対

　以上がApéryの加速法の全容となりますが、最後に一つApéryの加速法に関する興味深い現象であるApéry双対というものについて紹介しておきましょう。

　例えば定理2系から常に$q^{(k)}_0\neq0$が成り立つとき
$$\frac{\pp^{(0)}_k}{\qq^{(0)}_k} =a^{(0)}_0+\sum^{k-1}_{l=0}\frac{b^{(l)}_1}{a^{(l)}_1+r^{(l)}_1},\quad \qq^{(0)}_k=\prod^{k-1}_{l=0}(a^{(l)}_1+r^{(l)}_1)$$
と級数表示できたことに注意しましょう。

双対性について

　いまApéry双対は、興味深いことに、その名前の通り「$\pp^{(n)}_k,\qq^{(n)}_k$は$\pp^{(0)}_k,\qq^{(0)}_k$の反復Bauer-Muir変換を与える」という双対性を持っていることがわかります。

　また次のような漸化式からApéry双対に関する連分数表示
$$\frac{\pp^{(n)}_k}{\qq^{(n)}_k} =\t a^{(n)}_0 +\frac{\t b^{(n)}_1}{\t a^{(n)}_1}\p \frac{\t b^{(n)}_2}{\t a^{(n)}_2}\p\cc\p \frac{\t b^{(n)}_k}{\t a^{(n)}_k}$$
の係数も求めることができます。

　以上をまとめると$\pp^{(0)}_k,\qq^{(0)}_k$の反復Bauer-Muir変換$\pp^{(n)}_k,\qq^{(n)}_k$に対応する数列
$$\t a^{(n)}_k,\t b^{(n)}_k, \t r^{(n)}_k,\widetilde R^{(n)}_k,\t d^{(n)}_k,\t t^{(n)}_k,\T^{(n)}_k$$
は次のように求まることがわかります。

　ちなみにこのことから$\t a^{(n)}_k,\t b^{(n)}_k$が
\begin{alignat}{3} \t a^{(n+1)}_k&=\t t^{(n)}_k &&\times\l(\t a^{(n)}_{k+1}+\t r^{(n)}_{k+1}-\t r^{(n)}_{k-1}\frac{\t d^{(n)}_k}{\t d^{(n)}_{k-1}}\r)\\ \t b^{(n+1)}_k&=\t t^{(n)}_k\t t^{(n)}_{k-1} &&\times\t b^{(n)}_k\frac{\t d^{(n)}_k}{\t d^{(n)}_{k-1}} \end{alignat}
という漸化式を満たしていることも確かめられます。

連分数表示について

　また
$$\t a^{(n)}_0=\frac{\pp^{(n)}_0}{\qq^{(n)}_0},\quad \t a^{(n)}_1=\frac{\qq^{(n)}_1}{\qq^{(n)}_0},\quad \t b^{(n)}_1=\frac{\pp^{(n)}_1\qq^{(n)}_0-\pp^{(n)}_0\qq^{(n)}_1}{(\qq^{(n)}_0)^2}$$
とおいたとき、これは
$$\t a^{(n)}_0=\frac{p^{(0)}_n}{q^{(0)}_n},\quad \t a^{(n)}_1=\frac{q^{(0)}_{n+1}}{q^{(0)}_n}+r^{(0)}_{n+1},\quad \t b^{(n)}_1=\frac{q^{(0)}_{n+1}}{q^{(0)}_n} \l(\frac{p^{(0)}_{n+1}}{q^{(0)}_{n+1}}-\frac{p^{(0)}_n}{q^{(0)}_n}\r)$$
と求まり、これによってApéry双対は
$$\lim_{k\to\infty}\frac{\pp^{(n)}_k}{\qq^{(n)}_k} =\t a^{(n)}_0+\frac{\t b^{(n)}_1}{\t a^{(m)}_1} \p\K^\infty_{k=1}\frac{-t^{(k-1)}_{n+1}d^{(k-1)}_{n+1}}{r^{(k)}_{n+1}+t^{(k-1)}_{n+1}R^{(k-1)}_{n+1}}$$
という連分数表示を持つことがわかります。
　特に$n=0$において$\t a^{(0)}_0,\t a^{(0)}_1,\t b^{(0)}_1$は次のように求まることに注意しましょう。

収束性について

　一般にApéry双対
$$\frac{\pp^{(n)}_k}{\qq^{(n)}_k} =\t a^{(n)}_0 +\frac{\t b^{(n)}_1}{\t a^{(n)}_1}\p \frac{\t b^{(n)}_2}{\t a^{(n)}_2}\p\cc\p \frac{\t b^{(n)}_k}{\t a^{(n)}_k}$$
が双対前と同じ値に収束するとは限りませんが
$$\pp^{(n)}_k,\qq^{(n)}_k,\t a^{(n)}_k,\t b^{(n)}_k, \t r^{(n)}_k,\t d^{(n)}_k,\t t^{(n)}_k,\T^{(n)}_k$$
が加速性を伴う反復Bauer-Muir変換を定めていることや、$\t t^{(n)}_k$を規定する有理関数$\t t_n(y)$が$y\geq n$において連続であることなどがわかれば、そのApéry変換について
$$\lim_{k\to\infty}\frac{\pp^{(n)}_k}{\qq^{(n)}_k} =\lim_{k\to\infty}\frac{\pp^{(k)}_k}{\qq^{(k)}_k}$$
が成り立つと考えられるので、$\pp^{(n)}_n/\qq^{(n)}_n=p^{(n)}_n/q^{(n)}_n$に注意すると次のような予想が立てられます。

　適当な仮定の下でこれが証明できるのかはわかりませんが、とりあえず経験則としてこういうことが成り立つ、ということだけ覚えておけばいいと思います。

嬉しさ

　特にこれが成り立っているときに嬉しいのが、$p^{(0)}_n,q^{(0)}_n$の反復Bauer-Muir変換を流用することで$\pp^{(0)}_k,\qq^{(0)}_k$の反復Bauer-Muir変換を求める手間を省ける、という点にあります。
　下の例からもわかるように、この考え方は非常に便利なので絶対に覚えておきましょう。

公式集

　以上で今回の記事は終わりとなりますが、上で紹介した公式たちは実際の計算において非常によく使うこととなるので、それらを参照しやすいよう以下にまとめておくことにしましょう。

反復Bauer-Muir変換

　特にこのとき$R^{(k)}_n\ (n\geq1)$を規定する多項式$R_k(n)$について$R^{(k)}_0=R_k(0)$が成り立つことにも注意しましょう。
　またこれは超幾何級数
$$\sum^\infty_{n=1}A_n\quad \l(\frac{A_n}{A_{n-1}}=\frac{f(n)}{g(n)}\r)$$
で言うところの、$f(1)=0$の場合における
$$\sum^\infty_{n=1}A_n =\frac{g(1)A_1}{g(1)}\p\K^\infty_{n=2}\frac{-f(n)g(n-1)}{f(n)+g(n)}$$
という連分数や、$g(0)=0$の場合における
$$\l(\sum^\infty_{n=0}A_n\r)^{-1} =\frac1{A_0}\l(1-\frac{f(1)}{f(1)+g(1)}\p\K^\infty_{n=2}\frac{f(n)g(n-1)}{f(n)+g(n)}\r)$$
という連分数に対応しているのでした。

Apéry変換

　下の公式における記法
$$\K^\infty_{n=1}\frac{b_n}{a_n} =\K^\infty_{n=1}\l(\frac{b_{2n-1}}{a_{2n-1}}\p\frac{b_{2n}}{a_{2n}}\r)$$
はこの記事特有のものであることに注意してください。

　下の公式は本質的に縮約公式
\begin{align} \K^\infty_{n=1}\frac{b_n}{a_n} &=\frac{b_1}{a_1}\p\K^\infty_{n=1}\l(\frac{b_{2n}}{a_{2n}}\p\frac{b_{2n+1}}{a_{2n+1}}\r)\\ &=\frac{b_1a_2}{b_2+a_1a_2} \p\K^\infty_{n=1}\frac{-b_{2n}b_{2n+1}\frac{a_{2n+2}}{a_{2n}}}{b_{2n+2}+a_{2n+1}a_{2n+2}+b_{2n+1}\frac{a_{2n+2}}{a_{2n}}} \end{align}
であることに注意しましょう。

Apéry双対