2階P-線型再帰式のアルゴリズム構成
あいさつ
んちゃろはー🎵
今回はこの前書いた連分数による級数の加速方法のために超幾何数列の復習と2階のP-線型回帰式の解法を考えるよ。
- 多項式$p(x)\in\mathbb{C}[x]$の約数の集合を$Divisor(p)$の様に書く。
基本事項
$n$に関する多項式列$\{p_{k}(n)\}_{k\in\mathbb{N}_{0}}\subset\mathbb{C}[n]$に対して定まる以下の漸化式をN階のP-線形回帰式と呼ぶ。
\begin{eqnarray}
\left\{
\begin{array}{l}
\sum_{k=0}^{N}p_{k}(n)a_{n+k}=0\\
a_{0}=A\\
a_{1}=B
\end{array}
\right.
\end{eqnarray}
数列$\{a_{n}\}_{n\in\mathbb{N}_{0}}$が以下の性質を持つ時、超幾何項という。
\begin{equation}
\forall n\in\mathbb{N}_{0}:\frac{a_{n+1}}{a_{n}}\in\mathbb{C}(n)
\end{equation}
以下$\mathfrak{t}(n)\coloneqq\{\{a_{n}\}_{n\in\mathbb{N}_{0}}\subset\mathbb{C}\}|\frac{a_{n+1}}{a_{n}}\in\mathbb{C}(n)\}$の様に定めておく。
超幾何数列$\{a_{n}\}_{n\in\mathbb{N}_{0}}\in\mathfrak{t}(n)$は一般的にどの様な形になるだろうか？
定義より$\frac{a_{n+1}}{a_{n}}=\frac{(n-B_{1})(n-B_{2})\cdots(n-B_{M})}{(n-A_{1})(n-A_{2})\cdots(n-A_{N})}z$と書ける事が分かる。ゆえに
\begin{equation}
a_{n}=a_{0}\frac{(-B_{1})_{n}(-B_{2})_{n}\cdots(-B_{M})_{n}}{(-A_{1})_{n}(-A_{2})_{n}\cdots(-A_{N})_{n}}z^{n}
\end{equation}
超幾何数列$\{a_{n}\}_{n\in\mathbb{N}_{0}}$について以下の事を証明せよ。
- $\forall \{r_{n}\}_{n\in\mathbb{N}_{0}}\subset \mathbb{C}(r_{n}\in\mathbb{C}(n)):\{r_{n}a_{n}\}_{n\in\mathbb{N}_{0}}\in\mathfrak{t}(n)$
- $\exists \{b_{n}\}\in\mathfrak{t}(n)\ s.t.\ \frac{b_{n}}{a_{n}}\in\mathbb{C}(n)$であるならば$\forall \{r_{n}\}_{n\in\mathbb{N}_{0}},\{s_{n}\}_{n\in\mathbb{N}_{0}}\subset\mathbb{C}(r_{n},s_{n}\in\mathbb{C}(n)):\{r_{n}a_{n}+s_{n}b_{n}\}_{n\in\mathbb{N}_{0}}\in\mathfrak{t}(n)$
[1]
\begin{equation}
\frac{r_{n+1}a_{n+1}}{r_{n}a_{n}}=\frac{r_{n+1}}{r_{n}}\frac{a_{n+1}}{a_{n}}\in\mathbb{C}(n)
\end{equation}
[2]
\begin{eqnarray}
\frac{r_{n+1}a_{n+1}+s_{n+1}b_{n+1}}{r_{n}a_{n}+s_{n}b_{n}}&=&\frac{r_{n+1}\frac{a_{n+1}}{a_{n}}+s_{n+1}\frac{b_{n+1}}{b_{n}}\frac{b_{n}}{a_{n}}}{r_{n}+s_{n}\frac{b_{n}}{a_{n}}}\in\mathbb{C}(n)
\end{eqnarray}
問題2がどれだけ面白い事を言っているか確認しておきましょう。
$a_{n}\coloneqq\frac{1}{\begin{pmatrix}2n\\n\end{pmatrix}},b_{n}\coloneqq\frac{a_{n}}{n^{2}}$とする。
\begin{equation}
\frac{a_{n+1}}{a_{n}}=\frac{4n+2}{n+1}=4\frac{n+\frac{1}{2}}{n+1}\in\mathbb{C}(n)
\end{equation}
ゆえに
\begin{eqnarray}
\frac{a_{n+1}+r_{n+1}b_{n+1}}{a_{n}+r_{n}b_{n}}&=&\frac{\frac{4n+2}{n+1}+r_{n+1}\frac{(n+1)^{2}}{n^{2}}\frac{4n+2}{n+1}\frac{1}{n^{2}}}{1+\frac{r_{n}}{n^{2}}}\\
&=&\frac{(4n+2)\{n^{4}+r_{n+1}(n+1)^{2}\}}{n^{2}(n+1)(n^{2}+r_{n})}
\end{eqnarray}
$r_{n}=An+B$とおく。すると以下の様に書ける。
\begin{eqnarray}
\frac{a_{n+1}+r_{n+1}b_{n+1}}{a_{n}+r_{n}b_{n}}&=&\frac{(4n+2)\{n^{4}+An^{3}+(3A+B)n^{2}+(3A+2B)n+A+B\}}{n^{2}(n+1)(n^{2}+An+B)}
\end{eqnarray}
\begin{eqnarray}
\left\{
\begin{array}{l}
A-B=16\\
8A-4B=81
\end{array}
\right.
\end{eqnarray}
\begin{eqnarray}
\left\{
\begin{array}{l}
A=\frac{17}{4}\\
B=-\frac{47}{4}
\end{array}
\right.
\end{eqnarray}
\begin{eqnarray}
n^{4}+An^{3}+(3A+B)n^{2}+(3A+2B)n+A+B&=&n^{4}+\frac{17}{4}n^{3}+n^{2}-\frac{43}{4}n-\frac{30}{4}\\
&=&\frac{1}{4}(4n^{4}+17n^{3}+4n^{2}-43n-30)\\
&=&\frac{1}{4}(n+2)(n+3)(4n^{2}-3n-5)\\
&=&(n+2)(n+3)(n+\frac{13\sqrt{2}-6}{16})(n-\frac{13\sqrt{2}+6}{16})
\end{eqnarray}
\begin{eqnarray}
n^{2}+An+B&=&n^{2}+\frac{17}{4}n-\frac{47}{4}\\
&=&(n+\frac{17-\sqrt{1041}}{8})(n+\frac{17+\sqrt{1041}}{8})
\end{eqnarray}
まとめると
\begin{equation}
\sum_{n=1}^{\infty}\frac{1}{\begin{pmatrix}2n\\n\end{pmatrix}}+
\frac{17}{4}\sum_{n=1}^{\infty}\frac{1}{n\begin{pmatrix}2n\\n\end{pmatrix}}-\frac{47}{4}
\sum_{n=1}^{\infty}\frac{1}{n^{2}\begin{pmatrix}2n\\n\end{pmatrix}}=\sum_{n=1}^{\infty}\frac{(2)_{n}(3)_{n}(\frac{13\sqrt{2}-6}{16})_{n}(-\frac{13\sqrt{2}+6}{16})_{n}}{(\frac{17-\sqrt{1041}}{8})_{n}(\frac{17+\sqrt{1041}}{8})_{n}}
\end{equation}
2階P-線型回帰式解法考察
$n$に関する多項式列$\{p_{k}(n)\}_{\in\mathbb{N}_{0}}\subset\mathbb{C}[n]$に対して定まる1階P-線型回帰式の解は超幾何数列になる。
\begin{equation}
p_{0}(n)a_{n}+p_{1}(n)a_{n+1}=0
\end{equation}
ゆえに
\begin{equation}
\frac{a_{n+1}}{a_{n}}=-\frac{p_{n}}{p_{n+1}}\in\mathbb{C}(n)
\end{equation}
上記の様に1階P-線形回帰式は常に超幾何数列になるので簡単に解ける。
では2階のP-線型回帰式はどうなるだろう？
$n$に関する多項式列$\{p_{k}(n)\}_{k\in\mathbb{N}_{0}}\subset\mathbb{C}[n]$に対して定まる2階P-線型回帰式の解法を考察せよ。
[1]まずとにかく定義を書こう。
\begin{equation}
p_{0}(n)a_{n}+p_{1}(n)a_{n+1}+p_{2}(n)a_{n+2}=0
\end{equation}
[2]戦略
闇雲にやるのはいやだよね。
じゃあ、どうしたい？
とりあえず、$a_{n}$が超幾何関数であるとしてみない？
[3][2]の戦略を使いたいから$a_{n+1}$で割ってみましょ。
\begin{equation}
p_{0}(n)\frac{1}{\frac{a_{n+1}}{a_{n}}}+p_{1}(n)+p_{2}(n)\frac{a_{n+2}}{a_{n+1}}=0
\end{equation}
仮定より、$b_{n}\coloneqq\frac{a_{n+1}}{a_{n}}$とおくとこれは$n$に関する有理関数になる。すなわち以下の漸化式を得る。
\begin{equation}
p_{0}(n)+p_{1}(n)r_{n}+p_{2}(n)r_{n}r_{n+1}=0
\end{equation}
[4]次に互いに素な多項式$s(n),t(n)\in\mathbb{C}[n]$を使用して$r_{n}\coloneqq\frac{t(n)}{s(n)}$と表し通分すると
\begin{equation}
p_{0}(n)s(n)s(n+1)+p_{1}(n)t(n)s(n+1)+p_{2}(n)t(n)t(n+1)=0
\end{equation}
この式から、以下の式を得る。
\begin{eqnarray}
\left\{
\begin{array}{l}
t(n)|p_{0}(n)s(n+1)\\
s(n+1)|p_{2}(n)t(n)
\end{array}
\right.
\end{eqnarray}
[5]もし$\gcd(t(n),s(n+1))=1$であれば
\begin{eqnarray}
\left\{
\begin{array}{l}
s(n)|p_{2}(n-1)\\
t(n)|p_{0}(n)
\end{array}
\right.
\end{eqnarray}
が得られるので、実は、$s(n),t(n)$の候補は$p_{2}(n-1),p_{0}(n)$の約数しかないという極めて重要な事が分かる。
[6]では$t(n),s(n+1)$が共通の最大公約数$d(n+1)$を持ったとすると
\begin{eqnarray}
\exists u(n),v(n)\in\mathbb{C}[n](\gcd(u(n),v(n)),\gcd(u(n+1),v(n))=1)\ s.t.\ \left\{
\begin{array}{l}
s(n+1)=d(n+1)u(n+1)\\
t(n)=d(n+1)v(n)
\end{array}
\right.
\end{eqnarray}
の様に書けるので結局下記の式が得られる。
\begin{eqnarray}
\left\{
\begin{array}{l}
u(n)|p_{2}(n-1)\\
v(n)|p_{0}(n)
\end{array}
\right.
\end{eqnarray}
[7]つまり、$r_{n}=\frac{v(n)}{u(n)}\frac{d(n+1)}{d(n)}$の様に分解した時、$\gcd(u(n),v(n)),\gcd(u(n+1),v(n))=1$を満たすなら$u(n),v(n)$の候補は$p_{2}(n-1),p_{0}(n)$の約数のどれかである事が分かる。
[8][7]の様に記号を定めると以下の新たなP-線型再帰式を得る。
\begin{equation}
p_{0}(n)u(n)u(n+1)d(n)+p_{1}(n)u(n+1)v(n)d(n+1)+p_{2}(n)v(n)v(n+1)d(n+2)=0
\end{equation}
後は、$p_{2}(n-1),p_{0}(n)$の約数分だけ考えて、上記漸化式を満たす多項式$d(n)$を探すだけ。
まとめておこう
$n$に関する多項式列$\{p_{k}(n)\}_{k\in\mathbb{N}_{0}}\subset\mathbb{C}[n]$に対して定まる2階P-線型回帰式の解法は次の様に与えられる。
0.$p_{0}(n)a_{n}+p_{1}(n)a_{n+1}+p_{2}(n)a_{n+2}=0$
1.$\frac{a_{n+1}}{a_{n}}$が超幾何関数であると仮定する。
2.$p_{0}(n),p_{2}(n)$の約数の集合を$Divisor(p_{0}),Divisor(p_{1})$を求める。
3.次に、次数が低い方から順番に$u(n)\in Divisor(p_{2}(n-1)),v(n)\in Divisor(p_{0}(n))$を抽出し以下のP-線型漸化式を解く。
\begin{equation}
p_{0}(n)u(n)u(n+1)d(n)+p_{1}(n)u(n+1)v(n)d(n+1)+p_{2}(n)v(n)v(n+1)d(n+2)=0
\end{equation}
4.上記の方法で$d(n)$が見つかったら以下の様な有理関数を$\frac{a_{n+1}}{a_{n}}$に代入する。
\begin{equation}
\frac{a_{n+1}}{a_{n}}=\frac{v(n)}{u(n)}\frac{d(n+1)}{d(n)}
\end{equation}
5.最後にこれから以下の解を得る。
\begin{equation}
a_{n}=a_{0}\frac{d(n)}{d(0)}\prod_{k=0}^{n-1}\frac{v(k)}{u(k)}
\end{equation}
定理2において4.の式で$d(n)$はどの程度絞れるだろうか？
[1]まず分かる事最高次数に関してとにかく$0$にならないといけない事から少なくとも次の事が分かる。
$\deg{p_{0}}+2\deg{u},\deg{p_{1}}+\deg{u}+\deg{v},\deg{p_{2}}+2\deg{v}$のいずれも等しくない場合は棄却
[2]次に最高次数の次の項に注目する。
以下次の様に記号を定める。
\begin{eqnarray}
\left\{
\begin{array}{l}
p_{0}(n)u(n)u(n+1)=A_{k}n^{k}+A_{k-1}n^{k-1}+\cdots\\
p_{1}(n)u(n+1)v(n)=B_{l}n^{l}+B_{l-1}n^{l-1}+\cdots\\
p_{2}(n)v(n+1)v(n)=C_{m}n^{m}+C_{m-1}n^{m-1}+\cdots\\
d(n)=D_{p}n^{p}+D_{p-1}n^{p-1}+\cdots
\end{array}
\right.
\end{eqnarray}
[3]例えば仮に、$k=l\gt m$であったとすると
\begin{align}
&(A_{k}n^{k}+A_{k-1}n^{k-1}+\cdots)(D_{p}n^{p}+D_{p-1}n^{p-1}+\cdots)+(B_{k}n^{k}+B_{k-1}n^{k-1}+\cdots)(D_{p}n^{p}+\{D_{p-1}+pD_{p})n^{p-1}+\cdots\}+\cdots\\
&(A_{k}+B_{k})D_{p}n^{k+p}+\{(A_{k}+B_{k})D_{p-1}+(A_{k-1}+pB_{k}+B_{k-1})D_{p}\}n^{k+p-1}+\cdots\\
&=0
\end{align}
より以下の厳しい条件が得られる。
\begin{eqnarray}
\left\{
\begin{array}{l}
p=-\frac{A_{k}+B_{k}}{B_{k-1}}\in\mathbb{N}\\
-B_{k-1}|A_{k}+B_{k}
\end{array}
\right.
\end{eqnarray}
この様に最高次数の次の次数の係数を見ることで$d$の最高次数自体にも制限をかけれる事が分かる。
展覧会
以下様に構成しようとも解けないなら意味がない。
という事で実際に定理2に基づ解を構成しよう。
$\{a_{n}\}_{n\in\mathbb{N}}\subset\mathbb{C}$が以下の漸化式を満たしたとする。するとどの様な解を持つだろうか？
\begin{equation}
-a_{n}+(z+n-k)a_{n+1}-(n+1)za_{n+2}=0
\end{equation}
$k=1$の場合のみ解いてみよ。
[1]$p_{0}(n)=-1,p_{2}(n)=-(n+1)z$なので
\begin{eqnarray}
\left\{
\begin{array}{l}
Divisor(p_{0}(n))=\{1\}\\
Divisor(p_{2}(n))=\{1,(n+1)\}
\end{array}
\right.
\end{eqnarray}
[2]
\begin{eqnarray}
\left\{
\begin{array}{l}
-d(n)+(z+n-k)d(n)-(n+1)zd(n+2)=0\\
-n(n+1)d(n)+(n+1)(z+n-k)d(n+1)-(n+1)zd(n+2)=0
\end{array}
\right.
\end{eqnarray}
[3]$d(n)=D_{m}n^{m}+D_{m-1}n^{m-1}+\cdots$として
\begin{align}
&-n(n+1)(D_{m}n^{m}+D_{m-1}n^{m-1}+\cdots)+(n+1)(z+n-k)\{D_{m}n^{m}+(mD_{m}+D_{m-1})n^{m-1}+\cdots\}-(n+1)z\{D_{m}n^{m}+(2mD_{m}+D_{m-1})n^{m-1}+\cdots\}\\
&=(-1+1)D_{m}n^{m+2}+\{-D_{m}-D_{m-1}+(z-k+1)D_{m}+(mD_{m}+D_{m-1})-zD_{m}\}n^{m+1}+\cdots\\
&=(m-k)D_{m}n^{m+1}+\cdots
\end{align}
[4]$m=k$を得る。では簡単な例として$k=1$の場合はどうだろうか？
\begin{align}
&-n(n+1)(D_{1}n+D_{0})+(n+1)(z+n-1)(D_{1}n+D_{1}+D_{0})-(n+1)z(D_{1}n+2D_{1}+D_{0})\\
&=\{-D_{0}+(z-1)D_{1}+z(D_{1}+D_{0})-zD_{1}-z(2D_{1}+D_{0})\}n+(z-1)(D_{1}+D_{0})-z(2D_{1}+D_{0})\\
&=\{-(z+1)D_{1}-D_{0}\}n-(z+1)D_{1}-D_{0}\\
&=\{-(z+1)D_{1}-D_{0}\}(n+1)
\end{align}
より
\begin{equation}
D_{0}=-(z+1)D_{1}
\end{equation}
ゆえに
\begin{equation}
\frac{a_{n+1}}{a_{n}}=\frac{1}{n}\frac{n-z}{n-z-1}
\end{equation}
\begin{equation}
a_{n}=\frac{(-z)_{n}}{(n-1)!(-z-1)_{n}}=-\frac{n-z-1}{(n-1)!(z+1)}
\end{equation}
本当に上記の式が成り立つのだろうか？検証しておこう。
\begin{equation}
\frac{n-z-1}{(n-1)!(z+1)}-\frac{(z+n-1)(n-z)}{n!(z+1)}+\frac{z(n-z+1)}{n!(z+1)}=0
\end{equation}
分母分子を払うと以下の様になるので正しい事が示された。
\begin{align}
&n(n-z-1)-(z+n-1)(n-z)+z(n-z+1)\\
&=n^{2}-(z+1)n-n^{2}+n+z^{2}-z+zn-z^{2}+z\\
&=0
\end{align}
この記事を高評価した人
この記事に送られたバッジ
投稿者
