Nørlund–Ris integral

I matematik relaterar Nørlund–Rice-integralen, ibland kallad Rice's metod, den n: te framåtskillnaden mellan en funktion och en linjeintegral på det komplexa planet . Det förekommer vanligtvis i teorin om ändliga skillnader och har också använts inom datavetenskap och grafteori för att uppskatta binära trädlängder. Den är döpt efter Niels Erik Nørlund och Stephen O. Rice . Nørlunds bidrag var att definiera integralen; Rice bidrag var att demonstrera dess användbarhet genom att tillämpa sadelpunktstekniker för sin utvärdering.

Definition

Den n :te framåtriktade skillnaden för en funktion f ( x ) ges av

$\Delta ^{n}[f](x)=\summa _{ k=0}^{n}{n \välj k}(-1)^{nk}f(x+k)$

där ${n \choose k}$ är binomialkoefficienten .

Nörlund–Ris-integralen ges av

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

där f förstås vara meromorft , α är ett heltal, $0\leq \alpha \leq n$ , och integrationskonturen förstås cirkla runt polerna placerade vid heltalen α, ... , n , men omger varken heltal 0, ..., $\alpha -1$ eller någon av polerna i f . Integralen kan också skrivas som

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

där B ( a , b ) är Eulers betafunktion . Om funktionen $f(z)$ är polynomiellt begränsad på höger sida av det komplexa planet, kan konturen förlängas till oändlighet på höger sida, vilket gör att transformationen kan skrivas som

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

där konstanten c är till vänster om α.

Poisson–Mellin–Newton-cykeln

Poisson-Mellin-Newton-cykeln, noterad av Flajolet et al. 1985, är observationen att likheten mellan Nørlund-Rice-integralen och Mellin-transformen inte är oavsiktlig, utan är relaterad med hjälp av binomialtransformen och Newton-serien . I denna cykel, låt $\{f_{n}\}$ vara en sekvens och låt g ( t ) vara motsvarande Poisson-genererande funktion , det vill säga låt

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

Tar sin Mellin-förvandling

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

man kan då återta den ursprungliga sekvensen med hjälp av Nörlund–Rice-integralen:

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

där Γ är gammafunktionen .

Riesz menar

En närbesläktad integral förekommer ofta i diskussionen om Riesz betyder . Mycket grovt kan man säga att den är relaterad till Nörlund–Rice-integralen på samma sätt som Perrons formel är relaterad till Mellintransformen: snarare än att behandla oändliga serier, handlar den om finita serier.

Verktyg

Integralrepresentationen för dessa typer av serier är intressant eftersom integralen ofta kan utvärderas med hjälp av asymptotisk expansion eller sadelpunktstekniker ; däremot kan den framåtriktade skillnadsserien vara extremt svår att utvärdera numeriskt, eftersom de binomiala koefficienterna växer snabbt för stora n .

Se även

• Tabell över Newtonska serier
• Lista över faktoriella och binomiska ämnen

• 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 och Robert Sedgewick, " Mellin transforms and asymptotics: Finite differences and Rice's integrals ", Theoretical Computer Science 144 (1995) s 101–124.
• Peter Kirschenhofer, " [1] ", The Electronic Journal of Combinatorics , Volym 3 (1996) Issue 2 Artikel 7.