AOP_Tom1 (1021736), страница 31
Текст из файла (страница 31)
д. Если а(п) н 4(п) — формулы, содержащие символ О, то запись а(п) = 4(п) означает, что множество функций, относящихся к классу а(п), содержигпсл в множестве функций, относящихся к классу р(п). Следовательно, большинство привычных операций можно выполнять, пользуясь знаком "=": если а(п) = )5(п) и )3(п) = 7(п), то а(п) = т(п). Кроме того, если а(п) = д(п) н если 5(п) — формула, полученная в результате подстановки р(п) вместо некоторых а(п) в формуле 7(п), то т(г1) = 6(п). Из зтих двух утверждений следует, например, что если д(хм хо,...,х ) — любая действительная функция и если оь(п) = рь(п) для 1 < й < гп, то д(а1(п),ат(п),,о,(п)) д(А (и), дт(п),, д (п)) Вот некоторые простые операции, которые можно выполнять с символом О.
Рассмотрим несколько примеров. Производящие функции, приведенные в разделе 1.2.9, для всех неотрицательных целых т дают важные асимптотические формулы для достаточно малых еч 2 1 м е' = 1+ т -!- — вз -(- ° + — з~ -(- 0(з"'+1), 2! ти! ( ц т-~-1 !п(1+э) = г — -з'+ + з" +0(г +'), 2 ти (12) (1+в) =1+аз+ з~+.. + ! 1г™+0(г +'), (14) — !и — =г+Нгг~+ .
+Н г +0(х +1). 1 — з 1 — з (15) |и" 4+0(и" '), ь=о 1)ь ~ т 1 т-ь + О( г-т-1) ь=а т и (16) иг = (17) выражающие факторнальные степени через обычные степени, асимптотически спра- ведливы для любого действительного т и любого фиксированного целого тп > О, в то время как сумма расходится для всех и (см. упр. 12). Ра ~умеется, если т — неотрицательное целое, то ие и иг являются просто многочленами степени т и (17) — это, в сущности, то же, что и 1.2.6 (44) Если т —.неотрицательное целое и !и! ) !т(, то бесконечная сумма ~„, ' е [," ) и' " сходится к ие = 1/(и — 1) — '". Эту сумму можно записать также в более естественном виде, 2 1 е (" ')и" ", воспользовавшись соотношением 1.2.6-(58).
Приведем один прогтой пример для иллюстрации введенных понятий. Рассмотрим величину ~уп. По мере увеличения и последовательность корней и-й степени из фиксированного числа будет убывать, но совсем не очевидно, убывающей или возрастающей будет последовательность ~/й Оказывается, что ,",1и убывает и стремится к единице. Теперь давайте рассмотрим несколько более сложную величину и(~/й — 1). Здесь (~/й — 1) убывает при увеличении и.
А как будет себя вести и(,"/й — 1)? Эта задача легко решается с помощью приведенных выше формул. Имеем Цй = ем"?" = 1+ (!пи(и) + 0((1пи(и)'), (18) Важно отметить, что константы М и т при каждом конкретном О зависят одна от другой. Например, очевидно, что функция е' = 0(1) при !з! < т для любого фиксированного т, так как (е ! < е!'!; но не существует константы М, такой, что !е'! < М для всех л Поэтому по мере увеличения т нам придется брать все большее и большее значение М.
Иногда асимптотическая формула справедлива, хотя не существует соответствующего сходящегося бесконечного ряда Например, основные формулы так как 1пи/и — с О при и -+ оа (см. упр. 8 и 11). Соотношение (18) доказывает утверждение о том, что т/и -с 1. Более того, из него следует, что пЯи — 1) = с(1пгс/гс+0((1пи/и) )) =!пи+0((1пи)т/и). (19) Другими словами, и( /и — 1) приближенно равно 1и и; эти величины отличаются на величину О((!пи) /и), которая стремится к нулю при и, стремящемся к бесконечности.
Многие часто неправильна пользуются записями с символом О, считая, что они дают точный порядок роста, т. е. определяют как верхнюю, так и нижнюю грани. Например, алгоритм сортировки и чисел можно назвать неэффективным. "потому что время его выполнения составляет 0(ит)". Но из этого никак не следует, что время выполнения алгоритма не составляет также 0(и).
Для нижних граней существует другая запись, с символом "большая омега". Утверждение (20) д(и) = й(/(и)) означает, что существуют положительные константы Б и ио, такие, что с]д(и)/ > Ьс[/(п)! длЯ всех сс > ио. Эта запись позволяет сделать правильный вывод о том, что алгоритм сортировки, время выполнения которого равна й(ит), будет не таким эффективным, как алгоритм, время выполнения которого равно 0(и!о8 п) (для достаточно больших п). Но, не зная констант, подразумеваемых записями с символалси 0 и й, мы ничего не можем сказать о том, насколько большим должно быть и, чтобы метод 0(и )об п) начал выигрывать в эффективности. И наконец, чтобы точно указать порядок роста, не давая при этом точных значений констант, можно воспользоваться записью с символом вбальшвя тета": д(и) = О[/(и)) ч=ь д(и) = О(/(и)) и д(и) = й(/(и)).
(21) УПРАЖНЕНИЯ 1. [НМ01] Чему равен !сш„О(и Пв)? 2. [М!О] М-р Далл*, применяя "очевидную" формулу О(/(п)) — 0(/(и)) = О, получил удивительные результаты. В чем была его ошибка, и как должна выглядеть правая часть "очевидной" формулы? 3. [М!5] Умножьте (1ц и с- уеО(1/и)) иа(п+О(с/п)) и представьте результате помощью символа О. 4. [М10] Дайте асимптотичесссое разложение п(~/а — 1), где а > О, с точностью до членов порядка О(1/и~). 5. [Мдд] докажите кли опровергните следующее О(/(и) + д(п)) = /(и) + 0(д(п)), если /(и) и д(п) положительны для всех и. (Ср. с формулой (10).) 6.
[Мдд] Где ошибка в следующем рассуждении? ?Так как п = О(и) и 2п = О(и), ..., то в и ~ ди=~ О( ) =О( ')- с В оригинале — В. С, Есцй. От аигл. "4ц!Г (" тупица" ). — Прим. перев. 7. (НМ15) Докажите, что для произвольного целого гл нельзя найти такое М, чтобы для сколь угодно больших значений х выполнялось неравенство е* < Мх™. й. (НМ20) Докажите, что (!пл)~/л -+ О при и -+ со. 9. (НМ20) Покажите, что ет 1 = 1+ 0(ты) для всех фиксированных гп > О. 10. (НМ22) Сформулируйте утверждение, аналогичное утверждению из упр. 9, относительно 1п(1+ О(» )). и 11.
(М11) Объясните, почему верна формула (18). 12. (НМ25) Докажите, что ~,'с~с]л " не стремится к нулю при 1 -+ оо для любого ЦЕЛОГО Л. ВОСПОЛЬЗуйтЕСЬ тЕМ, ЧтО [,,'З С] = ( — -')С (ЗС) (ХЕг/(Е* — 1)) М~. ь 13. (М10) Докажите или опровергните следующее: 0(л) = й(/(и)) тогда и только тогда, когда /(л) = О(0(л)). а1.2.11.2. Формула суммирования Эйлера.
Одним из лучших методов получения приближенных значений сумм является метод, предложенный Леонардом Эйлером. Он состоит в том, чтобы аппроксимировать конечную сумму интегралом, и во многих случаях позволяет получать приближения с любой степенью точности. (Соттепсагй Асаг)ет1ю Яс1епИагпт Реггоройгалее 6 (1732), 68 — 97.] 1 2 3 4 5 б 7 Рис. 12. Сравнение суммы с интегралом. На рис. 12 сравниваются )1п /(х) г)х и 2 "„' /(/с) при л = 7. Предполагая, что /(х) — дифференцируемвя функция, с помощью метода Эйлера можно получить удобную формулу для разности между интегралом и суммой. Для удобства введем следующее обозначение; (х) = х тог( 1 = х — 1х].
Начдем выкладки со следующего тождества: С+1 гс+' ((х) - ;) / (х) Нх ж (- - — й)/(-)]с — /(х) (х с с г" +1 = †,1(/(2 + Ц + /(й)) — / /(х)(х. (2) (Мы применили формулу интегрирования по частям.) Складывая обе части етого равенства для 1 < /с < л, находим, что в г ((*) - ) /'(х) б* ж ~ /(й) + -,'(ж - /(1)) - / т -, 1 1<1<в 1 т. е. г" гю у(!4) = / 14(х) г!х — 1 (у(71) — у(1)) + / В1((х))14 (х) 4!х, (3) 1«в<44 1 1 Во — 1, В1 — — г, В1=3, В5=0, В4= — эе (6) некоторые последующие значения чисел Бернулли приведены в приложении А. Так как функция — г е ' — 1 х с=+1 е' — 1 2 2 е= — 1 2 является четной, то (6) Вз = В5 = В7 = Вэ = Умножая обе части равенства (4) на е' — 1 и приравнивая коэффициенты при одинаковых степенях х, получим формулу " ( )Вь = В„+б„1.
(7) (См. упр. 1.) Теперь определим многочлен Бернулли В (х) = ~~1 ( )Вьх (8) Если п4 = 1, то В1(х) = Ввх+ В1 = х — -'; этот многочлен использовался выше, в соотношении (3). Если гп > 1, то согласно (7) В (1) = В = В (0),. другими словами, В,„((х)) не имеет разрывов при целых значениях х. Вскоре станет ясно, какое отношение к нашей теме имеют многочлены Бернулли н числа Бернулли.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
