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

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

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

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

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

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

Определение

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

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

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

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

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

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

Если $f\sim g$ и $a\sim b$, то в некоторых мягких условиях имеют место следующие:

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

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

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

• Факториал $$n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}$$ — это приближение Стирлинга
• Функция разделения
  Для положительного целого числа n функция статистической суммы p ( n ) дает количество способов записи целого числа n в виде суммы положительных целых чисел, где порядок слагаемых не учитывается. $$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}e^{\pi {\sqrt {\frac {2n}{3}}}}$$
• Функция Эйри
  Функция Эйри, Ai( x ), является решением дифференциального уравнения y″ − xy = 0 ; оно имеет множество приложений в физике. $$\operatorname {Ai} (x)\sim {\frac {e^{-{\frac {2}{3}}x^{\frac {3}{2}}}}{2{\sqrt {\pi }}x^{1/4}}}$$
• Функции Ханкеля $${\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 .

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

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

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

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

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

• Гамма-функция $${\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 )$$
• Экспоненциальный интеграл $$xe^{x}E_{1}(x)\sim \sum _{n=0}^{\infty }{\frac {(-1)^{n}n!}{x^{n}}}\ (x\to \infty )$$
• Функция ошибки $${\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 )$$ где м !! это двойной факториал .

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

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

Выражение слева справедливо на всей комплексной плоскости. $w\neq 1$, а правая часть сходится только при $|w|<1$. Умножение на $e^{-w/t}$ и интеграция обеих сторон дает $$\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$$

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

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

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

Основная статья: Асимптотическое распределение

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

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

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

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

Приложения

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

Примеры приложений следующие.

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

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

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

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

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

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

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

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

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

Н.А.: Но моя ценность $x$ это всего лишь 100.

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

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

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

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

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

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

А.А.: Это почти лучшее, что я могу получить. Почему бы вам не взять более высокие значения $x$?

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

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

А.А.: Разве я тебе не говорил? Моя оценка в 20% была недалеко от 14% реальной ошибки.

НА: !!! . . . !

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

См. также

• Асимптота - предел касательной в точке, стремящейся к бесконечности.
• Асимптотическая вычислительная сложность - в теории вычислений. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Асимптотическая плотность - концепция теории чисел . Страницы с краткими описаниями целей перенаправления.
• Асимптотическая теория (статистика) - Исследование свойств сходимости статистических оценок.
• Асимптотология - Работа с прикладными математическими системами в предельных случаях.
• Обозначение Big O — описывает предельное поведение функции.
• Член ведущего порядка - термины в математическом выражении с наибольшим порядком величины.
• Метод доминирующего баланса - Решение упрощенной формы уравнения.
• Метод согласованных асимптотических разложений
• Лемма Ватсона - лемма об асимптотическом поведении интегралов. Страницы, отображающие описания из Викиданных в качестве запасного варианта.

Ссылки

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

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

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