(Читается эта запись так: "Я„ равно натуральному логарифму от п плюс постоянная Эйлера плюс о большое от единицы на п".)

Вообще говоря, каждый рс13, когда /(п) является функцией от положительного целого п, можно использовать запись 0(/(п)); она обозначает величину, точное значение которой неизвестно, и известно только, что ее значение не слишком велико*. Запись 0(/(п)) всегда обозначает следующее: существуют положительные константы М и щ, такие, что величина х„, представленная в виде 0(/(п)), удовлетворяет условию х„ < М /(п) для всех целых п > uq. Мы не можем сказать, каковы на самом деле эти константы М и по, так как в каждом случае они зависят от соотношения, в котором использован символ О.

Например, соотношение (1) означает, что Я„ - Inn - 7I < М/п, когда п > щ. Хотя значения констант М и по не указаны, мы можем быть уверены, что для достаточно большого п величина 0(1/п) будет сколь угодно малой.

Рассмотрим еще несколько примеров. Мы знаем, что

1+2+ +71 = гг(п 4- i)(n 4- 1) = 4- п + гг. Отсюда следует, что

1 + 2 + --- + п = 0{n), (2)

1- + 2 + - + п=0{п), (3)

I- + 2 + --- + п = п +0{п). (4)

Соо1ношенце (2) до< хагочно грубое, хотя и правильное. Соотношение (3) является более сильным, а (4) - еще сильнее. Чтобы подтвердить правильность этих соотношений, докажем, что еслп Р(п) = ао 4- йгп 4-----h Отп" -произвольный многочлен

степени, меньшей илн равной т, то Р{п) = 0(п"). Это вытекает из следующих оценок:

\Р{п)\ < Ы + ai п + • • • + laln" = (ао /п" 4- Ы/п""- + + laDn"

< (ao4-ai4----4-a)n",

где п > 1. Поэтому можно взять М = \ао\ 4- ai 4-----1- \ат\ и по = 1. Можно было

бы взять также, скажем, М = ао/2" 4- la, /2"" 4-----h lal и По = 2.

Символ О очень полезен в работе с приближенными формулами, так как позволяет кратко описать суть дела, опустив ненужные детали. Более того, с символами О можно выполнять хорошо известные алгебраические операции, хотя нужно иметь в виду некоторые особенности. Самый важный момент заключается в односторонности равенств: мы пишем п -{-п = О(п), но ни в коем случае не 0{п) - п- 4- п. (В противном случае, так как п- = О(п), можно прийти к полному абсурду, получив равенство jv? = п -Ь п.) Мы всегда следуем соглашению, что правая часть равенства несет не больше информации, чем левая; правая часть - это "огрубление" левой.

Соглашение гю поводу использования знака "=" можно более точно сформулировать следующим образом: формулы, содержащие запись 0(/(п)), можно рассматривать как множества функций от п. Запись 0(/(п)) обозна5!ает множество всех

* По сравнению с f(n) -Прим ред.

функций д от целых чисел«;ДЛя которых существуют константы М и по, такие, что \д{п)\ < М /(п) для всех целых п > щ. Если 5 и Т - множества функций, то S + T обозначает множество {д +k 3 6 5 и Л € Г}; аналогично определяются множества 5 + с, 5-Г, 5-Г, log5 и т. д. Если а{п) и 0{п) -формулы, содержащие символ О, то запись а(п) = 0{п) означает, что множество функций, относящихся к классу а(п), содержится в множестве функций, относящихся к классу 0(п).

Следовательно, большинство привычных операций можно выполнять, пользуясь знаком "=": если а(п) = /3(п) и /3(п) = 7(п), то а{п) = 7(п). Кроме того, если а{п) = /3{п) и если S{n) - формула, полученная в результате подстановки /3{п) вместо некоторых а{п) в формуле 7(п), то 7(п) = 6{п). Из этих двух утверждений следует, например, что если g{xi,X2,.. ,Хт)-любая действительная функция и если afc(n) = /Зк{п) для 1 < А; < т, то g{ai{n),a2{n), ..,am(n)) = <?(A(n),/?2(n),...,/?„(n)).

Вот некоторые простые операции, которые можно вьшолнять с символом О-

fin) О (fin)), (5)

