Приближение Стирлингса - Википедия - Stirlings approximation

Сравнение приближения Стирлинга с факториалом

В математика, Приближение Стирлинга (или же Формула Стирлинга) является приближением для факториалы. Это хорошее приближение, приводящее к точным результатам даже для небольших значений п. Он назван в честь Джеймс Стирлинг, хотя впервые об этом заявил Авраам де Муавр.^[1][2][3]

Версия формулы, обычно используемая в приложениях:

${ Displaystyle пер п! = п пер п-п + О ( пер п)}$

(в нотация большой O, так как ${ displaystyle n to infty}$) или изменением основания логарифма (например, в нижняя граница наихудшего случая для сравнительной сортировки ),

${ displaystyle log _ {2} n! = n log _ {2} n-n log _ {2} e + O ( log _ {2} n).}$

Указание константы в О(ln п) термин ошибки дает 1/2ln (2πn), что дает более точную формулу:

${ displaystyle n! sim { sqrt {2 pi n}} left ({ frac {n} {e}} right) ^ {n},}$

где знак ~ означает, что две величины асимптотический: их отношение стремится к 1 при п стремится к бесконечности.

Можно также дать простые оценки, действительные для всех положительных целых чисел п, а не только для больших п:

${ displaystyle { sqrt {2 pi}} n ^ {n + { frac {1} {2}}} e ^ {- n} leq n! leq e n ^ {n + { frac { 1} {2}}} e ^ {- n}}$

за ${ Displaystyle п = 1,2,3, ldots}$. Это следует из более точные границы ошибок обсуждается ниже.

Вывод

Грубо говоря, простейший вариант формулы Стирлинга можно быстро получить, аппроксимируя сумму

${ Displaystyle пер п! = сумма _ {j = 1} ^ {п} пер j}$

с интеграл:

${ displaystyle sum _ {j = 1} ^ {n} ln j приблизительно int _ {1} ^ {n} ln x , { rm {d}} x = n ln n-n +1.}$

Полная формула вместе с точными оценками ее погрешности может быть получена следующим образом. Вместо приближения п!считается натуральный логарифм, так как это медленно меняющаяся функция:

${ displaystyle ln n! = ln 1+ ln 2+ cdots + ln n.}$

Правая часть этого уравнения минус

${ Displaystyle { tfrac {1} {2}} ( ln 1+ ln n) = { tfrac {1} {2}} ln n}$

это приближение правило трапеции интегрального

${ displaystyle ln n! - { tfrac {1} {2}} ln n приблизительно int _ {1} ^ {n} ln x , { rm {d}} x = n ln п-п + 1,}$

и ошибка в этом приближении дается Формула Эйлера – Маклорена:

${ displaystyle { begin {align} ln n! - { tfrac {1} {2}} ln n & = { tfrac {1} {2}} ln 1+ ln 2+ ln 3+ cdots + ln (n-1) + { tfrac {1} {2}} ln n & = n ln n-n + 1 + sum _ {k = 2} ^ {m} { frac {(-1) ^ {k} B_ {k}} {k (k-1)}} left ({ frac {1} {n ^ {k-1}}} - 1 right) + R_ {m, n}, end {align}}}$

куда B_k это Число Бернулли, и р_м,п - остаточный член в формуле Эйлера – Маклорена. Возьмите пределы, чтобы найти это

${ displaystyle lim _ {n to infty} left ( ln n! -n ln n + n - { tfrac {1} {2}} ln n right) = 1- sum _ {k = 2} ^ {m} { frac {(-1) ^ {k} B_ {k}} {k (k-1)}} + lim _ {n to infty} R_ {m, n}.}$

Обозначим этот предел как у. Потому что остаток р_м,п в Формула Эйлера – Маклорена удовлетворяет

${ displaystyle R_ {m, n} = lim _ {n to infty} R_ {m, n} + O left ({ frac {1} {n ^ {m}}} right),}$

куда нотация big-O , объединение приведенных выше уравнений дает формулу аппроксимации в ее логарифмической форме:

${ displaystyle ln n! = п ln left ({ frac {n} {e}} right) + { tfrac {1} {2}} ln n + y + sum _ {k = 2 } ^ {m} { frac {(-1) ^ {k} B_ {k}} {k (k-1) n ^ {k-1}}} + O left ({ frac {1} { n ^ {m}}} right).}$

