Д. Кнут - Искусство программирования том 1 (1119450), страница 31
Текст из файла (страница 31)
Но, не зная констант, подразумеваемых записями с символами 0 и й, мы ничего не можем сказать о том, насколько большим должно быть и, чтобы метод 0(п 1ойп) начал выигрывать в эффективности. И наконец, чтобы точно указать порядок роста, не давая при этом точных значений констант, можно воспользоваться записью с символом "большая тета": д( ) = <Э(/(и)) с=э д(п) ж О(/(и)) д( ) ее П(/( )). (21) УПРАЖНЕНИЯ 1.
[НМ01) Чему равен !пп„„О(п Ые)2 2. [М!0] М-р даллв, применяя "очевидную" формулу О(/(и)) — О(/(и)) = О, получил удивительные результаты. В чем была его ошибка, и каи должна выглядеть правая часть "очевидной" формулы? 3. [М!5) Умножьте (!пи+у+О(1/и)) на (и+0(т/й)) и представьте результат с помощью символа О. 4. [М1б[ Дайте асимптотическое разложение п(1/а — 1), где а > О, с точностью до членов порядка О(1/пе). б. [Мдд) Докажите или опровергните следующее О(/(и) + д(п)) = /(и) + 0(д(?)), если /(и) и д(п) положительны для всех и.
(Ср. с формулой (10).) 6. [Мдд[ Где ошибка в следующем рассужценииу "Так как и = 0(п) и 2п = 0(п), ..., и !еп = ~ О(я) = 0(п')" * В оригинале — В. С. !1нП. От англ, нбн!Г' (" тупица" ). — Прим. иерее. 7. [НМ15] Докажите, что для произвольного целого гп нельзя найти такое М, чтобы для сколь угодно больших значений х выполнялось неравенство е* < Мх"'.
8. [НМ20] Докажите, что (!пи) /и -э 0 при и -э со. 9. [НМ20) Покажите, что ещ ~ = 1+ О(з ) для всех фиксированных ш > О. 10. [НМ22] Сформулируйте утверлсдение, аналогичное утверждению из упр. 9, относительно !п(1+ О(зы)). ь 11. [М11) Объясните, почему верна формула (18), 12. [НМ25] Докажите, что [,'~ ь)п ~ не стремится к нулю при 1 — > оо для любого целого и.
Воспользуйтесь тем, что [, ~ „] = (--')Е [з~] (зе /(е' — 1))О~. ь 13. [М10) Докажите или опровергните следующее: д(п) = й(/(и)) тогда и только тогда, когда /(и) = О(0(п)) е1.2.11.2. Формула суммировании Эйлера. Одним из лучших методов получения приближенных значений сумм является метод, предложенный Леонардом Эйлером. Он состоит в том, чтобы аппроксимировать конечную сумму интегралом, и во многих случаях позволяет получать приближения с любой степенью точности. [Соттеп!агй Аслот!ю Зс!епс!агшп Реггоро!!галю 6 (1732), 68-97.] 1 2 3 4 б б 7 Рис.
12. Сравнение суммы с интегралом. На рис. 12 сравниваются ]," /(х) ох и ~„", /()с) при и = 7. Предполагая, что /(х) — дифференцируемая функция, с помощью метода Эйлера можно получить удобную формулу для разности между интегралом и суммой. Для удобства введем следующее обозначение: (х) = хтог) 1 = х — [х]. Нащем выкладки со следующего тождества: ь.~-г г"+' ((х) — з) / (х) Пх = (х — Й вЂ” 1)/(х)), — /(х) йх гь+г = з(/(/г+ 1) + /(/с)) — / /(х) г(х. (2) (Мы применили формулу интегрирования по частям.) Складывая обе части этого равенства для 1 < !г < и, находим, что ь гь ((х) — ~1) / (х) с!х = ~~' /(/с) + 1 — (/(и) — /(1)) — /(х) ох, 1 ~«ь<п 1 и п 7(х) — /,Г(х) с(х — 1(у(п) — у(1)) + З~ В1((х))у (х) 15х, (3) 1<5<а 1 1 где В1(х) — многочлен В1(х) = х — 1.
Это и есть искомая формула, .связывающая сумму с интегралом. Продолжая интегрировать по частям, можно получать более точные приближения. Но прежде чем это сделать, рассмотрим числа Бернулли, которые являются коэффициентами следующего бесконечного ряда: х Взг Вьх" — = Ва + В1 г + — + (4) е' — 1 21 к1 ь>а Коэффициенты этого ряда, которые встречаются во многих задачах, были введены Якобом Бернулли (Ласйиеэ Вегпои111) в работе Агэ Соп1есселй, опубликованной после его смерти в 1713 году.
Самое интересное, что почти в то же самое время данные числа были открыты и японцем Такакузу Секи (ТаЫшхн Бе1п) и впервые опубликованы в 1712 году, вскоре после его смерти. [См. Такакахи Бе151'э Со1!ессе11 Иогкэ (Оэака, 1974), 39-42.] Имеем Ве = 1, В1 = — 1, Вт = 5, Вз = О, В1 = -эе (б) некоторые последующие значения чисел Бернулли приведены в приложении А. Так как функция 5 х хе=+1 + е' — 1 2 2 е= — 1 2 е ' — 1 является четной, то (6) Вз=вь=вт=вэ= =О. Умножая обе части равенства (4) на е' — 1 и приравнивая коэффициенты при одинаковых степенях х, получим формулу ~~, ( ) Вь = Вп + 4„1.
(7) (См. упр. 1.) Теперь определим многочлен Бернулли В (х) = ~ (™)Вьх (8) (9) = тВ 1(х) Если т = 1, то В1(х) = Вех + В1 —— х — 1; этот многочлен использовался выше, в соотношении (3). Если т ) 1, то согласно (7) В (1) = В = В (О); другими словами, В, ((х)) не имеет разрывов при целых значениях х. Вскоре станет ясно, какое отношение к нашей теме имеют многочлены Бернулли и числа Бернулли.
Дифференцируя (8), находим и, следовательно. при гп > 1 можем проинтегрировать по частям: г" — / В,„(( ))/1'* (*) (* = ,(В ,( )/ 1( ) - В +,(О)/(-1( )) 㻠— — Вв~.ь1((х))/~ ~В(х) с(х. (-+ц Х С помощью этого результата можно улучшить формулу (3) и, воспользовавшись (6), получигь обшую формулу Эйлера г" Е /(~) =~ /(х)~--'Яп)-Ы))+ — '(/'(и)-/'(ц)+" 1<ь<и (-ц- в„, (~,„ц® ь ы /( )(х+~ — „, (/" "( ) — /<" "(ц)+В., (10) 1 ым где ц +1 г" Вгп~ = 1 / Вюь((х))/ (х) Нх.
(1Ц Остаток Я „будет мал при очень малых значениях В,„((х))/1"'1(х)/гп', и фактически можно показать, что для четного т (12) [См СМагЬ, 39 5.) С другой стороны, обычно оказывается, что при увеличении гп функция /~ ~(х) возрастает по модулю, поэтому существует "наилучшее" значение гп, при котором ~В „~ принимает наименьшее значение (если и фиксировано) Известно„что, когда т четно, существует число д, такое, что Н „= В -" (/(-+0(п) — /~-+В(Ц), 0 < В < 1 В„ (т+ 2)' (13) Н„| = )и и + ~ — ( — ц ( — „— 1) + Л в (,и" с=1 (14) Тогда В 'у = 1пп (Н„1 — !пи) = ~ ~— ( — Ц" + 1нп Я л-~ оо 1с в — >Ос ыь (15) при условии, что /< +э>(х)/' «Ю(х) > 0 для 1 < х < и.
В данном случае остаток меньше первого отбрасываемого члена и имеет такой же знак, как и у него Упрощенный вариант этого результата доказывается в упр. 3 А теперь применим формулу Эйлера к некоторым важным примерам Сначала положим /(х) = 1/х Производные будут иметь вид /~ ~ = (-Ц гп'/х +', поэтому согласно (10) получим Воспользовавшись тем, что е = х/2я (см. упр. 5), и разложив экспоненту в ряд, получим окончательный результат; УПРАЖНЕНИЯ 1.
[М10] Докажите соотношение (7). 2. [НМ20] Заметьте, что формула (9) следует из (8) для любой последовательности В„, а не только для той, которая определяется соотношением (4). Обънсните, почему использование последней является необходимым условием справедливости соотношения (10). 3. [ШИО] Пусть С ь = ((-1) В /т!)(/~ Ц(п) — /1ю Ц(1)) — т-и корректирующий член в формуле суммирования Эйлера. Считая, что функция /1 ~(х) имеет постоянный знак на промежутке 1 < х < и, докажите, что [Н „] < [С,„„[ при пг = 2к ) 0; другими словами, покажите, что значение остатка по модулю не больше значения последнего вычисленного члена 4.
[НМ20] (Суммы сшгпгней.) Если /(х) = х, то все производные функции / порядка т+ 1 и выше равны нулю, поэтому формула суммировании Эйлера дает гаечное значение суммы Н (и)= ~ к'", о<э< выраженное с помощью чисел Бернулли (Именно изучая суммы Н,„(п) для т = 1, 2, 3, ..., Бернулли и Секи пришли к открытию этих чисел.) Представьте Бь(п) с помощью многочлгнов Бернулли Проверьте полученный результат для т = О, 1 и 2. (Обратите внимание, что суммирование в искомой сумме выполняется по 0 < к < и, а не по 1 < 1г < п; в формуле суммирования Эйлера единицу везде можно заменить нулем.) б. [НМ30) На основании формулы и с помощью произведения Валлиса (упр.
1.2.5 — 18) покажите, что к = з/2ях. [Укаганое. Рассмотрите ( ") для больших значений и ] 6. [НМ00] Покажите, что приближенная формула Стирлинга справедлива также дчя нецелых значений и. Гь ) = 2 *(г) [1! ~О(-)), )О, [Указание. В формуле суммирования Эйлера положите /(х) = 1п(х+ с) и воспользуйтесь определением Г(х), которое дано в разделе 1.2.5.] 7. [НМЗ2] Чему равно приближенное значение 1'2г3г..
и"? 8. [М20] Найдите асимптотическое представление для 1п(оп +Ьп)' с абсолютной погрешностью О(~ г) Воспользуйтесь полученным результатом для нахождения асимптотическог ь г го представления для ('"„)/с" ("„) с относительной погрешностью О(п ), где с — положительная константа В данном случае под абсолютной пагргшное)яью понимаем такое г, которое удовлетворяет соотношению (точное значение) = (приближенное значение) + г, а под относншельной погрешносшью — г, удовлетворяющее соотношейию (точное значение) = (приближенное значение)(1+ г). 9. (М95] Найдите асимптотическое представление для (г„") с относительной погрешностью порядка О(и г) двумя способами.
(а) с помощью приближенной формулы Стирлинга; (Ь) с помощью упр. 1.2.6-47гг формулы 1.2.11.1 — (1б). и — 1 п — 2 и — 2 ~~- (и — /г)" (п — 7г)! Р(п) = 1+ + — + и и п — 1 и! ь=е Я(и) = 1+ + ь=! (2) Л(п)=1+ + + п+1 п+1 и+2 (3) Эти функции, на первый взгляд, похожи, но на самом деле в корне отличаются одна от другой.
Онн возникают в некоторых алгоритмах, которые будут рассмотрены несколько позже. И Р(и), и Я(и) — конечные суммы, .в то время как гс(и)— бесконечная сумма. Может показаться, что при больших и значения всех трех сумм будут практически одинаковы, хотя совсем не очевидно, каким будет приближенное значение каждой из них в отдельности. В процессе поиска приближенных значений этих функций мы получим ряд очень поучительных побочных результатов. (Если хотите, можете временно прекратить чтение и попьпаться самостоятельно исследовать эти функции, прежде чем вернуться к книге и выяснить, как с мими поступим мы.) Прежде всего отметим важную связь между 1„1(п) и Рт(п): п~ еп Формула Стирлинга говорит о том, что п! и"/ип приближенно равно ь/2кп, поэтому можно догадаться, что каждая из функций Я(и) и Л(п) приближенно равна ь/ки/2.
Теперь, чтобы продвинуться дальше, рассмотрим частные суммы ряда для е". Воспользовавшись формулой Тейлора с остаточным членом /~п)(О)ап Г* 1п /( ) =/(о)+/'(о)*+ "+/ (,) + / —,/ш+н( — 1)(1, (5) мы вскоре поймем необходимость введения важной функции, которая называется неполной гамма-функцией: 7(а,к) = / е г1" г Дб го (б) Будем считать, что а > О. Из упр. 1.2.5-20 имеем з(а, оо) = Г(а); этим и объясняется название "неполная гамма-функция". Для нее существует два полезных разложения *1.2.11.3.
Применение асимптотических формул. В данном разделе мы рассмотрим три следующие интересные суммы, чтобы найти их приближенные значения: в ряд пр Ствпеням х (см. упр. 2 и 3)1 Ха Ха+1 Ха+2 у(а,х) — — — — + а а+1 2! (а+2) (-1)" х"+' Ы (/с+ а) 5~а Е .(.+ ) ...(.+ ) х' х'"' х'+2 а а(о+1) о(о+1)(0+2) Из второй формулы видна связь с В(п): 166 „(, ) у(х+ 1, х+ р) 1 Г(х+ 1) Г(х+1) /0 106 44 1 гаа та+3 Г(х+ 1) /, Г(х + Ц /, (10) Обозначим — е 3* 445, Га 1.9 А =/ е 14143 и рассмотрим по очереди кауидый из этих интегралов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