с-0[f{n)) = 0[f{n)), если с - константа, (6)

0{f{n))+0{f{n))=0{fin)), (7)

0{Oif{n)))=0{fin)), (8)

0{fin))0{g{n))=0{f{n)g{n)), (9)

0{f{n)g{n))=fin)0{gin)). (10)

Символ О также часто используется с функциями комплексного переменного z в окрестности точки 2 = 0 Через О (/(г)) мы обозначаем люб>ю величину g{z), такую, что \g{z)\ < M\f{z)\ при \z\ < г (Как и прежде, М и г - это некоторые неопределенные константы, хотя мы мох ли бы определить их, если бы захотели.) Применительно к О-записи всегда должны указываться используемая пере.менная и область ее изменения. Если у нас переменная п, то неявно предполагается, что в записи 0(/(п)) подразумеваются функции от большого целого п Если же используется переменная г, то предполагается, что 0{f{z)) относится к функция.м малого комплексного числа z.

Предположим, что g(z)-это функция, заданная бесконечным степенным рядом

Ф) = Е"**>

it>0

сходящимся в точке z = Zq. Тогда сумма абсолютных значений 5Z>o litl сходится также при \z\ < \zo\. Если zq ф О, то можно записать

g{z) = ао + ai2 + • • + az + 0(2"+) (11)

Так как g{z) = Oq -Ь Ojz -Ь • • • -Ь OmZ™ Л- z"+(a„,+i -Ь аг -Ь • • ), нужно тотько показать, что величина в скобках ограничена при \z\ < г, где г - некоторое положительное число Действительно, величина am+i + [от+г!»" + ат+з " Н----является

ее верхней гранью при z < г < 2о.

Рассмотрим несколько примеров. Производящие функции, приведенные в разделе 1.2.9, для всех неотрицательных целых m дают важные асимптотические формулы для достаточно малых z:

1 + .+ ..

1п(1 -Ьг) = 2

+ -z"+Oiz ml

+ 0(2"+!),

(1+2)

СИ

= 1 + а2 +

(12)

(13) (14) (15)

- - 2 + H2Z + + HmZ" + 0(2™+!).

Важно отметить, что константы Миг при каждом конкретном О зависят одна от другой. Например, очевидно, что функция = 0(1) при \z\ < г для любого фиксированного г, так как \е-\ < el; но не существует константы М, такой, что \е\ < М для всех z Поэтому по мере увеличения г нам придется брать все большее и большее значение М.

Иногда асимптотическая формула справедлива, хотя не существует соответствующего сходящегося бесконечного ряда Например, основные формулы

r - m - l

к=0 т

Ir-ki

+ 0{п

г-т-1

(16)

(17)

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

,1/2-fc

расходится для всех п (см. упр. 12). Ра(умеется, если г - неотрицательное целое, то п*" и п- являются просто многочленами степени г и (17)-это, в сущности, то же, что и 1.2.6 (44) Если г - неотрицательное целое и \п\ > \г\, то бесконечная сумма J2T=o Ir-k] "" сходится к п"= 1/(п-1). Эту сумму можно записать также в более естественном виде, YlTo {Уг}~ воспользовавшись соотношением 1.2.6-(58).

Приведем один простой пример для иллюстрации введенных понятий. Рассмотрим величину {/п. По мере увеличения п последовательность корней п-й степени из фиксированного числа будет убывать, но совсем не очевидно, убывающей или возрастающей будет последовательность Оказывается, что п убывает и стремится к единице. Теперь давайте рассмотрим несколько более сложную величину п(у - 1). Здесь ({/п - 1) убывает при увеличении п. А как будет себя вести п(-1)?

Эта задача легко решается с помощью приведенных выше формул. Имеем