Асимптотические методы. Часть III. Определение и свойства асимптотических разложений

Асимптотическое интегрирование дифференциальных уравнений

Асимптотические методы. Часть III. Определение и свойства асимптотических разложений

Пусть имеем ряд (возможно и расходящийся)

(53)

Обозначим через сумму первых членов ряда.

Будем говорить, что ряд (53) представляет собой асимптотическое разложение функции для достаточно больших , если выражение

удовлетворяет условию

(54)

( — любое фиксированное число), даже если ( — фиксировано). То обстоятельство, что данный ряд есть асимптотическое разложение функции (асимптотический степенной ряд), обозначается так:

Смысл асимптотического разложения состоит в том, что ряд (53) может служить источником приближенных формул

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

Пример 11. Найти асимптотическое разложение функции

(55)

Решение. Применяя раз интегрирование по частям, получаем

Обозначим и положим

Имеем

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

отсюда, поскольку , будем иметь

(56)

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

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

для всякого фиксированного , так что ряд дает асимптотическое разложение данной функции .

Если выполняется условие (54), то для коэффициентов ряда (53) из (54) получаем

(57)

Отсюда следует, что если функция имеет асимптотическое разложение, то оно единственно.

Напротив, один и тот же ряд вида (53) может служить асимптотическим разложением для разных функций. Например, для функции

в силу (57) асимптотическим разложением является ряд (53), все коэффициенты , которого равны нулю. Очевидно, что этот же ряд является асимптотическим разложением и для функции . Говорят, что асимптотический ряд представляет не одну функцию, а класс асимптотически равных функций.

Операции над асимптотическими рядами

1) Если

(58)

то

(59)

2) Если имеют место асимптотические разложения (58), то асимптотическое разложение функции может быть получено путем формального перемножения разложений (58).

3) Если функция имеет асимптотическое разложение

(60)

начинающееся с члена , то имеет место асимптотическое разложение

(61)

т.е. асимптотическое разложение (60) можно формально интегрировать почленно.

4) Формальное почленное дифференцирование асимптотического разложения, вообще говоря, недопустимо.

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

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

Приложения к интегрированию дифференциальных уравнений

1. Рассмотрим дифференциальное уравнение

(62)

Ряд

(63)

расходящийся при всех значениях , формально удовлетворяет данному уравнению, в чем нетрудно убедиться непосредственной проверкой. Уравнению (62) удовлетворяет функция

причем интеграл в правой части находится при . Повторным интегрированием по частям находим

где

При имеем

Следовательно, взяв первые членов ряда, мы совершим ошибку, меньшую (n+1)-го члена. Нетрудно видеть, что в данном случае

Поэтому построенный ряд является асимптотическим и может быть использован для вычисления интеграла и тем самым решения уравнения (62).

2. Если есть решение уравнения Бесселя , то, подставив вместо функцию , обнаружим, что будет удовлетворять уравнению

(64)

Для больших это уравнение естественно попытаться заменить уравнением

(65)

которое имеет решение .

Можно улучшить точность (для больших ) заменой постоянных и разложениями по отрицательным степеням :

Это означает, что решение уравнения (64) можно искать в виде

(66)

Подставив выражение (66) в уравнение (64), получим

(67)

Этот процесс можно продолжить и дальше. Существенно заметить, что эти выражения приводят к точному результату для (см. Бесселевы функции полуцелого индекса).

Уравнение (65) является, как говорят, предельным уравнением для уравнения (64) (уравнение (65) получается из (64), если в коэффициенте при совершить предельный переход при ).

Решение уравнения (65) для больших (особенно для ) достаточно хорошо определяет поведение решения исходного уравнения (64).

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

Возьмем функцию

(68)

и сконструируем дифференциальное уравнение, для которого будет решением. Имеем

Попробуем, чтобы и были связаны соотношением

(69)

Тогда заданная функция будет удовлетворять дифференциальному уравнению

(70)

Предположим, что , например, . Тогда из условия (69) найдем и решение

(71)

уравнения (70) при будет колеблющимся. С другой стороны,

поэтому предельным уравнением, соответствующим уравнению (70), будет

