Abramov's algorithm

В математике, особенно в компьютерной алгебре , алгоритм Абрамова вычисляет все рациональные решения линейного рекуррентного уравнения с полиномиальными коэффициентами . Алгоритм был опубликован Сергеем Абрамовым в 1989 году.

Универсальный знаменатель

Основное понятие в алгоритме Абрамова — универсальный знаменатель. Позволять ${\textstyle \mathbb {K} }$ — поле характеристики нулевой . Дисперсия ​ ${\textstyle \operatorname {dis} (p,q)}$ из двух многочленов ${\textstyle p,q\in \mathbb {K} [n]}$ определяется как $$\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}$- раз сдвинутый полином $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}$ с полиномиальными коэффициентами $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))}$ и $$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)}$ и поэтому его называют универсальным знаменателем.

Алгоритм

Пусть еще раз ${\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))}$ рекуррентное уравнение эквивалентно $$\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)}$.

algorithm rational_solutions is
    input: Linear recurrence equation ${\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}$.
    output: The general rational solution ${\textstyle y}$ if there are any solutions, otherwise false.

    ${\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))}$
    Solve ${\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)}$ for general polynomial solution ${\textstyle z(n)}$
    if solution ${\textstyle z(n)}$ exists then
        return general solution ${\textstyle y(n)=z(n)/u(n)}$
    else
        return false
    end if

Пример

Однородное рекуррентное уравнение порядка ${\textstyle 1}$$$(n-1)\,y(n)+(-n-1)\,y(n+1)=0$$над ${\textstyle \mathbb {Q} }$ имеет рациональное решение. Его можно вычислить, рассматривая дисперсию $$D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.$$Это дает следующий универсальный знаменатель: $$u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n$$и $$\ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).$$Умножив исходное рекуррентное уравнение на ${\textstyle \ell (n)}$ и замена ${\textstyle y(n)=z(n)/u(n)}$ приводит к $$(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)}$ общее рациональное решение $$y(n)={\frac {c}{(n-1)n}}$$для произвольного ${\textstyle c\in \mathbb {Q} }$.

Ссылки

WikiProject Mathematics в Викиданных