Accueil🇫🇷Chercher

Algorithme d'Abramov

En mathématiques, en particulier en calcul formel, l'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 1989[1] - [2].

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 de deux polynômes est par définition

,

désigne l'ensemble des entiers non négatifs. Ainsi, la dispersion est le plus grand entier tel que le polynôme et le polynôme décalé de ont un facteur commun. La dispersion est égale à si un tel n'existe pas. La dispersion peut être calculée comme la plus grande racine entière non négative du résultant[3] - [4].

Soit

une relation de récurrence d'ordre à coefficients polynomiaux , avec et soit une solution rationnelle. On pose pour deux polynômes relativement premiers . Soit et

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

Algorithme

Soit à nouveau

une équation de récurrence à coefficients polynomiaux et soit un dénominateur universel. On pose pour un polynôme inconnu ; en notant

l'équation de récurrence équivaut à

.

Comme on peut simplifier par , on obtient une équation de récurrence linéaire avec des coefficients polynomiaux qui peut être résolue pour . Il existe des algorithmes pour trouver des solutions polynomiales. Les solutions pour peuvent ensuite être utilisées à nouveau pour calculer les solutions rationnelles [2].

algorithm rational_solutions is
    input: Linear recurrence equation .
    output: The general rational solution  if there are any solutions, otherwise false.
    
    
    
    Solve  for general polynomial solution 
    if solution  exists then
        return general solution 
    else
        return false
    end if

Exemple

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

sur a une solution rationnelle. Elle peut être calculée en considérant la dispersion

.

Cela donne le dénominateur universel suivant:

et

.

En multipliant l'équation de récurrence d'origine par et en posant on obtient :

.

Cette équation a la solution polynomiale

pour une constante arbitraire . En posant la solution rationnelle générale est

pour un quelconque.

Références

  1. Abramov, « Rational solutions of linear differential and difference equations with polynomial coefficients », USSR Computational Mathematics and Mathematical Physics, vol. 29, no 6, , p. 7–12 (ISSN 0041-5553, DOI 10.1016/s0041-5553(89)80002-3).
  2. Sergei A. Abramov, « Rational solutions of linear difference and q-difference equations with polynomial coefficients », ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, , p. 285–289 (ISBN 978-0897916998, DOI 10.1145/220346.220383, lire en ligne).
  3. Yiu-Kwong Man et Francis J. Wright, Fast polynomial dispersion computation and its application to indefinite summation (ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation), , 175–180 p. (ISBN 978-0-89791-638-7, DOI 10.1145/190347.190413)
  4. Jürgen Gerhard, Modular Algorithms in Symbolic Summation and Symbolic Integration, coll. « Lecture Notes in Computer Science » (no 3218), , 224 p. (ISBN 978-3-540-24061-7, DOI 10.1007/b104035, lire en ligne).
  5. William Y.C. Chen, Peter Paule et Husam L. Saad, « Converging to Gosper's algorithm », Advances in Applied Mathematics, vol. 41, no 3, , p. 351–364 (DOI 10.1016/j.aam.2007.11.004, arXiv 0711.3386).

Articles liés

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.