(72)

Его общее решение

(73)

не содержит колеблющейся части.

Итак, асимптотическое поведение решения (71) дифференциального уравнения (70) нельзя «угадать» по поведению решения (73) предельного уравнения (72).

Приведем некоторые относящиеся сюда результаты. Пусть дано дифференциальное уравнение

(74)

где

(75)

так что

(76)

Предельное уравнение в данном случае имеет вид

(77)

и является уравнением с постоянными коэффициентами. Пусть — корни (которые мы для простоты предполагаем различными) характеристического уравнения

(78)

Решения предельного уравнения — экспоненты .

Оказывается [16], что асимптотическое поведение решений уравнения (74) аналогично не поведению линейных комбинаций экспонент , а поведению линейных функций

(79)

где показатели определяются формулами

(80)

Функции (79) зависят не только от и , т.е. не только от предельных значений и при , но также и от коэффициентов , участвующих в правых частях равенств (75).

Теорема. Если характеристическое уравнение имеет различные корни и и если

то уравнение

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

(81)

Если корни характеристического уравнения совпадают, то может появиться логарифмический член. Решение можно представить асимптотическим рядом типа первого ряда (81), тогда как другое решение теперь представимо рядом вида

(82)

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

Источник: http://MathHelpPlanet.com/static.php?p=asimptoticheskoe-integrirovanie-differentsialnyh-uravneniy

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

Асимптотические методы. Часть III. Определение и свойства асимптотических разложений

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

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

Итак приступим.

Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа: O(g(n)), Ω(g(n)), Θ(g(n)). Давайте разбермся, что же это такое, но сначала я перечислю основные классы сложности применяемые при анализе: f(n) = O(1) константа f(n) = O(log(n)) логарифмический рост f(n) = O(n) линейный рост f(n) = O(n*log(n)) квазилинейный рост f(n) = O(nm) полиномиальный рост f(n) = O(2n) экспоненциальный рост Если раньше вы не встречались с подобными обозначениями, не переживайте, после прочтения этой статьи, все станет намного понятнее.

А начнем мы с символа O.

O(g(n))

Сначала приведу формальное определение:

(1.1) Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).

Таким образом O – означает верхнее ограничение сложности алгоритма. Давайте теперь попробуем применить это знание на практике. Возьмем известную любому программисту задачу сортировки. Допустим нам необходимо отсортировать массив чисел, размерностью 10 000 000 элементов. Договоримся рассматривать худший случай, при котором для выполнения алгоритма понадобится наибольшее количество итераций. Не долго думая, мы решаем применять сортировку пузырьком как самую простую с точки зрения реализации. Сортировка пузырьком позволяет отсортировать массив любой размерности без дополнительных выделений памяти. Вроде бы все прекрасно и мы с чистой совестью начинаем писать код (для примеров здесь и далее будет использоваться язык Python).

def bubble_sort(arr): . . for j in xrange(0, N — 1): . . . . for i in xrange(0, N — 1): . . . . . . if(arr[i] > arr[i+1]): . . . . . . . . tmp = arr[i] . . . . . . . . arr[i] = arr[i+1] . . . . . . . . arr[i+1] = tmp

