Algorithme d'Abramov

En mathématiques, en particulier en calcul formel, lModèle:'algorithme d'Abramov est un algorithme qui 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 1989Modèle:,.

Dénominateur universel

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

$\mathrm{dis}(p,q)=\max \{k\in \mathbb{N}:\mathrm{deg}(\mathrm{pgcd}(p(n),q(n+k)))\ge 1\}\cup \{-1\}$,

où $\mathbb{N}$ désigne l'ensemble des entiers non négatifs. Ainsi, la dispersion est le plus grand entier $k\in \mathbb{N}$ tel que le polynôme $p$ et le polynôme $q$ décalé de $k$ ont un facteur commun. La dispersion est égale à $-1$ si un tel $k$ n'existe pas. La dispersion peut être calculée comme la plus grande racine entière non négative du résultant${\mathrm{res}}_n(p(n),q(n+k))\in 𝕂[k]$Modèle:,.

Soit

$\sum _{k=0}^r{p}_k(n)y(n+k)=f(n)$

une relation de récurrence d'ordre $r$ à coefficients polynomiaux $p_k\in 𝕂[n]$, avec $f\in 𝕂[n]$ et soit $y(n)\in 𝕂(n)$ une solution rationnelle. On pose $y(n)=p(n)/q(n)$ pour deux polynômes relativement premiers $p,q\in 𝕂[n]$. Soit $D=\mathrm{dis}(p_r(n-r),p_0(n))$ et

$u(n)=\mathrm{pgcd}([p_0(n+D){]}^{\underset{\_}{D+1}},[p_r(n-r){]}^{\underset{\_}{D+1}})$

où

$[p(n){]}^{\underset{\_}{k}}=p(n)p(n-1)\cdots p(n-k+1)$

désigne la factorielle décroissante d'une fonction. Alors $q(n)$ divise $u(n)$ . Par conséquent, le polynôme $u(n)$ peut être utilisé comme dénominateur pour toutes les solutions rationnelles $y(n)$ et c'est pourquoi on l'appelle un dénominateur universel.

Algorithme

Soit à nouveau

${\sum }_{k=0}^r{p}_k(n)y(n+k)=f(n)$

une équation de récurrence à coefficients polynomiaux et soit $u(n)$ un dénominateur universel. On pose $y(n)=z(n)/u(n)$ pour un polynôme inconnu $z(n)\in 𝕂[n]$ ; en notant

$\ell (n)=\mathrm{ppcm}(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 on peut simplifier par $u(n+k)$, on obtient une équation de récurrence linéaire avec des coefficients polynomiaux qui peut être résolue pour $z(n)$. Il existe des algorithmes pour trouver des solutions polynomiales. Les solutions pour $z(n)$ peuvent ensuite être utilisées à nouveau pour calculer les solutions rationnelles $y(n)=z(n)/u(n)$.

algorithm rational_solutions is
    input: Linear recurrence equation ${\sum }_{k=0}^r{p}_k(n)y(n+k)=f(n),p_k,f\in 𝕂[n],p_0,p_r\ne 0$.
    output: The general rational solution $y$ if there are any solutions, otherwise false.

    $D=\mathrm{disp}(p_r(n-r),p_0(n))$
    $u(n)=\mathrm{pgcd}([p_0(n+D){]}^{\underset{\_}{D+1}},[p_r(n-r){]}^{\underset{\_}{D+1}})$
    $\ell (n)=\mathrm{ppcm}(u(n),\dots ,u(n+r))$
    Solve ${\sum }_{k=0}^r{p}_k(n)\frac{z(n+k)}{u(n+k)}\ell (n)=f(n)\ell (n)$ for general polynomial solution $z(n)$
    if solution $z(n)$ exists then
        return general solution $y(n)=z(n)/u(n)$
    else
        return false
    end if

Exemple

L'équation de récurrence homogène d'ordre $1$

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

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

$D=\mathrm{dis}(p_1(n-1),p_0(n))=\mathrm{disp}(-n,n-1)=1$.

Cela donne le dénominateur universel suivant:

$u(n)=\mathrm{pgcd}([p_0(n+1){]}^{\underset{\_}{2}},[p_r(n-1){]}^{\underset{\_}{2}})=(n-1)n$

et

$\ell (n)=\mathrm{ppcm}(u(n),u(n+1))=(n-1)n(n+1)$.

En multipliant l'équation de récurrence d'origine par $\ell (n)$ et en posant $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

$z(n)=c$

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

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

pour un $c\in \mathbb{Q}$ quelconque.

Articles liés

• Suite définie par récurrence