Apéryの加速法4：Birkhoff-Adamsの定理

はじめに

　この記事では 前回の記事 に引き続きApéryの加速法について解説していきます。
　さて 前回の記事 では多項式係数の連分数
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc$$
に対し、そのtail sequence
$$x_n=\frac{b_{n+1}}{a_{n+1}}\p\frac{b_{n+2}}{a_{n+2}}\p\frac{b_{n+3}}{a_{n+3}}\p\cc$$
はある多項式$r_n$によって
$$x_n=r_n+O\l(\frac1n\r)$$
と近似でき、特にこの多項式$r_n$によるBauer-Muir変換
$$\frac{P_n}{Q_n}=\frac{p_n+r_np_{n-1}}{q_n+r_nq_{n-1}}$$
を考えることで連分数の加速を引き起こすことができる、ということついて解説しました。
　ということで今回の記事では 前回の記事 にて用いたBirkhoff-Adamsの定理の詳細を述べるとともに、Bauer-Muir変換によって具体的にどの程度の加速が生じるのか、ということについて解説していきます。

Birkhoff-Adamsの定理

　まずはBirkhoff-Adamsの定理の詳細な主張について紹介していきましょう。

特性方程式

　Birkhoff-Adamsの定理とは大まかに次のような主張のことを言います。

　さて実際にはいくつかの例外に関する場合分けが必要になるわけですが、その例外が発生する条件について説明するために、まずはこのような$u_n,v_n$が存在したときにその漸近展開に関する定数$\a,\b,\la,\mu,c_k,c'_k$はどのように求まるかを考えていきましょう。
　と言ってもやることとしては単純で、$u_n$の漸近展開から$u_{n+1},u_{n+2}$の漸近展開を求め
$$u_{n+2}-f(n)u_{n+1}-g(n)u_n=0$$
の展開係数を比較することで次のような方程式が得られます。

　ただし$\binom xn$は一般化二項係数
$$\binom xn=\frac{x(x-1)(x-2)\cdots(x-n+1)}{n!}$$
としました。

　具体的には$c_0=1$としていたことに注意すると、$k=0$の方程式は
$$\a^2-A_0\a-B_0=0$$
と書き下せ、またこれが成り立つとき$k=1$の方程式は
$$2\a^2\la-\a(\la A_0+A_1)-B_1=0$$
と書き下せ、さらにこれが成り立つとき$k\geq 2$の方程式は
\begin{align} 0=(A_0-2\a)(k-1)c_{k-1} &+\sum^{k-2}_{j=0}\l(\a^22^{k-j}\binom{\la-j}{k-j}-\a\sum^k_{i=j}\binom{\la-j}{i-j}A_{k-i}-B_{k-j}\r)c_j\\ =(A_0-2\a)(k-1)c_{k-1} &+\l(\a(4\a-A_0)\frac{(\la-k+2)(\la-k+1)}2-\a((\la-k+2)A_1+A_2)-B_2\r)c_{k-2}\\ &+\sum^{k-3}_{j=0}\l(\a^22^{k-j}\binom{\la-j}{k-j}-\a\sum^k_{i=j}\binom{\la-j}{i-j}A_{k-i}-B_{k-j}\r)c_j \end{align}
と表すことができます。

場合分けについて

　いまこのことから$\a,\b$は二次方程式
$$X^2-A_0X-B_0=0$$
の解として定まり、またこのとき$A_0-2\a=\b-\a$が成り立つことに注意すると、次のような場合に次のような事実や問題が生じることがわかります。

case I：$\a\neq\b$のとき

