Algorithme d'Abramov

En mathématiques, en particulier en calcul formel, l'algorithme d'Abramov calcule toutes les solutions rationnelles d'une relation de récurrence linéaire à coefficients polynomiaux . L'algorithme a été publié par Sergei A. Abramov en 1989.

Dénominateur universel

Le concept principal de l'algorithme d'Abramov est la notion de dénominateur universel. Soit ${\textstyle \mathbb {K} }$ être un corps de caractéristique zéro. La dispersion ${\textstyle \operatorname {dis} (p,q)}$ de deux polynômes ${\textstyle p,q\in \mathbb {K} [n]}$ est par définition

$$\operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},$$

$$\operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},$$

où ${\textstyle \mathbb {N} }$ désigne l'ensemble des entiers non négatifs. Ainsi, la dispersion est le plus grand entier ${\textstyle k\in \mathbb {N} }$ tel que le polynôme ${\textstyle p}$ et le polynôme $q$ décalé de ${\textstyle k}$ ont un facteur commun. La dispersion est égale à ${\textstyle -1}$ si tel ${\textstyle k}$ n'existe pas. La dispersion peut être calculée comme la plus grande racine entière non négative du résultant ${\textstyle \operatorname {res} _{n}(p(n),q(n+k))\in \mathbb {K} [k]}$ . Soit ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ être une relation de récurrence d'ordre ${\textstyle r}$ à coefficients polynomiaux $p_{k}\in \mathbb {K} [n]$, avec ${\textstyle f\in \mathbb {K} [n]}$ et soit ${\textstyle y(n)\in \mathbb {K} (n)}$ une solution rationnelle. On peut écrire ${\textstyle y(n)=p(n)/q(n)}$ pour deux polynômes relativement premiers ${\textstyle p,q\in \mathbb {K} [n]}$ . Soit ${\textstyle D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))}$ et

$$u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})$$

où ${\textstyle [p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)}$ désigne la factorielle décroissante d'une fonction. Alors ${\textstyle q(n)}$ divise ${\textstyle u(n)}$ . Par conséquent, le polynôme ${\textstyle u(n)}$ peut être utilisé comme dénominateur pour toutes les solutions rationnelles ${\textstyle y(n)}$ et c'est pourquoi on l'appelle un dénominateur universel.

Algorithme

Soit à nouveau ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ être une équation de récurrence à coefficients polynomiaux et soit ${\textstyle u(n)}$ un dénominateur universel. Après avoir posé ${\textstyle y(n)=z(n)/u(n)}$ pour un polynôme inconnu ${\textstyle z(n)\in \mathbb {K} [n]}$ et avec ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$ l'équation de récurrence équivaut à

$$\sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).$$

Comme le ${\textstyle u(n+k)}$ se simplifie ceci est une équation de récurrence linéaire avec des coefficients polynomiaux qui peut être résolue pour une solution polynomiale inconnue ${\textstyle z(n)}$ . Il existe des algorithmes pour trouver des solutions polynomiales . Les solutions pour ${\textstyle z(n)}$ peuvent ensuite être utilisées à nouveau pour calculer les solutions rationnelles ${\textstyle y(n)=z(n)/u(n)}$ .

l'algorithme rational_solutions est
  entrée: équation de récurrence linéaire ${\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: La solution rationnelle générale ${\textstyle y}$ s'il y a des solutions, sinon faux.

  ${\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))}$
  Résoudre ${\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)}$ pour la solution polynomiale générale ${\textstyle z(n)}$
  si solution ${\textstyle z(n)}$ existe alors
    retour solution générale ${\textstyle y(n)=z(n)/u(n)}$
  autre
    retourner faux
  fin si

Exemple

L'équation de récurrence homogène d'ordre ${\textstyle 1}$

$$(n-1)\,y(n)+(-n-1)\,y(n+1)=0$$

sur ${\textstyle \mathbb {Q} }$ a une solution rationnelle. Elle peut être calculée en considérant la dispersion

$$D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.$$

Cela donne le dénominateur universel suivant:

$$u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n$$

et

$$\ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).$$

En multipliant l'équation de récurrence d'origine par ${\textstyle \ell (n)}$ et en posant ${\textstyle y(n)=z(n)/u(n)}$ on obtient

$$(n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.$$

Cette équation a la solution polynomiale ${\textstyle z(n)=c}$ pour une constante arbitraire ${\textstyle c\in \mathbb {Q} }$ . En utilisant ${\textstyle y(n)=z(n)/u(n)}$ la solution rationnelle générale est

$$y(n)={\frac {c}{(n-1)n}}$$

pour arbitraire ${\textstyle c\in \mathbb {Q} }$ .

Références

Mathématiques WikiProject sur Wikidata