Участник:Nkorzh — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Алгоритм "обратных" корней!)
(Объяснил асимптотику)
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
=== Асимптотическое поведение последовательности, заданной рекуррентным соотношением ===
 
=== Асимптотическое поведение последовательности, заданной рекуррентным соотношением ===
== Необходимые определения ==
+
== Нахождение асимптотики рекуррентной последовательности ==
{{Определение
+
Здесь будет рассмотрен метод поиска функции, которая имеет одинаковую асимптотику<ref>[https://ru.wikipedia.org/wiki/%D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE Асимптотическое равенство]</ref> с <tex>a_n</tex>, то есть при <tex>n \rightarrow \infty</tex> будет отличаться от <tex>a_n</tex> в константу раз. Из [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности | теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]] известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: <tex>A(t)=\dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot  t^2 - \ldots - c_s \cdot t^s</tex>, <tex>deg(P) < s</tex>, тогда <tex>Q(t)</tex> — многочлен конечной степени, следовательно, он имеет <tex>s</tex> корней <tex>t_i\in \mathbb{C}</tex>, каждый из которых имеет некоторую кратность <tex>f_i</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>
 
}}
 
 
 
{{Определение
 
|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>g(n)</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>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>A(t)=\dfrac{P(t)}{Q(t)}=\dfrac{c_1}{(1-r_1 t)^{f_1}} + \dfrac{c_2}{(1-r_2 t)^{f_2}} + \ldots + \dfrac{c_s}{(1-r_s t)^{f_s}}</tex>, а из  [[Произведение Адамара рациональных производящих функций#lemma1 | леммы о представлении коэффициента последовательности, заданной рациональной ПФ, в форме квазимногочлена]] мы знаем, чему равен <tex>n</tex>-й коэффициент последовательности, которую задает каждая дробь, тогда <tex>n</tex>-й коэффициент
 +
<tex>A(t)</tex> будет равен <tex>c_1 \begin{pmatrix} f_1 - 1 + n \\ f_1 - 1 \end{pmatrix} r_1^{n} + c_2 \begin{pmatrix} f_2 - 1 + n \\ f_2 - 1 \end{pmatrix} r_2^{n}+\ldots+
 +
c_s \begin{pmatrix} f_s - 1 + n \\ f_s - 1 \end{pmatrix} r_s^{n}</tex>. Очевидно, наибольший вклад в поведение <tex>a_n</tex> вносит наибольший по модулю <tex>r_i</tex> с наибольшей кратностью <tex>f_i</tex>.
  
Тогда <tex>r_i \in \mathbb{R}</tex>, в этом случае <tex>a_n \sim n^{f_i - 1} \cdot r_{i}^{n}</tex>
+
Зная, что <tex>\begin{pmatrix} f_i - 1 + n \\ f_i - 1 \end{pmatrix} = \dfrac{(n + 1)(n + 2)\ldots(n + f_i - 1)}{(f_i - 1)!}</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>t_i</tex>, то есть <tex>r_i = \dfrac{1}{t_i}</tex>.
Тогда <tex>\forall j \in 1\dots l :\; r_j = z e^{i \phi_j}</tex>, где <tex>z</tex> — модуль каждого из корней.
+
Тогда имеем набор <tex>r_1, r_2, \,\dots, r_s</tex> обратных корней <tex>Q(t)</tex> с кратностью соответственно <tex>f_1, f_2, \,\dots, f_s</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> — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби.
+
# Существует единственный максимальный по модулю обратный корень: <tex>\exists i: \: \forall j \neq i \; |r_i| > |r_j|</tex>.<br/> Тогда <tex>r_i \in \mathbb{R}</tex>, в этом случае <tex>a_n \sim n^{f_i - 1} \cdot r_{i}^{n}</tex>.
 +
#  Существует несколько максимальных по модулю обратных корней:<br/> Найдем коэффициенты корней <tex>c_i</tex>, которые получаются разложением <tex>A(t)</tex> на сумму простых дробей в вида <tex>\dfrac{c_i}{(1 - r_i t)^{f_i}}</tex>. <br/> Возьмем те обратные корни, кратность которых максимальна, тогда имеем набор <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> — модуль каждого из корней. <br/>Значит <tex>\displaystyle a_n \sim n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot r_j^n} = 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>
+
|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>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>.
Строка 38: Строка 27:
 
Выберем максимальный по модулю <tex>r_1 = 2</tex>, тогда <tex>a_n \sim n^{f_1 - 1} \cdot r_{1}^{n} = 2^n</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>
+
|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>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>.
Строка 51: Строка 40:
 
2^{n - 2}\cdot (1 + (1 - i)\cdot i^n + (1 + i) \cdot (-i)^n)</tex>.
 
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> можно поставить знак равенства.
+
В этом примере оценка включает в себя все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена<ref>[[Произведение Адамара рациональных производящих функций#lemma1 | Лемма о представлении коэффициента рациональной производящей функции в форме квазимногочлена]]</ref>. Это значит, что вместо знака <tex>\sim</tex> можно поставить знак равенства.
  
 
== См. также ==
 
== См. также ==
 
* [[Производящая функция]]
 
* [[Производящая функция]]
 
* [[Произведение Адамара рациональных производящих функций]]
 
* [[Произведение Адамара рациональных производящих функций]]
 +
 +
==Примечания==
 +
 +
<references />
  
 
== Источники информации ==
 
== Источники информации ==
* Graham, Knuth, and Patashnik: Concrete Mathematics
+
* ''Graham R.L., Knuth D.E., and Patashnik O.'' (1994) Concrete Mathematics. Second edition. Massachusetts: Addison-Weasley Publishing Company, Inc. P.340-347.
 
* [https://en.wikipedia.org/wiki/Generating_function#Asymptotic_growth_of_a_sequence Wikipedia {{---}} Asymptotic growth of a sequence]
 
* [https://en.wikipedia.org/wiki/Generating_function#Asymptotic_growth_of_a_sequence Wikipedia {{---}} Asymptotic growth of a sequence]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Производящие функции]]

Текущая версия на 20:05, 15 июня 2021

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

Нахождение асимптотики рекуррентной последовательности

Здесь будет рассмотрен метод поиска функции, которая имеет одинаковую асимптотику[1] с [math]a_n[/math], то есть при [math]n \rightarrow \infty[/math] будет отличаться от [math]a_n[/math] в константу раз. Из теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: [math]A(t)=\dfrac{P(t)}{Q(t)}[/math], где [math]Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_s \cdot t^s[/math], [math]deg(P) \lt s[/math], тогда [math]Q(t)[/math] — многочлен конечной степени, следовательно, он имеет [math]s[/math] корней [math]t_i\in \mathbb{C}[/math], каждый из которых имеет некоторую кратность [math]f_i[/math].

Идея

Дробно-рациональную производящую функцию можно представить в виде [math]A(t)=\dfrac{P(t)}{Q(t)}=\dfrac{c_1}{(1-r_1 t)^{f_1}} + \dfrac{c_2}{(1-r_2 t)^{f_2}} + \ldots + \dfrac{c_s}{(1-r_s t)^{f_s}}[/math], а из леммы о представлении коэффициента последовательности, заданной рациональной ПФ, в форме квазимногочлена мы знаем, чему равен [math]n[/math]-й коэффициент последовательности, которую задает каждая дробь, тогда [math]n[/math]-й коэффициент [math]A(t)[/math] будет равен [math]c_1 \begin{pmatrix} f_1 - 1 + n \\ f_1 - 1 \end{pmatrix} r_1^{n} + c_2 \begin{pmatrix} f_2 - 1 + n \\ f_2 - 1 \end{pmatrix} r_2^{n}+\ldots+ c_s \begin{pmatrix} f_s - 1 + n \\ f_s - 1 \end{pmatrix} r_s^{n}[/math]. Очевидно, наибольший вклад в поведение [math]a_n[/math] вносит наибольший по модулю [math]r_i[/math] с наибольшей кратностью [math]f_i[/math].

Зная, что [math]\begin{pmatrix} f_i - 1 + n \\ f_i - 1 \end{pmatrix} = \dfrac{(n + 1)(n + 2)\ldots(n + f_i - 1)}{(f_i - 1)!}[/math], и, пренебрегая константой, получаем, что [math]a_n \sim n^{f_i - 1} \cdot r_i^{n}[/math].

Алгоритм

Найдем обратные корни к [math]t_i[/math], то есть [math]r_i = \dfrac{1}{t_i}[/math]. Тогда имеем набор [math]r_1, r_2, \,\dots, r_s[/math] обратных корней [math]Q(t)[/math] с кратностью соответственно [math]f_1, f_2, \,\dots, f_s[/math]:

  1. Существует единственный максимальный по модулю обратный корень: [math]\exists i: \: \forall j \neq i \; |r_i| \gt |r_j|[/math].
    Тогда [math]r_i \in \mathbb{R}[/math], в этом случае [math]a_n \sim n^{f_i - 1} \cdot r_{i}^{n}[/math].
  2. Существует несколько максимальных по модулю обратных корней:
    Найдем коэффициенты корней [math]c_i[/math], которые получаются разложением [math]A(t)[/math] на сумму простых дробей в вида [math]\dfrac{c_i}{(1 - r_i t)^{f_i}}[/math].
    Возьмем те обратные корни, кратность которых максимальна, тогда имеем набор [math]r_1, r_2, \,\dots, r_l[/math], в котором каждый обратный корень имеет максимальную кратность [math]f[/math]. Тогда [math]\forall j \in 1 \,\dots\, l :\; r_j = z e^{i \phi_j}[/math], где [math]z[/math] — модуль каждого из корней.
    Значит [math]\displaystyle a_n \sim n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot r_j^n} = 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}}[/math], где [math]c_j[/math] — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби.

Примеры задач

Задача:
Оцените асимптотическое поведение коэффициента [math]a_n[/math] производящей функции [math]A(t)=\dfrac{t^2}{1 - 2t - t^2 + 2t^3}[/math] при [math]n \rightarrow \infty[/math].

Найдем корни знаменателя производящей функции: [math]Q(t) = 1 - 2t - t^2 + 2t^3 = (1 - 2t)(1 - t)(1 + t)[/math], тогда обратные корни: [math]r_1 = 2,\,f_1 = 1;\; r_2 = 1,\, f_2 = 1;\; r_3 = -1,\, f_3 = 1[/math].

Выберем максимальный по модулю [math]r_1 = 2[/math], тогда [math]a_n \sim n^{f_1 - 1} \cdot r_{1}^{n} = 2^n[/math].

Задача:
Оцените асимптотическое поведение коэффициента [math]a_n[/math] производящей функции [math]A(t)=\dfrac{1}{(1 - 2t)(1 + 4t^2)}[/math] при [math]n \rightarrow \infty[/math].

Найдем корни знаменателя производящей функции: [math]Q(t) = (1 - 2t)(1 + 4t^2)[/math]: [math]t_1 = \dfrac{1}{2},\, t_2 = \dfrac{1}{2i},\, t_3 = -\dfrac{1}{2i}[/math], тогда обратные корни: [math]r_1 = 2,\,f_1 = 1;\; r_2 = 2i,\, f_2 = 1;\; r_3 = -2i,\, f_3 = 1[/math]. Все три обратных корня имеют одинаковый модуль [math]z = 2[/math] и кратность [math]f = 1[/math].

Для определения доминирующего коэффициента разложим производящую функцию на простые дроби, например, с помощью метода неопределенных коэффициентов, так мы найдем [math]c_i:[/math]

[math]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}[/math]

[math]\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)[/math].

В этом примере оценка включает в себя все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена[2]. Это значит, что вместо знака [math]\sim[/math] можно поставить знак равенства.

См. также

Примечания

Источники информации