Взяв экспоненту с обеих сторон и выбрав любое положительное целое число м, получается формула с неизвестной величиной е^у. За м = 1, формула

${ displaystyle n! = e ^ {y} { sqrt {n}} left ({ frac {n} {e}} right) ^ {n} left (1 + O left ({ frac {1} {n}} right) right).}$

Количество е^у можно найти, взяв предел с обеих сторон как п стремится к бесконечности и используя Продукт Уоллиса, что показывает, что е^у = √2π. Таким образом, получается формула Стирлинга:

${ displaystyle n! = { sqrt {2 pi n}} left ({ frac {n} {e}} right) ^ {n} left (1 + O left ({ frac {1 } {n}} right) right).}$

Альтернативный вывод

Альтернативная формула для п! с использованием гамма-функция является

${ displaystyle n! = int _ {0} ^ { infty} x ^ {n} e ^ {- x} , { rm {d}} x.}$

(что видно при многократном интегрировании по частям). Переписывание и изменение переменных Икс = нью-йорк, получается

${ Displaystyle п! = int _ {0} ^ { infty} e ^ {n ln xx} , { rm {d}} x = e ^ {n ln n} n int _ {0 } ^ { infty} e ^ {n ( ln yy)} , { rm {d}} y.}$

Применение Метод Лапласа надо

${ displaystyle int _ {0} ^ { infty} e ^ {n ( ln yy)} , { rm {d}} y sim { sqrt { frac {2 pi} {n} }} e ^ {- n},}$

который восстанавливает формулу Стирлинга:

${ displaystyle n! sim e ^ {n ln n} n { sqrt { frac {2 pi} {n}}} e ^ {- n} = { sqrt {2 pi n}} left ({ frac {n} {e}} right) ^ {n}.}$

Фактически, дальнейшие поправки также могут быть получены с использованием метода Лапласа. Например, вычисление разложения двух порядков с использованием метода Лапласа дает

${ displaystyle int _ {0} ^ { infty} e ^ {n ( ln yy)} , { rm {d}} y sim { sqrt { frac {2 pi} {n} }} e ^ {- n} left (1 + { frac {1} {12n}} right)}$

и дает формулу Стирлинга двум порядкам:

${ displaystyle n! sim e ^ {n ln n} n { sqrt { frac {2 pi} {n}}} e ^ {- n} left (1 + { frac {1} { 12n}} right) = { sqrt {2 pi n}} left ({ frac {n} {e}} right) ^ {n} left (1 + { frac {1} {12n }}верно).}$

Версия этого метода для комплексного анализа^[4] рассматривать ${ displaystyle { frac {1} {п!}}}$ как Коэффициент Тейлора экспоненциальной функции ${ displaystyle e ^ {z} = sum _ {n = 0} ^ { infty} { frac {z ^ {n}} {n!}}}$, рассчитанный Интегральная формула Коши в качестве

${ displaystyle { frac {1} {n!}} = { frac {1} {2 pi i}} oint limits _ {| z | = r} { frac {e ^ {z}} {z ^ {n + 1}}} , mathrm {d} z.}$

Затем этот линейный интеграл можно аппроксимировать с помощью метод перевала при соответствующем выборе обратного радиуса ${ displaystyle r = r_ {n}}$. Преобладающая часть интеграла около седловой точки затем аппроксимируется действительным интегралом и методом Лапласа, тогда как оставшаяся часть интеграла может быть ограничена сверху, чтобы получить член ошибки.

Скорость сходимости и оценки ошибок

Относительная ошибка в усеченном ряду Стирлинга vs. п, от 0 до 5 членов. Изломы на кривых представляют собой точки, в которых усеченный ряд совпадает с Γ (п + 1).

Формула Стирлинга фактически является первым приближением к следующей серии (теперь называемой Серия Стирлинга^[5]):

${ displaystyle n! sim { sqrt {2 pi n}} left ({ frac {n} {e}} right) ^ {n} left (1 + { frac {1} {12n }} + { frac {1} {288n ^ {2}}} - { frac {139} {51840n ^ {3}}} - { frac {571} {2488320n ^ {4}}} + cdots верно).}$

