Выпускная квалификационная работа
«Символ О»
Содержание
Введение………………………………………………………….
Глава 1. Символ О………………………………………………..
§1. Основные определения, примеры…………………..……
§2. Основные соотношения.………………………………….
§3. Решение задач…………………………………………….
Глава 2. Приложения символа О………………………………...
§1. Асимптотическое решение трансцендентных уравнений действительного переменного..……………..……..……
§2. Асимптотическое решение интегралов………………….
§3. Асимптотическое вычисление суммы ряда…..…………
Литература………………………………………………………...
стр. 3
стр. 5
стр. 5
стр. 9
стр. 14
стр. 18
стр. 18
стр. 22
стр. 24
стр. 26
Введение
/>Слово асимптотика имеетгреческое происхождение и буквально означает «никогда не соединяющиеся». Изучаяконические сечения, древнегреческие математики рассматривали, в частности,гиперболы, такие, как график функции />,
имеющийпрямые y = x и y = -x своими «асимптотами». При /> криваяприближается к асимптотам, но никогда не соприкасается с ними. В наши дни слово«асимптотика» используется в более широком смысле для обозначения любойприближенной величины, которая становится все более точной по мере приближениянекоторого параметра к предельному значению.
Точные решения, если их удается получить, — этозамечательно: окончательный ответ вызывает чувство глубокого удовлетворения. Нои приближенное значение иногда оказывается в цене.
В 1894 году Пауль Бахман придумал обозначение для асимптотическогоанализа. В последующие годы его популярности способствовали Эдмунд Ландау и др.Мы встречаем это обозначение в формулах наподобие:
/>, (1.1)
котораяговорит нам, что n-егармоническое число равно натуральному логарифму n плюс константа Эйлера плюс некоторая величина,которая составляет «О большое от 1 на n». Эта последняя величина точно не определена, однако,какой бы она ни была, обозначение «О» позволяет утверждать, что она непревосходит константу, умноженную на 1/n.
Величину О(1/n)можно считать пренебрежимо малой, если только нас не интересуют величины,отличающиеся от 1/nлишь постоянным множителем.
Приложения символа Оможно встретить в разных областях математики, а также и в физике. Например, вкниге Панченкова А.Н. «Асимптотические методы в экстремальных задачах механики»рассматривается применение асимптотических методов в решении задачаэродинамики.
Цель дипломной работы:
изучить понятие «Символ О»и показать его применения.
Задачи:
1. Изучить понятие «Символ О»,дать определение.
2. Изучить и доказать основныесоотношения.
3. Показать применение символаО при решении задач.
4. Найти применение символа Ов различных областях математики.
На основании поставленных целейи задач квалификационная работа разбита на две главы.
Глава 1 «Символ О»состоит из трех параграфов. В первом параграфе рассматриваются основныеопределения, приводятся примеры; во втором – формулируются утверждения,приводятся их доказательства; третий параграф посвящен решению задач.
Глава 2 «Приложения символа О»освещает применение символа О, а именно, при решении трансцендентныхуравнений, при вычислении интегралов, при нахождении суммы рядов.
Глава 1. Символ О.
§1. Основные определения, примеры
Определение1:
f(n)= O(g(n)) длявсех n Î N (1.1.1)
означает, чтосуществует такая константа С, что
/> для всех n Î N; (1.1.2)
а если обозначениеO(g(n))использовано внутри формулы, то оно обозначает функцию f(n), удовлетворяющую (1.1.2). Значения функции f(n) неизвестны, но мы знаем, что они не слишком велики.
Символ «О» включает неопределенную константу С, каждоевхождение О может подразумевать различные С, но каждая из этихконстант не зависит от n.
Пример1: мы знаем, чтосумма квадратов первых nнатуральных чисел равна
n = />.
Можно записать n = О(n3),
так как /> для всех целых n. Можно получить более точную формулу
n = />О(n2), так как
/> для всех целых n. Можно также небрежно отбросить часть информации изаписать n = О(n10).
Определение О не заставляет нас давать наилучшую оценку.
Рассмотрим пример, когда переменная n – не целочисленная.
Пример2: />, где х –вещественное число.
Здесь уже нельзя сказать, что S(x) = O(x3), так как отношение /> неограниченно растет при х®0. Нельзя также сказать, что S(x) = O(x), т.к. отношение /> неограниченно растет,когда х стремится к бесконечности. Значит, мы не можем использоватьсимвол «О» для оценки S(x).
Эта дилемма разрешается благодаря тому, что на переменные, используемые сО, обычно накладываются какие-либо ограничения. Если, например, мыпоставим условие, что />, или что />, где e — произвольная положительнаяконстанта, или что х – целое число, то мы сможем записать S(x) = O(x3). Если же наложено условие /> или />, где с –произвольная положительная константа, то в этом случае S(x) = O(x). «О большое» зависит от контекста, отограничений на используемые переменные.
Эти ограничения часто задаются в виде предельных соотношений.
Определение2: соотношение f(n) = O(g(n)) при n®¥ означает, что существуют две константы С и n0, такие, что
/> при всех n ³ n0. (1.1.3)
Замечание1: Значения Си n0могут быть разными для разных О, но они независят от n.
Определение3: запись f(х) = O(g(х)) при х®0 означает, что существуют двеконстанты С и e,такие, что
/>, если только />. (1.1.4)
Теперь О представляет неопределенную функцию иодну или две неопределенные константы, зависящие от контекста.
Замечание2: запись /> корректна, но в этомравенстве нельзя менять местами правую и левую части. В противном случае мыможем прийти к нелепым выводам, наподобие n = n2,исходя из верных тождеств n = О(n2) и n2 = О(n2).
Работая с символом «О» мы имеем дело с односторонними равенствами.Правая часть уравнения содержит не больше информации, чем левая, и фактическиможет содержать меньше информации; правая часть является «огрублением» левой.
Если говорить строго формально, то запись O(g(n)) обозначает не какую-то однуфункцию f(n), а сразу множество функций f(n), таких, что /> длянекоторой константы С. Обычная формула g(n),не включающая символ О, обозначает множество, содержащее одну функцию f(n) = g(n).Если S и T суть множества функций от n, то запись S + T обозначает множество всех функций вида f(n) + g(n),где f(n)ÎS и g(n)ÎT; другие обозначения вроде S – T,ST, S/T, />, еS, ln S определяются аналогично. Тогда «равенство» между двумя такимимножествами функций есть теоретико-множественное включение; знак «=» вдействительности означает «Í».
Пример3: «Уравнение» /> означает, что S1 Í S2, где S1есть множество всех функций вида />, длякоторых найдется константа С1, такая, что />, а S2 есть множество всех функций />, для которых найдетсяконстанта С2, такая, что />.
Можно строго доказать это «равенство», если взять произвольный элемент излевой части и показать, что он принадлежит правой части: пусть /> таково, что />, следует доказать, чтосуществует такая константа С2, что />. Константа /> решает проблему, так как /> для всех целых n.
Замечание3: Если в формулеиспользуется несколько переменных, то символ О представляет множествофункций от двух или более переменных, а не только от одной. В областьопределения каждой функции входят все переменные, которые в данном контексте«свободны» для изменения.
Тут есть некоторая тонкость ввиду того, что переменные могут иметь смысллишь в части выражения, если они связаны знаком S или подобным.
Пример4: />, целое n ³ 0. (1.1.5)
Выражение k2 + O(k) в левой части отвечает множеству всех функций отдвух переменных вида k2 + f(k, n),для которых найдется константа С, такая, что /> для 0 £ k £ n.Сумма таких множеств функций для 0 £ k £ n есть множество всех функций g(n) вида
/>,
где f удовлетворяет сформулированномуусловию. Поскольку
/>то все такие функции g(n)принадлежат правой части (1.1.5); следовательно, (1.1.5) справедливо.
§2. Основные соотношения
Соотношение1: /> если />. (1.2.1)
Доказательство:
Пусть />, тогда /> по свойству степени имодуля. />, где С = 1. А поопределению (1.1.2) символа О это и означает, что /> при />. Соотношение 1 доказано.
Соотношение2: />. (1.2.2)
Доказательство:
Покажем строго в соответствии с теоретико-множественнымопределением символа О, что левая часть является подмножеством правойчасти.
Любая функция из левой части имеет вид a(n) + b(n), и существуют константы m0, B, n0, C, такие, что
/> и />.
Следовательно, функция в левой части
/>
А, значит, по определению символа О левая часть принадлежит правойчасти. Соотношение 2 доказано.
Соотношение3: f(n) = O(f(n)); (1.2.3)
Доказательство:Для любой функции f(n) верно неравенство />./>, гдеС = 1. Поопределению символа О (1.1.2) это и означает, что f(n) = O(f(n)). Соотношение 3 доказано.
Соотношение4: O(f(n))O(g(n)) = O(f(n)g(n)); (1.2.4)
Доказательство:
Покажем в соответствии с теоретико-множественнымопределением символа О, что левая часть является подмножеством правойчасти.
В левой части функции имеют вид a(n) × b(n), такие, что существуют константы В, С,n0, m0, что
/> и
/>.
Тогда /> для любого n ³ max(n0, m0,). Значит левая частьпринадлежит правой части, а, следовательно, является подмножеством правой частипо определению символа О. Соотношение 6 доказано.
Соотношение5: O(O(f(n))) = O(f(n)); (1.2.5)
Доказательство:
Покажем, что левая часть является подмножеством правойчасти.
Функция из левой части имеет вид a(n)такой, что существуют положительные константы С, В, n0, m0такие, что
/>
Следовательно, по определению левая часть является подмножеством правойчасти. Соотношение 5 доказано.
Соотношение 6: С × O(f(n)) = O(f(n)), если С – константа; (1.2.6)
Доказательство:
Существует такая константа В, что />,по определению (1.1.1) С = О(1). Тогда С × O(f(n)) = О(1) × O(f(n)) = (по 1.2.4) = O(f(n)).
Соотношение доказано.
Соотношение7: O(f(n)g(n)) = f(n)O(g(n)). (1.2.7)
Доказательство:
Покажем, что левая часть является подмножеством правойчасти.
В левой части функции имеют вид a(n),такие, что существуют константы С, n0, что
/>.
По определению символа О мы получаем верное равенство (1.2.7).Соотношение 7 доказано.
Соотношение8: O(f(n)2) = O(f(n))2. (1.2.8)
Доказательство:
O(f(n)2) = O(f(n) · f(n)) = (по 1.2.7)= f(n) · O(f(n)) = (по 1.2.3) = О(f(n)) · O(f(n)) = O(f(n))2
Соотношение доказано.
Соотношение9: еO(f(n)) = 1 + O(f(n)), если f(n) = О(1) (1.2.9)
Доказательство:
еO(f(n)) = еg(n), где/>. Т.к. f(n) = О(1), т.е. />,то/>.
/>
/>. Значит еO(f(n)) = 1 + O(f(n)).
Соотношение доказано.
Соотношение10: Если сумма /> сходится абсолютно длянекоторого комплексного числа z = z0, то
/>.
Доказательство:
Данное соотношение очевидно,поскольку
/>.
Соотношение доказано.
Замечание4: В частности, S(z) = O(1) при z ® 0 и S(1/n) = O(1) при n ® ¥ при том только условии, что S(z) сходится хотя бы для одного ненулевого значения z. Мы можем использовать этот принципдля того, чтобы, отбросив хвост степенного ряда, начиная с любого удобногоместа, оценить этот хвост через О. Так, например, не только S(z) = O(1), но и
S(z) = a0 + O(z), S(z) = a0 + a1z + O(z2),
и т.д.,поскольку
/>,
а последняясумма, как и сама S(z), абсолютно сходится при z = z0и есть О(1).
В таблице №1 приведены самые полезные асимптотические формулы [2],половина из которых получена просто путем отбрасывания членов степенного ряда всоответствии с этим правилом.Таблица №1
Асимптотическиеаппроксимации, справедливые при n ® ¥ и z ® 0
/> (1.2.10)
/> (1.2.11)
/> (1.2.12)
/> (1.2.13)
/> (1.2.14)
/> (1.2.15)
Асимптотические формулы для Hn, n!не являются начальными отрезками сходящихся рядов; если неограниченнопродолжить эти формулы, то полученные ряды будут расходиться при всех n.
Говорят, что асимптотическая аппроксимация имеет абсолютную погрешность O(g(n)),если она имеет вид f(n) + O(g(n)), где f(n)не включает О. Аппроксимация вида f(n)(1 + O(g(n)))имеет относительную погрешность O(g(n)), если f(n) не включает О. Например,аппроксимация Hnв таблице №1 имеет абсолютную погрешность O(n-6); аппроксимацияn! — относительную погрешность O(n-4). (Правая часть (1.2.11) не такая,как требуется, — f(n)(1 + O(n-4)), но ее можно переписать как
/>.
Абсолютная погрешность этой аппроксимации есть O(nn-3.5e-n). Абсолютная погрешность соотноситсяс числом верных десятичных цифр справа от десятичной точки, которые сохраняютсяпосле отбрасывания члена О; относительная погрешность связана с числомверных «значащих цифр».
§3. Решение задач
Задача1. Что неверно вследующих рассуждениях? Поскольку n = O(n) и 2n = O(n) и так далее, то заключаем, что />?
Решение:
Замена kn на O(n) подразумевает различные С для различных k; а нужно, чтобы все О имелиобщую константу. В действительности, в данном случае требуется, чтобы Ообозначало множество функций двух переменных, k и n.Правильно будет записать />.
Задача 2. Докажите или опровергните: О(f(n) + g(n)) = f(n) + O(g(n)),если f(n) и g(n) положительны для всех nÎN.
Решение:Утверждение ложно.Пусть f(n) = n2,а g(n) = 1.Найдем такую функцию j(n), которая бы принадлежала левому множеству, но непринадлежала бы правому множеству, т.е. ($С1)("n)[j(n)£ C1(n2 + 1)] и ("С2)($n³n0)[j(n)> n2 + C2].Возьмем j(n) = 2n2.1). Пусть С1 = 3, тогда ("n³n0)2n2 £3(n2 + 1). Значит функция j(n)принадлежит левому множеству.2). ("С2) ($n>/>) 2n2 > n2+ C2. Значит функция j(n) непринадлежит правому множеству.
Задача 3. Докажите или опровергните: cos O(x) = 1 + O(x2) для всехвещественных х.
Решение:
Если функция g(x) принадлежит левой части так, что g(x) = cos y для некоторого y, причем /> длянекоторой константы С, то
g(x) = cos y = 1 — 2sin2 (y/2) £ 1= 1 + 0 × х2. Значитсуществует такая константа В, что g(x) £ 1 + В × х2. Следовательно,множество из левой части содержится в правой части, и формула верна.
Задача 4. Докажите, что />.
Решение:
Преобразуем левую часть следующимобразом:
/>.
Заметим, что />, тогда />, где С – константа,тогда можно записать по определению символа О, что />. Используя это дляпреобразованного равенства, получаем, что
/> = (по 1.2.4)
/>
Что и требовалось доказать.
Задача 5. Вычислите /> при nÎN.
Решение:
/>
/> (по 1.2.6)
/> (по 1.2.3)
/>(по 1.2.4)
/> (по 1.2.2)
/>/>
Задача6. Вычислите (n + 2 + O(n-1))n с относительной погрешностью
O(n-1), при n®¥.
Решение:
/>
/> (по 1.2.3 и 1.2.4)
/>
При n®¥ k = (2n-1+ O(n-2))®0, тогда ln (1+ k)®0. Тогда при n®¥
ln (1 + k) = k.
/>/> (по 1.2.9)
/>.
Задача 7. Докажите, что />, при nÎN, n®¥.
Решение:
Покажем, что />. (*)
Поопределению /> - функция аn такая, что />. Получаем, что />, значит />.
Теперьдокажем, что />:
/>= (по 1.2.4 и 1.2.6) = /> = (по (*))
= /> (по 1.2.6) = />(по 1.2.9)
= /> (по 1.2.6) =/>.
Глава 2. Приложения символа О.
§1. Асимптотическое решениетрансцендентных уравнений: действительного переменного
Пример 1.
Рассмотрим уравнение
x +th x = u,
где u — действительныйпараметр, /> - гиперболический тангенс[6], />, х и th x – непрерывные, строго возрастающие функции на всейчисловой прямой.
Найдем асимптотическиеприближения для корня:
1). Функция u(x) = x +th x непрерывна и строго монотонна на R.По теореме о непрерывности обратной функции, существует обратная к ней функция х(и),непрерывная и строго монотонная на Еи = R.
Так как при х®¥ и(х)®¥, то при и®¥ х(и)®¥.
Пусть и®¥,тогда х®¥ и />.
Значит, х(и) ~ и,при и®¥. Это первое асимптотическое приближениедля корня.
2). Приведем уравнение к виду:
x = и — th x.
/>+С,где С – некоторая константа. По определению символа О thx = 1+O(1).
x =и – 1 + О(1) — это второе асимптотическое приближение корня.
3). Докажем, что е-2х= О(е-2и): (2.1.1)
подставим второеасимптотическое приближение корня
е-2х = е-2(и – 1+ О(1))= е-2и × е2×еО(1)= (по 1.2.3 и 1.2.9) = е2О(е-2и)(1+ О(1))×=
(по 1.2.3) = е2О(е-2и)(2О(1)) = (по 1.2.6 и 1.2.4) = О(е-2и).
Разложим th x в ряд [6], удобный прибольших х:
th x =1 – 2е-2х + 2е-4х – 2е-6х +… (х> 0)
Тогда по теореме [3]: (2.1.2)
если ряд /> сходится при />, тогда для фиксированного n /> влюбом круге />, где />.
Ряд – 2е-2х + 2е-4х– 2е-6х +… сходится при х > 0, т.е. /> и его сумма равна th x — 1. Значит, по теореме: th x — 1 = О(е-2х), т.е.
th x=О(е-2х)+1.
Тогда x= и — th x = и – 1 + О(е-2х) = (по 2.1.1) = и– 1 + О(О(е-2и)) =
(по 1.2.5) = и – 1 + О(е-2и).
Таким образом, x = и – 1 + О(е-2и) — этот третьеасимптотическое приближение корня.
4). Докажем, что е-2х= е-2и+2 + О(е-4и): (2.1.3)
подставим третьеасимптотическое приближение корня
/>(по1.2.9)/>
/>(по1.2.6)/>
(по 1.2.3 и 1.2.4)/>.
Ряд 2е-4х – 2е-6х+ 2е-8х – 2е-10х +… сходится при х > 0,т.е. /> и его сумма равна th x –1 + 2е-2х. Значит, по теореме: th x – 1 + 2е-2х =О(е-4х),
т.е. th x=О(е-4х)+1 — 2е-2х.
Тогда x= и — th x = и – 1 + 2е-2х + О(е-4х)= (по 2.1.3) =
= и – 1 + 2(е-2и+2 + О(е-4и))+ О(е-4х) = (по 1.2.6) =
= и – 1 + 2е-2и+2 + О(е-4и)+ О(е-2х × е-2х)= (по 2.1.1) =
= и – 1 + 2е-2и+2 + О(е-4и)+ О(О(е-2и)×О(е-2и)) = (по 1.2.4) =
= и – 1 + 2е-2и+2 + О(е-4и)+ О(О(е-4и)) = (по 1.2.5) =
= и – 1 + 2е-2и+2 + О(е-4и)+ О(е-4и) = и – 1 + 2е-2и+2 + 2О(е-4и)= (по 1.2.6) =
= и – 1 + 2е-2и+2 + О(е-4и).
Таким образом, x = и – 1 + 2е-2и+2 + О(е-4и) — этот четвертое асимптотическое приближение корня.
Продолжая этот процесс, получимпоследовательность приближений с ошибками, асимптотический порядок которыхпостоянно убывает. Сходимость этой последовательности при неограниченномвозрастании числа шагов на основе проведенных рассуждений увидеть трудно, ночисленные возможности этого процесса можно оценить, взяв, например, и =5:
1) х = 5;
2) х = и – 1 + О(1)= 5 – 1 = 4; (не учитываем ошибку О(1))
3) x= и – 1 + О(е-2и) = 5 – 1 = 4; (не учитываем ошибку О(е-2и))
4) x= и – 1 + 2е-2и+2 + О(е-4и) = 5 – 1 +0,000670925… = 4,000670925… (не учитываем ошибку О(е-4и))
Точное значение, полученноестандартными численными методами, равно 4,0006698…
Пример 2.
Найдем большие положительныекорни уравнения
x tg x = 1
Это уравнение можно обратитьследующим образом:
/>,
где n –целое число, а арктангенс принимает значения в интервале />, находим, что x ~ np при(n → ¥).
Если x > 1, то [6]
/>
1). По теореме (2.1.2) />.
/>.
2). />
По теореме (2.1.2) />. Тогда />.
/>.
3). />
По теореме (2.1.2) />. Тогда />.
/>.
И так далее.
§2. Асимптотическое решениеинтегралов
Пример 1. Вычислить /> при х > 1.
Разложим в ряд [6]:
/>
По теореме (2.1.2) />, т.е. />.
/>
Пример 2. Вычислить /> при e®+0,/>, А(х) — ступенчатаяфункция: А(х) = 0 при х А(х) = Аk, k £ x k+ 1,
Аk = а1 + а2+…+ аk ,аk = k -1. Причем />.
Воспользуемся асимптотическойформулой [4]
/>,
где g — постоянная Эйлера />. Введем функцию Ã(х)= lnx + g.
/>
/>.
Последний интеграл имеетпорядок О(e ln e) при e®+0,а предпоследний – равен -g/2,так что
/>.
S(e) = I+ J, где
/>.
Оценим интеграл J. Пусть />, тогда" k ³ 1
/>.
Прологарифмируем />, получим />. Значит />
Следовательно,
/>.
Получаем, что
/>.
§3. Асимптотическое вычисление суммыряда
При нахождении суммы ряданередко используется формула суммирования Эйлера [2]:
/>
где />
Вk –числа Бернулли, Вm({x}) – многочлен Бернулли.
Вk = (-1)kb2k. [6]
/>. Коэффициенты bkвычисляются, используя теорему о единственности разложения функции в степеннойряд:
/>
путем приравнивая коэффициентов:
коэффициент при х: b0= 1,
коэффициент при хk: />
/>
Пример 1. Найти />.
По 1.2.10 Нk = ln k + O(1). Тогда />.
/> Применим формулусуммирования Эйлера:
/>
/>
/>
/>
/>.
Пример 2. Найти />
Применим формулу суммированияЭйлера:
/>
/>/>
Пример 3. Найти асимптотику при n ® ¥ суммы />
Члены этой суммы быстро растутс ростом номера, так что главный член асимптотики равен последнему члену суммы:S(n) ~ n!, n ® ¥. Действительно,
/>
Следовательно,
/>
Литература
1. Брейн, Н.Г. Асимптотические методы в анализе / Н.Г. Брейн. – М.:Иностранная литература, 1961.
2. Грэхем, Р. Конкретная математика. Основание информатики: Пер. с англ. /Р. Грэхем, Д. Кнут, О. Паташник. – М.: Мир, 1998.
3. Олвер, Ф. Введение в асимптотические методы и специальные функции / Ф.Олвер. – М.: Наука, 1978.
4. Панченков, А.Н. Асимптотические методы в экстремальных задачах механики/ А.Н. Панченков. – Новосибирск: Наука, 1982.
5. Федорюк, М.В. Асимптотика: интегралы и ряды / М.В. Федорюк. – М.: Наука,1987.
6. Фихтенгольц, Г.М. Курс дифференциального и интегрального исчисления. Том2. / Г.М. Фихтенгольц. – М.: Наука, 1969.