Выпускная квалификационная работа

«Символ О»

Содержание

Введение

С лово асимптотика имеет греческое происхождение и буквально означает «никогда не соединяющиеся». Изучая конические сечения, древнегреческие математики рассматривали, в частности, гиперболы, такие, как график функции ,

имеющий прямые 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 = О(n³),

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

_n = О(n²), так как

для всех целых n. Можно также небрежно отбросить часть информации и записать _n = О(n¹⁰).

Определение О не заставляет нас давать наилучшую оценку.

Рассмотрим пример, когда переменная n – не целочисленная.

Пример 2: , где х – вещественное число.

Здесь уже нельзя сказать, что S(x) = O(x³), так как отношение неограниченно растет при х0. Нельзя также сказать, что S(x) = O(x), т.к. отношение неограниченно растет, когда х стремится к бесконечности. Значит, мы не можем использовать символ «О » для оценки S(x).

Эта дилемма разрешается благодаря тому, что на переменные, используемые с О, обычно накладываются какие-либо ограничения. Если, например, мы поставим условие, что , или что , где - произвольная положительная константа, или что х – целое число, то мы сможем записать S(x) = O(x³). Если же наложено условие или , где с – произвольная положительная константа, то в этом случае S(x) = O(x). «О большое» зависит от контекста, от ограничений на используемые переменные.

Эти ограничения часто задаются в виде предельных соотношений.

Определение 2: соотношение f(n) = O(g(n)) при n означает, что существуют две константы С и n₀, такие, что

при всех n n₀. (1.1.3)

Замечание 1: Значения С и n₀ могут быть разными для разных О, но они не зависят от n.

Определение 3: запись f(х) = O(g(х)) при х0 означает, что существуют две константы С и , такие, что

, если только . (1.1.4)

Теперь О представляет неопределенную функцию и одну или две неопределенные константы, зависящие от контекста.

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

Работая с символом «О » мы имеем дело с односторонними равенствами. Правая часть уравнения содержит не больше информации, чем левая, и фактически может содержать меньше информации; правая часть является «огрублением» левой.

Если говорить строго формально, то запись 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: «Уравнение» означает, что S₁  S₂, где S₁ есть множество всех функций вида , для которых найдется константа С₁, такая, что , а S₂ есть множество всех функций , для которых найдется константа С₂, такая, что .

Можно строго доказать это «равенство», если взять произвольный элемент из левой части и показать, что он принадлежит правой части: пусть таково, что , следует доказать, что существует такая константа С₂, что . Константа решает проблему, так как для всех целых n.

Замечание 3: Если в формуле используется несколько переменных, то символ О представляет множество функций от двух или более переменных, а не только от одной. В область определения каждой функции входят все переменные, которые в данном контексте «свободны» для изменения.

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

Пример 4: , целое n  0. (1.1.5)

Выражение k² + O(k) в левой части отвечает множеству всех функций от двух переменных вида k² + 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), и существуют константы m₀, B, n₀, 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)

Доказательство:

Покажем в соответствии с теоретико-множественным определением символа О, что левая часть является подмножеством правой части.