Русская Википедия:Интеграл Норлунда — Райса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Интеграл Норлунда — Райса (метод Райса) — интеграл, связывающий <math>n</math> конечных разностей с криволинейным интегралом в комплексной плоскости. Интеграл используется в теории конечных разностей, а также в Информатике и теории графов для оценки длины двоичного дерева.

Интеграл назван в честь Нильса Э. Норлунда и Стефана О. Райса; Норлунд определил интеграл; Райс нашёл ему применение в методе перевала.

Определение

Для мероморфной функции <math>f</math> <math>n</math>-ю конечную разность <math>\Delta^n[f](x)</math> можно представить в виде:

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

где

<math>{n \choose k}</math> — Биномиальный коэффициент.

Переходя к интегрированию в окрестности полюсов точек <math>\alpha \ldots n</math> и при условии, что функция <math>f</math> полюсов не имеет, получим:

<math>\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)\ldots(z-n)}\, dz</math>

для <math>0 \leqslant \alpha \leqslant n (\alpha \in \mathbb {N})</math>.

Интеграл также можно записать в виде:

<math>\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,</math>

где

<math>B(a,b)</math> — бета-функция Эйлера.

Если функция <math>f</math> полиномиально ограничена, например, справа, то интеграл можно продлить направо до бесконечности, получив запись:

<math>\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,</math>

где

<math>c<\alpha</math>

Цикл Пуассона — Меллина — Ньютона

Пусть <math>\{f_n\}</math> — некая последовательность и пусть <math>g(t)</math> — некая производящая функция последовательности, причём <math>g(t) = e^{-t} \sum_{n=0}^\infty f_n t^n.</math>

Используя преобразование Меллина, получим, что

<math>\phi(s)=\int_0^\infty g(t) t^{s-1}\, dt.</math>

Тогда можно найти исходную последовательность с помощью интеграла Норлунда — Райса:

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

где

<math>\Gamma</math> — гамма-функция.

Применение

Это интегральное представление интересно тем, что интеграл Норлунда — Райса часто может быть оценён с использованием методов асимптотического разложения или методом перевала.

См. также

• Биномиальное преобразование

Литература

• 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», The Electronic Journal of Combinatorics, Volume 3 (1996) Issue 2 Article 7.