Явная формула для коэффициентов этого ряда была дана Г. Немесом.^[6][а] Первый график в этом разделе показывает относительная ошибка против. п, от 1 до всех 5 перечисленных выше терминов.

Относительная ошибка в усеченном ряду Стирлинга в зависимости от количества используемых терминов

В качестве п → ∞, ошибка в усеченном ряду асимптотически равна первому пропущенному члену. Это пример асимптотическое разложение. Это не сходящийся ряд; для любого частности значение п есть только определенное количество членов ряда, которые улучшают точность, после чего точность ухудшается. Это показано на следующем графике, который показывает относительную ошибку в зависимости от количества членов в серии для большего количества членов. Точнее, пусть S(п, т) быть серией Стирлинга т сроки оцениваются вп. Графики показывают

${ displaystyle left | ln left ({ frac {S (n, t)} {n!}} right) right |,}$

что, когда оно мало, по сути является относительной ошибкой.

Написание серии Стирлинга в виде

${ displaystyle ln n! sim n ln n-n + { tfrac {1} {2}} ln (2 pi n) + { frac {1} {12n}} - { frac {1 } {360n ^ {3}}} + { frac {1} {1260n ^ {5}}} - { frac {1} {1680n ^ {7}}} + cdots,}$

известно, что ошибка при усечении ряда всегда имеет противоположный знак и, самое большее, той же величины, что и первый пропущенный член.

Более точные оценки, сделанные Роббинсом,^[7] действительно для всех положительных целых чисел п находятся

