Intégration symbolique par création télescopique

TD du cours de Calcul formel, Frédéric Chyzak, Décembre 2004

Il s'agit dans ce TD d'implanter l'algorithme de Fasenmyer donné en cours pour la sommation symbolique hypergéométrique paramétrée.

Par simplicité, on se limite à des suites hypergéométriques h_n,k en deux indices, n et k, la sommation portant sur k. Tout au long du sujet, on testera sur les deux exemples suivant :

• somme du binôme : Rn:=(n+1)/(n+1-k); Rk:=(n-k)/(k+1); S:=[<i,j>:i in [0..1],j in [0..1]];
• identité de Dixon : Rn:=((n+1)/(n+1-k))^3; Rk:=-((n-k)/(k+1))^3; S:=[<i,j>:i in [0..3],j in [0..3];

On suivra les étapes de programmation suivantes :

1. Construire le corps des fractions rationnelles en n et k. On utilisera les fonctions RationalField et FunctionField.
2. Écrire des fonctions DecalageN, DecalageK et DecalageInverseK réalisant respectivement les décalages n devient n+1, k devient k+1, k devient k-1 sur une fraction rationnelle. On utilisera la fonction hom.
3. Écrire une fonction Facteur qui prend en entrée les deux fractions rationnelles R_n(n,k) = h_n+1,k / h_n,k et R_k(n,k) = h_n,k+1 / h_n,k associées à une suite hypergéométrique et donc supposées vérifier la relation de commutation
   R_n(n,k+1) R_k(n,k) = R_k(n+1,k) R_n(n,k),
   ainsi que deux entiers positifs i et j, et renvoie la fraction
   h_n+i,k+j / h_n,k.
4. Écrire une fonction Fasenmyer qui prend en entrée les deux fractions rationnelles R_n et R_k et un ensemble S de paires (i,j) et appliquer l'algorithme de Fasenmyer pour la suite hypergéométriques représentée par R_n et R_k relativement au support S. L'ensemble sera simplement représenté par une séquence Magma. On pourra procéder comme suit :
   1. calculer les fractions h_n+i,k+j / h_n,k pour les (i,j) de S, intervenant dans la mise en équation
      ∑_(i,j)∈S φ_i,j(n) h_n+i,k+j / h_n,k = 0 ;
   2. déterminer leur dénominateur commun. On utilisera les fonctions Denominator et Lcm ;
   3. déduire l'équation à coefficient polynomiaux
      ∑_(i,j)∈S φ_i,j(n) p_i,j(n,k) = 0
      régissant les φ_i,j. On utilisera la fonction Numerator ;
   4. retirer un éventuel contenu commun des coefficients p_i,j de l'équation. On utilisera la fonction Gcd ;
   5. calculer le degré en k maximal des coefficients p_i,j de l'équation. On utilisera les fonctions Degree et Maximum ;
   6. construire et résoudre le système linéaire auquel satisfont les coefficients φ_i,j. Plus précisément, on construira une matrice dont chaque ligne donne les coefficients en k de l'une des entrées φ_i,j de S, extraits par degrés croissants et on recherchera les vecteurs lignes qui, multipliés à gauche de la matrice, produisent une combinaison linéaire nulle des lignes de la matrice. On utilisera les fonctions Coefficient, Matrix, NullSpace, et Basis ;
   7. pour chaque vecteur ligne (φ_i1,j1,...,φ_is,js) de la base de solutions, construire les sommes sur j des φ_i,j, et normaliser la famille de récurrences
      ∑_i  ∑_{j t.q. (i,j)∈S} φ_i,j(n)  ∑_k h_n+i,k = 0
      obtenues, de façon à renvoyer la récurrence sur ∑_k h_n,kd'ordre minimal représentée par le vecteur de ses coefficients. On utilisera la fonction EchelonForm.

Last modified: Wed Dec 8 16:30:13 CET 2004