　$\la,\mu$は
\begin{align} \a(\a-\b)\la-(A_1\a+B_1)&=0\\ \b(\b-\a)\mu-(A_1\b+B_1)&=0 \end{align}
によって定まり、$c_k$は$c_0=1$および
$$c_{k-1}=-\frac1{(\b-\a)(k-1)} \sum^{k-2}_{j=0}\l(\a^22^{k-j}\binom{\la-j}{k-j}-\a\sum^k_{i=j}\binom{\la-j}{i-j}A_{k-i}-B_{k-j}\r)c_j$$
という漸化式によって定まる($c'_k$についても同様)。

case II：$\a=\b$かつ$A_0\a+B_1\neq0$のとき

　$k=1$の方程式$A_0\a+B_1=0$が満たされないため、上述のような漸近展開を持つ解は存在しないことになる。

case III：$\a=\b$かつ$A_0\a+B_1=0$のとき

　$\la,\mu$は二次多項式
$$F(\k)=\a^2\k(\k-1)-\a(A_1\k+A_2)-B_2$$
の根として定まり、$c_k$は$c_0=1$および
$$c_{k-2}=-\frac1{F(\la-k+2)} \sum^{k-3}_{j=0}\l(\a^22^{k-j}\binom{\la-j}{k-j}-\a\sum^k_{i=j}\binom{\la-j}{i-j}A_{k-i}-B_{k-j}\r)c_j$$
という漸化式によって定まる($c'_k$についても同様)。
　ただし$p=\la-\mu$が正整数となるときは$F(\la-p)=0$となってしまい、$k=p+2$の方程式
$$0=\sum^{k-3}_{j=0}\l(\a^22^{k-j}\binom{\la-j}{k-j}-\a\sum^k_{i=j}\binom{\la-j}{i-j}A_{k-i}-B_{k-j}\r)c_j$$
が満たされるとは限らないため、このとき$u_n$のような漸近挙動を持つ解は存在しないことになる。
　さらに$\la=\mu$が成り立つときは$u_n,v_n$に関する方程式が一致してしまうので、また別の漸近挙動を持つ解が存在することになる。

Birkhoff-Adamsの定理

　では以上のことを踏まえてBirkhoff-Adamsの定理の詳細な主張について見ていきましょう。
　以下$f(n),g(n)$は$n\to\infty$において
$$f(n)\sim\sum^\infty_{k=0}\frac{A_k}{n^k},\quad g(n)\sim\sum^\infty_{k=0}\frac{B_k}{n^k}\quad(B_0\neq0)$$
という漸近挙動を持つ数列とし、また漸化式
$$X_{n+2}=f(n)X_{n+1}+g(n)X_n\quad\cdots(\bigstar)$$
の特性方程式
$$X^2=A_0X+B_0$$
の解を$\a,\b$とおくものとします。

　なおこの定数$\g$について
$$\g=2\sqrt{-\frac{A_0A_1+2B_1}{2\a^2}}\neq0$$
が成り立つことに注意しましょう。

補足：$c_k$の満たす漸化式について

　ちなみにcase II の場合も
$$u_{n+2}-f(n)u_{n+1}-g(n)u_n=0$$
の漸近挙動を考えることで$c_k$についての漸化式を立てることができますが
$$e^{\g(\sqrt{n+m}-\sqrt n)} =\sum^\infty_{k=0}\frac{(m\g)^k}{k!}\frac1{(\sqrt{n+m}+\sqrt n)^k}\qquad(m=1,2)$$
とかを展開したり積を取ったりする都合、その漸化式は非常に煩雑になります。
　またcase III-(ii),(iii)の場合も
\begin{align} 0&=u_{n+2}-f(n)u_{n+1}-g(n)u_n\\ &=w_{n+2}-f(n)w_{n+1}-g(n)w_n\\ &\qquad{}+c(v_{n+2}\log(n+2)-f(n)v_{n+1}\log(n+1)-g(n)v_n\log n)\\ &=w_{n+2}-f(n)w_{n+1}-g(n)w_n\\ &\qquad{}+c(v_{n+2}\log\l(1+\frac2n\r)-f(n)v_{n+1}\log\l(1+\frac1n\r)) \end{align}
の漸近展開を考えることで$c_k$についての漸化式や$c$についての方程式が得られます(ただし(ii)において$c_{\la-\mu}$の取り方は任意となります)。

補足：case III-(ii)について

　ちなみにcase III-(ii)における定数$c$について参考文献では "may be zero" や "may happen to be zero" と説明されていますが、これはおそらく「経験則として$0$であることが多い」という意味だと思います。
　実際常に$c=0$が成り立つわけではなく、例えば
$$X_n=\l(2-\frac1{n^2}\r)X_{n-1}-\l(1-\frac1{n^2}\r)X_{n-2}$$
という漸化式は$(\la,\mu)=(1,0)$を満たすのに対し、$\la$に対応する解
$$u_n=n+\sum^n_{k=1}\frac1k$$
は$u_n=n+\log n+O(1)$という漸近挙動を持っていることがわかります(なお$\mu$に対応する解は$v_n=1$となります)。
　ただ$c=0$であるか否かは今回の記事の内容には関わってこないので、あまり気にする必要はありません。

反例構成について

　ちなみに上の反例は
$$X_{n+1}=n(2n+1)X_n-n^3(n+1)X_{n-1}$$
という漸化式を満たす数列
$$p_n=(n!)^2\sum^n_{k=1}\frac1k,\quad q_n=(n!)^2$$
を$r_n=-n^2+1$という多項式を用いて
\begin{align} p'_n&=p_{n+1}+r_{n+1}p_n=(n!)^2\l(\sum^n_{k=1}\frac1k+n+1\r)\\ q'_n&=q_{n+1}+r_{n+1}q_n=(n!)^2 \end{align}
とBauer-Muir変換することで得られる漸化式
$$X_{n+1}=(2(n+1)^2-1)X_n-n^3(n+2)X_{n-1}$$
を由来としています。
　このようにcase III-(iii)に属す漸化式をBauer-Muir変換することでcase III-(ii)に属す漸化式であって$c\neq0$を満たすようなものを無数に構成することができます。

拡張版Birkhoff-Adamsの定理

　ところで我々が考えているのは多項式や有理関数などのように
\begin{align} a_n&\sim n^d\l(a+\frac{a'}n+\frac{a''}{n^2}+\cdots\r)\\ b_n&\sim n^{2d}\l(b+\frac{b'}n+\frac{b''}{n^2}+\cdots\r)\quad(b\neq0) \end{align}
と漸近展開できる数列を係数とする漸化式
$$Y_n=a_nY_{n-1}+b_nY_{n-2}$$
であったので、このような漸化式を対象とした拡張版の主張も与えておきましょう。

展開係数の計算

　いま上のような漸化式に対し$Y_n=(n!)^dX_n$および
$$f(n)=\frac{a_n}{n^d},\quad g(n)=\frac{b_n}{n^d(n-1)^d}$$
とおくことで
$$X_n=f(n)X_{n-1}+g(n)X_{n-2}$$
という漸化式に帰着させることができます。
　またこの$f(n),g(n)$の展開係数は
$$f(n)\sim a+\frac{a'}n+\frac{a''}{n^2}+\cdots$$
および
\begin{align} g(n) &\sim\l(1-\frac1n\r)^{-d}\l(b+\frac{b'}n+\frac{b''}{n^2}+\cdots\r)\\ &=\l(1+\frac dn+\frac{d(d+1)}{2n^2}+\cdots\r) \l(b+\frac{b'}n+\frac{b''}{n^2}+\cdots\r)\\ &=b+\frac{b'+bd}n+\frac1{n^2}\l(b''+b'd+b\frac{d(d+1)}2\r)+\cdots \end{align}
を求まることに注意すると次のような主張が得られます。

拡張版Birkhoff-Adamsの定理

　以下$a_n,b_n$は$n\to\infty$において
\begin{align} a_n&\sim n^d\l(a+\frac{a'}n+\frac{a''}{n^2}+\cdots\r)\\ b_n&\sim n^{2d}\l(b+\frac{b'}n+\frac{b''}{n^2}+\cdots\r)\quad(b\neq0) \end{align}
という漸近挙動を持つ数列とし、また漸化式
$$Y_n=a_nY_{n-1}+b_nY_{n-1}\quad\cdots(\bigstar)$$
の特性方程式
$$Y^2=aY+b$$
の解を$\a,\b$とおくものとします。

連分数の収束速度

　さて以上によって準備は整ったのでここからは連分数
$$\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}$$
の収束速度や、そのBauer-Muir変換
$$\frac{P_n}{Q_n}=\frac{p_n+r_np_{n-1}}{q_n+r_nq_{n-1}}$$
の収束速度を測定していくこととしましょう。
　いま連分数の収束速度は 前回の記事 の補題6として示した以下の主張によって評価できるのでした。

　実際これと拡張版Birkhoff-Adamsの定理を用いることで次のような評価が得られます。

Bauer-Muir変換の収束速度

　そして各種の定数$\a,\b,\g,\la,\mu$が上のように求まっているとき、Bauer-Muir変換
\begin{align} P_n&=p_n+r_np_{n-1}\\ Q_n&=q_n+r_nq_{n-1} \end{align}
が満たす漸化式
$$X_n=\l(a_n+r_n-r_{n-2}\frac{d_{n-1}}{d_{n-2}}\r)X_{n-1}+b_{n-1}\frac{d_{n-1}}{d_{n-2}}X_{n-2}$$
に対応する定数$\g',\la',\mu'$はどのように求まり、またそれによって$P_n/Q_n$の収束速度がどのように求まるかを考えていきましょう。

case I,II の場合

　いま
$$r_n=-\b(n^d+r'n^{d-1}+\cdots)$$
なる多項式$r_n$に対し
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
の次数を$d'$とおくと
$$\frac{d_{n-1}}{d_{n-2}}=1+\frac{d'}n+\cdots$$
が成り立つことから
\begin{align} a_n+r_n-r_{n-2}\frac{d_{n-1}}{d_{n-2}} &=a_n+(r_n-r_{n-2})+r_{n-2}\l(1-\frac{d_{n-1}}{d_{n-2}}\r)\\ &=n^d\l(a+\frac{a'+\b(d'-2d)}n+\cdots\r)\\ b_{n-1}\frac{d_{n-1}}{d_{n-2}} &=n^{2d}\l(b+\frac{b'-2bd}n+\cdots\r)\l(1+\frac{d'}n+\cdots\r)\\ &=n^{2d}\l(b+\frac{b'+b(d'-2d)}n+\cdots\r) \end{align}
と展開できることに注意すると以下のような主張が得られます。

case III の場合

　なおcase IIIの場合はもう一段解深い係数が必要になる都合、その計算も煩雑になるため途中計算は少し端折って説明します。
　いまcase IIIにおいて
$$r_n=-\a(n^d+r'n^{d-1}+\cdots)$$
とおいたとき、$d_n$の$n^{2d-1}$の係数は自動的に$0$となり、また$n^{2d-2}$の係数は
$$r'(r'-1)\a^2-(a'(r'-d)+a'')\a-b''-\frac{d(d-1)}2\a^2$$
表せるので、$d_n$の次数を下げるためには$r'=\la,\mu$とおく必要があります。
　特に 前回の記事 の補題5から
$$x_n=-\frac{v_n}{v_{n-1}}=-\a n^d\l(1+\frac\mu n+\cdots\r)$$
が成り立つことに注意すると$r'=\mu$とおくのが適当であり、このとき以下の主張が成り立ちます。

　なおこんな泥臭い計算をしなくても
\begin{align} u_n+r_nu_{n-1}&\sim(n!)^d\a^nn^{\la-1}\\ v_n+r_nv_{n-1}&\sim(n!)^d\a^nn^{\mu+d'-2d+1} \end{align}
となることを直接示せそうな気もしますが、あまり気にしないこととします。

まとめ

　つまり以上の事実をまとめると
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
の次数$d'$に応じて、元の連分数$p_n/q_n$とBauer-Muir変換$P_n/Q_n$の収束速度は

• case I のときは$O(1/n^{2d-d'})$だけ加速され
• case II のときは全く加速されず
• case III のときは$O(1/n^{2d-d'+2})$だけ加速される

ということがわかりました。

テクニック集

　以上により今回の記事の目的は達成されたので、以下では実際にBauer-Muir変換やその収束速度を計算する際に使えるテクニックでも紹介していこうと思います。

超幾何級数由来の連分数について

　まず超幾何級数
$$S=\sum^\infty_{n=1}A_n\quad\l(\frac{A_n}{A_{n-1}}=\frac{f(n)}{g(n)},\ \deg f=\deg g\r)$$
を由来とする連分数
$$S=\frac{g(1)A_1}{g(1)}\p\K^\infty_{n=2}\frac{-f(n)g(n-1)}{f(n)+g(n)}$$
に対し、各種の定数$\a,\b,\g,\la,\mu$がどのように求まるかについて紹介しましょう。
　具体的な計算は省略しますが実際に特性方程式を求めるなり、漸化式の解
$$u_n=\prod^n_{m=1}g(m),\quad v_n=u_n\l(S-\sum^n_{m=1}A_m\r)$$
の漸近挙動を直接評価するなりすることで次のような主張が得られます。

　特に超幾何級数由来の連分数においてcase IIは発生し得ないので、以下case I,IIIのみを考えることとします。

各数列の係数について

　いまBauer-Muir加速法において
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
の次数を十分小さくするような多項式
$$r_n=r(n^d+r'n^{d-1}+\cdots)$$
を求める際、その係数$r,r'$が満たす方程式から自動的に$-\a,-\b$や$\la,\mu$という定数が求まり、その一方の定数$-\b,\mu$を$r_n$の係数として採用するわけですが、このときもう一方の定数$\a,\la$は$a_n+r_n$の係数として次のように現れることを覚えておきましょう。

　またこのとき(ずらし)Bauer-Muir変換
\begin{align} P_n&=p_{n+1}+r_{n+1}p_n\\ Q_n&=q_{n+1}+r_{n+1}q_n \end{align}
の満たす漸化式の係数について
\begin{align} a_{n+1}+r_{n+1}-r_{n-1}\frac{d_n}{d_{n-1}} &=n^d\l(a+\frac{a'+\a d'+(\b-\a)d}n+\cdots\r)\\ b_n\frac{d_n}{d_{n-1}} &=n^{2d}\l(b+\frac{b'+bd'}n+\cdots\r) \end{align}
が成り立つことも覚えておきましょう。

反復Bauer-Muir変換について

　さて次回以降の記事ではBauer-Muir変換の反復
\begin{align} p^{(k+1)}_n&=p^{(k)}_{n+1}+r^{(k)}_np^{(k)}_n\\ q^{(k+1)}_n&=q^{(k)}_{n+1}+r^{(k)}_nq^{(k)}_n \end{align}
を考えていくわけですが、その過程で$r^{(k)}_n$や$a^{(k)}_n$などの数列の一般項を求めるのに非常に労力を要することとなります。
　そのためその計算を少しでも楽にするのに、上述の事実を用いて$r^{(k)}_n$や$a^{(k)}_n$などの冒頭の係数を予め求めておくことが非常に有効となります。
　具体的には例えば
$$d^{(k)}_n=r^{(k)}_n(a^{(k)}_{n+1}+r^{(k)}_{n+1})-b^{(k)}_{n+1}$$
が常に$n$に依らない定数となるとき、次のような事実が成り立つことをよく覚えておきましょう。