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

Описание предельного поведения функции

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

В качестве иллюстрации предположим, что нас интересуют свойства функции f  ( n ), когда n становится очень большим. Если f ( n ) = n ² + 3 n , то когда n становится очень большим, член 3 n становится незначительным по сравнению с ⁿ 2 ^. Говорят, что функция f ( n ) « асимптотически эквивалентна n 2 , когда n → ∞ ». Это часто записывается символически как f  ( n ) ~ n ² , что читается как « f ( n ) асимптотически к n ² ».

Примером важного асимптотического результата является теорема о простых числах . Пусть π( x ) обозначает функцию подсчета простых чисел (которая не связана напрямую с константой pi ), то есть π( x ) — это количество простых чисел , которые меньше или равны x . Тогда теорема утверждает, что $${\displaystyle \pi (x)\sim {\frac {x}{\ln x}}.}$$

Асимптотический анализ обычно используется в информатике как часть анализа алгоритмов и часто выражается там в терминах нотации «О» большое .

Определение

Формально, если заданы функции f  ( x ) и g ( x ) , мы определяем бинарное отношение тогда и только тогда, когда (de Bruijn 1981, §1.4) $${\displaystyle f(x)\sim g(x)\quad ({\text{as }}x\to \infty )}$$ $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.}$$

Символ ~ — это тильда . Отношение является отношением эквивалентности на множестве функций x ; функции f и g называются асимптотически эквивалентными . Областью определения f и g может быть любое множество, для которого определен предел: например, действительные числа, комплексные числа, положительные целые числа.

Такое же обозначение используется и для других способов перехода к пределу: например, x → 0 , x ↓ 0 , | x | → 0. Способ перехода к пределу часто не указывается явно, если это ясно из контекста.

Хотя приведенное выше определение распространено в литературе, оно проблематично, если g ( x ) равно нулю бесконечно часто, когда x стремится к предельному значению. По этой причине некоторые авторы используют альтернативное определение. Альтернативное определение в нотации little-o заключается в том, что f ~ g тогда и только тогда, когда $${\displaystyle f(x)=g(x)(1+o(1)).}$$

Это определение эквивалентно предыдущему определению, если g ( x ) не равно нулю в некоторой окрестности предельного значения. ^{[1] [2]}

Характеристики

Если и , то при некоторых мягких условиях ^{[ необходимо дополнительное объяснение ]} справедливо следующее: ${\displaystyle f\sim g}$ ${\displaystyle a\sim b}$

• ${\displaystyle f^{r}\sim g^{r}}$, для каждого действительного r
• ${\displaystyle \log(f)\sim \log(g)}$если ${\displaystyle \lim g\neq 1}$
• ${\displaystyle f\times a\sim g\times b}$
• ${\displaystyle f/a\sim g/b}$

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

Примеры асимптотических формул

• Факториал — это приближение Стерлинга. $${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}}$$
• Функция разделения
  Для положительного целого числа n функция распределения p ( n ) определяет количество способов записи целого числа n в виде суммы положительных целых чисел, где порядок слагаемых не учитывается. $${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}e^{\pi {\sqrt {\frac {2n}{3}}}}}$$
• Функция Эйри
  Функция Эйри, Ai( x ), является решением дифференциального уравнения y″ − xy = 0 ; она имеет множество приложений в физике. $${\displaystyle \operatorname {Ai} (x)\sim {\frac {e^{-{\frac {2}{3}}x^{\frac {3}{2}}}}{2{\sqrt {\pi }}x^{1/4}}}}$$
• Функции Ганкеля $${\displaystyle {\begin{aligned}H_{\alpha }^{(1)}(z)&\sim {\sqrt {\frac {2}{\pi z}}}e^{i\left(z-{\frac {2\pi \alpha -\pi }{4}}\right)}\\H_{\alpha }^{(2)}(z)&\sim {\sqrt {\frac {2}{\pi z}}}e^{-i\left(z-{\frac {2\pi \alpha -\pi }{4}}\right)}\end{aligned}}}$$

