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

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

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

Примером важного асимптотического результата является теорема о простых числах . Пусть $π(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 \to 0$ , $x ↓ 0$ , $| х | \to 0$ . Способ перехода к пределу часто не указывается явно, если он ясен из контекста.

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

f(x)=g(x)(1+o(1)).

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

Свойства [ править ]

Если $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, \dots, n$ , для некоторого положительного целого числа $n$ . Асимптотическое распределение позволяет $i$ изменяться без ограничений, то есть $n$ бесконечно.

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

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

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

Приложения [ править ]

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

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

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

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

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

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

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

Н.А.: Я хочу оценить свою функцию $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), но ее машине потребуется месяц вычислений, чтобы дать ответ. Она возвращается к своему асимптотическому коллеге и получает полностью удовлетворительный ответ. ^[4]

См. также [ править ]

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

Примечания [ править ]

^ «Асимптотическое равенство» , Энциклопедия математики , EMS Press , 2001 [1994]
^ Эстрада и Канвал (2002 , §1.2)
^ Перейти обратно: ^а ^б Хауисон, С. (2005), Практическая прикладная математика , Издательство Кембриджского университета
^ Брюйн, Николаас Говерт де (1981). Асимптотические методы анализа . Дуврские книги по высшей математике. Нью-Йорк: Дуврское изд. п. 19. ISBN 978-0-486-64221-5 .

Ссылки [ править ]

Балсер, В. (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.
Статья об анализе временных рядов с использованием асимптотического распределения

[1] «Асимптотическое равенство» , Энциклопедия математики , EMS Press , 2001 [1994]

[2] Эстрада и Канвал (2002 , §1.2)

[Howison-3] Перейти обратно: ^а ^б Хауисон, С. (2005), Практическая прикладная математика , Издательство Кембриджского университета

[4] Брюйн, Николаас Говерт де (1981). Асимптотические методы анализа . Дуврские книги по высшей математике. Нью-Йорк: Дуврское изд. п. 19. ISBN 978-0-486-64221-5 .

[1]

[2]

[3]

[4]