Norlund-Rice integrală

Integrala Norlund-Rice ( metoda Rice ) este o integrală care leagă diferențele finite cu o integrală curbilinie în planul complex . Integrala este folosită în teoria diferențelor finite și în informatică și teoria graficelor pentru a estima lungimea unui arbore binar . $n$

Integrala este numită după Niels E. Norlund și Stefan O. Rice ; Norlund a definit integrala; Orezul a găsit o utilizare pentru el în metoda de trecere .

Definiție

Pentru o funcție meromorfă , diferența finită poate fi reprezentată ca: $f$ $n$ $\Delta ^{n}[f](x)$

\Delta ^{n}[f](x)=\sum _{k=0}^{n}{n \alegeți k}(-1)^{nk}f(x+k),

Unde

{n \alege k)

— Coeficient binomial .

Trecând la integrarea în vecinătatea polilor punctelor și cu condiția ca funcția să nu aibă poli, obținem: $\alpha \ldots n$ $f$

\sum _{k=\alpha }^{n}{n \alegeți k}(-1)^{nk}f(k)={\frac {n!}{2\pi i}}\ unt _{\gamma }{\frac {f(z)}{z(z-1)(z-2)\ldots (zn)))\,dz

pentru .

0\leqslant \alpha \leqslant n(\alpha \in \mathbb {N} )

Integrala poate fi scrisă și ca:

\sum _{k=\alpha }^{n}{n \alegeți k}(-1)^{k}f(k)=-{\frac {1}{2\pi i}}\ unt _{\gamma }B(n+1,-z)f(z)\,dz,

Unde

B(a,b)

este funcția beta Euler .

Dacă funcția este mărginită polinomial, de exemplu, la dreapta, atunci integrala poate fi extinsă la dreapta la infinit, obținându-se notația: $f$

\sum _{k=\alpha }^{n}{n \alegeți 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,

Unde

c<\alpha

Ciclul Poisson-Mellin-Newton

Să fie o secvență și să fie o funcție generatoare a secvenței și $\{f_{n}\}$ $g(t)$ $g(t)=e^{-t}\sum _{n=0}^{\infty }f_{n}t^{n}.$

Folosind transformarea Mellin , obținem asta

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

Apoi puteți găsi secvența originală folosind integrala Norlund-Rice:

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

Unde

\Gamma

este funcția gamma .

Aplicație

Această reprezentare integrală este interesantă prin faptul că integrala Norlund-Rice poate fi adesea estimată folosind metode de expansiune asimptotică sau metoda punctului de șa .

Vezi și

Transformare binomială

Literatură

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 și Robert Sedgewick, „ Mellin transforms and asymptotics: Finite differences and Rice's integrals (link indisponibil) ”, Theoretical Computer Science 144 (1995) pp. 101–124.
Peter Kirschenhofer, „ A Note on Alternating Sums ”, The Electronic Journal of Combinatorics , Volumul 3 (1996) Numărul 2 Articolul 7.