Выпускная квалификационная работа
«Символ О»
Содержание
| Введение…………………………………………………………. Глава 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 = $IMAGE6$.
Можно записать n = О(n3),
так как $IMAGE7$ для всех целых n. Можно получить более точную формулу
n = $IMAGE8$О(n2), так как
$IMAGE9$ для всех целых n. Можно также небрежно отбросить часть информации и записать n = О(n10).
Определение О не заставляет нас давать наилучшую оценку.
Рассмотрим пример, когда переменная n – не целочисленная.
Пример 2: $IMAGE10$, где х – вещественное число.
Здесь уже нельзя сказать, что S(x) = O(x3), так как отношение $IMAGE11$ неограниченно растет при х®0. Нельзя также сказать, что S(x) = O(x), т.к. отношение $IMAGE12$ неограниченно растет, когда х стремится к бесконечности. Значит, мы не можем использовать символ «О» для оценки S(x).
Эта дилемма разрешается благодаря тому, что на переменные, используемые с О, обычно накладываются какие-либо ограничения. Если, например, мы поставим условие, что $IMAGE13$, или что $IMAGE14$, где e - произвольная положительная константа, или что х – целое число, то мы сможем записать S(x) = O(x3). Если же наложено условие $IMAGE15$ или $IMAGE16$, где с – произвольная положительная константа, то в этом случае S(x) = O(x). «О большое» зависит от контекста, от ограничений на используемые переменные.
Эти ограничения часто задаются в виде предельных соотношений.
Определение 2: соотношение f(n) = O(g(n)) при n®¥ означает, что существуют две константы С и n0, такие, что
$IMAGE17$ при всех n ³ n0. (1.1.3)
Замечание 1: Значения С и n0 могут быть разными для разных О, но они не зависят от n.
Определение 3: запись f(х) = O(g(х)) при х®0 означает, что существуют две константы С и e, такие, что
$IMAGE18$, если только $IMAGE19$. (1.1.4)
Теперь О представляет неопределенную функцию и одну или две неопределенные константы, зависящие от контекста.
Замечание 2: запись $IMAGE20$ корректна, но в этом равенстве нельзя менять местами правую и левую части. В противном случае мы можем прийти к нелепым выводам, наподобие n = n2, исходя из верных тождеств n = О(n2) и n2 = О(n2).
Работая с символом «О» мы имеем дело с односторонними равенствами. Правая часть уравнения содержит не больше информации, чем левая, и фактически может содержать меньше информации; правая часть является «огрублением» левой.
Если говорить строго формально, то запись O(g(n)) обозначает не какую-то одну функцию f(n), а сразу множество функций f(n), таких, что $IMAGE21$ для некоторой константы С. Обычная формула 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, $IMAGE22$, еS, ln S определяются аналогично. Тогда «равенство» между двумя такими множествами функций есть теоретико-множественное включение; знак «=» в действительности означает «Í».
Пример 3: «Уравнение» $IMAGE23$ означает, что S1 Í S2, где S1 есть множество всех функций вида $IMAGE24$, для которых найдется константа С1, такая, что $IMAGE25$, а S2 есть множество всех функций $IMAGE26$, для которых найдется константа С2, такая, что $IMAGE27$.
Можно строго доказать это «равенство», если взять произвольный элемент из левой части и показать, что он принадлежит правой части: пусть $IMAGE24$ таково, что $IMAGE25$, следует доказать, что существует такая константа С2, что $IMAGE30$. Константа $IMAGE31$ решает проблему, так как $IMAGE32$ для всех целых n.
Замечание 3: Если в формуле используется несколько переменных, то символ О представляет множество функций от двух или более переменных, а не только от одной. В область определения каждой функции входят все переменные, которые в данном контексте «свободны» для изменения.
Тут есть некоторая тонкость ввиду того, что переменные могут иметь смысл лишь в части выражения, если они связаны знаком S или подобным.
Пример 4: $IMAGE33$, целое n ³ 0. (1.1.5)
Выражение k2 + O(k) в левой части отвечает множеству всех функций от двух переменных вида k2 + f(k, n), для которых найдется константа С, такая, что $IMAGE34$ для 0 £ k £ n. Сумма таких множеств функций для 0 £ k £ n есть множество всех функций g(n) вида
$IMAGE35$,
где f удовлетворяет сформулированному условию. Поскольку
$IMAGE36$то все такие функции g(n) принадлежат правой части (1.1.5); следовательно, (1.1.5) справедливо.
§2. Основные соотношения
Соотношение 1: $IMAGE37$ если $IMAGE38$. (1.2.1)
Доказательство:
Пусть $IMAGE39$, тогда $IMAGE40$ по свойству степени и модуля. $IMAGE41$, где С = 1. А по определению (1.1.2) символа О это и означает, что $IMAGE37$ при $IMAGE38$. Соотношение 1 доказано.
Соотношение 2: $IMAGE44$. (1.2.2)
Доказательство:
Покажем строго в соответствии с теоретико-множественным определением символа О, что левая часть является подмножеством правой части.
Любая функция из левой части имеет вид a(n) + b(n), и существуют константы m0, B, n0, C, такие, что
$IMAGE45$ и $IMAGE46$.
Следовательно, функция в левой части
$IMAGE47$
А, значит, по определению символа О левая часть принадлежит правой части. Соотношение 2 доказано.
Соотношение 3: f(n) = O(f(n)); (1.2.3)
Доказательство:
Для любой функции f(n) верно неравенство $IMAGE48$. $IMAGE49$, где С = 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, что
$IMAGE50$ и
$IMAGE51$.
Тогда $IMAGE52$ для любого n ³ max(n0, m0,). Значит левая часть принадлежит правой части, а, следовательно, является подмножеством правой части по определению символа О. Соотношение 6 доказано.
Соотношение 5: O(O(f(n))) = O(f(n)); (1.2.5)
Доказательство:
Покажем, что левая часть является подмножеством правой части.
Функция из левой части имеет вид a(n) такой, что существуют положительные константы С, В, n0, m0 такие, что
$IMAGE53$
Следовательно, по определению левая часть является подмножеством правой части. Соотношение 5 доказано.