Интеграл Норлунда — Райса (метод Райса) — интеграл, связывающий
конечных разностей с криволинейным интегралом в комплексной плоскости. Интеграл используется в теории конечных разностей, а также в Информатике и теории графов для оценки длины двоичного дерева.
Интеграл назван в честь Нильса Э. Норлунда и Стефана О. Райса; Норлунд определил интеграл; Райс нашёл ему применение в методе перевала.
Определение
Для мероморфной функции
-ю конечную разность
можно представить в виде:
- где
— Биномиальный коэффициент.
Переходя к интегрированию в окрестности полюсов точек
и при условии, что функция
полюсов не имеет, получим:
- для
.
Интеграл также можно записать в виде:
- где
— бета-функция Эйлера.
Если функция
полиномиально ограничена, например, справа, то интеграл можно продлить направо до бесконечности, получив запись:
- где
![{\displaystyle c<\alpha }](https://wikimedia.org/api/rest_v1/media/math/render/svg/da1cd6721ba58ec11cba5341b774b02af32a93a3)
Цикл Пуассона — Меллина — Ньютона
Пусть
— некая последовательность и пусть
— некая производящая функция последовательности, причём
Используя преобразование Меллина, получим, что
![{\displaystyle \phi (s)=\int _{0}^{\infty }g(t)t^{s-1}\,dt.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53cd6213c0f13502b8eb9612142edebb11977ffe)
Тогда можно найти исходную последовательность с помощью интеграла Норлунда — Райса:
- где
— гамма-функция.
Применение
Это интегральное представление интересно тем, что интеграл Норлунда — Райса часто может быть оценён с использованием методов асимптотического разложения или методом перевала.
См. также
Литература
- 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.
Эта страница в последний раз была отредактирована 25 марта 2019 в 16:27.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.