アブラモフのアルゴリズム

数学、特にコンピュータ代数において、アブラモフのアルゴリズムは、多項式係数を持つ線形回帰方程式のすべての有理解を計算する。このアルゴリズムは、セルゲイ・A・アブラモフによって1989年に発表された。^{[ 1 ] [ 2 ]}

普遍分母

アブラモフのアルゴリズムの主な概念は、普遍分母です。 を特性0の体とします。2つの多項式の分散は と定義され、 は非負の整数の集合を表します。したがって、分散は、多項式と回シフトされた多項式が共通因数を持つ最大値です。そのようなが存在しない場合はとなります。分散は、結果の最大の非負の整数根として計算できます。^{[ 3 ] [ 4 ]}を、多項式係数、多項式の右辺、有理数列解 を 持つの位数の再帰方程式とします。2つの互いに素な多項式 について と書くことができます。 と とし、は関数の階乗降を表すとします。次に でを割ります。したがって、多項式はすべての有理解の分母として使用できるため、普遍分母と呼ばれます。^{[ 5 ]}${\textstyle \mathbb {K} }$ ${\textstyle \operatorname {dis} (p,q)}$ ${\textstyle p,q\in \mathbb {K} [n]}$ $${\displaystyle \operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},}$$ ${\textstyle \mathbb {N} }$ ${\textstyle k\in \mathbb {N} }$ ${\textstyle p}$ ${\textstyle k}$ ${\displaystyle q}$ ${\textstyle -1}$ ${\textstyle k}$ ${\textstyle \operatorname {res} _{n}(p(n),q(n+k))\in \mathbb {K} [k]}$ ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ ${\textstyle r}$ ${\displaystyle p_{k}\in \mathbb {K} [n]}$ ${\textstyle f\in \mathbb {K} [n]}$ ${\textstyle y(n)\in \mathbb {K} (n)}$ ${\textstyle y(n)=p(n)/q(n)}$ ${\textstyle p,q\in \mathbb {K} [n]}$ ${\textstyle D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))}$ $${\displaystyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}$$ ${\textstyle [p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)}$ ${\textstyle q(n)}$ ${\textstyle u(n)}$ ${\textstyle u(n)}$ ${\textstyle y(n)}$

アルゴリズム

再び、多項式係数と普遍分母を持つ漸化式を とする。未知の多項式を代入し、 と設定すると、この漸化式は となる。をキャンセルすると、これは多項式係数を持つ線形漸化式となり、未知の多項式解を求めることができる。多項式解を求めるアルゴリズムが存在する。 の解は、有理数解を計算するために再び用いることができる。^{[ 2 ]}${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ ${\textstyle u(n)}$ ${\textstyle y(n)=z(n)/u(n)}$ ${\textstyle z(n)\in \mathbb {K} [n]}$ ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$ $${\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).}$$ ${\textstyle u(n+k)}$ ${\textstyle z(n)}$ ${\textstyle z(n)}$ ${\textstyle y(n)=z(n)/u(n)}$

アルゴリズムrational_solutionsは、入力:線形再帰方程式です。 出力:解が存在する場合は一般的な有理解、それ以外の場合は false です。${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n),p_{k},f\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$ ${\textstyle y}$ ${\textstyle D=\operatorname {disp} (p_{r}(n-r),p_{0}(n))}$ ${\textstyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}$ ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$ 一般多項式解を 解き、解が存在する場合は一般解を返し、そうでない場合はfalse を返す。${\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)}$ ${\textstyle z(n)}$ ${\textstyle z(n)}$ ${\textstyle y(n)=z(n)/u(n)}$ 

例

上の位数 の同次漸化式には有理解があります。これは分散 を考慮することで計算できます。これにより、次の普遍分母が得られます。および元の漸化式に を掛け、 を代入すると になります。この方程式は、任意の定数 に対して多項式解を持ちます。一般的な有理解を用いると、任意の に対して となります。 ${\textstyle 1}$ $${\displaystyle (n-1)\,y(n)+(-n-1)\,y(n+1)=0}$$ ${\textstyle \mathbb {Q} }$ $${\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.}$$ $${\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n}$$ $${\displaystyle \ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).}$$ ${\textstyle \ell (n)}$ ${\textstyle y(n)=z(n)/u(n)}$ $${\displaystyle (n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.}$$ ${\textstyle z(n)=c}$ ${\textstyle c\in \mathbb {Q} }$ ${\textstyle y(n)=z(n)/u(n)}$ $${\displaystyle y(n)={\frac {c}{(n-1)n}}}$$ ${\textstyle c\in \mathbb {Q} }$

参考文献

1. アブラモフ, セルゲイ A. (1989). 「多項式係数を持つ線形微分方程式と差分方程式の有理解」. USSR計算数学と数理物理学. 29 (6): 7– 12. doi : 10.1016/s0041-5553(89)80002-3 . ISSN  0041-5553 .
2. アブラモフ、セルゲイ・A. (1995). 「多項式係数を持つ線形差分方程式とq差分方程式の有理解」 . 1995年国際記号計算・代数計算シンポジウム - ISSAC '95 の議事録. pp.  285– 289. doi : 10.1145/220346.220383 . ISBN 978-0897916998. S2CID  15424889 .
3. Man, Yiu-Kwong; Wright, Francis J. (1994). 「高速多項式分散計算と不定和への応用」.記号および代数計算に関する国際シンポジウム - ISSAC '94 の議事録. pp.  175– 180. doi : 10.1145/190347.190413 . ISBN 978-0897916387. S2CID  2192728 .
4. Gerhard, Jürgen (2005).記号的和と記号的積分におけるモジュラーアルゴリズム. コンピュータサイエンス講義ノート. 第3218巻. doi : 10.1007/b104035 . ISBN 978-3-540-24061-7. ISSN  0302-9743 .
5. Chen, William YC; Paule, Peter; Saad, Husam L. (2007). 「ゴスパーのアルゴリズムへの収束」. arXiv : 0711.3386 [ math.CA ].

ウィキデータのウィキプロジェクト数学