Méthode de Rice

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, la méthode de Rice (aussi appelée intégrale de Nörlund–Rice) relie la n-ième différence finie d'une fonction à une intégrale curviligne dans le plan complexe. Comme telle, elle apparait souvent dans la théorie des différences finies, et trouve des applications en informatique et en théorie des graphes pour estimer des longueurs d'arbre binaire. Elle ainsi appelée en l'honneur de Niels Erik Nörlund et de Stephen O. Rice. La contribution de Nörlund fut de définir l'intégrale, tandis que la contribution de Rice a consisté à illustrer son utilité en l'évaluant par la méthode du point col.

Définition[modifier | modifier le code]

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

\Delta^n[f](x)= \sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x+k)

{n \choose k} est le coefficient binomial.

L'intégrale de Nörlund–Rice est donnée par

\sum_{k=\alpha}^n {n \choose k} (-1)^{n-k} f(k) = 
\frac{n!}{2\pi i}
\oint_\gamma \frac{f(z)}{z(z-1)(z-2)\cdots(z-n)}\, dz

f est méromorphe, α est un entier, 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

\sum_{k=\alpha}^n {n \choose k} (-1)^{k} f(k) = 
-\frac{1}{2\pi i}
\oint_\gamma B(n+1, -z) f(z)\, dz

B(a,b) est la fonction bêta d'Euler. Si la fonction f(z) 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

\sum_{k=\alpha}^n {n \choose k} (-1)^{n-k} f(k) = 
\frac{-n!}{2\pi i}
\int_{c-i\infty}^{c+i\infty} \frac{f(z)}{z(z-1)(z-2)\cdots(z-n)}\, dz

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

Le cycle Poisson–Mellin–Newton[modifier | modifier le code]

Le cycle Poisson–Mellin–Newton, noté par Philippe Flajolet et al. in 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 cyle, soit \{f_n\} une suite, et soit g(t) la série génératrice de Poisson correspondante, c'est-à-dire

g(t) = e^{-t} \sum_{n=0}^\infty f_n t^n.

En prenant sa transformée de Mellin

\phi(s)=\int_0^\infty g(t) t^{s-1}\, dt,

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

f_n = \frac{(-1)^n }{2\pi i} 
\int_\gamma 
\frac {\phi(s)}{\Gamma(-s)} \frac{n!}{s(s-1)\cdots (s-n)}\, ds

où Γ est la fonction gamma.

Moyenne de Riesz[modifier | modifier le code]

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.

Utilité[modifier | modifier le code]

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.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]