В математике , Формула Стирлинга (или формула Стирлинга ) является приближением для факториалов . Это хорошее приближение, приводящее к точным результатам даже для малых значений n . Он назван в честь Джеймса Стирлинга , хотя впервые об этом заявил Абрахам де Муавр . [1] [2] [3]
Сравнение приближения Стирлинга с факториалом
Версия формулы, обычно используемая в приложениях:
Полная формула вместе с точными оценками ее погрешности может быть получена следующим образом. Вместо того, чтобы приближать n ! , считается ее натуральный логарифм , так как это медленно меняющаяся функция :
где используется нотация большого O , объединение приведенных выше уравнений дает формулу аппроксимации в ее логарифмической форме:
Взяв экспоненту с обеих сторон и выбрав любое положительное целое число m , можно получить формулу с неизвестной величиной e y . Для m = 1 формула
Величину e y можно найти, взяв предел с обеих сторон, поскольку n стремится к бесконечности, и используя произведение Уоллиса , которое показывает, что e y = √ 2 π . Таким образом, получается формула Стирлинга:
Альтернативное происхождение
Альтернативная формула для n ! с использованием гамма - функцию в
(что видно при многократном интегрировании по частям). Переписывая и меняя переменные x = ny , получаем
Фактически, дальнейшие поправки также могут быть получены с использованием метода Лапласа. Например, вычисление разложения двух порядков с использованием метода Лапласа дает
Затем этот линейный интеграл может быть аппроксимирован методом перевала с соответствующим выбором обратного радиуса.. Преобладающая часть интеграла около седловой точки затем аппроксимируется действительным интегралом и методом Лапласа, тогда как оставшаяся часть интеграла может быть ограничена сверху, чтобы получить член ошибки.
Скорость сходимости и оценки ошибок
Относительная ошибка в усеченном ряду Стирлинга в зависимости от n для 0–5 членов. Изломы кривых представляют собой точки, в которых усеченный ряд совпадает с Γ ( n + 1) .
Формула Стирлинга фактически является первым приближением следующего ряда (теперь называемого рядом Стирлинга [5] ):
Явная формула для коэффициентов этого ряда была дана Г. Немесом. [6] [a] Первый график в этом разделе показывает относительную ошибку в зависимости от n для всех 5 членов, перечисленных выше.
Относительная ошибка в усеченном ряду Стирлинга в зависимости от количества используемых терминов
При n → ∞ ошибка в усеченном ряду асимптотически равна первому пропущенному члену. Это пример асимптотического разложения . Это не сходящийся ряд ; для любого конкретного значения n существует только такое количество членов ряда, которые улучшают точность, после чего точность ухудшается. Это показано на следующем графике, который показывает относительную ошибку в зависимости от количества членов в ряду для большего количества членов. Точнее, пусть S ( n , t ) будет рядом Стирлинга для t членов, вычисленных в n . Графики показывают
что, когда оно мало, по сути является относительной ошибкой.
Написание серии Стирлинга в виде
известно, что ошибка при усечении ряда всегда имеет противоположный знак и, самое большее, той же величины, что и первый пропущенный член.
Более точные оценки, сделанные Роббинсом [7], справедливые для всех натуральных чисел n, следующие :
Однако гамма-функция, в отличие от факториала, более широко определена для всех комплексных чисел, кроме неположительных целых чисел; тем не менее, формула Стирлинга все еще может применяться. Если Re ( z )> 0 , то
Повторное интегрирование по частям дает
где В п представляет собой г N -го числа Бернулли (заметим , что предел суммы , какне сходится, поэтому эта формула представляет собой просто асимптотическое разложение ). Формула справедлива для z достаточно больших по модулю, когда | arg ( z ) | <π - ε , где ε положительно, с погрешностью O ( z −2 N + 1 ) . Соответствующее приближение теперь можно записать:
где расширение идентично разложению в приведенной выше серии Стирлинга для n ! , за исключением того, что n заменяется на z - 1 . [8]
Дальнейшее применение этого асимптотического разложения - для комплексного аргумента z с постоянной Re ( z ) . Смотри, например , формула Стирлинга применяется в Im ( г ) = т в тэта - функции Римана-Зигеля на прямой линии1/4+ это .
Границы ошибок
Для любого натурального числа N вводятся следующие обозначения:
Один из способов сделать это - с помощью сходящейся серии перевернутых возрастающих экспонент . Если
тогда
где
где s ( n , k ) обозначает числа Стирлинга первого рода . Отсюда получается версия серии Стирлинга.
который сходится при Re ( x )> 0 .
Версии для калькуляторов
Приближение
и его эквивалентная форма
может быть получено путем перегруппировки расширенной формулы Стирлинга и наблюдая совпадение между результирующей мощностью серией и рядом Тейлор разложением гиперболического синусом функции. Это приближение подходит для более чем 8 десятичных цифр для z с действительной частью больше 8. Роберт Х. Виндшитл предложил его в 2002 году для вычисления гамма-функции с хорошей точностью на калькуляторах с ограниченной памятью программ или регистров. [12]
Гергё Немес предложил в 2007 году приближение, которое дает такое же количество точных цифр, что и приближение Виндшитля, но намного проще: [13]
или эквивалентно,
Альтернативное приближение для гамма-функции, сформулированное Шринивасой Рамануджаном ( Ramanujan 1988 [ требуется пояснение ] ):
для x ≥ 0 . Эквивалентное приближение для ln n ! имеет асимптотическую ошибку1/1400 п 3 и дается
Приближение можно сделать точным, задав парные верхние и нижние границы; одно из таких неравенств [14] [15] [16] [17]
Оценка центрального эффекта в биномиальном распределении
В информатике, особенно в контексте рандомизированных алгоритмов , принято генерировать случайные битовые векторы, длина которых равна степени двойки. Многие алгоритмы, производящие и использующие эти битовые векторы, чувствительны к количеству сгенерированных битовых векторов или манхэттенскому расстоянию между двумя такими векторами. Часто особый интерес представляет плотность "честных" векторов, где количество популяции n- битного вектора точно равно. Это составляет вероятность того, что повторное подбрасывание монеты во многих попытках приведет к ничьей.
Приближение Стирлинга к , Центральный и максимальный биномиальный коэффициент из биномиального распределения , упрощает особенно приятно , когда принимает форму , для целого числа . Здесь нас интересует, насколько уменьшается плотность центрального населения по сравнению с, получая последнюю форму в затухании в децибелах :
Это простое приближение демонстрирует удивительную точность:
Двоичное уменьшение получается от дБ при делении на .
Как прямая дробная оценка:
И снова оба примера демонстрируют точность, которая легко превосходит 1%:
Интерпретируя повторное подбрасывание монеты, сеанс, включающий чуть более миллиона подбрасываний монет (бинарный миллион), имеет один шанс из примерно 1300 закончиться ничьей.
Оба этих приближения (одно в логическом пространстве, другое в линейном пространстве) достаточно просты для многих разработчиков программного обеспечения, чтобы получить оценку мысленно с исключительной точностью по стандартам мысленных оценок.
Биномиальное распределение близко аппроксимирует нормальное распределение для больших, поэтому эти оценки, основанные на приближении Стирлинга, также относятся к пиковому значению функции массы вероятности для больших а также , как указано для следующего распределения: .
История
Формула была впервые открыта Абрахамом де Муавром [2] в виде
Де Муавр дал приближенное выражение в виде рациональных чисел для натурального логарифма константы. Вклад Стирлинга состоял в том, чтобы показать, что константа в точности равна. [3]
Смотрите также
Приближение Ланцоша
Приближение Спужа
Заметки
^ Другие термины перечислены в Он-лайн энциклопедии целочисленных последовательностей как A001163 и A001164 .
Рекомендации
^ Dutka Жак (1991), "Ранняя история функции факториала", Архив для истории точных наук , 43 (3): 225-249, DOI : 10.1007 / BF00389433
^ а бЛе Кам, Л. (1986), "Центральная предельная теорема около 1935 года", Статистическая наука , 1 (1): 78–96 [стр. 81], doi : 10.1214 / ss / 1177013818 , MR 0833276 , Результат, полученный с использованием формулы, первоначально доказанной де Муавром, но теперь называемой формулой Стирлинга, встречается в его «Доктрине шансов» 1733 года.. [ ненадежный источник? ]
^ а бПирсон, Карл (1924), «Историческое примечание о происхождении нормальной кривой ошибок», Biometrika , 16 (3/4): 402–404 [стр. 403], doi : 10.2307 / 2331714 , JSTOR 2331714 , я считаю, что тот факт, что Стирлинг показал, что арифметическая константа Де Муавра была √ 2 π , не дает ему права утверждать теорему, [...]
^ Филипп Флажолет и Роберт Седжвик, Аналитическая комбинаторика , стр. 555.
^FWJ Olver, AB Olde Daalhuis, DW Lozier, BI Schneider, RF Boisvert, CW Clark, BR Miller и BV Saunders, ред. «Электронная библиотека математических функций NIST» .CS1 maint: использует параметр авторов ( ссылка )
^Роббинс, Герберт (1955), "Замечание о формуле Стирлинга", Американский Математический Месячный , 62 (1): 26-29, DOI : 10,2307 / 2308012 , JSTOR 2308012
^Шпигель, MR (1999). Математический справочник формул и таблиц . Макгроу-Хилл. п. 148.
^ FW Schäfke, A. Sattler, Restgliedabschätzungen für die Stirlingsche Reihe, Примечание. Мат. 10 (1990), 453–470.
^ Г. Немес, границы ошибок и экспоненциальные улучшения для асимптотических разложений гамма-функции и ее обратной, Proc. Рой. Soc. Эдинбург, секта. А 145 (2015), 571–596.
^«Архивная копия» (PDF) . Архивировано (PDF) из оригинала 28 января 2012 года . Проверено 1 марта 2012 .CS1 maint: заархивированная копия как заголовок ( ссылка )
^ Тот, В. Т. Программируемые калькуляторы: калькуляторы и гамма-функция (2006). Архивировано 31 декабря 2005 г. в Wayback Machine .
^Карацуба, Екатерина (2001), "О асимптотического представления гамма - функции Эйлера Рамануджаном", Журнал вычислительной и прикладной математики , 135 (2): 225-240, DOI : 10.1016 / S0377-0427 (00) 00586-0.
^Мортичи, Кристинель (2011), "Оценка Рамануджана для гамма-функции с помощью аргументов монотонности", Рамануджан Дж. , 25 : 149–154
^Mortici, Cristinel (2011), "Улучшенные асимптотические формулы для гамма-функции", Ж. вычисл . Математика. Прил. , 61 : 3364–3369.
^Мортичи, Кристинель (2011), «О формуле большого аргумента Рамануджана для гамма-функции», Рамануджан Дж. , 26 : 185–192.
Olver, FWJ; Olde Daalhuis, AB; Lozier, DW; Шнайдер, Б.И.; Бойсверт, РФ; Кларк, CW; Миллер, Б. Р. и Сондерс, Б. В., Цифровая библиотека математических функций NIST , версия 1.0.13 от 16 сентября 2016 г.
Абрамовиц М. и Стегун И. (2002), Справочник по математическим функциям
Nemes, G. (2010), "Новое асимптотическое разложение для гамма - функции", Archiv дер Mathematik , 95 (2): 161-169, DOI : 10.1007 / s00013-010-0146-9
Пэрис, Р. Б., Камински, Д. (2001), Асимптотика и интегралы Меллина – Барнса , Нью-Йорк: Cambridge University Press, ISBN 978-0-521-79001-7
Whittaker, ET & Watson, GN (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.