Algorithme d'Abramov - Abramov's algorithm

En mathématiques, en particulier en algèbre informatique , l'algorithme d'Abramov calcule toutes les solutions rationnelles d'une équation 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 un dénominateur universel. Soit un champ de caractéristique zéro. La dispersion de deux polynômes est définie comme ${\ 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 \},}

où désigne l'ensemble des entiers non négatifs. Par conséquent, la dispersion est le maximum tel que le polynôme et le polynôme décalé -times ont un facteur commun. C'est si un tel n'existe pas. La dispersion peut être calculée comme la plus grande racine entière non négative de la résultante . Soit une équation de récurrence d'ordre à coefficients polynomiaux, polynomiale droite et solution de séquence rationnelle . Il est possible d'écrire pour deux polynômes relativement premiers . Laissez et

{\ 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} (nr), p_ {0} (n))}

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

où désigne la factorielle décroissante d'une fonction. Puis se divise . Ainsi, le polynôme peut être utilisé comme dénominateur pour toutes les solutions rationnelles et par conséquent, il est appelé un dénominateur universel.

{\ 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)}

Algorithme

Soit à nouveau une

équation de récurrence avec des coefficients polynomiaux et un dénominateur universel. Après avoir substitué un polynôme inconnu et défini l'équation de récurrence équivaut à

{\ 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) = \ nom_opérateur {lcm} (u (n), \ points, u (n + r))}

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

En tant qu'annulation, il s'agit d'une équation de récurrence linéaire avec des coefficients polynomiaux qui peut être résolue pour une solution polynomiale inconnue . Il existe des algorithmes pour trouver des solutions polynomiales . Les solutions pour peuvent ensuite être utilisées à nouveau pour calculer les solutions rationnelles .

{\ 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

Exemple

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

{\ Displaystyle (n-1) \, y (n) + (- n-1) \, y (n + 1) = 0}

plus a une solution rationnelle. Il peut être calculé en considérant la dispersion

{\ textstyle \ mathbb {Q}}

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

Cela donne le dénominateur universel suivant:

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

et

{\ displaystyle \ ell (n) = \ nom_opérateur {lcm} (u (n), u (n + 1)) = (n-1) n (n + 1).}

La multiplication de l'équation de récurrence originale par et la substitution conduit à

{\ 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.}

Cette équation a la solution polynomiale pour une constante arbitraire . Utiliser la solution rationnelle générale est

{\ textstyle z (n) = c}

{\ textstyle c \ in \ mathbb {Q}}

{\ textstyle y (n) = z (n) / u (n)}

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

pour arbitraire .

{\ textstyle c \ in \ mathbb {Q}}

Références

^ Abramov, Sergei A. (1989). "Solutions rationnelles d'équations différentielles et différentielles linéaires avec coefficients polynomiaux". Mathématiques computationnelles de l'URSS et physique mathématique . 29 (6): 7–12. doi : 10.1016 / s0041-5553 (89) 80002-3 . ISSN 0041-5553 .
^ ^un ^b Abramov, Sergei A. (1995). Solutions rationnelles d'équations de différence linéaire et de différence q avec des coefficients polynomiaux . Actes de l'ISSAC '95 du Symposium international de 1995 sur le calcul symbolique et algébrique . 285-289. doi : 10.1145 / 220346.220383 . ISBN 978-0897916998 .
^ Homme, Yiu-Kwong; Wright, Francis J. (1994). Calcul rapide de dispersion polynomiale et son application à la sommation indéfinie . ISSAC '94 Actes du Symposium international sur le calcul symbolique et algébrique . 175-180. doi : 10.1145 / 190347.190413 . ISBN 978-0897916387 .
^ Gerhard, Jürgen (2005). Algorithmes modulaires en sommation symbolique et intégration symbolique . Notes de cours en informatique . 3218 . doi : 10.1007 / b104035 . ISBN 978-3-540-24061-7 . ISSN 0302-9743 .
^ Chen, William YC; Paule, Peter; Saad, Husam L. (2007). "Convergence à l'algorithme de Gosper". arXiv : 0711,3386 [ math.CA ].

Mathématiques WikiProject sur Wikidata

[1] Abramov, Sergei A. (1989). "Solutions rationnelles d'équations différentielles et différentielles linéaires avec coefficients polynomiaux". Mathématiques computationnelles de l'URSS et physique mathématique . 29 (6): 7–12. doi : 10.1016 / s0041-5553 (89) 80002-3 . ISSN 0041-5553 .

[Abramov_1995-2] un ^b Abramov, Sergei A. (1995). Solutions rationnelles d'équations de différence linéaire et de différence q avec des coefficients polynomiaux . Actes de l'ISSAC '95 du Symposium international de 1995 sur le calcul symbolique et algébrique . 285-289. doi : 10.1145 / 220346.220383 . ISBN 978-0897916998 .

[3] Homme, Yiu-Kwong; Wright, Francis J. (1994). Calcul rapide de dispersion polynomiale et son application à la sommation indéfinie . ISSAC '94 Actes du Symposium international sur le calcul symbolique et algébrique . 175-180. doi : 10.1145 / 190347.190413 . ISBN 978-0897916387 .

[4] Gerhard, Jürgen (2005). Algorithmes modulaires en sommation symbolique et intégration symbolique . Notes de cours en informatique . 3218 . doi : 10.1007 / b104035 . ISBN 978-3-540-24061-7 . ISSN 0302-9743 .

[5] Chen, William YC; Paule, Peter; Saad, Husam L. (2007). "Convergence à l'algorithme de Gosper". arXiv : 0711,3386 [ math.CA ].

Languages

In other projects

Algorithme d'Abramov - Abramov's algorithm

Contenu

Dénominateur universel

Algorithme

Exemple

Références