9.3 ОПЕРАЦИИ С «О»

Как и для любого математического формализма, в случае О-обозначений имеются правила оперирования с ними, освобождающие нас от обращения к громоздкому определению. Доказав один раз, с использованием определения, справедливость

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

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

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

В упр. 9 доказывается (9.22); доказательства остальных правил аналогичны. Можно всегда заменять что-либо, имеющее вид одной из левых частей на то, что записано справа, безотносительно к ограничениям на переменную

Соотношения (9.27) и (9.23) позволяют доказать тождество Это свойство позволяет иногда сэкономить скобки, поскольку мы теперь можем писать

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

А можно ли также писать

Нет! Это некорректно, поскольку множество функций не является ни подмножеством, ни „надмножеством" для Правильно будет заменять но это выглядит нелепо. Так что мы будем использовать „возведение О в степень" только в тех случаях, когда показатель степени является целой положительной константой.

Степенные ряды дают нам одну из самых полезных операций. Если сумма

сходится абсолютно для некоторого комплексного числа то

Это очевидно, поскольку

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

и т. д., поскольку

а последняя сумма, как и сама абсолютно сходится при и есть . В табл. 491 приведены самые полезные асимптотические формулы, половина из которых получена просто путем отбрасывания членов степенного ряда в соответствии с этим правилом.

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

справедливую для . В табл. 491 этот принцип иллюстрируется асимптотической формулой для чисел Бернулли

С другой стороны, асимптотические формулы для в табл. 491 не являются начальными отрезками сходящихся рядов; если неограниченно продолжить эти формулы, то полученные ряды будут расходиться при всех Особенно легко просматривается это в случае поскольку, как мы уже видели в разд. 7.3, пример 5, степенной ряд всюду расходится. И тем не менее эти отрезки расходящихся рядов дают полезные аппроксимации.

Говорят, что асимптотическая аппроксимация имеет абсолютную погрешность если она имеет вид где не включает О. Аппроксимация вида

Таблица 491 Асимптотические аппроксимации, справедливые при

имеет относительную погрешность если не включает О. Например, аппроксимация в табл. 491 имеет абсолютную погрешность аппроксимация — относительную погрешность (Правая часть (9.29) не такая, как требуется, — ), но ее можно при желании переписать как

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

Воспользовавшись сокращением степенных рядов, мы можем доказать общие правила

