P再帰方程式

Linear recurrence equation

数学において、P-再帰方程式とは、係数列が多項式で表せる列からなる線型方程式です。P-再帰方程式は、多項式係数を持つ線型再帰方程式（または線型再帰関係、線型差分方程式）です。これらの方程式は、数学の様々な分野、特に組合せ論において重要な役割を果たします。これらの方程式の解となる列は、ホロノミック、P-再帰、またはD-有限と呼ばれます。

1980年代後半から、これらの方程式の解を求める最初のアルゴリズムが開発されました。セルゲイ・A・アブラモフ、マルコ・ペトコフシェク、マーク・ファン・ホーイは、多項式解、有理数解、超幾何解、ダランベルシアン解を求めるアルゴリズムを記述しました。

意味

を特性零の体（例えば）、の多項式、数列、未知数数列とします。この方程式は多項式係数を持つ線型回帰方程式と呼ばれます（この記事のすべての回帰方程式はこの形式です）。と が両方とも零でない場合、 は方程式の位数と呼ばれます。 が零の場合、方程式は同次方程式と呼ばれ、 が零でない場合、方程式は非同次方程式と呼ばれます。 ${\textstyle \mathbb {K} }$ ${\textstyle \mathbb {K} =\mathbb {Q} }$ ${\textstyle p_{k}(n)\in \mathbb {K} [n]}$ ${\textstyle k=0,\dots ,r}$ ${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$ ${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$ $${\displaystyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$$ ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\textstyle r}$ ${\textstyle f}$

これは と書くこともできます。ここでは多項式係数を持つ線形再帰演算子であり、はシフト演算子、つまり です。 ${\textstyle Ly=f}$ ${\textstyle L=\sum _{k=0}^{r}p_{k}N^{k}}$ ${\textstyle N}$ ${\textstyle N\,y(n)=y(n+1)}$

閉じた形式の解

またはは、多項式係数を持つ再帰方程式と等価です。この方程式の解を計算するアルゴリズムはいくつか存在します。これらのアルゴリズムでは、多項式解、有理数解、超幾何解、ダランベルティ解を計算できます。同次方程式の解は、線形再帰演算子の核によって与えられます。数列の空間の部分空間として、この核は基底を持ちます。^[1]を の基底とすると、任意定数の形式的な和は同次問題 の一般解と呼ばれます。が の特殊解、すなわちである場合、 は非同次問題の解でもあり、非同次問題の一般解と呼ばれます。 ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ ${\textstyle Ly=f}$ ${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$ ${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$ ${\textstyle \ker L}$ ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}}$ ${\textstyle c_{1},\dots ,c_{m}\in \mathbb {K} }$ ${\textstyle Ly=0}$ ${\textstyle {\tilde {y}}}$ ${\textstyle Ly=f}$ ${\textstyle L{\tilde {y}}=f}$ ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}+{\tilde {y}}}$

多項式解

1980年代後半、セルゲイ・A・アブラモフは、右辺が多項式である再帰方程式 の一般多項式解を求めるアルゴリズムを説明した。彼（および数年後にはマルコ・ペトコフシェク）は、多項式解の次数境界を与えた。この方法により、この問題は線形方程式系 を考えるだけで簡単に解くことができる。^{[2] [3] [4] 1995年にアブラモフ、ブロンスタイン、ペトコフシェクは、再帰方程式}のべき級数解を特定のべき基底（つまり通常の基底 ではない）で考えることで、多項式の場合をより効率的に解くことができることを示した。^[5] ${\textstyle y(n)\in \mathbb {K} [n]}$ ${\textstyle f(n)\in \mathbb {K} [n]}$ ${\textstyle (x^{n})_{n\in \mathbb {N} }}$

より一般的な解（例えば、有理数解や超幾何解）を見つけるための他のアルゴリズムも、多項式解を計算するアルゴリズムに依存しています。

合理的な解決策