Асимптотическое расширение

Асимптотическое разложение функции f ( x ) на практике является выражением этой функции в терминах ряда , частичные суммы которого не обязательно сходятся, но так, что взятие любой начальной частичной суммы дает асимптотическую формулу для f . Идея состоит в том, что последовательные члены обеспечивают все более точное описание порядка роста f .

В символах это означает, что у нас есть но также и для каждого фиксированного k . Ввиду определения символа последнее уравнение означает в маленькой нотации o , т.е. намного меньше, чем ${\displaystyle f\sim g_{1},}$ ${\displaystyle f-g_{1}\sim g_{2}}$ ${\displaystyle f-g_{1}-\cdots -g_{k-1}\sim g_{k}}$ ${\displaystyle \sim }$ ${\displaystyle f-(g_{1}+\cdots +g_{k})=o(g_{k})}$ ${\displaystyle f-(g_{1}+\cdots +g_{k})}$ ${\displaystyle g_{k}.}$

Отношение приобретает свой полный смысл, если для всех k , что означает форму асимптотической шкалы . В этом случае некоторые авторы могут злоупотреблять написанием для обозначения утверждения Однако следует быть осторожным, чтобы это не было стандартным использованием символа и чтобы оно не соответствовало определению, данному в § Определение. ${\displaystyle f-g_{1}-\cdots -g_{k-1}\sim g_{k}}$ ${\displaystyle g_{k+1}=o(g_{k})}$ ${\displaystyle g_{k}}$ ${\displaystyle f\sim g_{1}+\cdots +g_{k}}$ ${\displaystyle f-(g_{1}+\cdots +g_{k})=o(g_{k}).}$ ${\displaystyle \sim }$

В настоящей ситуации это соотношение фактически следует из объединения шагов k и k −1; вычитая из получаем ie ${\displaystyle g_{k}=o(g_{k-1})}$ ${\displaystyle f-g_{1}-\cdots -g_{k-2}=g_{k-1}+o(g_{k-1})}$ ${\displaystyle f-g_{1}-\cdots -g_{k-2}-g_{k-1}=g_{k}+o(g_{k}),}$ ${\displaystyle g_{k}+o(g_{k})=o(g_{k-1}),}$ ${\displaystyle g_{k}=o(g_{k-1}).}$

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

Примеры асимптотических разложений

• Гамма-функция $${\displaystyle {\frac {e^{x}}{x^{x}{\sqrt {2\pi x}}}}\Gamma (x+1)\sim 1+{\frac {1}{12x}}+{\frac {1}{288x^{2}}}-{\frac {139}{51840x^{3}}}-\cdots \ (x\to \infty )}$$
• Экспоненциальный интеграл $${\displaystyle xe^{x}E_{1}(x)\sim \sum _{n=0}^{\infty }{\frac {(-1)^{n}n!}{x^{n}}}\ (x\to \infty )}$$
• Функция ошибки , где m !! — двойной факториал . $${\displaystyle {\sqrt {\pi }}xe^{x^{2}}\operatorname {erfc} (x)\sim 1+\sum _{n=1}^{\infty }(-1)^{n}{\frac {(2n-1)!!}{n!(2x^{2})^{n}}}\ (x\to \infty )}$$

Рабочий пример

Асимптотические разложения часто возникают, когда обычный ряд используется в формальном выражении, которое заставляет брать значения вне его области сходимости. Например, мы можем начать с обычного ряда $${\displaystyle {\frac {1}{1-w}}=\sum _{n=0}^{\infty }w^{n}}$$

Выражение слева справедливо на всей комплексной плоскости , тогда как правая часть сходится только при . Умножение на и интегрирование обеих частей дает ${\displaystyle w\neq 1}$ ${\displaystyle |w|<1}$ ${\displaystyle e^{-w/t}}$ $${\displaystyle \int _{0}^{\infty }{\frac {e^{-{\frac {w}{t}}}}{1-w}}\,dw=\sum _{n=0}^{\infty }t^{n+1}\int _{0}^{\infty }e^{-u}u^{n}\,du}$$

