18
правок
Изменения
Init: Асимптотическое поведение последовательности, заданной рекуррентным соотношением
=== Асимптотическое поведение последовательности, заданной рекуррентным соотношением ===
== Необходимые определения ==
{{Определение
|id=def_linear.
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется '''линейной рекуррентной последовательностью''' (англ. ''constant-recursive sequence''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}
<определение через большую омега>
Здесь будет рассмотрен метод поиска функции <tex>g(n)</tex>, такой что <tex>a_{n} \in \Omega(g(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>A(t) = \dfrac{P(t)}{Q(t)}</tex>, тогда <tex>Q(t)</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>
''' '''
== Необходимые определения ==
{{Определение
|id=def_linear.
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется '''линейной рекуррентной последовательностью''' (англ. ''constant-recursive sequence''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}
<определение через большую омега>
Здесь будет рассмотрен метод поиска функции <tex>g(n)</tex>, такой что <tex>a_{n} \in \Omega(g(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>A(t) = \dfrac{P(t)}{Q(t)}</tex>, тогда <tex>Q(t)</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>
''' '''