1989年、セルゲイ・A・アブラモフは、一般有理解、すなわち多項式右辺 を持つ は、普遍分母の概念を用いることで求められることを示した。普遍分母とは、あらゆる有理解の分母が を割り切れる多項式である。アブラモフは、この普遍分母が最初と最後の係数多項式と のみを用いることで計算できることを示した。この普遍分母をすべての有理解の未知の分母に代入することは、変換された方程式のすべての多項式解を計算することで求められる。^[6] ${\textstyle y(n)\in \mathbb {K} (n)}$ ${\textstyle f(n)\in \mathbb {K} [n]}$ ${\textstyle u}$ ${\textstyle u}$ ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\displaystyle y}$

超幾何解

連続する2つの項の比が における有理関数、すなわちであるとき、その数列は超幾何的であると呼ばれる。これは、数列が多項式係数を持つ1階漸化方程式の解である場合に限る。超幾何数列の集合は加法に関して閉じていないため、数列空間の部分空間ではない。 ${\textstyle y(n)}$ ${\displaystyle n}$ ${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$

1992年、マルコ・ペトコフシェクは、右辺が超幾何列の和である再帰方程式の一般超幾何解を求めるアルゴリズムを提示した。このアルゴリズムは、有理関数のゴスパー・ペトコフシェク標準形を用いている。この特定の表現を用いることで、変換された方程式の多項式解を考えるだけで十分である。^[3] ${\displaystyle f}$

Mark van Hoeij による、より効率的な異なるアプローチがあります。最初と最後の係数多項式と の根（特異点と呼ばれる）を考慮すると、すべての超幾何列は、 とに対しての形式で表現されるという事実を利用して、段階的に解を構築できます。ここで はガンマ関数と体 の代数閉包を表します。すると、 は方程式の特異点（つまり、またはの根）でなければなりません。さらに、指数 の境界を計算できます。固定値に対して、の候補を与える仮説を立てることができます。特定の に対して、再びアブラモフのアルゴリズムによって有理関数を得るための仮説を立てることができます。すべての可能性を考慮すると、再帰方程式の一般解が得られます。^{[7] [8]} ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\textstyle y(n)}$ $${\displaystyle y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$ ${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$ ${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$ ${\textstyle i\neq j}$ ${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$ ${\textstyle \Gamma (n)}$ ${\textstyle {\overline {\mathbb {K} }}}$ ${\textstyle \mathbb {K} }$ ${\textstyle \xi _{1},\dots ,\xi _{s}}$ ${\textstyle p_{0}}$ ${\textstyle p_{r}}$ ${\textstyle e_{i}}$ ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$ ${\textstyle z}$ ${\textstyle z}$ ${\textstyle r(n)}$

ダランベルティアン解

数列がダランベルシアン数列であるとは、ある超幾何数列に対して が成り立ち、 が差分演算子、すなわち を表すことを意味するときである。これは、 となるような有理係数を持つ一次線形回帰演算子が存在するとき、かつその場合に限る。^[4] ${\displaystyle y}$ ${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$ ${\textstyle h_{1},\dots ,h_{k}}$ ${\textstyle y=\sum x}$ ${\textstyle \Delta y=x}$ ${\textstyle \Delta }$ ${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$ ${\textstyle L_{1},\dots ,L_{k}}$ ${\textstyle L_{k}\cdots L_{1}y=0}$

1994年、アブラモフとペトコフシェクは、再帰方程式の一般ダランベルシアン解を計算するアルゴリズムを報告した。このアルゴリズムは超幾何解を計算し、再帰的に再帰方程式の次数を減少させる。^[9]

例

符号付き順列行列

サイズの符号付き置換行列の数は、数列で表すことができます。符号付き置換行列とは、すべての行とすべての列にちょうど1つの非ゼロ要素を持つ正方行列です。非ゼロ要素は です。数列は、多項式係数を持つ線形回帰方程式と初期値によって決定されます。超幾何解を求めるアルゴリズムを適用すると、ある定数 に対する一般的な超幾何解を求めることができます。また、初期値を考慮すると、数列 は符号付き置換行列の数を表します。^[10] ${\displaystyle n\times n}$ ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$ ${\textstyle \pm 1}$ $${\displaystyle y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$ ${\textstyle y(0)=1,y(1)=2}$ $${\displaystyle y(n)=c\,2^{n}n!}$$ ${\textstyle c}$ ${\textstyle y(n)=2^{n}n!}$

退縮

要素を持つ集合の反転 の数は再帰方程式によって与えられ、例えばペトコフシェクのアルゴリズムを適用すると、この再帰方程式には多項式解、有理数解、超幾何解は存在しないことがわかる。^[4] ${\textstyle y(n)}$ ${\textstyle n}$ $${\displaystyle y(n)=(n-1)\,y(n-2)+y(n-1).}$$

アプリケーション

関数が超幾何的であるとき、 はとにおける有理関数を表す。超幾何和は、 が超幾何的である形式の有限和である。ツァイルバーガーの独創的なテレスコーピングアルゴリズムは、このような超幾何和を多項式係数を持つ再帰方程式に変換することができる。この方程式を解くことで、例えば の閉形式解と呼ばれる超幾何解の線型結合を得ることができる。^[4] ${\textstyle F(n,k)}$ ${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$ ${\textstyle \mathbb {K} (n,k)}$ ${\textstyle n}$ ${\textstyle k}$ ${\textstyle f(n)=\sum _{k}F(n,k)}$ ${\textstyle F(n,k)}$ ${\textstyle f}$

参考文献

1. 数列がほぼすべての項において等しい場合、その数列は等しいとみなされる。この基底は有限である。これについては、ペトコフシェク、ウィルフ、ツァイルベルガー共著の著書『A=B』に詳しく記載されている。
2. アブラモフ、セルゲイ・A. (1989). 「線形微分方程式と差分方程式の多項式解の探索に関連するコンピュータ代数の問題」モスクワ大学計算数学・サイバネティクス. 3 .
3. Petkovšek, Marko (1992). 「多項式係数を持つ線形回帰の超幾何解」. Journal of Symbolic Computation . 14 ( 2–3 ): 243– 264. doi :10.1016/0747-7171(92)90038-6. ISSN  0747-7171.
4. ペトコフシェク、マルコ;ウィルフ、ハーバート S.ツァイルベルガー、ドロン (1996)。 A=B。 AKピーターズ。ISBN 978-1568810638. OCLC  33898705。
5. Abramov, Sergei A.; Bronstein, Manuel; Petkovšek, Marko (1995). 「線形作用素方程式の多項式解について」. 1995年国際記号計算・代数計算シンポジウム - ISSAC '95 の議事録. ACM. pp.  290– 296. CiteSeerX 10.1.1.46.9373 . doi :10.1145/220346.220384. ISBN  978-0897916998. S2CID  14963237。
6. アブラモフ, セルゲイ A. (1989). 「多項式係数を持つ線形微分方程式と差分方程式の有理解」. USSR計算数学・数理物理学. 29 (6): 7– 12. doi :10.1016/s0041-5553(89)80002-3. ISSN  0041-5553.
7. van Hoeij, Mark (1999). 「線形再帰方程式の有限特異点と超幾何解」. Journal of Pure and Applied Algebra . 139 ( 1–3 ): 109–131 . doi :10.1016/s0022-4049(99)00008-0. ISSN  0022-4049.
8. Cluzeau, Thomas; van Hoeij, Mark (2006). 「線形再帰方程式の超幾何解の計算」.工学・通信・コンピューティングにおける応用代数. 17 (2): 83– 115. doi :10.1007/s00200-005-0192-x. ISSN  0938-1279. S2CID  7496623.
9. Abramov, Sergei A.; Petkovšek, Marko (1994). 「線形微分方程式と差分方程式のダランベルティアン解」.記号計算と代数計算に関する国際シンポジウム - ISSAC '94 の議事録. ACM. pp.  169– 174. doi :10.1145/190347.190412. ISBN 978-0897916387. S2CID  2802734。
10. "A000165 - OEIS". oeis.org . 2018年7月2日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=P-recursive_equation&oldid=1319624430"