Интеграл в левой части можно выразить через показательный интеграл . Интеграл в правой части, после подстановки , можно распознать как гамма-функцию . Оценивая оба, получаем асимптотическое разложение ${\displaystyle u=w/t}$ $${\displaystyle e^{-{\frac {1}{t}}}\operatorname {Ei} \left({\frac {1}{t}}\right)=\sum _{n=0}^{\infty }n!\;t^{n+1}}$$

Здесь правая часть явно не сходится ни для какого ненулевого значения t . Однако, сохраняя t малым и усекая ряд справа до конечного числа членов, можно получить довольно хорошее приближение к значению . Подстановка и замечание, что приводит к асимптотическому разложению, приведенному ранее в этой статье. ${\displaystyle \operatorname {Ei} (1/t)}$ ${\displaystyle x=-1/t}$ ${\displaystyle \operatorname {Ei} (x)=-E_{1}(-x)}$

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

В математической статистике асимптотическое распределение — это гипотетическое распределение, которое в некотором смысле является «предельным» распределением последовательности распределений. Распределение — это упорядоченный набор случайных величин Z _i для i = 1, …, n , для некоторого положительного целого числа n . Асимптотическое распределение позволяет i изменяться без ограничений, то есть n бесконечно.

Частным случаем асимптотического распределения является случай, когда поздние записи стремятся к нулю, то есть Z _i стремится к 0, когда i стремится к бесконечности. Некоторые примеры «асимптотического распределения» относятся только к этому особому случаю.

Это основано на понятии асимптотической функции, которая чисто стремится к постоянному значению ( асимптоте ), когда независимая переменная стремится к бесконечности; «чистая» в этом смысле означает, что для любой желаемой близости эпсилон существует некоторое значение независимой переменной, после которого функция никогда не отличается от константы более чем на эпсилон.

Асимптота — это прямая линия, к которой приближается кривая, но никогда не встречается и не пересекается. Неформально можно говорить о том, что кривая встречается с асимптотой «на бесконечности», хотя это не точное определение. В уравнении y становится произвольно малым по величине с ростом x . ${\displaystyle y={\frac {1}{x}},}$

Приложения

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

Примеры применения следующие.

• В прикладной математике асимптотический анализ используется для построения численных методов приближенного решения уравнений .
• В математической статистике и теории вероятностей асимптотики используются при анализе долгосрочного или крупномасштабного поведения случайных величин и оценок.
• В информатике при анализе алгоритмов рассматривается производительность алгоритмов.
• Поведение физических систем , примером чего является статистическая механика .
• При анализе аварий, при определении причин аварии посредством моделирования подсчета большого количества аварий в заданное время и в заданном пространстве.

Асимптотический анализ является ключевым инструментом для исследования обыкновенных и частных дифференциальных уравнений, которые возникают при математическом моделировании явлений реального мира. ^[3] Наглядным примером является вывод уравнений пограничного слоя из полных уравнений Навье-Стокса, управляющих потоком жидкости. Во многих случаях асимптотическое разложение находится в степени малого параметра ε : в случае пограничного слоя это безразмерное отношение толщины пограничного слоя к типичному масштабу длины задачи. Действительно, приложения асимптотического анализа в математическом моделировании часто ^[3] сосредоточены вокруг безразмерного параметра, который, как было показано или предполагается, мал посредством рассмотрения масштабов рассматриваемой задачи.

Асимптотические разложения обычно возникают при приближении определенных интегралов ( метод Лапласа , метод перевала , метод наискорейшего спуска ) или при приближении распределений вероятностей ( ряды Эджворта ). Графики Фейнмана в квантовой теории поля являются еще одним примером асимптотических разложений, которые часто не сходятся.

Асимптотический и численный анализ

Дебройн иллюстрирует использование асимптотики в следующем диалоге между доктором NA, численным аналитиком, и доктором AA, асимптотическим аналитиком:

