Асимптотические обозначения в уравнениях



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Асимптотические обозначения в уравнениях



· Если в правой части уравнения находится только асимптотическое обозначение (например n = O(n²)), то знак равенства обозначает принадлежность множеству (nO(n²)).

· Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула ex − 1 = x + o(x) обозначает, что ex − 1 = x + f(x), где f(x) — функция, о которой известно только то, что она принадлежит множеству o(x). Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, — содержит только одну функцию из класса O(n2).

· Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило:
какие бы мы функции не выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным.
Например, запись x + o(x) = O(x) обозначает, что для любой функции f(x) ∈ o(x), существует некоторая функция g(x), такая что выражение x + f(x) = g(x) — верно для всех x.

· Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом.
Например: 4n4 + 4n2 + 1 = 4n4 + Θ(n2) = Θ(n4). Отметим, что такая интерпретация подразумевает выполнение соотношения 4n4 + 4n2 + 1 = Θ(n4).

Приведенная интерпретация подразумевает выполнение соотношения:

, где A, B, C — выражения, которые могут содержать асимптотические обозначения.

Примеры использования

· ex = 1 + x + x²/2 + O(x³) при x → 0.

· n! = O((n/e)n+1/2) при n → ∞.

· T(n) = (n + 1)2 = O(n2) при n → ∞.

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

Если положить n0 = 1 и c = 4, то для n≥1 будет выполняться неравенство (n + 1)2 < 4n2. Отметим, что нельзя положить n0 = 0, так как T(0) = 1 и, следовательно, это значение при любой константе c больше c02 = 0.

· Функция T(n) = 3n3 + 2n2 при n → ∞ имеет степень роста O(n3). Чтобы это показать, надо положить n0 = 0 и c = 5. Можно, конечно, сказать, что T(n) имеет порядок O(n4), но это более слабое утверждение, чем то, что T(n) имеет порядок роста O(n3).

· Докажем, что функция 3n при n → ∞ не может иметь порядок O(2n). Предположим, что существуют константы c и n0 такие, что для всех nn0 выполняется неравенство 3nc2n. Тогда c ≥ (3/2)n для всех nn0. Но (3/2)n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать (3/2)n для всех n больших некоторого n0.

· T(n) = n3 + 2n2 есть Ω(n3) при n → ∞. Для проверки достаточно положить c = 1. Тогда T(n) > cn3 для n = 0,1,....

История

Обозначение «„O“ большое» введено немецким математиком Паулем Бахманом (англ.) во втором томе его книги «Analytische Zahlentheorie» (Аналитическая теория чисел), вышедшем в 1894 году. Обозначение «„о“ малое» впервые использовано другим немецким математиком, Эдмундом Ландау в 1909 году; с работами последнего связана и популяризация обоих обозначений, в связи с чем их также называют символами Ландау. Обозначение пошло от немецкого слова «Ordnung» (порядок).


Непрерывная функция

Непрерывная функция — функция без «скачков», то есть такая у которой малые изменения аргумента приводят к малым изменениям значения отображения. График непрерывной функции может быть начерчен «не отрывая карандаш от бумаги».

Непрерывная функция вообще говоря, — синоним понятия непрерывное отображение, тем не менее, чаще всего этот термин используется в более узком смысле — для отображений между числовыми пространствами, например, на вещественной прямой. Эта статья посвящена именно непрерывным функциям, определённым на подмножестве вещественных чисел и принимающих вещественные значения.

Содержание · 1 Определения o 1.1 ε-δ определение § 1.1.1 Комментарии · 2 Связанные определения o 2.1 Точки разрыва · 3 Свойства o 3.1 Локальные o 3.2 Глобальные · 4 Примеры o 4.1 Элементарные функции o 4.2 Функция с устранимым разрывом o 4.3 Функция знака o 4.4 Ступенчатая функция o 4.5 Функция Дирихле o 4.6 Функция Римана · 5 Вариации и обобщения o 5.1 Равномерная непрерывность o 5.2 Полунепрерывность o 5.3 Односторонняя непрерывность o 5.4 Непрерывность почти всюду

Определения

ε-δ определение

Пусть и .

Функция f непрерывна в точке , если для любого существует δ > 0 такое, что

Функция f непрерывна на множестве E, если она непрерывна в каждой точке данного множества.

В этом случае говорят, что функция f класса C0 и пишут: или, подробнее, .

Комментарии

· Из определения следует, что функция непрерывна в каждой изолированной точке своей области определения.

· Определение непрерывности фактически повторяет определение предела функции в данной точке. Другими словами, функция f непрерывна в точке x0, предельной для множества E, если f имеет предел в точке x0, и этот предел совпадает со значением функции f(x0).

· Функция непрерывна в точке, если её колебание в данной точке равно нулю.

Связанные определения

Точки разрыва

Если попытаться построить отрицание свойства непрерывности функции в точке (предельной для области определения), то получится следующее: Существует такая окрестность значения функции в рассматриваемой точке, что сколь близко мы не подходили бы к данной точке, всегда можно будет найти точку, значение в которой окажется за пределами заданной окрестности.

В этом случае говорят, что функция f терпит разрыв в точке a.

Возможны два варианта:

· либо предел функции существует, но он не совпадает со значением функции в данной точке:

тогда точка a называется точкой устранимого разрыва функции f (в комплексном анализе — устранимая особая точка). Положив можно добиться непрерывности функции в этой точке. Такое изменение значения функции в точке, превращающее функцию в непрерывную в этой точке, называется доопределением по непрерывности.

· либо предела функции в данной точке не существует и тогда. В этом случае для числовой функции, заданной на вещественной прямой (или её подмножестве), возможно существование односторонних пределов. Отсюда возникает классификация точек (неустранимого) разрыва:

o если оба односторонних предела существуют и конечны, но хотя бы один из них отличен от значения функции в данной точке, то такую точку называют точкой разрыва первого рода;

o если хотя бы один из односторонних пределов не существует или не является конечной величиной, то такую точку называют точкой разрыва второго рода.

Свойства

Локальные

· Функция, непрерывная в точке , является ограниченной в некоторой 043Eкрестности этой точки.

· Если функция непрерывна в точке и (или ), то (или ) для всех , достаточно близких к .

· Если функции и непрерывны в точке , то функции и тоже непрерывны в точке .

· Если функции и непрерывны в точке и при этом , то функция тоже непрерывна в точке .

· Если функция непрерывна в точке и функция непрерывна в точке , то их композиция непрерывна в точке .

Глобальные

· Функция, непрерывная на отрезке (или любом другом компактном множестве), равномерно непрерывна на нём.

· Функция, непрерывная на отрезке (или любом другом компактном множестве), ограничена и достигает на нём свои максимальное и минимальное значения.

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

· Если функция непрерывна на отрезке и то существует точка в которой .

· Если функция непрерывна на отрезке и число удовлетворяет неравенству или неравенству то существует точка в которой .

· Непрерывное отображение отрезка в вещественную прямую инъективно в том и только в том случае, когда данная функция на отрезке строго монотонна.

· Монотонная функция на отрезке непрерывна в том и только в том случае, когда область ее значений является отрезком с концами и .

· Если функции и непрерывны на отрезке , причем и то существует точка в которой Отсюда, в частности, следует, что любое непрерывное отображение отрезка в себя имеет хотя бы одну неподвижную точку.

Примеры

Элементарные функции

Произвольные многочлены, рациональные функции, показательные функции, логарифмы, тригонометрические функции (прямые и обратные) непрерывны везде в своей области определения.



Последнее изменение этой страницы: 2016-09-05; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.51.151 (0.01 с.)