Интеграл Норлунда — Райса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править вики-текст]

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

\Delta^n[f](x)= \sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x+k),
где
{n \choose k} — Биномиальный коэффициент.

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

\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
для 0 \leqslant \alpha \leqslant n (\alpha \in \mathbb {N}).

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

\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) — бета-функция Эйлера.

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

\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,
где
c<\alpha

Цикл Пуассона — Меллина — Ньютона[править | править вики-текст]

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

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

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

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

f_n = \frac{(-1)^n }{2\pi i} \int_\gamma \frac {\phi(s)}{\Gamma(-s)} \frac{n!}{s(s-1)\cdots (s-n)}\, ds,
где
\Gamma — гамма-функция.

Применение[править | править вики-текст]

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]