(Здесь мы предполагаем, что аналогичные формулы для имеют место при Пусть, например, какая-то функция, лежащая в множестве, описываемом левой частью (9.36). Тогда найдутся константы , такие, что

Отсюда следует, что бесконечная сумма

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

Задача 1: снова колесо Фортуны

Попробуем теперь попытать счастья в некоторых асимптотических задачах. В гл. 3 мы вывели уравнение (3.13) для числа выигрышных позиций в одной игре:

Мы обещали, что асимптотическое значение будет вычислено в гл. 9. Сейчас мы как раз в главе 9; так что попробуем оценить при

Основная идея — избавиться от скобок и заменив К на Далее, мы можем записать

это называется „вынести за скобки главную часть! (Мы еще неоднократно воспользуемся этим приемом.) Теперь, из (9.38) и (9.26) имеем

Аналогично,

Отсюда следует, что число выигрышных позиций есть

Обратите внимание, как члены с О поглощают друг друга, пока не останется только одно О; это — типичная ситуация и еще одна иллюстрация полезности символа О внутри формул.

Задача 2: метаморфозы формулы Стирлинга

Аппроксимация Стирлинга для есть, без сомнения, самая знаменитая асимптотическая формула. Мы докажем ее позднее в этой главе; пока же попробуем лучше познакомиться с ее свойствами. Мы можем записать один из вариантов аппроксимации в виде

для некоторых констант а и Поскольку эта аппроксимация имеет место при всех больших она должна остаться в силе, если заменить на

Мы знаем, разумеется, что следовательно, правая часть последней формулы должна приводиться к правой части (9.40), поделенной на

Попробуем поэтому упростить (9.41). Из первого сомножителя можно вынести главную часть:

Здесь использовано соотношение (9.35).

Аналогично имеем

Единственная часть (9.41), преобразование которой требует некоторой изобретательности, - это множитель который равняется

(Мы выписываем члены до тех пор, пока не получим относительную погрешность Дело в том, что относительная погрешность произведения равна сумме относительных погрешностей сомножителей и все члены объединяются.)

Чтобы раскрыть мы сначала вычислим и затем образуем экспоненту,

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

Итак, мы привели правую часть (9.41) к виду умножить на умножить на произведение нескольких

Перемножая скобки и включая все асимптотически малые члены в получим

Н-да-а, мы надеялись прийти к поскольку именно это требуется для соответствия с правой частью (9.40). Мы где-то ошиблись? Нет, все правильно; следовательно, а

Это рассуждение не доказывает справедливость аппроксимации Стирлинга, но кое-что все-таки доказано, а именно то, что формула (9.40) не может иметь места, если а не равно Если заменить в (9.40) на и проделать все вычисления с относительной погрешностью то можно заключить, что в соответствии с табл. 491. (Этот способ определения а и не самый простой, но он работает.)

Задача простое число

Соотношение (9.31) есть асимптотическая формула для числа простых, не превосходящих Заменяя на

простое число, мы получаем следовательно

при Попробуем „решить" это уравнение относительно ; тогда мы найдем приблизительную величину простого числа.

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

(Имеем так как

Второй шаг — переставить две части (9.42), исключая О. Эта процедура допустима ввиду общего правила:

(Любое из этих соотношений следует из другого, если умножить обе части на —1 и прибавить Следовательно,

и, значит,

Это уравнение — „приближенное рекуррентное соотношение" для выражающее его через самого себя. Наша цель — преобразовать его в „приближенную замкнутую форму", и мы сможем сделать это, раскрывая рекуррентное соотношение асимптотически. Итак, попробуем раскрыть (9.44).

Прологарифмировав обе части, получим

Это значение можно подставить вместо в (9.44), однако хотелось бы, прежде чем выполнять подстановку, полностью избавиться от в правой части. Где-то в ходе преобразований последнее должно исчезнуть; но от него нельзя избавиться обычным для рекуррентных соотношений способом, поскольку в (9.44) не определены начальные условия для малых .

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

поскольку и правая часть стремится к нулю при Прекрасно, мы теперь знаем, что следовательно,

. Теперь мы можем получить из (9-45)

имея в руках эту оценку, мы можем заключить, что и, наконец, (9.45) дает

Это выражение можно подставить в правую часть (9.44), и мы получим

Это и есть приближенная величина простого числа.

Эту оценку можно улучшить, использовав вместо (9.42) более точную аппроксимацию Следующий член (9.31) говорит нам, что

действуя, как раньше, получим рекуррентное соотношение

имеющее относительную погрешность вместо Логарифмируя и сохраняя члены до нужной точности (но не слишком много), получим

Наконец, мы подставляем эти результаты в (9.47) и вот он, ответ:

Если, например, то это выражение дает в действительности миллионное простое число равно 15485863. Упражнение 21 показывает, что можно получить еще более точное приближение к если вместо (9.46) начать с более точного приближения к

Задача 4: одна сумма из старого итогового экзамена

Когда в 1970-71 г. в Станфордском университете началось преподавание конкретной математики, студентам предлагалось найти асимптотическое значение суммы

с относительной погрешностью Представим, что мы сдаем итоговый (домашний) экзамен и нам только что предложили именно эту задачу; какой будет наша первая инстинктивная реакция?

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

вполне естественно попытаться просуммировать все эти оценки:

Мы как будто приближаемся к результату полученному из суммы первых двух столбцов, но вычисления что-то уж очень разрастаются.

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

во-вторых, такой лучший метод, и много лучший, действительно есть, причем он находится прямо у нас перед глазами.

Действительно, нам известно выражение в конечном виде, это просто . Кроме того, мы знаем хорошую аппроксимацию для гармонических чисел; применим ее дважды:

Теперь можно вынести главный член и произвести упрощения, как мы делали при анализе аппроксимации Стирлинга. Имеем

После ряда удачных сокращений мы получим

плюс члены вида Чуть-чуть арифметики — и можно идти гулять:

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

Если мы сделали ошибку, скажем на в коэффициенте при то разность в 4 проявится в пятой десятичной цифре; так что наша асимптотическая формула, видимо, правильна.

Задача 5: бесконечная сумма

Теперь обратимся к одному вопросу об асимптотике, поставленному Соломоном Голомбом [78]: чему равно приближенное значение

где — число цифр, требуемых для записи числа в системе счисления с основанием

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

Поэтому мы ожидаем, что есть примерно для некоторой константы С.

Подобный быстрый анализ полезен для ориентации, однако, чтобы решить задачу, нужна лучшая оценка. Одна из возможных идей — выразить точно:

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

Действуя как в задаче 1, мы можем попробовать записать и подставить это выражение в формулу для Слагаемое, записанное здесь как всегда лежит между 0 и 1 и в среднем близко к так что оно себя ведет, наверное, очень хорошо. Но, тем не менее, эта аппроксимация недостаточно точная, чтобы сказать что-нибудь о она дает нуль значащих цифр (т. е. большую относительную ошибку) при малых к, а именно эти слагаемые вносят основной вклад в сумму. Нужна новая идея.

Ключ к решению (как в задаче 4) — применить наше искусство преобразования выражений и, прежде чем переходить к асимптотическим оценкам, привести сумму к более удобному виду. Можно ввести новую переменную суммирования

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

Однако пока мы придержим ее при себе и попытаемся еще кое-что упростить. Не надо спешить с переходом к асимптотическим оценкам. Суммирование по частям позволяет сгруппировать члены с одинаковыми значениями которые нам придется аппроксимировать:

Например, умножается на 1/22 и затем — на —1/32. (Мы воспользовались также тем, что

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

Теперь наша сумма сведется к

Осталось расписать четыре суммы: что уже просто.

Начнем, пожалуй, с , поскольку входит в О; таким образом, сразу будет видно, какую погрешность мы получим. (Нет смысла выполнять остальные вычисления с высокой точностью, если эти члены будут все равно поглощены О.) Эта сумма есть просто степенной ряд

и этот ряд сходится при так что мы можем оборвать его в любом желаемом месте. Если оставить от только слагаемые с то получим следовательно, (9.53) имеет абсолютную погрешность (Чтобы уменьшить эту погрешность можно было бы использовать более точную аппроксимацию для однако сейчас нам вполне достаточно точности

Если оборвать на слагаемом с получим и

это как раз та точность, что нам нужна.

Совсем просто вычислить :

Это телескопический ряд

Наконец, дает главный член суммы коэффициент при в (9.53):

Это есть

(Не примени мы раньше суммирование по частям, мы бы непосредственно увидели, что поскольку так что суммирование по частям не помогает в оценке главного члена, однако оно упрощает кое-что другое.)

Итак, мы оценили каждую из сумм в (9.53), и теперь можно объединить все и выписать ответ к задаче Голомба:

Заметьте, что это выражение растет медленнее, чем наша исходная прикидочная оценка Случается, что дискретные суммы не соответствуют интуиции, основанной на непрерывности.

Задача 6: Ф большое

В конце гл. 4 мы нашли, что число дробей Фарея составляет где

в (4.62) мы показали, что

Попробуем теперь оценить когда велико. (Именно суммы такого вида, в первую очередь, привели Бахмана к введению символа О.)

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

поскольку функция Мёбиуса принимает значения только —1, 0 или +1. Слагаемое в последнем множителе добавляет но для это нуль, так что сумма не может быть больше чем по абсолютной величине.

Этот предварительный анализ показывает, что, вероятно, удобно будет записать

Таким образом, мы убрали функцию пол; остается оценить сумму с точностью иными словами, мы хотим оценить с точностью Но это уже легко; можно просто распространить сумму на все значения к до добавляемые при этом члены составят

Мы доказали в (7.89), что Следовательно, и мы получаем ответ: