Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
9.4 ДВА АСИМПТОТИЧЕСКИХ ПРИЕМАТеперь, приобретя некоторую легкость в обращении с О, попробуем взглянуть на сделанное, имея в виду более далекую перспективу. Тогда наш арсенал асимптотических методов пополнится новыми важными боевыми средствами, которые понадобятся нам для борьбы с более трудными задачами. Трюк 1: раскрутка При оценке
Мы доказали, что Следующая задача очень хорошо иллюстрирует метод раскрутки: каково асимптотическое значение коэффициента
при
приравнивание коэффициентов при
Наша задача эквивалентна нахождению асимптотической формулы для решения (9.58) с начальным условием
мало что дают для выявления закономерности, а целочисленная последовательность Нашим первым шагом на пути решения задачи будет наблюдение, что
Это уравнение можно использовать в качестве отправной точки для раскрутки: подставляя его в правую часть (9.58), получим
следовательно,
Можно сделать еще один шаг раскрутки:
что
Продолжится ли это до бесконечности? Может быть, мы получим На самом деле нет; мы уже достигли поворотного пункта. Попытка продолжить раскрутку приведет к сумме
которая есть В действительности, сейчас мы уже знаем о
Первая сумма здесь
Последняя оценка справедлива потому, например, что
(В упр. 54 рассматривается более общий способ оценки остатков подобных рядов.) Третья сумма в (9.60) равна
это устанавливается с помощью уже знакомых аргументов. Итак, (9.60) доказывает, что
Наконец, мы можем вновь подставить эту формулу в рекуррентное соотношение, выполнив еще один шаг раскрутки; в результате получим
(Упражнение 23 „заглядывает внутрь" оставшегося О.) Трюк 2: смена „хвостов“ Вывод (9.62) был в чем-то такой же, как вывод асимптотического значения (9.56) для Эти наши рассуждения суть частные случаи важного трехшагового асимптотического метода суммирования, который мы сейчас и обсудим с большей общностью. Если нам нужно оценить значение 1 Сначала разбить весь диапазон суммирования на два непересекающихся диапазона „подавляющей" частью, в том смысле, что она включает достаточно членов, чтобы верно представлять наиболее значащие цифры всей суммы при больших 2 Найти асимптотическую оценку
справедливую при к 3 Наконец, доказать, что каждая из трех сумм
Если все три шага успешно завершаются, то получаем в итоге хорошую оценку:
Вот как это можно обосновать. Мы можем „обрубить" хвост у данной суммы, получив хорошую оценку в диапазоне
Хвост же можно заменить другим, даже весьма плохо аппроксимирующим первый, поскольку ни один из них не играет заметной роли:
Например, когда мы оценивали сумму в (9.60), имели
диапазоны суммирования были
и мы нашли, что
Это дало (9.61). Аналогично, оценивая
Мы вывели (9.56), заметив, что Рассмотрим еще один пример, где эффективно такое „перебрасывание хвоста". (В отличие от предыдущих примеров, этот иллюстрирует рассматриваемый трюк в его максимальной общности, с
Основной вклад в эту сумму вносят малые к ввиду наличия в знаменателе
Мы можем доказать эту оценку для
(В рассматриваемом диапазоне Следовательно, мы можем применить описанный трехшаговый метод, положив
Все, что остается сделать, - это найти хорошие оценки для трех величин! в (9.63), и мы установим, что Погрешность, допущенная в главной части суммы,
Поскольку
еще меньше. И наконец, можно легко вычислить сумму в заммкнутом виде, и мы получаем желаемую асимптотическую формулу:
Из использованного метода совершенно ясно, что, на самом деле,
для любого фиксированного В нашем решении есть только один недостаток: мы были чересчур осторожными. Мы вывели (9.64) в предположении
|
1 |
Оглавление
|