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

В математике интеграл Норлунда -Райса , иногда называемый методом Райса , связывает n- ю прямую разность функции с линейным интегралом на комплексной плоскости . Он обычно появляется в теории конечных разностей , а также применяется в информатике и теории графов для оценки длины двоичного дерева . Он назван в честь Нильса Эрика Норлунда и Стивена О. Райса . Вклад Норлунда заключался в определении интеграла; Вклад Райс заключался в том, чтобы продемонстрировать его полезность, применив для его оценки методы седловой точки .

Определение

n -я прямая разность функции f ( x ) определяется выражением

$\Delta ^{n}[f](x)=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}f(x+k)$

где ${n \choose k}$ – биномиальный коэффициент .

Интеграл Нёрлунда – Райса имеет вид

$\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)\cdots (z-n)}}\,dz$

где f считается мероморфным , α — целое число, $0\leq \alpha \leq n$, а контуром интегрирования считается обводка полюсов, расположенных в целых числах α, ..., n , но не охватывающая ни целых чисел 0, ..., $\alpha -1$ ни один из полюсов f . Интеграл также можно записать как

$\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(z)$ в полиномиально ограничен правой части комплексной плоскости, то контур можно расширить до бесконечности в правой части, что позволяет записать преобразование в виде

$\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 находится слева от α.

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

Цикл Пуассона-Меллина-Ньютона, отмеченный Флажоле и др. в 1985 году является наблюдением о том, что сходство интеграла Норлунда–Райса с преобразованием Меллина не случайно, а связано посредством биномиального преобразования и ряда Ньютона . Пусть в этом цикле $\{f_{n}\}$ — последовательность , и пусть g ( t ) — соответствующая производящая функция Пуассона , то есть пусть

$g(t)=e^{-t}\sum _{n=0}^{\infty }{\frac {t^{n}}{n!}}f_{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$

где Γ — гамма-функция , которая сокращается с гаммой из Главной теоремы Рамануджана .

Рисс означает

Тесно связанный интеграл часто встречается при обсуждении средних значений Рисса . Грубо говоря, можно сказать, что она связана с интегралом Нёрлунда – Райса так же, как формула Перрона связана с преобразованием Меллина: вместо бесконечных серий она имеет дело с конечными сериями.

Утилита

Интегральное представление для этих типов рядов интересно, потому что интеграл часто можно вычислить с использованием асимптотического разложения или перевала методов ; напротив, ряд прямых разностей может быть чрезвычайно сложно оценить численно, поскольку биномиальные коэффициенты быстро растут при больших n .

См. также

• Таблица ньютоновских рядов
• Список факториальных и биномиальных тем

Ссылки

• Нильс Эрик Норлунд, Лекции по разностному исчислению , (1954) Издательство Челси, Нью-Йорк.
• Дональд Э. Кнут, Искусство компьютерного программирования , (1973), Vol. 3 Аддисон-Уэсли.
• Филипп Флажоле и Роберт Седжвик, « Преобразования Меллина и асимптотика: конечные разности и интегралы Райса », Theoretical Computer Science 144 (1995), стр. 101–124.
• Питер Киршенхофер, « [1] », Электронный журнал комбинаторики , Том 3 (1996), Выпуск 2, Статья 7.
• Филипп Флажоле, лекция « Меллин, вид с неба », стр. 35 .