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

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

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

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

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

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

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

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

за . Это следует из более точные границы ошибок обсуждается ниже.

Вывод

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

с интеграл:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Версия этого метода для комплексного анализа[4] рассматривать как Коэффициент Тейлора экспоненциальной функции , рассчитанный Интегральная формула Коши в качестве

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

потом [9][10]

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

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

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

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

тогда

куда

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

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

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

Приближение

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

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

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

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

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

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

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

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

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

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

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

Двоичное уменьшение получается от дБ при делении на .

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

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

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

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

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

История

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

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

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

Примечания

  1. ^ Дополнительные термины перечислены в Он-лайн энциклопедия целочисленных последовательностей в качестве A001163 и A001164.

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

  1. ^ Дутка, Жак (1991), "Ранняя история факториальной функции", Архив истории точных наук, 43 (3): 225–249, Дои:10.1007 / BF00389433
  2. ^ а б Ле Кам, Л. (1986), "Центральная предельная теорема около 1935 года", Статистическая наука, 1 (1): 78–96 [стр. 81], Дои:10.1214 / сс / 1177013818, МИСТЕР  0833276, Результат, полученный с использованием формулы, первоначально доказанной де Муавром, но теперь называемой формулой Стирлинга, встречается в его «Доктрине шансов» 1733 года..[ненадежный источник? ]
  3. ^ а б Пирсон, Карл (1924), "Историческое примечание о происхождении нормальной кривой ошибок", Биометрика, 16 (3/4): 402–404 [стр. 403], Дои:10.2307/2331714, JSTOR  2331714, Я считаю, что тот факт, что Стирлинг показал, что арифметическая постоянная Де Муавра была 2π не дает ему права требовать теоремы, [...]
  4. ^ Филипп Флажолет и Роберт Седжвик, Аналитическая комбинаторика, п. 555.
  5. ^ F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R.F. Boisvert, C.W. Clark, B.R. Miller и B.V. Saunders, ред. «Электронная библиотека математических функций NIST».CS1 maint: использует параметр авторов (связь)
  6. ^ Nemes, Gergő (2010), "О коэффициентах асимптотического разложения n!", Журнал целочисленных последовательностей, 13 (6): 5 п.
  7. ^ Роббинс, Герберт (1955), «Замечание о формуле Стирлинга», Американский математический ежемесячник, 62 (1): 26–29 с., Дои:10.2307/2308012, JSTOR  2308012
  8. ^ Шпигель, М. Р. (1999). Математический справочник формул и таблиц. Макгроу-Хилл. С. 148.
  9. ^ F. W. Schäfke, A. Sattler, Restgliedabschätzungen für die Stirlingsche Reihe, Примечание. Мат. 10 (1990), 453–470.
  10. ^ Г. Немес, границы ошибок и экспоненциальные улучшения для асимптотических разложений гамма-функции и ее обратной величины, Proc. Рой. Soc. Эдинбург, секта. А 145 (2015), 571–596.
  11. ^ «Архивная копия» (PDF). В архиве (PDF) из оригинала от 28.01.2012. Получено 2012-03-01.CS1 maint: заархивированная копия как заголовок (связь)
  12. ^ Тот, В. Т. Программируемые калькуляторы: калькуляторы и гамма-функция (2006) В архиве 2005-12-31 на Wayback Machine.
  13. ^ Nemes, Gergő (2010), "Новое асимптотическое разложение для гамма-функции", Archiv der Mathematik, 95 (2): 161–169, Дои:10.1007 / s00013-010-0146-9, ISSN  0003-889X.
  14. ^ Карацуба, Екатерина (2001), "Об асимптотическом представлении гамма-функции Эйлера Рамануджаном", Журнал вычислительной и прикладной математики, 135 (2): 225–240, Дои:10.1016 / S0377-0427 (00) 00586-0.
  15. ^ Мортичи, Кристинель (2011), «Оценка Рамануджана для гамма-функции с помощью аргументов монотонности», Рамануджан Дж., 25: 149–154
  16. ^ Mortici, Cristinel (2011), "Улучшенные асимптотические формулы для гамма-функции", Comput. Математика. Appl., 61: 3364–3369.
  17. ^ Мортичи, Кристинель (2011), «О формуле большого аргумента Рамануджана для гамма-функции», Рамануджан Дж., 26: 185–192.

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