Асимптотичний аналіз

В математичному аналізі асимптотичний аналіз — це метод опису граничної поведінки. Дана методологія має багато застосувань в природничих науках. Наприклад

• в інформатиці для аналізу алгоритмів, при розгляді виконання алгоритмів, що застосовуються для дуже великих наборів вхідних даних.
• поведінка дуже великих фізичних систем.
• в аналізі аварій, коли встанувлюється причина аварії за допомогою кількісного моделювання, з великим числом аварійних ситуацій в даний час і даному місці.

Найпростіший приклад, розгляд функції f(n), при описі її властивостей, коли n стає занадто великим. Таким чином, якщо f(n)=n²+3n, елемент 3n стає незначним в порівнянні з n², при занадто великих n. Тоді кажуть, що функція f(n) є асимптотично еквівалентна n² при n → ∞ й символічно записують як f(n) ~ n².

Означення

Формально, для заданих двох комплекснозначних функцій f і g, що залежать від натурального аргументу n, пишемо

$f \sim g \quad (\text{as } n\to\infty)$

щоб позначити цей факт в термінах о-маленького, то

$f(n) = g(n) + o(g(n))\quad($ при $n\to\infty),\,$

що еквівалентно

$f(n) = (1+o(1))g(n)\quad($ при $n\to\infty).$

Це означає, що для довільної додатньої константи ε знайдеться така константа N, що

$|f(n)-g(n)|\leq\epsilon|g(n)|$ для всіх $n\geq N~$.

Якщо функція g(n) не рівна нулю (інакше границя записана нижче буде невизначеною), це твердження еквівалентне

$\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1.$

Це відношення є відношення еквівалентності на множині функцій від n. Клас еквівалентності f загалом складається з усіх функцій g, котрі рівні f, в граничному сенсі.

Асимптотичний розклад

Асимптотичний розклад функції f(x) фактично це представлення цієї функції у вигляді рядів, часткові суми яких не обов'язково збігаються, але такі що будь-які часткові суми представляють собою асимптотичні формули для f.