NA: Я хочу оценить свою функцию для больших значений с относительной погрешностью не более 1%. ${\displaystyle f(x)}$ ${\displaystyle x}$

АА: . ${\displaystyle f(x)=x^{-1}+\mathrm {O} (x^{-2})\qquad (x\to \infty )}$

НА: Извините, я не понимаю.

АА: ${\displaystyle |f(x)-x^{-1}|<8x^{-2}\qquad (x>10^{4}).}$

НА: Но мое значение составляет всего 100. ${\displaystyle x}$

АА: Почему ты так не сказал? Мои оценки дают

${\displaystyle |f(x)-x^{-1}|<57000x^{-2}\qquad (x>100).}$

НА: Для меня это не новость. Я уже знаю, что . ${\displaystyle 0<f(100)<1}$

AA: Я могу немного выиграть в некоторых своих оценках. Теперь я нахожу, что

${\displaystyle |f(x)-x^{-1}|<20x^{-2}\qquad (x>100).}$

НА: Я просил 1%, а не 20%.

AA: Это почти лучшее, что я могу получить. Почему бы вам не взять большие значения ? ${\displaystyle x}$

НА: !!! Я думаю, лучше спросить мою электронно-вычислительную машину.

Машина: f(100) = 0,01137 42259 34008 67153

АА: Разве я вам не говорил? Моя оценка в 20% не сильно отличалась от 14% реальной погрешности.

НА: !!! . . . !

Несколько дней спустя мисс NA хочет узнать значение f(1000), но ее машине потребуется месяц вычислений, чтобы дать ответ. Она возвращается к своему Асимптотическому Коллеге и получает полностью удовлетворительный ответ. ^[4]

Смотрите также

• Асимптота  – предел касательной в точке, стремящейся к бесконечности
• Асимптотическая вычислительная сложность  – вычислительная сложность, измеряемая предельным поведением использования ресурсов для больших входных данных.Pages displaying wikidata descriptions as a fallback
• Асимптотическая плотность  – Концепция в теории чиселPages displaying short descriptions of redirect targets
• Асимптотическая теория (статистика)  – Изучение свойств сходимости статистических оценок.
• Асимптотология  – работа с прикладными математическими системами в предельных случаях
• Обозначение «большое О»  — описывает предельное поведение функции.
• Член ведущего порядка  – Члены математического выражения с наибольшим порядком величины.
• Метод доминирующего баланса  – Решение упрощенной формы уравнения
• Метод согласованных асимптотических разложений
• Лемма Ватсона  – лемма об асимптотическом поведении интеграловPages displaying wikidata descriptions as a fallback

Примечания

1. "Асимптотическое равенство", Энциклопедия математики , EMS Press , 2001 [1994]
2. Эстрада и Канвал (2002, §1.2)
3. Howison, S. (2005), Практическая прикладная математика , Cambridge University Press
4. Брюйн, Николаас Говерт де (1981). Асимптотические методы анализа . Дуврские книги по высшей математике. Нью-Йорк: Дуврское изд. п. 19. ISBN 978-0-486-64221-5.

Ссылки

• Балсер, В. (1994), От расходящихся степенных рядов к аналитическим функциям, Springer-Verlag , ISBN 9783540485940
• де Брейн, Н.Г. (1981), Асимптотические методы анализа, Dover Publications , ISBN 9780486642215
• Эстрада, Р.; Канвал, Р.П. (2002), Распределительный подход к асимптотике, Birkhäuser , ISBN 9780817681302
• Миллер, П.Д. (2006), Прикладной асимптотический анализ, Американское математическое общество , ISBN 9780821840788
• Мюррей, Дж. Д. (1984), Асимптотический анализ, Springer, ISBN 9781461211228
• Париж, Р. Б.; Камински, Д. (2001), Асимптотика и интегралы Меллина-Барнса, Cambridge University Press

Внешние ссылки

• Асимптотический анализ — домашняя страница журнала, издаваемого IOS Press
• Статья об анализе временных рядов с использованием асимптотического распределения