18
правок
Изменения
Исправил пояснение ко второму примеру
}}
{{Определение
|id=def_asymp_equal.
|definition=Функции <tex>f: \;\mathbb{N} \rightarrow \mathbb{R}</tex> и <tex>g: \;\mathbb{N} \rightarrow \mathbb{R}</tex> ''имеют одинаковую асимптотику'', или ''одинаковый рост'', при <tex>n \rightarrow \infty</tex>, если существует предел <tex>\displaystyle\lim_{n \rightarrow \infty}{\dfrac{f(n)}{g(n)}}</tex>, и он равен <tex>1</tex>.
}}
Здесь будет рассмотрен метод поиска функции <tex>g(n)</tex>, такой что <tex>\displaystyle\lim_{n \rightarrow \infty}{\dfrac{a_{n}}{g(n)}} = 1</tex> имеет одинаковую асимптотику с <tex>a_n</tex>.
Из [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%81%D0%B2%D1%8F%D0%B7%D0%B8_%D0%BC%D0%B5%D0%B6%D0%B4%D1%83_%D1%80%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D1%8F%D1%89%D0%B5%D0%B9_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8_%D0%B8_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B9_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E_%D0%B7%D0%B0%D0%B4%D0%B0%D0%B2%D0%B0%D0%B5%D0%BC%D0%BE%D0%B9_%D0%B5%D0%B9_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8&oldid=74516 теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности] известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: <tex>A(t)=\dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>, <tex>deg(P) < k</tex>.
<tex>r_1, r_2, \dots, r_s</tex> с кратностью соответственно <tex>f_1, f_2, \dots, f_s</tex>.
''' Существует единственный максимальный обратный корень: <tex>\exists i: \: \forall j \neq i \; |r_i| > |r_j|</tex>'''
Тогда <tex>r_i \in \mathbb{R}</tex>, в этом случае <tex>a_n \sim n^{f_i - 1} \cdot r_{i}^{n}</tex>
''' Существует несколько максимальных по модулю корней ''' Возьмем те из них, кратность которых максимальна, тогда имеем <tex>r_1, r_2, \dots, r_l</tex>, у каждого из которых кратность <tex>f</tex>.Тогда <tex>\forall j \in 1\dots l :\; r_j = z e^{i \phi_j}</tex>, где <tex>z</tex> — модуль каждого из корней. Значит <tex>\displaystyle a_n \sim n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot (z\cdot e^{i \phi_j})^{n}} = n^{f - 1} z^n \sum_{j = 1}^{l} {c_j \cdot e^{i \phi_j n}}</tex>, где <tex>c_j</tex> — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби. == Примеры задач =={{Задача|definition = Оцените асимптотическое поведение коэффициента <tex>a_n</tex> производящей функции <tex>A(t)=\dfrac{t^2}{1 - 2t - t^2 + 2t^3}</tex> при <tex>n \rightarrow \infty</tex>}}Найдем корни знаменателя производящей функции: <tex>Q(t) = 1 - 2t - t^2 + 2t^3 = (1 - 2t)(1 - t)(1 + t)</tex>, тогда обратные корни: <tex>r_1 = 2,\,f_1 = 1;\; r_2 = 1,\, f_2 = 1;\; r_3 = -1,\, f_3 = 1</tex>. Выберем максимальный по модулю <tex>r_1 = 2</tex>, тогда <tex>a_n \sim n^{f_1 - 1} \cdot r_{1}^{n} = 2^n</tex>.{{Задача|definition = Оцените асимптотическое поведение коэффициента <tex>a_n</tex> производящей функции <tex>A(t)=\dfrac{1}{(1 - 2t)(1 + 4t^2)}</tex> при <tex>n \rightarrow \infty</tex>}}Найдем корни знаменателя производящей функции: <tex>Q(t) = (1 - 2t)(1 + 4t^2)</tex>: <tex>t_1 = \dfrac{1}{2},\, t_2 = \dfrac{1}{2i},\, t_3 = -\dfrac{1}{2i}</tex>, тогда обратные корни: <tex>r_1 = 2,\,f_1 = 1;\; r_2 = 2i,\, f_2 = 1;\; r_3 = -2i,\, f_3 = 1</tex>.Все три обратных корня имеют одинаковый модуль <tex>z = 2</tex> и кратность <tex>f = 1</tex>. Для определения доминирующего коэффициента разложим производящую функцию на простые дроби, например, с помощью метода неопределенных коэффициентов, так мы найдем <tex>c_i:</tex> <tex>A(t) = \dfrac{\frac{1}{4}}{\frac{1}{2} - t} + \dfrac{\frac{1 - i}{4}}{t + \frac{1}{2i}} + \dfrac{\frac{1 + i}{4}}{t - \frac{1}{2i}},\; c_1 = \dfrac{1}{4},\, c_2 = \dfrac{1 - i}{4},\, c_3 = \dfrac{1 + i}{4}</tex> <tex>\displaystyle a_n \sim n^{f - 1} \sum_{i = 1}^{3} {c_i \cdot r_i^{n}} = n^{1 - 1} \cdot \left(\dfrac{1}{4} \cdot 2^n + \dfrac{1 - i}{4} \cdot (2i)^n + \dfrac{1 + i}{4} \cdot (-2i)^n \right) =2^{n - 2}\cdot (1 + (1 - i)\cdot i^n + (1 + i) \cdot (-i)^n)</tex>. Данная оценка учитывает все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%90%D0%B4%D0%B0%D0%BC%D0%B0%D1%80%D0%B0_%D1%80%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D1%8F%D1%89%D0%B8%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 квазимногочлена], поэтому вместо знака <tex>\sim</tex> можно поставить знак равенства.
