Apéryの加速法3：Bauer-Muir加速
はじめに
この記事では
前回の記事
に引き続きApéryの加速法について解説していきます。
さて
前回の記事
ではBauer-Muir変換という連分数の変形法について解説しましたが、
初回の記事
でも紹介したようにこれを連分数の加速に応用するというのがApéryの加速法の発想の一つなのでした。
ということで今回の記事では多項式係数の連分数
$$\K^\infty_{n=1}\frac{g(n)}{f(n)}
=\frac{g(1)}{f(1)}\p\frac{g(2)}{f(2)}\p\frac{g(3)}{f(3)}\p\cc$$
に対し、具体的にどのような$r_n$を用いてBauer-Muir変換を施すことで加速連分数が得られるのか、ということついて解説していきます。
発想
復習
まずBauer-Muir変換とは与えられた連分数
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc$$
に対し、その収束分数
$$\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}$$
の末尾をズラした分数
$$\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+r_n}$$
を考えることで構成されるのでした。
発想
また一次分数変換
\begin{align}
f_n(X)
&=\frac{p_n+Xp_{n-1}}{q_n+Xq_{n-1}}\\
&=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc\p\frac{b_n}{a_n+X}
\end{align}
は(単射な)連続関数であることや、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$$
について$f_n(x_n)=x$が成り立つことを踏まえると
$$r_n\approx
\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$を取ってくることで連分数の加速
$$\l|x-\frac{P_n}{Q_n}\r|\ll\l|x-\frac{p_n}{q_n}\r|$$
を引き起こせると推測できます。
考察
ところでBauer-Muirの変換公式にも出てきた数列
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
を考えると$r_n$は
\begin{align}
r_n
&=\frac{b_{n+1}+d_n}{a_{n+1}+r_{n+1}}\\
&=\frac{b_{n+1}+d_n}{a_{n+1}}\p\frac{b_{n+2}+d_{n+1}}{a_{n+2}+r_{n+2}}\\
&=\frac{b_{n+1}+d_n}{a_{n+1}}\p\frac{b_{n+2}+d_{n+1}}{a_{n+2}}\p\frac{b_{n+3}+d_{n+2}}{a_{n+3}}\p\cc\p\frac{b_N+d_{N-1}}{a_N+r_N}
\end{align}
と展開できるので、$d_n$が適当な意味で十分小さくなるような$r_n$を取ってくれば
$$r_n\approx
\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$$
となってくれそうな感じがします。
Bauer-Muir加速法
そして実際$a_n,b_n$が多項式として表せるとき、$x_n$がある多項式$r_n$によって
$$x_n=r_n+o(1)$$
と近似できるものと仮定すると、この$r_n$としてあり得る多項式の候補は次のような特徴付けによって絞り込むことができます。
多項式$a_n,b_n,r_n$に対し
\begin{align}
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+o(1)
\end{align}
が成り立つとすると、多項式
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
について
$$\deg d_n<\max\{\deg r_n,\deg(a_n+r_n)\}$$
が成り立つ。
$x_n$が
$$x_n=\frac{b_{n+1}}{a_{n+1}+x_{n+1}}$$
という関係式を満たすことから
\begin{align}
0
&=x_n(a_{n+1}+x_{n+1})-b_{n+1}\\
&=(r_n+o(1))(a_{n+1}+r_{n+1}+o(1))-b_{n+1}\\
&=d_n+o(r_n)+o(a_{n+1}+r_{n+1})
\end{align}
が成り立つことに注意するとわかる。
つまり$d_n$の次数を十分小さくするような多項式$r_n$を求めることで連分数を加速させることができる、ということであり、以上の考察をまとめると次のような主張が得られます。
ある$n_0$より先で$a_n,b_n$が多項式として表せるような連分数
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc$$
に対し、多項式$r_n$を
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}\quad(n\geq n_0)$$
の次数を十分小さくするようなものの中で
$$r_n\approx
\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$$
を満たしそうなものとして取ったとき、これによるBauer-Muir変換
\begin{align}
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}}\\
&=a_0+\frac{b_1}{a_1+r_1}+\frac{b_1d_1/(a_1+r_1)^2}{a_2+r_2-d_1/(a_1+r_1)}
\p\K^\infty_{n=2}\frac{b_nd_n/d_{n-1}}{a_{n+1}+r_{n+1}-r_{n-1}d_n/d_{n-1}}
\end{align}
は元の連分数より収束が速くなる(ならないこともある)。
このような連分数の加速法のことをBauer-Muir加速(法)と呼ぶことにする。
なおBauer-Muir変換の由来となった論文Bauer(1872), Muir(1877)には変換の加速性に関する記述は無さそうに見えるため、この加速法にBauer-Muirの名を付けるのは少し違和感がありますが、Cohen(2024)ではこれをBauer-Muir Accelerationと呼んでおり、またそれ以外にいい呼び方も思いつかなかったのでこのように呼ぶことにしています。
ひとまず本当に加速されるのか、どのくらい加速されるのかという疑問は置いといて、いくつかの具体例を眺めつつこのBauer-Muir加速の効力を見ていくこととしましょう。
なお級数を多項式係数の連分数に書き換えるには
この記事
で紹介した次の公式が使えることに注意しましょう。
$R_n=A_n/A_{n-1}$とおいたとき
$$\sum^\infty_{n=1}A_n=\frac{A_1}1\p\K^\infty_{n=2}\frac{-R_n}{1+R_n}$$
が成り立つ。
またこの記事では使いませんが、$A_0=1$において
\begin{align}
\l(\sum^\infty_{n=0}A_n\r)^{-1}
&=\l(\frac11\p\K^\infty_{n=1}\frac{-R_n}{1+R_n}\r)^{-1}\\
&=1-\frac{A_1}{1+A_1}\p\K^\infty_{n=2}\frac{-R_n}{1+R_n}
\end{align}
が成り立つことも覚えておくといいかもしれません($a_1$の値を取り替えることができるので、$a_1+r_1=0$となってしまうときとかに役に立ちます)。
任意の数列$\la_n\neq0$に対し
$$\K^\infty_{n=1}\frac{b_n}{a_n}=\frac{\la_1b_1}{\la_1a_1}\p\K^\infty_{n=2}\frac{\la_{n-1}\la_nb_n}{\la_na_n}$$
が成り立つ。
ちなみにBauer-Muir変換の収束分数
$$\frac{P_n}{Q_n}=\frac{p_n+r_np_{n-1}}{q_n+r_nq_{n-1}}$$
は
\begin{align}
\frac{P_n}{Q_n}
&=\frac{P_0}{Q_0}+\sum^{n-1}_{m=0}\l(\frac{P_{m+1}}{Q_{m+1}}-\frac{P_m}{Q_m}\r)\\
&=\frac{P_0}{Q_0}+\sum^{n-1}_{m=0}\frac{d_m}{Q_mQ_{m+1}}\prod^m_{j=1}(-b_j)
\end{align}
と級数表示でき、これによって
初回の記事
にて紹介したような加速級数も得ることができます。
具体例
$O(1/n)$で収束する連分数
\begin{align}
\frac\pi4
&=\sum^\infty_{n=1}\frac{(-1)^{n-1}}{2n-1}\\
&=\frac11\p\K^\infty_{n=2}\frac{(2n-3)/(2n-1)}{1-(2n-3)/(2n-1)}\\
&=\frac11\p\K^\infty_{n=2}\frac{(2n-3)^2}2
\end{align}
について
$$d_n=r_n(r_{n+1}+2)-(2n-1)^2$$
の次数を低くする、特に定数とするような多項式$r_n$を求めると
$$(r_n,d_n)=(2n-3,-4),(-(2n-1),0)$$
の二通りが考えられるが
$$r_n\approx\frac{(2n-1)^2}2\p\frac{(2n+1)^2}2\p\frac{(2n+3)^2}2\p\cc$$
であるためには$r_n=2n-3$の方が適切である。
このとき対応するBauer-Muir変換から
\begin{align}
\frac\pi4
&=-3+\frac10\p\frac4{15}\p\K^\infty_{n=3}\frac{(2n-5)^2}6\\
&=-3+\frac14\l(15+\K^\infty_{n=3}\frac{(2n-5)^2}6\r)\\
\pi&=3+\K^\infty_{n=1}\frac{(2n-1)^2}6
\end{align}
が得られ、その収束速度は$O(1/n^3)$となる。
ちなみにこの連分数は
$$\pi=3+\sum^\infty_{n=1}\frac{(-1)^{n-1}}{n(n+1)(2n+1)}$$
と級数表示できる。
$O(1/n2^n)$で収束する連分数
\begin{align}
\log2
&=\sum^\infty_{n=1}\frac1{n2^n}\\
&=\frac{1/2}1\p\K^\infty_{n=2}\frac{-(n-1)/2n}{1+(n-1)/2n}\\
&=\frac12\p\K^\infty_{n=1}\frac{-2(n-1)^2}{3n-1}
\end{align}
について
$$d_n=r_n(r_{n+1}+3n+2)+2n^2$$
を定数とするような多項式$r_n$は
$$(r_n,d_n)=(-(n-1),2),(-2n,0)$$
の二通りあり、適切なのは$r_n=-(n-1)$の方である。
このとき対応するBauer-Muir変換は
$$\log2=\frac12+\frac{1/2}3\p\K^\infty_{n=2}\frac{-2(n-1)^2}{3n}$$
と求まり、その収束速度は$O(1/n^32^n)$となる。
ちなみにこの連分数は
$$\log2=\frac12+\sum^\infty_{n=1}\frac2{n(n+1)(n+2)2^n}$$
と級数表示できる。
$O(1/(n+1)!)$で収束する連分数
\begin{align}
e&=1+\sum^\infty_{n=1}\frac1{n!}\\
&=1+\frac11\p\K^\infty_{n=2}\frac{-1/n}{1+1/n}\\
&=1+\frac11\p\K^\infty_{n=2}\frac{-(n-1)}{n+1}
\end{align}
について
$$d_n=r_n(r_{n+1}+n+2)+n$$
を定数とするような多項式$r_n$は
$$(r_n,d_n)=(-1,-1),(-n,0)$$
の二通りあるが、適切なのは$r_n=-1$の方であり、このとき対応するBauer-Muir変換から
\begin{align}
e&=\frac10\p\frac13\p\K^\infty_{n=3}\frac{-(n-2)}{n+1}\\
&=3+\K^\infty_{n=1}\frac{-n}{n+3}
\end{align}
が得られる。この二行目の右辺は$O(1/(n+4)!)$で収束する。
ちなみにこの連分数は
$$e=3-\sum^\infty_{n=1}\frac1{n(n+1)^2n!}$$
と級数表示できる。
$O(1/n^3)$で収束する連分数
\begin{align}
\frac34\z(3)
&=\sum^\infty_{n=1}\frac{(-1)^{n-1}}{n^3}\\
&=\frac11\p\K^\infty_{n=2}\frac{(n-1)^3/n^3}{1-(n-1)^3/n^3}\\
&=\frac11\p\K^\infty_{n=2}\frac{(n-1)^6}{3n^2-3n+1}
\end{align}
について
$$d_n=r_n(r_{n+1}+3n^2+3n+1)-n^6\qquad(n\geq1)$$
の次数を低くする多項式$r_n$を考えると
$$r_{n+1}=n^3+\frac32n+\frac34,\quad
d_n=\frac{39}4n^2-\frac{49}{16}$$
と求まるが、対応するBauer-Muir変換は非常に煩雑となる。
指数積分
$$I(x)=\int^\infty_0\frac{e^{-t}}{x+t}dt=e^x\int^\infty_x\frac{e^{-t}}tdt$$
は
$$I(x)=\frac1x\p\frac11\p\frac1x\p\frac21\p\frac2x\p\frac31\p\frac3x\p\cc$$
という連分数表示を持つことが知られており、これを
この記事
の公式3を用いて縮約することで$O(e^{-4\sqrt{xn}})$で収束する連分数
$$I(x)=\frac1{x+1}\p\K^\infty_{n=2}\frac{-(n-1)^2}{2n+x-1}$$
が得られる。
いまこれに対し$r_n=-n$とおくと
$$d_n=r_n(r_{n+1}+2n+x+1)+n^2=-xn$$
となるので、これに関するBauer-Muir変換は
$$I(x)=\frac1x-\frac{1/x}{x+2}\p\K^\infty_{n=2}\frac{-n(n-1)}{2n+x}$$
と求まる。ただし収束速度は変換前とほぼ変わらず$O(e^{-4\sqrt{xn}})$となる。
Bauer-Muir減速
ちなみに上の例からもわかるように$d_n$の次数を小さくする多項式$r_n$の候補は基本的に二通り存在し、そのうち一方だけが加速を生み出すわけですが、実はもう一方の多項式を選ぶことで連分数を減速させることができます(なおどうして減速が起きるのかは 次回の記事 の記事における議論を少しイジることでわかります)。
例1において得られた連分数
$$\pi=3+\K^\infty_{n=1}\frac{(2n-1)^2}6$$
について
$$d_n=r_n(r_{n+1}+6)-(2n+1)^2$$
を定数とするような$r_n$は
$$(r_n,d_n)=(2n-3,-16),(-(2n+3),-4)$$
の二通り存在し、そのうち加速を生み出さない方$r_n=-(2n+3)$に関するBauer-Muir変換を考えると
$$\pi=\frac41\p\K^\infty_{n=2}\frac{(2n-3)^2}2$$
が得られる。
このようにBauer-Muir変換によって加速させたものを減速させることで(何故か)元の連分数を得ることができます。特にこのことを利用すると、収束速度の高い連分数が与えられたときに、それを減速させていくことでその由来となった級数を特定する、といったことができることを覚えておきましょう。
$x_n$の漸近挙動について
さて上での考察によると
$$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(1)$$
と近似できることが認められればBauer-Muir加速法における加速性が保証されるのでした。
ということで実際に$x_n$が適当な多項式で近似できるということを確かめていきましょう。
ここで$x_n$は次のような表示を持つことに注意しましょう。
連分数
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc$$
に対し、その収束分数とtail sequenceをそれぞれ
\begin{align}
\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_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
\end{align}
とおいたとき
$$x_n=-\frac{q_n}{q_{n-1}}\frac{x-\frac{p_n}{q_n}}{x-\frac{p_{n-1}}{q_{n-1}}}$$
が成り立つ。
\begin{align}
x
&=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc\p\frac{b_n}{a_n+x_n}\\
&=\frac{p_n+x_np_{n-1}}{q_n+x_nq_{n-1}}
\end{align}
が成り立つことに注意するとわかる。
級数の視点から
まずは変換前の連分数が超幾何級数を由来とするとき、つまりある多項式$f(n),g(n)$が存在して
$$\frac{A_n}{A_{n-1}}=\frac{f(n)}{g(n)}$$
が成り立つような数列$A_n$に関する級数
$$S=\sum^\infty_{n=1}A_n$$
を由来とする場合について考えてみましょう。
このときオイラーの連分数公式から$S$は
\begin{align}
S
&=\frac{A_1}1\p\K^\infty_{n=2}\frac{-f(n)/g(n)}{1+f(n)/g(n)}\\
&=\frac{g(1)A_1}{g(1)}\p\K^\infty_{n=2}\frac{-f(n)g(n-1)}{f(n)+g(n)}
\end{align}
と表すことができ、その収束分数$p_n/q_n$について
$$p_n=q_n\sum^n_{k=1}A_k,\quad q_n=\prod^n_{k=1}g(k)$$
が成り立つので、上の補題から$x_n$は
\begin{align}
x_n
&=-g(n)\frac{\sum^\infty_{k=n+1}A_k}{\sum^\infty_{k=n}A_k}\\
&=-g(n)+\frac{g(n)A_n}{\sum^\infty_{k=n}A_k}
\end{align}
と表せることとなります。
また以下に例示するような手法によって
$$\frac1{g(n)A_n}\sum^\infty_{k=n}A_k
=\frac{c_0}{n^d}+\frac{c_1}{n^{d+1}}+\cdots+\frac{c_d}{n^{2d}}+O\l(\frac1{n^{2d+1}}\r)$$
という漸近展開が得られることに注意すると、$x_n$も
\begin{align}
x_n
&=-g(n)+\frac{n^d}{c_0+\frac{c_1}n+\dots+\frac{c_d}{n^d}+O(\frac1{n^{d+1}})}\\
&=-g(n)+n^d\l(c'_0+\frac{c'_1}n+\cdots+\frac{c'_d}{n^d}+O\l(\frac1{n^{d+1}}\r)\r)\\
&=-g(n)+c'_0n^d+c'_1n^{d-1}+\cdots+c'_d+O\l(\frac1n\r)
\end{align}
のように展開できることがわかります。
$$\z(3)=\sum^\infty_{n=1}\frac1{n^3}$$
の場合を考えると$g(n)=n^3$より
$$\frac1{g(n)A_n}\sum^\infty_{k=n}A_k=\sum^\infty_{k=n}\frac1{k^3}$$
が成り立ち、これに
オイラー・マクローリンの和公式
\begin{align}
\sum^{b-1}_{k=a}F(k)
=\int^b_aF(x)dx-\frac{F(b)-F(a)}2
&+\sum^m_{k=1}\frac{B_{2k}}{(2k)!}(F^{(2k-1)}(b)-F^{(2k-1)}(a))\\
&+\int^b_a\frac{B_{2m+1}(x-\lfloor x\rfloor)}{(2m+1)!}F^{(2m+1)}(x)dx
\end{align}
を適用することで
$$\sum^\infty_{k=n}\frac1{k^3}
=\frac1{2n^2}+\frac1{2n^3}+\frac1{4n^4}+O\l(\frac1{n^5}\r)$$
と展開できるので
\begin{align}
x_n
&=-n^3+\frac{2n^2}{1+\frac1n+\frac1{2n^2}+O(\frac1{n^3})}\\
&=-n^3+2n^2\l(1-\frac1n+\frac1{2n^2}+O\l(\frac1{n^3}\r)\r)\\
&=-n^3+2n^2-2n+1+O\l(\frac1n\r)
\end{align}
を得る。
$$\frac\pi4=\sum^\infty_{n=1}\frac{(-1)^{n-1}}{2n-1}$$
の場合を考えると$g(n)=2n-1$より
$$\frac1{g(n)A_n}\sum^\infty_{k=n}A_k=\sum^\infty_{k=n}\frac{(-1)^{k-n}}{2k-1}$$
が成り立ち、これに
オイラー・ブールの和公式
$$\sum^{b-1}_{k=a}(-1)^kF(k+h)
=\frac12\sum^m_{k=0}\frac{E_k(h)}{k!}((-1)^{b-1}F^{(k)}(b)+(-1)^aF^{(k)}(a))
+\frac12\int^b_a\frac{\widetilde E_m(h-x)}{m!}F^{(m+1)}(x)dx$$
を$F(x)=\frac1{x-1},h=\frac12$について適用することで
$$\sum^\infty_{k=n}\frac{(-1)^{k-n}}{2k-1}=\frac1{4(n-1)}+O\l(\frac1{n^3}\r)$$
と展開できるので
\begin{align}
x_n
&=-(2n-1)+\frac{4(n-1)}{1+O(\frac1{n^2})}\\
&=-(2n-1)+4(n-1)\l(1+O\l(\frac1{n^2}\r)\r)\\
&=2n-3+O\l(\frac1n\r)
\end{align}
を得る。
$$\log2=\sum^\infty_{n=1}\frac1{n2^n}$$
の場合を考えると$g(n)=2n$より
\begin{align}
\frac1{g(n)A_n}\sum^\infty_{k=0}A_{n+k}
&=\sum^\infty_{k=0}\frac1{(n+k)2^{k+1}}\\
&=\frac1n\sum^\infty_{j=0}\sum^\infty_{k=0}\frac1{2^{k+1}}\l(-\frac{k}{n}\r)^j\\
&=\frac1n-\frac1{n^2}+O\l(\frac1{n^3}\r)
\end{align}
と展開できるので
\begin{align}
x_n&=-2n+\frac n{1-\frac1n+O(\frac1{n^2})}\\
&=-2n+n\l(1+\frac1n+O\l(\frac1{n^2}\r)\r)\\
&=-(n-1)+O\l(\frac1n\r)
\end{align}
を得る。
$$e=1+\sum^\infty_{n=1}\frac1{n!}$$
の場合を考えると$g(n)=n$より
\begin{align}
\frac1{g(n)A_n}\sum^\infty_{k=0}A_{n+k}
&=\sum^\infty_{k=0}\frac{(n-1)!}{(n+k)!}\\
&=\frac1n+\frac1{n(n+1)}+\frac1{n(n+1)(n+2)}+\cdots\\
&=\frac1n+\frac1{n^2}+O\l(\frac1{n^3}\r)
\end{align}
と展開できるので
\begin{align}
x_n&=-n+\frac n{1+\frac1n+O\l(\frac1{n^2}\r)}\\
&=-n+n\l(1-\frac1n+O\l(\frac1{n^2}\r)\r)\\
&=-1+O\l(\frac1n\r)
\end{align}
を得る。
一般の場合について
以上により超幾何級数由来の連分数に対しては$x_n$の漸近展開を直接計算できることがわかりました。
また一般に
$$\z(3)=\frac65\p\K^\infty_{n=1}\frac{-n^6}{(2n+1)(17n^2+17n+5)}$$
のように超幾何級数に表せない場合でも、Birkhoff-Adamsの定理というものを用いれば$x_n$は
$$x_n\sim n^d\sum^\infty_{k=0}\frac{c_k}{n^k}$$
という形の漸近展開を持つことが示せます。
定理の仮定について
以下Birkhoff-Adamsの定理に必要な仮定として、多項式係数の連分数
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc$$
の$a_n,b_n$の次数について、ある非負整数$d$が存在し
$$\deg a_n\leq d,\quad \deg b_n=2d$$
が成り立つものとします。
例えば超幾何級数由来の連分数
$$S=\frac{g(1)A_1}{g(1)}\p\K^\infty_{n=2}\frac{-f(n)g(n-1)}{f(n)+g(n)}$$
においては
$$\deg f=\deg g=d$$
であることが必要十分となります。
なおそうでないとき、つまり$\deg f<\deg g$であるときは元から$O(1/n!)$程度の収束速度を持つので加速を考える需要はあまりないと思います。
このときBirkhoff-Adamsの定理とは次のような主張のことを言います(詳細は 次回の記事 にて)。
多項式$a_n,b_n$の係数を
\begin{align}
a_n&=an^d+a'n^{d-1}+\cdots\\
b_n&=bn^{2d}+b'n^{2d-1}+\cdots\quad(b\neq0)
\end{align}
とし、また二次方程式
$$X^2=aX+b$$
の解を$X=\a,\b$とおく。
このとき漸化式
$$X_n=a_nX_{n-1}+b_nX_{n-2}$$
について(いくつかの例外を除き)
\begin{align}
u_n&\sim(n!)^d\a^nn^\la\sum^\infty_{k=0}\frac{c_k}{n^k}\\
v_n&\sim(n!)^d\b^nn^{\mu}\sum^\infty_{k=0}\frac{c'_k}{n^k}
\end{align}
という形の漸近挙動を持つ基本解$X_n=u_n,v_n$が存在する(ただし$c_0=c'_0=1$とした)。
またこのように漸化式
$$X_n=a_nX_{n-1}+b_nX_{n-2}$$
が異なる漸近挙動を満たす解$X_n=u_n,v_n$を持つとき、$x_n$はこの$u_n,v_n$を用いて次のように表すことができます。
漸化式
$$X_n=a_nX_{n-1}+b_nX_{n-2}$$
の$0$でない解$X_n=u_n,v_n$であって
$$\lim_{n\to\infty}\frac{v_n}{u_n}=0$$
を満たすようなものに対し
$$-\frac{v_n}{v_{n-1}}
=\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$$
が成り立つ。
$a_n,b_n$の最初の数項を適当に置き換えることで
$$x=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc$$
は有限値に収束するものとしてよい。
このときその収束分数
$$\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}$$
について$p_n,q_n$も漸化式
$$X_n=a_nX_{n-1}+b_nX_{n-2}$$
を満たすので($u_n,v_n$は明らかに線形独立であることに注意すると)ある定数$A,B,C,D$が存在して
\begin{align}
p_n&=Au_n+Bv_n\\
q_n&=Cu_n+Dv_n
\end{align}
が成り立つ。また
$$\deg\begin{pmatrix}
p_n&q_n\\p_{n-1}&q_{n-1}
\end{pmatrix}
=\prod^n_{k=1}(-b_k)\neq0$$
より$p_n,q_n$は線形独立であることに注意すると
$$x=\lim_{n\to\infty}\frac{p_n}{q_n}=\frac AC$$
が成り立つことがわかるので補題3より
$$x_n
=-\frac{p_n-xq_n}{p_{n-1}-xq_{n-1}}
=-\frac{v_n}{v_{n-1}}$$
を得る。
つまりBirkhoff-Adamsの定理から
$$v_n\sim(n!)^d\b^nn^{\mu}\sum^\infty_{k=0}\frac{c'_k}{n^k}$$
という漸近展開が得られているとき、$x_n$は
\begin{align}
x_n
&=-\frac{v_n}{v_{n-1}}\\
&\sim-\b n^d
\frac{n^\mu\sum^\infty_{k=0}c'_k/n^k}{(n-1)^\mu\sum^\infty_{k=0}c'_k/(n-1)^k}\\
&=-\b n^d\l(1+\frac{c''_1}n+\cdots+\frac{c''_d}{n^d}+O\l(\frac1{n^{d+1}}\r)\r)\\
&=-\b(n^d+c''_1 n^{d-1}+\cdots+c''_d)+O\l(\frac1n\r)
\end{align}
と展開できるわけです。
ちなみに簡単な計算によって$c''_1=\mu$となることもわかったりします。
特殊な場合について
なお
$$\int^\infty_0\frac{e^{-t}}{x+t}dt=\frac1{x+1}\p\K^\infty_{n=2}\frac{-(n-1)^2}{2n+x-1}$$
のように$\a=\b$かつ
$$aa'+2(b'+bd)\neq0$$
という特殊な条件を満たす場合においては、$u_n,v_n$の漸近展開は
\begin{align}
u_n&\sim(n!)^d\a^ne^{\g\sqrt n}n^\la\sum^\infty_{k=0}\frac{c_k}{n^{k/2}}\\
v_n&\sim(n!)^d\a^ne^{-\g\sqrt n}n^\la\sum^\infty_{k=0}\frac{c'_k}{n^{k/2}}
\end{align}
という形になり、$x_n$の漸近展開も
$$x_n=-\frac{v_n}{v_{n-1}}\sim-\a n^d\sum^\infty_{k=0}\frac{c''_k}{n^{k/2}}$$
となるため、これを多項式でどう近似しようにも少なくとも$O(n^{d-\frac12})$だけのズレが生じてしまいます。
実際そのためかこの場合においてはBauer-Muir加速法によって加速を引き起こすことはできません(このことは
次回の記事
において確かめられます)。
次回の記事に向けて
さて上ではBirkhoff-Adamsの定理を用いることで$x_n$が多項式によって近似できることがわかりましたが、Birkhoff-Adamsの定理からわかることは他にもいくつかあります。
その詳細については
次回の記事
にてじっくり掘り下げていきますが、ここでもその概要について簡単に紹介しておきましょう。
$r_n$の取り方について
いま補題1によると
$$d_n=r_n(a_{n+1}+r_{n+1})-b_{n+1}$$
の次数を$d$未満にするような多項式$r_n$を考えることで
$$x_n=r_n+o(1)$$
を満たすような多項式$r_n$の候補が求まるのでした。
特に
\begin{align}
a_n&=an^d+a'n^{d-1}+\cdots\\
b_n&=bn^{2d}+b'n^{2d-1}+\cdots\\
r_n&=rn^d+r'n^{d-1}+\cdots
\end{align}
とおくと、$d_n$における$n^{2d}$の係数は
$$r^2+ar-b$$
と表せるので、二次方程式
$$X^2=aX+b$$
が異なる解$\a,\b$を持つとき、$r_n$の候補は$r=-\a$であるものと$r=-\b$であるものの二通り得られることとなります。
また上での議論から
$$u_n\sim(n!)^d\a^nn^\la,\quad
v_n\sim(n!)^d\b^nn^\mu$$
に対し
$$\lim_{n\to\infty}\frac{v_n}{u_n}=\lim_{n\to\infty}\frac{(\b/\a)^n}{n^{\la-\mu}}=0$$
が成り立つように$\a,\b$を選ぶことで
$$x_n=-\b(n^d+\mu n^{d-1}+O\l(n^{d-2}\r))$$
が成り立っていたことに注意すると、$r=-\a,-\b$のうち絶対値の小さい方を選べばよいことがわかります。
また$|\a|=|\b|$のときは$\la,\mu$の実部の大小を比較すればよく、特に$\a,\b=\pm\sqrt b\in\R$かつ$a'>0$であるときは$r=\pm\sqrt b$のうち正の方を選ぶのが適当となります(詳細は
次回の記事
にて)。
なお$\a=\b$であるときは当然$r=-\a$一択となりますが、このときは$n^{d-1}$の係数$r'$が$-\a\la,-\a\mu$のどちらであるかを選択する必要が生じます。ただこのときも同様に$\la,\mu$のうち実部が小さいほうを選べばよいことがわかります。
連分数の収束速度について
また次の主張を用いることで連分数の収束速度を計ることもできます。
補題5の状況下で、連分数$x$とその収束分数
\begin{align}
x&=a_0+\frac{b_1}{a_1}\p\frac{b_2}{a_2}\p\cc\\
\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}
\end{align}
に対し
$$x-\frac{p_n}{q_n}=O\l(\frac{v_n}{u_n}\r)$$
が成り立つ。
ちなみに同様にして$q_nx-p_n=O(v_n)$が成り立つことも覚えておきましょう。
補題5の証明から
\begin{align}
p_n&=Au_n+Bv_n\\
q_n&=Cu_n+Dv_n
\end{align}
および$x=A/C$が成り立っていたことに注意すると
$$x-\frac{p_n}{q_n}
=\frac{AD-BC}{C^2}\frac{v_n}{u_n+\frac DCv_n}
=O\l(\frac{v_n}{u_n}\r)$$
を得る。
例えばこれによって
$$x-\frac{p_n}{q_n}=O\l(\frac{(\b/\a)^n}{n^{\la-\mu}}\r)$$
や
$$x-\frac{p_n}{q_n}=O(e^{-2\g\sqrt n})$$
といった評価が得られることとなります。
またこのようにしてBauer-Muir加速の変換前後における連分数の収束速度を求めることで、どの程度の加速が生じるのかを測定することもできます。
まとめ
ということで 次回の記事 ではBirkhoff-Adamsの定理の詳細を述べるとともに、上述のようにBauer-Muir加速法における$r_n$の選び方やその加速の大きさについて深堀りしていこうと思います。
おまけ
ちなみにBauer-Muir加速法における加速性は直接的な計算によっても確かめることができます。
実際Bauer-Muir変換
$$\frac{P_n}{Q_n}=\frac{p_n+r_np_{n-1}}{q_n+r_nq_{n-1}}$$
について上と同様にして
$$x-\frac{P_n}{Q_n}=O\l(\frac{v_n+r_nv_{n-1}}{u_n+r_nu_{n-1}}\r)$$
と評価できるので
$$x_n=-\frac{v_n}{v_{n-1}}=r_n+O\l(\frac1n\r)$$
であったことに注意すると、例えば$\a\neq\b$において
\begin{align}
x-\frac{P_n}{Q_n}
&=O\l(\frac{v_{n-1}/n}{u_n}\r)\\
&=O\l(\frac1{n^{d+1}}\frac{v_n}{u_n}\r)\\
&=O\l(\frac1{n^{d+1}}\l(x-\frac{p_n}{q_n}\r)\r)
\end{align}
が成り立ち、少なくとも$O(1/n^{d+1})$だけ加速されることがわかります。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