${ displaystyle { sqrt {2 pi}} n ^ {n + { frac {1} {2}}} e ^ {- n} e ^ { frac {1} {12n + 1}}$

Формула Стирлинга для гамма-функции

Для всех положительных целых чисел

${ Displaystyle п! = Гамма (п + 1),}$

куда Γ обозначает гамма-функция.

Однако гамма-функция, в отличие от факториала, более широко определена для всех комплексных чисел, кроме неположительных целых; тем не менее, формула Стирлинга все еще может применяться. Если Re (z) > 0, тогда

${ Displaystyle ln Gamma (z) = z ln z-z + { tfrac {1} {2}} ln { frac {2 pi} {z}} + int _ {0} ^ { infty} { frac {2 arctan left ({ frac {t} {z}} right)} {e ^ {2 pi t} -1}} , { rm {d}} т .}$

Повторное интегрирование по частям дает

${ displaystyle ln Gamma (z) sim z ln z-z + { tfrac {1} {2}} ln { frac {2 pi} {z}} + sum _ {n = 1 } ^ {N-1} { frac {B_ {2n}} {2n (2n-1) z ^ {2n-1}}},}$

куда B_п это п-го Число Бернулли (обратите внимание, что предел суммы как ${ displaystyle N to infty}$ не сходится, поэтому эта формула - просто асимптотическое разложение ). Формула верна для z достаточно большой по абсолютной величине, когда |аргумент (z)| <π - ε, куда ε положительный, со сроком погрешности О(z^{−2N+ 1}). Соответствующее приближение теперь можно записать:

${ displaystyle Gamma (z) = { sqrt { frac {2 pi} {z}}} , { left ({ frac {z} {e}} right)} ^ {z} left (1 + O left ({ frac {1} {z}} right) right).}$

где расширение идентично разложению приведенной выше серии Стирлинга для n !, за исключением того, что n заменено на z-1.^[8]

Дальнейшее применение этого асимптотического разложения для комплексного аргумента z с постоянным Re (z). См., Например, формулу Стирлинга, примененную в Я(z) = т из Тета-функция Римана – Зигеля по прямой 1/4 + Это.

Границы ошибок

Для любого положительного целого числа Nвводятся следующие обозначения:

${ Displaystyle ln Gamma (z) = z ln z-z + { tfrac {1} {2}} ln { frac {2 pi} {z}} + sum limits _ {n = 1} ^ {N-1} { frac {B_ {2n}} {2n left ({2n-1} right) z ^ {2n-1}}} + R_ {N} (z)}$

и

${ displaystyle Gamma (z) = { sqrt { frac {2 pi} {z}}} left ({ frac {z} {e}} right) ^ {z} left ({ sum limits _ {n = 0} ^ {N-1} { frac {a_ {n}} {z ^ {n}}} + { widetilde {R}} _ {N} (z)} right ).}$

потом ^[9][10]

${ displaystyle { begin {align} | R_ {N} (z) | & leq { frac {| B_ {2N} |} {2N (2N-1) | z | ^ {2N-1}}} { begin {cases} 1 & { text {if}} | arg z | leq { frac { pi} {4}}, | csc ( arg z) | & { text {if }} { frac { pi} {4}} <| arg z | <{ frac { pi} {2}}, sec ^ {2N} left ({ tfrac { arg z } {2}} right) & { text {if}} | arg z | < pi, end {cases}} [6pt] left | { widetilde {R}} _ {N} (z) right | & leq left ({ frac { left | a_ {N} right |} {| z | ^ {N}}} + { frac { left | a_ {N + 1 } right |} {| z | ^ {N + 1}}} right) { begin {cases} 1 & { text {if}} | arg z | leq { frac { pi} {4 }}, | csc ( arg z) | & { text {if}} { frac { pi} {4}} <| arg z | <{ frac { pi} {2} }. end {case}} end {align}}}$

Для получения дополнительной информации и других границ ошибок см. Цитируемые статьи.

Конвергентная версия формулы Стирлинга

Томас Байес показал в письме к Джон Кантон опубликовано Королевское общество в 1763 г. формула Стирлинга не давала сходящийся ряд.^[11] Получение сходящейся версии формулы Стирлинга влечет за собой оценку Формула Раабе:

${ displaystyle int _ {0} ^ { infty} { frac {2 arctan left ({ frac {t} {x}} right)} {e ^ {2 pi t} -1} } , { rm {d}} t = ln Gamma (x) -x ln x + x - { tfrac {1} {2}} ln { frac {2 pi} {x} }.}$

Один из способов сделать это - использовать сходящийся ряд инвертированных возрастающие экспоненты. Если

${ displaystyle z ^ { bar {n}} = z (z + 1) cdots (z + n-1),}$

тогда

${ displaystyle int _ {0} ^ { infty} { frac {2 arctan left ({ frac {t} {x}} right)} {e ^ {2 pi t} -1} } , { rm {d}} t = sum _ {n = 1} ^ { infty} { frac {c_ {n}} {(x + 1) ^ { bar {n}}}} ,}$

куда

${ displaystyle c_ {n} = { frac {1} {n}} int _ {0} ^ {1} x ^ { bar {n}} left (x - { tfrac {1} {2 }} right) , { rm {d}} x = { frac {1} {2n}} sum _ {k = 1} ^ {n} { frac {k | s (n, k) |} {(k + 1) (k + 2)}},}$

куда s(п, k) обозначает Числа Стирлинга первого рода. Отсюда получается версия серии Стирлинга.

${ displaystyle { begin {align} ln Gamma (x) & = x ln x-x + { tfrac {1} {2}} ln { frac {2 pi} {x}} + { frac {1} {12 (x + 1)}} + { frac {1} {12 (x + 1) (x + 2)}} + & quad + { frac {59} {360 (x + 1) (x + 2) (x + 3)}} + { frac {29} {60 (x + 1) (x + 2) (x + 3) (x + 4)}} + cdots, end {align}}}$

который сходится, когда Re (Икс) > 0.

Версии для калькуляторов

Приближение

${ displaystyle Gamma (z) приблизительно { sqrt { frac {2 pi} {z}}} left ({ frac {z} {e}} { sqrt {z sinh { frac { 1} {z}} + { frac {1} {810z ^ {6}}}}} right) ^ {z}}$

и его эквивалентная форма

${ displaystyle 2 ln Gamma (z) приблизительно ln (2 pi) - ln z + z left (2 ln z + ln left (z sinh { frac {1} {z}) } + { frac {1} {810z ^ {6}}} right) -2 right)}$

может быть получен путем перестановки расширенной формулы Стирлинга и наблюдения совпадения между результирующим степенным рядом и Серия Тейлор расширение гиперболический синус функция. Это приближение подходит для более чем 8 десятичных цифр для z с действительной частью больше 8. Роберт Х. Виндшитль предложил его в 2002 году для вычисления гамма-функции с хорошей точностью на калькуляторах с ограниченной памятью программ или регистров.^[12]

В 2007 году Гергё Немес предложил приближение, которое дает такое же количество точных цифр, что и приближение Виндшитля, но намного проще:^[13]