Я намерено не ввожу проверку на наличие хотябы одного обмена (которая кстати не сказывается на O — сложности алгоритма), ради упрощения понимания сути. Взглянув на код, сразу же обращаем внимание на вложеный цикл. О чем нам это говорит? Я надеюсь, что читатель знаком с основами программирования на любом языке (кроме функциональных, в которых циклы отсутствуют как таковые, а повторения реализуются рекурсией) и наглядно представляет себе, что такое вложеные циклы и как они работают. В данном примере, внешний цикл выполняется ровно n = 10 000 000 (т.к. наш массив состоит из 10 000 000 элементов) и столько же раз выполняется внутренний цикл, из этого очевидно следует, что общее кол-во итераций будет порядка n2. Т.е. кол-во итераций зависит от размерности входных данных как ф-ия от n2. Теперь, зная сложность алгоритма, мы можем проверить, насколько хорошо он будет работать в нашем случае. Подставив цифры в формулу n2 получаем ответ 10 000 000 * 10 000 000 = 10 000 000 000 0000 итераций. Хммм, впечатляет… В цикле у нас 3 комманды, предположим, что на выполнение каждой из них требуется 5 единиц времени (с1 = 5), тогда общее кол-во времени затраченного на сортировку нашего массива будет равно 5*f(n2) (синяя кривая на рис.1). рис.1. зеленая кривая соответствует графику ф-ии x2 при c = 1, синия c = 5, красная c = 7 Здесь и далее на всех графиках ось абсцисс будет соответствовать размерности входных данных, а ось ординат кол-ву итераций необходимых для выполнения алгоритма. Нас интересует только та часть координатной плоскости, которая соответствует значениям x большим 0, т.к. любой массив, по-определению, не может иметь отрицательный размер, поэтому, для удобства, уберем левые части графиков ф-ий, ограничившись лишь первой четвертью координатной плоскости. рис.2. зеленая кривая соответствует графику ф-ии x2 при c = 1, синия c = 5, красная c = 7 Возьмем c2 = 7. Мы видим, что новая ф-ия растет быстрее предыдущей (красная кривая на рис.2). Из определения (1.1), делаем вывод, что при с2 = 7 и n >= 0, g(n) = 7*n2 всегда больше или равна ф-ии f(n) = 5*n2, следовательно наша программа имет сложность O(n2). Кто не до конца понял это объяснение, посмотрите на графики ф-ий и заметьте, что ф-ия отмеченная на нем красным, при n >= 0 всегда имеет большее значение по y, чем ф-ия отмеченная синим. Теперь подумаем, хорошо ли это или плохо в нашем случае и можем ли мы заставить алгоритм работать эффективнее? Как можно понять из графиков, приведенных на рис. 2, квадратичная ф-ия возрастает довольно быстро и при большом объеме входных данных, сортировка массива таким способом, может занять довольно длительное время, причем увеличение мощности процессора, будет сказываться лишь на коэффициенте c1, но сам алгоритм, по-прежнему будет принадлежать к классу алгоритмов с полиномиальной функцией роста O(n2) (тут мы опять же используем определение (1.1) и подбираем такие c2 и N при которых с2*n2 будет возрастать быстрее чем наша ф-ия c1*n2 начиная с некоторого n >= N) и если в ближайшем будущем изобретут процессор, который будет сортировать наш массив всего за пару секунд, то при немного большем объеме входных данных, этот прирост в производительности будет полностью нивелирован кол-вом необходимых вычислений. Таким же временным средством является решение реализовать алгоритм на низкоуровневом языке (например ассемблере), так как все, что мы сможем сделать – это, опять же, лишь немного уменьшить коэффициент c1 при этом все-равно оставаясь в классе сложности O(n2). А что будет, если вместо одноядерного процессора, мы будем использовать 4-х ядерный? На самом деле, результат изменится не сильно. Разобьем наш массив на 4 части и каждую часть поручим выполнять отдельному ядру. Что мы получим? На сортировку каждой части понадобится ровно O((n / 4)2). Так как все части сортируются одновременно, то этот результат и будет конечным временем сортировки четырех подмассивов, размерностью n/4. Возведем получившееся выражение в квадрат, получив таким образом сложность равную O(1/16*n2 + n), где n — итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов. Поскольку анализ у нас асимптотический, то при достаточно больших n, ф-ия n2 будет вносить гораздо больший вклад в итоговый результат, чем n и поэтому мы спокойно можем им пренебречь, как наиболее медленно возрастающем членом, также за малозначимостью принебрегаем коэффициентом 1/16 (см. (1.1)), что в итоге дает нам все тоже O(n2). Мы приходим к неутишительному выводу о том, что увеличением числа процессоров, равно как и повышение их частоты, не дают существенного прироста при данном алгоритме сортировки. Что же можно сделать в этой ситуации, чтобы радикально ускорить сортировку? Необходимо, чтобы в худшем случае сложность алгоритма была меньше чем O(n2). Поразмыслив немного, мы решаем, что не плохо бы было, придумать такой алгоритм, сложность которого не превышает O(n), т.е. является линейной. Очевидно, что в случае O(n) скорость работы программы возрастет в N раз, так как вместо N2 итераций, нам необходимо будет сделать всего лишь N. Прогнозируемый прирост скорости отлично виден на рис.3. Серой прямой обозначена линейная сложность, а три кривых показывают сложность n2 при различных коэффициентах c.

