[ «Государственное образовательное учреждение высшего профессионального образования МОСКОВСКИЙ ГОСУДАРСТВННЫЙ ОБЛАСТНОЙ УНИВЕРСИТЕТ (МГОУ) Факультет ...»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ
Государственное образовательное учреждение высшего профессионального образования
МОСКОВСКИЙ ГОСУДАРСТВННЫЙ ОБЛАСТНОЙ УНИВЕРСИТЕТ
(МГОУ)
Факультет Физико-математический
«О-символика»
Луценко Евгения Сергеевна
МОСКВА 2014
Содержание
1. Введение
2. Обозначения «О-символики»
3. История вопроса
4. Доказательства свойств «о-малое» и «О-большое»
5. Асимптотика
6. Литература
Введение.
«O» большое и «o» малое (О и о) — математические обозначения для сравнения асимптотического поведения функций.
o(f) «о малое от » обозначает «бесконечно малое относительно », пренебрежимо малую величину при рассмотрении . Смысл термина
O(f) «О большое» зависит от его области применения, но всегда растёт не быстрее, чем , «O большое от »
В частности:
фраза «сложность алгоритма есть » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма не может быть ограничено величиной, которая растет медленнее, чем n!;
фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю).
Актуальность данной курсовой работы заключается в том, что тема «О-символика» используется в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов.
Цели работы: расскрыть более подробно смысл и значение символов
«О-символики», обозначить и доказать их свойства, уменьшить сложность понимания темы.
Обозначения.
Для функций f(n) и g(n) при используются следующие обозначения:
Обозначение Интуитивное объяснение Определение
f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически
f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически
f ограничена снизу и сверху функцией g асимптотически
g доминирует над f асимптотически
доминирует над g асимптотически
эквивалентна g асимптотически
где — проколотая окрестность точки .
История вопроса.
Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом (англ.) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году.
Эдмунд Георг Герман (Иезекииль) Ландау (14 февраля 1877, Берлин — 19 февраля 1938, Берлин) — немецкий математик родился в семье преуспевающего берлинского врача-еврея, профессора Леопольда Ландау, мать Йоханна Якоби происходила из известного банкирского дома Якоби. До 16 лет учился в берлинской Французской гимназии, который успешно закончил на 2 года раньше положенного.
В 1899 году под руководством Фробениуса подготовил и защитил диссертацию по теории чисел. В 1901 году защитил докторскую о рядах Дирихле в аналитической теории чисел. В 1909 году, после смерти Минковского, занимает его кафедру и становится профессором математики Гёттингенского университета. В конце 1920-х годов посетил Палестину. Был избран профессором Еврейского университета в Иерусалиме.
В 1934 году, под давлением нацистов, Ландау был вынужден уйти в отставку. Он не захотел покинуть Германию и продолжал жить в Берлине. С 1935 преподавал в Кембриджском, в 1937—1938 — в Брюссельском университетах.
Скончался в 1938 году от сердечного приступа.
Основные открытия Ландау относятся к аналитической теории чисел и комплексному анализу. Часть работ касается оснований математики.
Он исследовал распределение простых чисел и в 1909 году выпустил двухтомную монографию с первым систематическим изложением этой теории. Ландау сумел связать закон распределения простых чисел и распределение простых идеалов алгебраического числового тела. Ландау внёс существенный вклад в исследование функции Римана. В 1930 году опубликовал книгу «Основания анализа», которая считается классическим изложением предмета и в наши дни.
Имя Ландау носит доказанная им теорема об особых точках целых функций. Так же с работами его связана и популяризация обоих обозначений о-малое и О-большое, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок).
В честь Эдмунда Ландау названа также функция Ландау. В 1924 году Ландау был избран почётным членом Лондонского математического общества. Избран иностранным членом многих европейских Академий, в том числе иностранным членом - корреспондентом Российской академии наук (1924) и иностранным почётным членом АН СССР (1932).
Основные свойства:
Транзитивность
Рефлексивность
Симметричность
Перестановочная симметрия
Дополнительные свойства символов о-малое и О-большое
1.
2.
как следствия:
3.
4.
5.
Свойство 1 и 2
Пусть 1х и 2х – бесконечно малые функции при ха.
1х = о() и 2х = о()
1х + 2х = о()
1х = о() т.е. limхa1(x)=0 2х = о() т.е. limхa2(x)=0limхa1x2x=limхa1(x)±limхa2(x)=0
__________________________________________________________________
Свойство 3
= о(С) limхaС=0, С0, С=о()-?
limхaСС=СlimхaС=0 ;( limхa=0)- ?Умножение и деление на С0limхaСС=1С limхaСlimхaС=0 С=о__________________________________________________________________
Свойство 4
Cо=о, С-const 0=Co ; =o-?
С=o ; (limхa=0)-?
limхaС=0; limхa=limхaСС=(limхaС (limхaСС=0)Свойство 5
о(n)=o(k), n2 nN, k=1,2,…, n-1.=o(n); (=o(k)) - ?
limхan=0;( limхak=0)- ?limхan=limхakkn=limхa(k)·limхank =olimхank=o
__________________________________________________________________
Свойство 6
(o())n=o(n) nN
=olimхa=0
n=o(n)limхank=0-?
limхank=lim(хann)=(limхa)n=0
Пример:
(sinx)xn-3 (предположим sin x= o(x1-e), 0 (sinx)xn-3= o(x1-e)n)xn-3= o(xn-1)xn-3=o(xn-1)xn-3=св-во 8=o(xn-1-(n-3))=0(x2)__________________________________________________________________ 8 свойство o(n)=o(n-1);n2, nN=nlimхan=0 =on-1-? limхankт-1=limхan-1=limхan=0 __________________________________________________________________ 9 свойство limхak=1nCk kk=1nCk n=limхak=1nCkkk=1nCk k=0limxak=1nCk k=0limxaC11+ C22…Ck n=0limxaC1+ C2+C32…Ck n = 0 __________________________________________________________________ 10 свойство o(o())=o(); =o()=o(o()limхao()=0 ; limхa=0-?limхa=limхao()o1= limхao()limхao()=0 __________________________________________________________________ 11 свойство o(+o())=o()=o+o; =o-?; limхa=0- ? limхa=limхa(+o())(+o()=limхa+o()limхao()=0limхao()=0(limхa1+limхao()=0(+limхao()=0__________________________________________________________________ 12 свойство =o; =o() =; =o-?; limхa=0-? limхa=limхa=limхa=0 __________________________________________________________________ 13 свойство ~ -=o -=o limхa=1 limхa-=limхa-limхa1=1-1=0 __________________________________________________________________ Cвойства «O – большое» 1 свойство O(o(f(x))=o(f(x)) µ(x) = O(o(f(x)), g(x) = o(f) (x)Agx, limхag(x)f(x)=0 gconst=A limхag(x)f(x)=0, limхa(x)f(x)=0-? limхa(x)f(x)=limхag(x)(x)f(x)g(x)=0 __________________________________________________________________ 2 свойство o(O(f)x))) = o(f(x)) g(x)=O(f(x)) limхa(x)g(x)=0, x=o(g(x)xAgx limхa(x)g(x)=0-? limхa(x)g(x)=limхa(x)g(x)g(x)f(x)=0 __________________________________________________________________ 3 свойство O(o(f(x)) = O(f(x) g(x)=O(f(x))g(x)Af(x)x=O(gx)(x)A2 g(x) (x)A2 gxA2A1fx=Af(x) __________________________________________________________________ 5 свойство O(f(x)) + o(f(x) – O(f(x)) g(x) = o(f(x) = 0 g(x)f(x)A1 -const0,g(x)A1f(x) x=Of(x)(x)A2f(x) x+g(x)x+gxA1fx+A2fx=Af(x) __________________________________________________________________ Пример: 1)Sin x-x=o(x) -? limx0sinx-xx=0-? limx0sinx-xx=limx0(sinxx-1)=0 2) cos x – 1 + x22=ox2-?limx0cosx-1+x22x2=limx0-2sinx2x2+limx0x22x2=limx0-2sin2x2(x2)24+12=0 Асимптотические обозначения в уравнениях Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n)), то знак равенства обозначает принадлежность множеству (n O(n)). Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x 0 формула обозначает, что , где — функция, о которой известно только то, что она принадлежит множеству . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, — содержит только одну функцию из класса . Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:какие бы мы функции ни выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным. Например, запись обозначает, что для любой функции , существует некоторая функция g(x)O(x) такая, что выражение x+ f(x) = g(x) — верно для всех . Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с правилом.Например: . Отметим, что такая интерпретация подразумевает выполнение соотношения . Приведенная интерпретация подразумевает выполнение соотношения: , где A, B, C — выражения, которые могут содержать асимптотические обозначения. Примеры использования: при при (следует из формулы Стирлинга: Формула Стирлинга является первым приближением при разложении факториала в ряд Стирлинга: при . При выполнено неравенство . Поэтому положим . Отметим, что нельзя положить , так как и, следовательно, это значение при любой константе больше . Функция при имеет степень роста . Чтобы это показать, надо положить и . Можно, конечно, сказать, что имеет порядок , но это более слабое утверждение, чем то, что . Докажем, что функция при не может иметь порядок . Предположим, что существуют константы и такие, что для всех выполняется неравенство . Тогда для всех . Но принимает любое, как угодно большое, значение при достаточно большом , поэтому не существует такой константы , которая могла бы мажорировать для всех больших некоторого . . Для проверки достаточно положить . Тогда для Литература В. Н. Крупский Введение в сложность вычислений. Бугров, Никольский Высшая математика, том 2. http://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5http://ru.math.wikia.com/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5
«