Integral de Nørlund-Rice

En matemàtiques, la integral de Nørlund-Rice, de vegades anomenada mètode de Rice, relaciona la n-èsima diferència progressiva d'una funció amb una integral curvilínia al pla complex. Com a tal, apareix comunament en la teoria de les diferències finites i també s'ha aplicat a la informàtica i la teoria de grafs per estimar les longituds d'arbres binaris. Es denomina en honor de Niels Erik Nørlund i Stephen O. Rice. La contribució de Nørlund va ser definir la integral; la contribució de Rice va ser demostrar la seva utilitat mitjançant l'aplicació de tècniques de punt de sella a la seva avaluació.

Definició

La n-èsima diferència progressiva de la funció f(x) és

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

on ${n \choose k}$ és el coeficient binomial.

La integral de Nörlund–Rice és

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

on f s'entén que és meromorfa, α és un enter, $0\leq \alpha \leq n$, i el contorn de la integració s'entén que és el cercle de pols situats als enters α, ..., n, però no envolta cap nombre enter 0, ..., $\alpha -1$ ni cap dels pols de f. La integral també es pot escriure com

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

on B(a,b) és la funció beta d'Euler. Si la funció $f(z)$ està polinomialment limitada a la part dreta del pla complex, llavors el contorn pot ser estès a l'infinit a la banda dreta, permetent escriure la transformació com

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

on la constant c és a l'esquerra d' α.

El cicle Poisson–Mellin–Newton

El cicle Poisson-Mellin-Newton, descrit per Flajolet et al. el 1985, és l'observació que la semblança de la integral de Nørlund-Rice amb la transformada de Mellin no és accidental, sinó que es relaciona mitjançant la transformada binomial i les sèries de Newton. En aquest cicle, fem que $\{f_{n}\}$sigui una seqüència, i fem que g(t) ser la funció generatriu de Poisson corresponent, és a dir, fem que

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

Prenent la seva transformada de Mellin

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

llavors es pot recuperar la seqüència original mitjançant la integral 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$

on Γ és la funció gamma.

La mitjana de Riesz

Una integral estretament relacionada apareix sovint en la discussió de la mitjana de Riesz. De manera molt aproximada, es pot dir que està relacionada amb la integral de Nörlund-Rice de la mateixa manera que la fórmula de Perron està relacionada amb la transformada de Mellin; en lloc de tractar amb sèries infinites, tracta de sèries finites.

Utilitat

La representació integral d'aquests tipus de sèries és interessant perquè la integral sovint es pot avaluar utilitzant tècniques de desenvolupament asimptòtic o de punt de sella; per contra, les sèries de diferència progressiva poden ser extremadament difícils d'avaluar numèricament, ja que els coeficients binomials creixen ràpidament per a n grans.

Referències

• Niels Erik Nørlund, Vorlesungen uber Differenzenrechnung, (1954) Chelsea Publishing Company, New York.
• Donald E. Knuth, The Art of Computer Programming, (1973), Vol. 3 Addison-Wesley.
• Philippe Flajolet and Robert Sedgewick, "Mellin transforms and asymptotics: Finite differences and Rice's integrals", Theoretical Computer Science 144 (1995) pp 101–124.
• Peter Kirschenhofer, "A Note on Alternating Sums"  PDF, The Electronic Journal of Combinatorics, Volume 3 (1996) Issue 2 Article 7.

Vegeu també

• Llista de sèries newtonianes