Но оказывается, что сделать сортировку со сложностью O(n) в общем случае просто не возможно (док-во)! Так на какую же сложность мы в лучшем случае можем расчитывать? Она равна O(n*log(n)), что является теоретически доказаным минимальным верхнем пределом для любого алгоритма сортировки основанного на сравнении элементов. Это конечно немного не то, чего мы ожидали получить, но все же это уже и не O(n2). Осталось найти алгоритм сортировки удовлетворяющий нашим требованиям.

Покопавшись в интернете, видим, что им удовлетворяет «пирамидальная сортировка». Я не буду вдаваться в подробности алгоритма, желающие могут прочитать о нем самостоятельно на wiki, скажу только, что его сложность принадлежит классу O(n*log(n)) (т.е. максимально возможная производительность для сортировки), но при этом, он довольно труден в реализации. Посмотрим на графики ниже и сравним скорости возрастания кол-ва вычислений для двух рассмотренных алгоритмов сортировки. рис.4. Фиолетовая кривая показывает алгоритм со сложностью n*log(n). Видно, что на больших n, пирамидальная сортировка существенно выигрывает у сортировки пузырьком при любом из трех опробованных нами коэффициентах, однако все-равно уступает гипотетической сортировке линейной сложности (серая прямая на графике). В любом случае, даже на медленном компьютере она будет работать гораздо быстрее, чем «пузырек» на быстром. Остается открытым вопрос, целесообразно ли всегда предпочитать пирамидальную сортировку сортировке пузырьком? рис.5. Как видно на рис.5, при малых n, различия между двумя алгоритмами достаточно малы и выгода от использования пирамидальной сортировки — совсем незначительна, а учитывая, что «пузырек» реализуется буквально 5-6 строчками кода, то при малых n, он действительно является более предпочтительным с точки зрения умственных и временных затрат на реализацию 🙂 В заключении, чтобы более наглядно продемонстрировать разницу между классами сложности, приведу такой пример: Допустим у нас етсь ЭВМ 45-ти летней давности. В голове сразу всплывают мысли о больших шкафах, занимающих довольно-таки обширную площадь. Допустим, что каждая команда на такой машине выполняется примерно за 10 миллисек. С такой скоростью вычислений, имея алгоритм сложности O(n2), на решение поставленой задачи уйдет оооочень много времени и от затеи придется отказаться как от невыполнимой за допустимое время, если же взять алгоритм со сложностью O(n*log(n)), то ситуация в корне изменится и на расчет уйдет не больше месяца. Посчитаем, сколько именно займет сортировка массива в обоих случаях

сверх-неоптимальный алгоритм (бывает и такое, но редко):

O(2n) = оооооочень медленно, вселенная умрет, прежде чем мы закончим наш расчет…

пузырек:

O(n2) = 277777778 часов (классический “пузырек”)

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

O(n*log(n)) = 647 часов (то чего мы реально можем добиться, применяя пирамидальную сортировку)

фантастически-эффективный алгоритм:

O(n) = 2.7 часов (наш гипотетический алгоритм, сортирующий за линейное время)

и наконец:

O(log(n)) = оооооочень быстро, жаль, что чудес не бывает… Два последних случая (хоть они и не возможны в реальности при сортировке данных) я привел лишь для того, чтобы читатель ощутил огромную разницу между алгоритмами различных классов сложности.

На последок хочу заметить, что буквой O обычно обозначают минимальный из классов сложности, которому соответствует данный алгоритм. К примеру, я мог бы сказать, что сложность сортировки пузырьком равна O(2n) и теоретически это было бы абсолютно верным утверждением, однако на практике такая оценка была бы лишена смысла.

  • algorithms
  • asymptotic analysis

Источник: https://habr.com/post/78728/

Biz-books
Добавить комментарий