${ displaystyle Gamma (z) приблизительно { sqrt { frac {2 pi} {z}}} left ({ frac {1} {e}} left (z + { frac {1} { 12z - { frac {1} {10z}}}} right) right) ^ {z},}$

или эквивалентно,

${ displaystyle ln Gamma (z) приблизительно { tfrac {1} {2}} left ( ln (2 pi) - ln z right) + z left ( ln left (z + { frac {1} {12z - { frac {1} {10z}}}} right) -1 right).}$

Альтернативное приближение для гамма-функции, сформулированное следующим образом: Шриниваса Рамануджан (Рамануджан 1988^{[требуется разъяснение ]}) является

${ displaystyle Gamma (1 + x) приблизительно { sqrt { pi}} left ({ frac {x} {e}} right) ^ {x} left (8x ^ {3} + 4x ^ {2} + x + { frac {1} {30}} right) ^ { frac {1} {6}}}$

за Икс ≥ 0. Эквивалентное приближение для пер п! имеет асимптотическую ошибку 1/1400п³ и дается

${ displaystyle ln n! приблизительно n ln n-n + { tfrac {1} {6}} ln (8n ^ {3} + 4n ^ {2} + n + { tfrac {1} {30} }) + { tfrac {1} {2}} ln pi.}$

Приближение можно сделать точным, задав парные верхние и нижние границы; одно такое неравенство^{[14][15][16][17]}

${ displaystyle { sqrt { pi}} left ({ frac {x} {e}} right) ^ {x} left (8x ^ {3} + 4x ^ {2} + x + { frac {1} {100}} right) ^ {1/6} < Gamma (1 + x) <{ sqrt { pi}} left ({ frac {x} {e}} right) ^ {x} left (8x ^ {3} + 4x ^ {2} + x + { frac {1} {30}} right) ^ {1/6}.}$

Оценка центрального эффекта в биномиальном распределении

В информатике, особенно в контексте рандомизированные алгоритмы, обычно генерируют случайные битовые векторы, длина которых равна степени двойки. Многие алгоритмы, производящие и использующие эти битовые векторы, чувствительны к подсчет населения сгенерированных битовых векторов или Манхэттенское расстояние между двумя такими векторами. Часто особый интерес представляет плотность "справедливых" векторов, где численность популяции п-битовый вектор точно ${ displaystyle n / 2}$. Это составляет вероятность того, что повторное подбрасывание монеты после многих испытаний приводит к ничьей.

Приближение Стирлинга к ${ Displaystyle {п выбрать п / 2}}$, центральная и максимальная биномиальный коэффициент из биномиальное распределение, особенно хорошо упрощается там, где ${ displaystyle n}$ принимает форму ${ displaystyle 4 ^ {k}}$, для целого числа ${ displaystyle k}$. Здесь нас интересует, насколько уменьшается плотность центрального населения по сравнению с ${ Displaystyle 2 ^ {п}}$, получая последнюю форму в децибел затухание:

${ displaystyle { begin {align} log _ {2} {n choose n / 2} -n & = - k - { frac { log _ {2} ( pi) -1} {2}} + O ( log _ {2} n) & приблизительно -k-0.3257481 & приблизительно -k - { frac {1} {3}} & приблизительно mathbf {3k + 1} ~~ дБ ~ (затухание) end {align}}}$

Это простое приближение демонстрирует удивительную точность:

${ displaystyle { begin {align} 10 log _ {10} (2 ^ {- 1024} {1024 choose 512}) & приблизительно -16.033159 ~~~ { begin {cases} k & = 5 n = 4 ^ {k} & = 1024 3k + 1 & = mathbf {16} end {cases}} 10 log _ {10} (2 ^ {- 1048576} {1048576 choose 524288} ) & приблизительно -31.083600 ~~~ { begin {cases} k & = 10 n = 4 ^ {k} & = 1048576 3k + 1 & = mathbf {31} end {cases}} конец {выровнен}}}$

Двоичное уменьшение получается от дБ при делении на ${ Displaystyle 10 журнал (2) / журнал (10) приблизительно 3,0103 приблизительно 3}$.

В качестве прямой дробной оценки:

