Méthode de Rice

La n-ième différence finie avant de la fonction f(x) est donnée par

${\displaystyle \Delta ^{n}[f](x)=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}f(x+k)}$

où ${\displaystyle {n \choose k}}$ est le coefficient binomial.

L'intégrale de Nørlund-Rice est donnée par

${\displaystyle \sum _{k=\alpha }^{n}{n \choose k}(-1)^{n-k}f(k)={\frac {n!}{2\pi {\rm {i}}}}\oint _{\gamma }{\frac {f(z)}{z(z-1)(z-2)\cdots (z-n)}}\,{\rm {d}}z}$

où f est méromorphe, α est un entier, ${\displaystyle 0\leq \alpha \leq n}$, et le contour d'intégration entoure les pôles situées aux entiers α, … , n, mais aucun des pôles de f. L'intégrale peut aussi s'écrire sous la forme

${\displaystyle \sum _{k=\alpha }^{n}{n \choose k}(-1)^{k}f(k)=-{\frac {1}{2\pi {\rm {i}}}}\oint _{\gamma }\mathrm {B} (n+1,-z)f(z)\,{\rm {d}}z}$

où B(a,b) est la fonction bêta d'Euler. Si la fonction f(x) est polynomialement bornée sur la droite du plan complexe, alors le contour peut être étendu à l'infini à droite, ce qui donne la formule suivante

${\displaystyle \sum _{k=\alpha }^{n}{n \choose k}(-1)^{n-k}f(k)={\frac {-n!}{2\pi {\rm {i}}}}\int _{c-i\infty }^{c+i\infty }{\frac {f(z)}{z(z-1)(z-2)\cdots (z-n)}}\,{\rm {d}}z}$

où la constante c est à la gauche de α.

Le cycle Poisson-Mellin-Newton, remarqué par Philippe Flajolet et al. en 1985, est l'observation que la ressemblance de l'intégrale de Nørlund-Rice avec la transformée de Mellin n'est que le reflet d'une transformation binomiale et d'une série de Newton. Dans ce cycle, soit ${\displaystyle \{f_{n}\}}$ une suite, et soit g(t) la série génératrice de Poisson correspondante, c'est-à-dire

${\displaystyle g(t)={\rm {e}}^{-t}\sum _{n=0}^{\infty }f_{n}t^{n}.}$

En prenant sa transformée de Mellin

${\displaystyle \phi (s)=\int _{0}^{\infty }g(t)t^{s-1}\,{\rm {d}}t,}$

on peut retrouver la suite d'origine au moyen de l'intégrale de Nørlund-Rice :

${\displaystyle f_{n}={\frac {(-1)^{n}}{2\pi {\rm {i}}}}\int _{\gamma }{\frac {\phi (s)}{\Gamma (-s)}}{\frac {n!}{s(s-1)\cdots (s-n)}}\,{\rm {d}}s}$

où Γ est la fonction gamma.

Une intégrale intimement reliée à cette discussion apparaît dans les moyennes de Riesz. On peut en un sens dire qu'elles sont reliées à l'intégrale de Nørlund-Rice de la même façon que la formule de Perron est relié à la transformée de Mellin : plutôt que manipuler une série infinie, cela manipule une série finie.

La représentation intégrale de ces séries est intéressante car l'intégrale peut souvent être évaluée en utilisant un développement asymptotique ou une méthode du point col ; à l'inverse, la différence finie peut être extrêmement difficile à évaluer numériquement, car les coefficients binomiaux croissent rapidement pour de grande valeur de n.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Nørlund–Rice integral » (voir la liste des auteurs).
• (de) Niels Erik Nörlund, Vorlesungen uber Differenzenrechnung, 1954, Chelsea Publishing Company, New York.
• (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition]
• (en) Philippe Flajolet et Robert Sedgewick, « « Mellin transforms and asymptotics: Finite differences and Rice's integrals »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)} », Theoretical Computer Science, vol. 144, 1995, p. 101-124.
• (en) Peter Kirschenhofer, « A Note on Alternating Sums », Electronic Journal of Combinatorics, vol. 3, n^o 2, 1996, article 7.

Table de séries de Newton (en)