9.4 ДВА АСИМПТОТИЧЕСКИХ ПРИЕМА

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

Трюк 1: раскрутка

При оценке простого числа в задаче 3 из разд. 9.3 мы решали асимптотическое рекуррентное соотношение вида

Мы доказали, что сначала использовав рекуррентное соотношение для получения более слабого результата Это частный случай общего метода, называемого раскруткой (bootstrapping), в котором для нахождения асимптотического решения рекуррентного соотношения мы начинаем с грубой оценки и подставляем ее в рекуррентное соотношение; таким способом часто удается получать все лучшие и лучшие оценки, как бы „поднимая себя за волосы"

Следующая задача очень хорошо иллюстрирует метод раскрутки: каково асимптотическое значение коэффициента в производящей функции

при Продифференцировав это выражение по найдем

приравнивание коэффициентов при в обеих частях дает рекуррентное соотношение

Наша задача эквивалентна нахождению асимптотической формулы для решения (9.58) с начальным условием Первые несколько значений

мало что дают для выявления закономерности, а целочисленная последовательность не встречается в справочнике Слоана [276], так что о нахождении в замкнутой форме, видимо, не может быть речи, и лучшее, на что можно надеяться, - это вывод асимптотики.

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

Это уравнение можно использовать в качестве отправной точки для раскрутки: подставляя его в правую часть (9.58), получим

следовательно,

Можно сделать еще один шаг раскрутки:

что

Продолжится ли это до бесконечности? Может быть, мы получим для всех

На самом деле нет; мы уже достигли поворотного пункта. Попытка продолжить раскрутку приведет к сумме

которая есть так что мы не сможем получить для оценку, меньшую чем

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

Первая сумма здесь поскольку сходится для всех Вторая сумма — это „хвост" первой; можно получить верхнюю оценку, воспользовавшись (9.59):

Последняя оценка справедлива потому, например, что

(В упр. 54 рассматривается более общий способ оценки остатков подобных рядов.)

Третья сумма в (9.60) равна

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

Наконец, мы можем вновь подставить эту формулу в рекуррентное соотношение, выполнив еще один шаг раскрутки; в результате получим

(Упражнение 23 „заглядывает внутрь" оставшегося О.)

Трюк 2: смена „хвостов“

Вывод (9.62) был в чем-то такой же, как вывод асимптотического значения (9.56) для в обоих случаях мы начинали с конечной суммы, но к асимптотическому выражению приходили через рассмотрение бесконечной суммы. При этом нельзя было просто получить бесконечную сумму, добавив О к слагаемым; вместо этого приходилось действовать аккуратно и использовать один подход для малых к и другой — для больших.

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

1 Сначала разбить весь диапазон суммирования на два непересекающихся диапазона Сумма по должна быть

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

2 Найти асимптотическую оценку

справедливую при к Не требуется, чтобы эта оценка имела место при к

3 Наконец, доказать, что каждая из трех сумм

Если все три шага успешно завершаются, то получаем в итоге хорошую оценку:

Вот как это можно обосновать. Мы можем „обрубить" хвост у данной суммы, получив хорошую оценку в диапазоне там где это действительно нужно:

Хвост же можно заменить другим, даже весьма плохо аппроксимирующим первый, поскольку ни один из них не играет заметной роли:

Например, когда мы оценивали сумму в (9.60), имели

диапазоны суммирования были

и мы нашли, что

Это дало (9.61).

Аналогично, оценивая в (9.55), мы взяли

Мы вывели (9.56), заметив, что

Рассмотрим еще один пример, где эффективно такое „перебрасывание хвоста". (В отличие от предыдущих примеров, этот иллюстрирует рассматриваемый трюк в его максимальной общности, с ) Мы хотим найти асимптотическое значение величины

Основной вклад в эту сумму вносят малые к ввиду наличия в знаменателе . В диапазоне малых к имеем

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

(В рассматриваемом диапазоне

Следовательно, мы можем применить описанный трехшаговый метод, положив

Все, что остается сделать, - это найти хорошие оценки для трех величин! в (9.63), и мы установим, что

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

так что ее можно записать как Погрешность, вносимая новым хвостом, составляет

Поскольку ! растет быстрее любой степени эта маленькая погрешность поглощается слагаемым Хвост исходного ряда,

еще меньше.

И наконец, можно легко вычислить сумму в заммкнутом виде, и мы получаем желаемую асимптотическую формулу:

Из использованного метода совершенно ясно, что, на самом деле,

для любого фиксированного (Это начальный отрезок ряда, который расходится для любого фиксированного если устремить к )

В нашем решении есть только один недостаток: мы были чересчур осторожными. Мы вывели (9.64) в предположении тогда как в упр. 53 показывается, что эта оценка в действительности справедлива для всех значений к. Знай мы этот более сильный результат, нам не пришлось бы использовать трюк с двумя хвостами; мы могли бы сразу прийти к окончательному результату! Однако позднее нам встретится задача, где смена хвостов является единственным разумным приемом.