${ displaystyle { begin {align} {n choose n / 2} / 2 ^ {n} & = 2 ^ {{ frac {1- log _ {2} ( pi)} {2}} - k} + O (n) & приблизительно { sqrt { frac {2} { pi}}} ~ 2 ^ {- k} & приблизительно 0,7978846 ~ 2 ^ {- k} & приблизительно mathbf {{ frac {4} {5}} 2 ^ {- k}} end {выровнено}}}$

И снова оба примера демонстрируют точность, превосходящую 1%:

${ displaystyle { begin {align} {256 choose 128} 2 ^ {- 256} & приблизительно 20.072619 ^ {- 1} ~~~ { begin {cases} k & = 4 n = 4 ^ {k } & = 256 { frac {4} {5}} times { frac {1} {2 ^ {4}}} & = mathbf {20} ^ {- 1} end {case }} {1048576 choose 524288} 2 ^ {- 1048576} & приблизительно 1283.3940 ^ {- 1} ~~~ { begin {cases} k & = 10 n = 4 ^ {k} & = 1048576 { frac {4} {5}} times { frac {1} {2 ^ {10}}} & = mathbf {1280} ^ {- 1} end {cases}} end {выровнены} }}$

Интерпретируемый повторным подбрасыванием монеты, сеанс, включающий чуть более миллиона подбрасываний монеты (двоичный миллион), имеет один шанс из примерно 1300 закончиться ничьей.

Оба этих приближения (одно в логическом пространстве, другое в линейном пространстве) достаточно просты для многих разработчиков программного обеспечения, чтобы получить оценку мысленно с исключительной точностью по стандартам мысленных оценок.

Биномиальное распределение близко аппроксимирует нормальное распределение для больших ${ displaystyle n}$, поэтому эти оценки, основанные на приближении Стирлинга, также относятся к пиковому значению функция массы вероятности для больших ${ displaystyle n}$ и ${ displaystyle p = 0,5}$, как указано для следующего распределения: ${ Displaystyle { mathcal {N}} (np, , np (1-p))}$.

История

Формула была впервые открыта Авраам де Муавр^[2] в виде

${ displaystyle n! sim [{ rm {constant}}] cdot n ^ {n + { frac {1} {2}}} e ^ {- n}.}$

Де Муавр дал приблизительное выражение в виде рациональных чисел для натурального логарифма константы.Вклад Стирлинга состоял в том, чтобы показать, что постоянная точно равна ${ displaystyle { sqrt {2 pi}}}$.^[3]

Смотрите также

• Приближение Ланцоша
• Приближение Спужа

Примечания

Рекомендации

• Olver, F. W. J .; Olde Daalhuis, A. B .; Lozier, D.W .; Schneider, B.I .; Boisvert, R. F .; Clark, C.W .; Миллер, Б. Р. и Сондерс, Б. В., Цифровая библиотека математических функций NIST, Выпуск 1.0.13 от 16.09.2016
• Абрамовиц, М., Стегун, И. (2002), Справочник по математическим функциям
• Немес, Г. (2010), "Новое асимптотическое разложение для гамма-функции", Archiv der Mathematik, 95 (2): 161–169, Дои:10.1007 / s00013-010-0146-9
• Пэрис, Р. Б. и Камински, Д. (2001), Асимптотика и интегралы Меллина – Барнса., Нью-Йорк: Издательство Кембриджского университета, ISBN  978-0-521-79001-7
• Уиттакер, Э. Т. и Уотсон, Г. Н. (1996), Курс современного анализа (4-е изд.), Нью-Йорк: Cambridge University Press, ISBN  978-0-521-58807-2
• Дэн Ромик, Приближение Стирлинга для n!: Окончательное краткое доказательство?, The American Mathematical Monthly, Vol. 107, № 6 (июнь - июль 2000 г.), 556–557.
• Ю.-К. Ли, Замечание об идентичности гамма-функции и формулы Стирлинга, Real Analysis Exchang, Vol. 32 (1), 2006/2007, стр. 267–272.

внешняя ссылка

• "Формула Стирлинга", Энциклопедия математики, EMS Press, 2001 [1994]
• Петр Лущный, Формулы аппроксимации для факториальной функции n!
• Вайсштейн, Эрик В. «Приближение Стирлинга». MathWorld.
• Приближение Стирлинга в PlanetMath.