En matemáticas, particularmente en álgebra computacional , el algoritmo de Abramov calcula todas las soluciones racionales de una ecuación de recurrencia lineal con coeficientes polinomiales . El algoritmo fue publicado por Sergei A. Abramov en 1989. [1] [2]
El concepto principal del algoritmo de Abramov es un denominador universal. Dejar
ser un campo de característica cero. La dispersión
de dos polinomios
Se define como
![{\displaystyle \operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
dónde
denota el conjunto de números enteros no negativos. Por tanto, la dispersión es la máxima
tal que el polinomio
y el
-veces polinomio desplazado
tienen un factor común. Es
si tal
no existe. La dispersión se puede calcular como la raíz entera no negativa más grande de la resultante
. [3] [4] Deje
ser una ecuación de repetición de orden
con coeficientes polinomiales
, polinomio lado derecho
y solución de secuencia racional
. Es posible escribir
para dos polinomios relativamente primos
. Dejar
y ![{\displaystyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
dónde
denota el factorial descendente de una función. Luego
divide
. Entonces el polinomio
se puede utilizar como denominador para todas las soluciones racionales
y por eso se le llama denominador universal. [5]Deja de nuevo
ser una ecuación de recurrencia con coeficientes polinomiales y
un denominador universal. Después de sustituir
para un polinomio desconocido
y ambientación
la ecuación de recurrencia es equivalente a
![{\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Como el
cancelar esta es una ecuación de recurrencia lineal con coeficientes polinomiales que se pueden resolver para una solución polinomial desconocida
. Existen algoritmos para encontrar soluciones polinomiales . Las soluciones para
luego se puede usar de nuevo para calcular las soluciones racionales
. [2]algoritmo rational_solutions es entrada: ecuación de recurrencia lineal
. salida: la solución racional general
si hay alguna solución, de lo contrario falso.
Resolver
para solución polinomial general
si solución
existe entonces devuelve la solución general
de lo contrario, devuelve un final falso si
La ecuación de orden de recurrencia homogénea ![{\textstyle 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (n-1)\,y(n)+(-n-1)\,y(n+1)=0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
encima
tiene una solución racional. Se puede calcular considerando la dispersión ![{\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Esto produce el siguiente denominador universal: ![{\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y ![{\displaystyle \ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Multiplicando la ecuación de recurrencia original con
y sustituyendo
lleva a ![{\displaystyle (n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Esta ecuación tiene la solución polinomial
para una constante arbitraria
. Utilizando
la solución racional general es ![{\displaystyle y(n)={\frac {c}{(n-1)n}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
por arbitrario
.