Д. Кнут - Искусство программирования том 1 (1119450), страница 32
Текст из файла (страница 32)
Оценка 11. Выполнив подстановку 3 = х(1+ и) получим интеграл от О до бесконеч- ностю В результате дальнейшей подстановки 0 = и — 1п(1+ и), 120 = (1 — 1/(1+ и)) 4(и (она законна, так как 0 — монотонная функция ог и) получаем: у аа 11 = е *х* хс ~(1+и)*Ни = е *х / хе *«~1+ — ) 41г. (11) 0 0 Ю В последнем интеграле заменим 1+ 1/и рядом по степеням ш Тогда е = -ц — -и + -44' — -пэ+. = (и /2)(1 — -~+ -~ — за + 1 1 3 2 1 2 2 3 2 3 4 5 з г Полагая 40 м 1/20. получим н1 = и(1 — -и+ -и — -и +.
) = и — 1и + — и — — и +- — и + О(и ). 2 1 2 2 3 1/2 1 2 У 3 13 4 ' 1331 5 6 3 2 5 3 36 540 12960 (Это разложение можно получить на основании биномиальной теоремы. ЭффективНЫЕ МгтедЫ ВЫПОЛНЕННя ПОдсбНЫХ ПрЕОбраэоеаинй, а 1анжЕ друГИХ ОПЕраций Над Данное равенство специально было записано в более сложном виде, чем это необходимо, так как у(п,п) — часть у(и, оо) = Г(п) = (п — 1))1, а п1е"/п" — величина из (4).
Поэтому задача сводится к нахождению хороших оценок для у(п, п)/(п — 1) й Теперь определим приближенное значение у(х+1, х+р)/Г(х+1) для фиксированного у и больших х. Заметим, что используемые здесь методы важнее результатов, поэтому читателю следует внимательно разобраться в приведенных ниже выкладках. По определению имеем ~о хе *"(1+ — )ди = 0(е "*) (13) для любого фиксированного г > 0 и для больших х. Нас интересует аппроксимация с точностью до членов порядка 0(х ), и так как 0((1/е")*) намного меньше, чем 0(х ) для любых положительных г и т, нужно взять интеграл только от 0 до г для любого фиксированного положительного г.
Поэтому возьмем достаточно малое г, чтобы все выполненные выше операции над степенными рядами были законны (см. соотношения 1.2.11.1-(11) и 1.2.11.3-(13)). Так как хе *"и 11о = — / е 441 1й? = — Г(44 + 1), если 44 > — 1, (14) о — хь / о х'* то, подставляя ряд (12) в интеграл (11), окончательно получаем 11 — — е *х*(~/ — х 1 + — + — х / — — х + — х ' +0(х )). /и 1 2 2 з/2х 1 2 4, з/2х -з?2 11/2 3 24 135 576 Оценка 12. В интеграле 12 делаем подстановку 1 = и + х и получаем (1о) (16) Теперь и ' из е "(1+ — ) = ехр ~ — и+х1п(1+ — )) =ехр( — + — 2+0(х )) и2 и4 из =1 — — + — + — +0(х ) 2х 8хз Зхз для 0 < и < у и больших х.
Поэтому з 4 5 12=с х у — — х +( — + — )х +0(х ) — У -1 /Р Р 1 -2 -3 6 '1 12 40/ (17) степенными рядами, которые понадобятся нам несколько позже, рассматриваются в разделе 4,7.) Теперь можно получить разложение и в ряд по степеням ис 2 1 3 1 4 1 5 5 и=ю+-ю + — ю — — ю + — ю +0(ю); 3 36 270 4320 2 1 3 1+ — =1+ — + 2+ 3+0( 4) и ю 3 12 135 864 = — и + -+ — и / — — и+ — и / +0(и ). 1 112 2 3/2,2 4 3/2 32 (12) 3/2 3 12 135 432 Во всех этих формулах 0-запись относится к малым значениям аргумента, т.
е, (и! < г, (и! < г, ~ю) < г для достаточно малого положительного г. Не слишком ли сильное это ограничение? Предполагается, что подстановка 1 + 1/и как функции от и в (11) законна и для 0 < и < оо, а не только для (и( < г. К счастью, оказывается,что значение интеграла от 0 до оо почти полностью зависит от значений подынтегрвльной функции в окрестности нуля. В самом деле, получаем (см. упр.
4) И в заключение исследуем множитель е *х*/Г(х+ 1), который появляется при умножении (15) и (17) на коэффициент 1/Г(х+ 1) из (10). По формуле Стирлинга, которая согласно упр. 1.2.11.2-6 справедлива для гамма-функции, имеем е-ахь е-1/12х.ьО(х ) Г(х + 1) ь/2нх = — х '/~ — — х ~/~+ х а/~+0(х т/т). (18) ~/2я 12~/2я 288ч/2я А теперь из соотношений (10), (15), (17) н (18) получаем следующую теорему. Теорема А. Для больших значений х н фнкспрованного у 7(х+ 1.
х+ у) 1 /'у — 2/3'), з 1 / 23 у У~~ -з э Г(х+ 1) 2 1, ч/2х,) чг2н ~270 12 6 / + 0(х /~). 1 (19) ь" "й' /2 Р(п) = ~~~,, = —, ~ /с"~ / е "'(1+ — + 0(к а)). (20) г=-о а=о Таким образом, для получения значений Р(п) требуется изучить суммы вида а Е й -и/г -ь е Положим /(х) = х"+'/зе * и применим формулу суммирования Эйлера: й гп Е йпч1/зе-ь ха ь1/зе — ь Ях ь 1 Яч 1/2е-п,~ 1 пп-1/2е-и Я (21) 2 24 а=о Предварительный анализ.
остаточного члена (см. упр. 5) показывает, что В = 0(п"е "); и так как интеграл нвляется неполной гамма-функцией, имеем Ал-ь1/2 — ь ( э ) 4 1 и.~-1/3 — л ~ (р( я -а) ~=о (22) Для формулы (20) требуется еще найти оценку суммы /л-1/2 -ь ч ~ ~п — !)ч.1/2 -ь и-з/2 -и Е е = к н е Чп е а=о ейь< — 1 и это также можно получить с помощью соотношения (22).
Примененный метод показывает. что данное разложение можно продолжить настолько, насколько это необходимо, и получить приближенную формулу для последующих степеней х. Теорему А можно использовать для получения приближенных значений Л(п) н с/(п) с помощью (4) и (9), но л1ы сделаем это несколько позже. А пока давайте вернемся к сумме Р(п), для изучения которой, похоже, необходим немного другой метод.
Имеем Теперь в нашем распоряжении достаточно формул для того, чтобы определить приближенные значения Р(и), с1(и) и А(и); осталось только подставить, умножить и т. д. При этом нам представится случай воспользоваться разложением (и+ а)"эв = и"эве 1+ а(,6 — — ) — -~ 0(и з), (23) ах 1 2)и которое доказывается в упр. 6. Метод, который мы использовали в (21), дает только первые два члена асимптотического ряда для Р(и). Следующие члены можно получить с помощью важного метода, описанного в упр.
14. В результате всех этих рассуждений получаем нужные асимптотические формулы: (хи 2 11 /х 4 71 Р(и) = ~/ — — - + — ~/ — + — „— — ~/ — + 0(и ), (24) 'з' 2 3 24)/2и 135и 1152 1/2из 1з'и 1 1 ?х 4 1 / к Фи) = ~/ — — -+ — / — — — + — )/ +0(и ), (25) 'з/ 2 3 12 з' 2и 135и 2881/ 2из /ли и1 1 )к 4 1 /к Л(и) = ~/ — + — + — ~/ — + + — ~/ + 0(и ), (26) )/ 2 3 12)1 2и 135и 288)/2из Изученные нами функции только поверхностно рассматривались в опубликованных научных работах. Первый член -,/хи/2 в разложении суммы Р(и) был получен Г. Б. Демутом (Н. В. Оепп~зЬ) (РЬ. В. 1Ьез1з (8сап1огс1 ПпгеегЫу, ОсзоЬег, 1956), 67 — 68].
Используя данный результат, таблицу значений Р(и) для и < 2000 и хорошую логарифмическую линейку, автор в 1963 году продолжил эти исследовании и получил эмпирическую оценку Р(и) - „/ти/2 — 0.6667+0.575/,/и. Было естественно предположить, что на втором месте стоит 2/3, 0.6667 является приближенным шачением для 2/3, а 0.575, вероятно, будет приближением для у = 0.57721..., зоторое должно заменять это число в третьем слагаемом (почему бы не быть оптимистом?). Впоследствии, во время написания данного раздела, было найдено верное разложение для Р(и) и предположение о том, что 0.6667 нужно заменить на 2/3, подтвердилось.
Что же касается коэффициента 0.575, то он является приближением не для 7, а для Цз/х/2 0.5744. Это отлично подтверждает и теорию, и эмпирические оценки. Эквиваленты аснмптотических формул для 0(и) н В(и) были впервые определены выдающимся индийским математиком-самоучкой С. Рамануджаном (8.
Ватапп)ал), который поставил задачу оценки и! е"/2и" — Ц(и) в Х 1пс(?ап МаЗЬ. Яос. 3 (1911), 128; 4 (1912), 151-152. В качестве решения этой задачи он предложил асимптотический ряд 1 4, 8 з 1 -з — + — и — — и — — и + 3 135 2835 8505 который гораздо лучше соотношения (25). По сравнению с приведенным выше методом доказательство Рамануджана было более изящным. Оценивая 1м он выполнил подстановку З = х+из/2х хи выразил подынтегральное выражение в виде суммы чле. нов вида с,з )в ехр( — из)и'х "1з Ии. Интеграл 1з можно вообще не рассматривать, так как ау(ах) = хас *+э(а+1, х), где а > 0 (см. (8)).
Еще более простой — вероятно, самый простой из возможных — метод получения асимптотической формулы для 0(п) приведен вэупр. 20. Несмотря на излишнюю сложность, использованный нами метод все же является очень поучительным. Он был предложен Р Фюрхом (Н. РпгсЬ) [2емэсЬпй /йг РЬувйй 112 (1939), 92-95], который главным образом, интересовался значением у. удовлетворяющим соотношению 7(х+ 1, х+ у) = Г(х+ 1)/2 Асимптотические свойства неполной ~эмма-функции были впоследствии обобщены для комплексного аргумента Ф. Дж.
Трикоми (Р. С. Тпсопп) [ЛХай. Уе!шсЬп/с 53 (1950), 136-148]. См. также Н. М. Тепппе, Май. Сотр 29 (1975), 1109 — 1114; ЯАМ Х МасЬ. Апа1. 10 (1979), 757-766 Ссылки на некоторые другие исследования суммы ()(и) перечислены в работе Н. 1т'. Соц!6, АМЛХ 75 (1968), 1019 — 1021. При выводе асимптотических формул для сумм Р(п), 1/(и) и й(п) мы использовали только элементарные преобразования; но обратите внимание, что для каждой функции мы использовали свой метод! На самом деле во всех трех случаях можно было бы воспользоваться методом из упр. 14, который обсуждается в разделах 5.1.4 и 5.2.2. Это было бы более изящно, но менее поучительно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
