Участник:Nkorzh — различия между версиями
Nkorzh (обсуждение | вклад) м (→Алгоритм "обратных" корней!) |
Nkorzh (обсуждение | вклад) (Точки в примерах, ссылка на лемму во второй задаче, страница в ссылке на книгу, убрал определения, случаи завернул в список) |
||
Строка 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> в константу раз. Из [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_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>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Из [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 - | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Найдем обратные корни к <tex>t_i</tex>, то есть <tex>r_i = \dfrac{1}{t_i}</tex>. | |
− | Тогда <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: | Строка 17: | ||
Выберем максимальный по модулю <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: | Строка 30: | ||
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>. | ||
− | + | В этом примере оценка включает в себя все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена<ref>[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#lemma1 Лемма о представлении коэффициента рациональной производящей функции в форме квазимногочлена]</ref>. Это значит, что вместо знака <tex>\sim</tex> можно поставить знак равенства. | |
== См. также == | == См. также == | ||
* [[Производящая функция]] | * [[Производящая функция]] | ||
* [[Произведение Адамара рациональных производящих функций]] | * [[Произведение Адамара рациональных производящих функций]] | ||
+ | |||
+ | ==Примечания== | ||
+ | |||
+ | <references /> | ||
== Источники информации == | == Источники информации == | ||
− | * Graham, Knuth, and Patashnik: Concrete Mathematics | + | * Graham, Knuth, and Patashnik: Concrete Mathematics, p. 340 |
* [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] | ||
+ | |||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Производящие функции]] |
Версия 13:14, 12 июня 2021
Содержание
Асимптотическое поведение последовательности, заданной рекуррентным соотношением
Нахождение асимптотики рекуррентной последовательности
Здесь будет рассмотрен метод поиска функции, которая имеет одинаковую асимптотику[1] с , то есть при будет отличаться от в константу раз. Из теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: , где , , тогда — многочлен конечной степени, следовательно, он имеет корней , каждый из которых имеет некоторую кратность .
Найдем обратные корни к
, то есть . Тогда имеем набор обратных корней с кратностью соответственно :- Существует единственный максимальный обратный корень:
Тогда , в этом случае .
. - Существует несколько максимальных по модулю обратных корней:
Найдем коэффициенты корней , которые можно получить разложением на сумму простых дробей в вида .
Возьмем те обратные корни, кратность которых максимальна, тогда имеем , у каждого из которых некоторая максимальность кратность . Тогда , где — модуль каждого из корней.
Значит , где — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби.
Примеры задач
Задача: |
Оцените асимптотическое поведение коэффициента | производящей функции при .
Найдем корни знаменателя производящей функции:
, тогда обратные корни: .Выберем максимальный по модулю
, тогда .Задача: |
Оцените асимптотическое поведение коэффициента | производящей функции при .
Найдем корни знаменателя производящей функции:
: , тогда обратные корни: . Все три обратных корня имеют одинаковый модуль и кратность .Для определения доминирующего коэффициента разложим производящую функцию на простые дроби, например, с помощью метода неопределенных коэффициентов, так мы найдем
.
В этом примере оценка включает в себя все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена[2]. Это значит, что вместо знака можно поставить знак равенства.
См. также
Примечания
Источники информации
- Graham, Knuth, and Patashnik: Concrete Mathematics, p. 340
- Wikipedia — Asymptotic growth of a sequence