WikiSort.ru - Не сортированное

Асимптотическое равенство в математическом анализе — отношение эквивалентности между функциями, отношение которых стремится к единице в бесконечности: функции ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ называются асимптотически равными (или асимптотически эквивалентными), если:

${\displaystyle \lim \limits _{x\to \infty }{\frac {f(x)}{g(x)}}=1}$ .

Для обозначения асимптотического равенства используется тильда: ${\displaystyle f(x)\sim g(x)}$ .

Равносильное определение асимптотического равенства с использованием ${\displaystyle o}$ -нотации — выполнение соотношения ${\displaystyle f(x)=g(x)(1+o(1))}$ ^[1].

Говоря неформально, асимптотические функции почти равны при достаточно больших значениях ${\displaystyle x}$ (то есть можно добиться сколь угодно малой относительной погрешности ${\displaystyle f(x)}$ по отношению к ${\displaystyle g(x)}$ , и наоборот).

Примеры

Для всякого полинома ${\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\dots +a_{1}x+a_{0}}$ выполнено ${\displaystyle P(x)\sim a_{n}x^{n}}$ .

Довольно известной является формула Стирлинга, приближающая факториал непрерывной функцией:

${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}}$ .

Асимптотики полезны при оценке комбинаторных величин с достаточно большими параметрами. Например, подставив формулу Стирлинга в явную формулу вычисления биномиального коэффициента, можно получить, что:

${\displaystyle {\binom {2n}{n}}\sim {\sqrt {\frac {1}{\pi n}}}2^{2n}}$ .

Количество простых чисел, меньших некоторого заданного числа, также имеет простое асимптотическое приближение:

${\displaystyle \pi (n)\sim {\frac {n}{\ln {n}}}}$ ,

где ${\displaystyle \pi (n)}$  — количество простых чисел, меньших ${\displaystyle n}$ .

Свойства

Асимптотическое равенство в полном смысле является отношением эквивалентности, то есть оно рефлексивно, симметрично и транзитивно.

Если ${\displaystyle f(x)\sim g(x)}$ , то ${\displaystyle f(x)\sim g(x)+c}$ , и наоборот, где ${\displaystyle c=const}$

Если ${\displaystyle f(x)\sim g(x)}$ , то ${\displaystyle \ln {f(x)}\sim \ln {g(x)}}$ . Однако обратное, вообще говоря, неверно. Как пример можно привести ${\displaystyle f(n)=e^{n^{2}+n}}$ и ${\displaystyle g(n)=e^{n^{2}}}$ . Логарифмы этих функций асимптотически эквивалентны, но предельной точкой их отношения является бесконечная точка.

${\displaystyle f(x)\sim g(x)}$ тогда и только тогда, когда ${\displaystyle \ln {f(x)}=\ln {g(x)}+o(1)}$ .

Если ${\displaystyle f(x)\sim g(x)}$ , ${\displaystyle c=const}$ и ${\displaystyle A(x)=(c+o(1))^{f(x)}}$ , то ${\displaystyle A(x)=(c+o(1))^{g(x)}}$ .

Согласно теореме Штольца, для двух бесконечных рядов:

${\displaystyle \sum \limits _{n=0}^{\infty }{a_{n}}}$ и ${\displaystyle \sum \limits _{n=0}^{\infty }{b_{n}}}$ ,

если ${\displaystyle \forall n:\ b_{n}>0}$ и ряд:

${\displaystyle \sum \limits _{n=0}^{\infty }{b_{n}}}$

расходится, то из ${\displaystyle a_{n}\sim b_{n}}$ следует, что:

${\displaystyle \sum \limits _{k=0}^{n}{a_{k}}\sim \sum \limits _{k=0}^{n}{b_{k}}}$ .

Порядок роста

Сходным по смыслу с асимптотическим равенством, но менее строгим отношением является наличие одинакового порядка роста величин. Говорят, что функция ${\displaystyle f(x)}$ имеет порядок роста ${\displaystyle g(x)}$ если ${\displaystyle \exists a,A:\ \exists X:\ \forall x>X:ag(x)\leqslant f(x)\leqslant Ag(x)}$ . В этом случае используют обозначение ${\displaystyle f(x)=\Theta (g(x))}$ или ${\displaystyle f(x)\in \Theta (g(x))}$ .

При этом из одинаковости порядка роста отнюдь не следует существование константы ${\displaystyle c}$ такой, что ${\displaystyle cf(x)\sim g(x)}$ . Для примера достаточно заметить, что ${\displaystyle n\leqslant n(1+\sin {n})\leqslant 2n}$ , однако ${\displaystyle \nexists c:\ n(1+\sin {n})\sim cn}$ .

Примечания

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 6 сентября 2018 года.