stringtranslate.com

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

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

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

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

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

Определение

Формально, если заданы функции f  ( x ) и g ( x ) , мы определяем бинарное отношение тогда и только тогда, когда (de Bruijn 1981, §1.4)

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

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

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

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

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

Если и , то при некоторых мягких условиях [ необходимо дополнительное объяснение ] справедливо следующее:

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

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

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

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

В символах это означает, что у нас есть но также и для каждого фиксированного k . Ввиду определения символа последнее уравнение означает в маленькой нотации o , т.е. намного меньше, чем

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

В настоящей ситуации это соотношение фактически следует из объединения шагов k и k −1; вычитая из получаем ie

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

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

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

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

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

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

Здесь правая часть явно не сходится ни для какого ненулевого значения t . Однако, сохраняя t малым и усекая ряд справа до конечного числа членов, можно получить довольно хорошее приближение к значению . Подстановка и замечание, что приводит к асимптотическому разложению, приведенному ранее в этой статье.

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

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

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

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

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

Приложения

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

Ниже приведены примеры применения.

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

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

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

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

NA: Я хочу оценить свою функцию для больших значений с относительной погрешностью не более 1%.

АА: .

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

АА:

НА: Но мое значение составляет всего 100.

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

НА: Для меня это не новость. Я уже знаю, что .

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

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

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

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

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

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

НА: !!! . . . !

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

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

Примечания

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

Ссылки

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