Рекурентне співвідношення

Рекурентне співвідношення або рекурентне рівняння — рівняння, що встановлює залежність між членами невідомої послідовності та індексом.

Рекурентні співвідношення мають застосування в аналізі алгоритмів, цифровій обробці сигналів, економіці та біології. У комбінаториці часто виникають задачі, які можна звести до аналогічних задач для меншої кількості об'єктів. У цьому випадку задачу можна розв'язати за допомогою рекурентного співвідношення.

Задача розв'язування рекурентного співвідношення є знаходження невідомої послідовності. Загалом ця задача має нескінченно багато розв'язків. Кількість розв'язків обмежується заданням для невідомої послідовності початкових членів.

Основні поняття і означення

Послідовність $\{a_{n}\}$ називається рекурентною, якщо задані перші k членів $a_{0},\dots ,a_{k-1}$, а наступні члени визначаються через k попередніх членів і через їх номер у послідовності за правилом:

$$a_{n}=R(n,a_{n-1},a_{n-2},\dots ,a_{n-k}),n\geqslant k,$$

(*)

де R — деяка відома функція.

Співвідношення (рівняння) вигляду (*) називається рекурентним.

Порядком рекурентного співвідношення називається різниця між найбільшим та найменшим індексами членів, що входять у співвідношення.

Розв'язком рекурентного співвідношення називається послідовність, підставлення якої у співвідношення перетворює його у тотожність.

Початковими умовами називаються додаткові умови, що накладаються на послідовність, заданням значень її початкових членів.

Розв'язок рекурентного співвідношення, що залежить від довільних сталих, які можуть бути підібраними при будь-яких початкових умовах, називається загальним. Частинним розв'язком рекурентного співвідношення називається будь-який розв'язок, що може бути отриманий із загального, встановленням значень його сталих.

Приклади

• Послідовність Фібоначчі:

$a_{n}=a_{n-1}+a_{n-2},a_{0}=1,a_{1}=1.$

• Рекурентне співвідношення арифметичної прогресії:

$a_{n}=a_{n-1}+d.$

• Рекурентне співвідношення геометричної прогресії:

$a_{n}=qa_{n-1}.$

• Рекурентне співвідношення послідовності n!:

$a_{n}=na_{n},a_{0}=1.$

• Числа Каталана:

$a_{n}=\sum \limits _{i=0}^{n-1}a_{i}a_{n-i-1},a_{0}=1.$

• Рекурентне співвідношення синуса фіксованого кута:

$\sin(n+1)\alpha =2\sin \alpha \cos n\alpha +\sin(n-1)\alpha .$

Лінійні рекурентні співвідношення

Лінійні однорідні рекурентні співвідношення зі сталими коефіцієнтами

Лінійним однорідним рекурентним співвідношенням зі сталими коефіцієнтами порядку k називається рівняння

$a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=0,$

де всі коефіцієнти $c_{1},c_{2},\dots ,c_{k}$ — сталі.

Ці коефіцієнти визначають характеристичний поліном (або допоміжний поліном) цього співвідношення

$p(\lambda )=\lambda ^{k}+c_{1}\lambda ^{k-1}+c_{2}\lambda ^{k-2}+\cdots +c_{k}$.

Згідно з основною теоремою алгебри рівняння $p(\lambda )=0$, яке називається характеристичним, має $k$ коренів. Ці корені відіграють вирішальну роль в знаходженні невідомої послідовності.

Якщо всі корені $\lambda _{1},\lambda _{2},\dots ,\lambda _{k}$ прості, то загальний розв'язок такого рекурентного співвідношення має вигляд:

$a_{n}=B_{1}\lambda _{1}^{n}+B_{2}\lambda _{2}^{n}+\cdots +B_{k}\lambda _{k}^{n},$

де $B_{i}$ — сталі.

У випадку коли характеристичне рівняння має багатократні корені $\lambda _{1},\lambda _{2},\dots ,\lambda _{s}$ загальний розв'язок матиме вигляд:

$a_{n}=\sum _{i=1}^{s}(B_{i1}+B_{i2}n+\cdots +B_{il_{i}}n^{l_{i}-1})\lambda _{i}^{n},$

де $l_{i}$ — кратність кореня $\lambda _{i}$, $B_{ij}$ — сталі.

Якщо задані початкові умови для лінійного однорідного рекурентного співвідношення зі сталими коефіцієнтами порядку k, то коефіцієнти $B_{i}$ (або $B_{ij}$) знаходяться за допомогою розв'язання відповідної системи лінійних рівнянь. У іншому випадку ці коефіцієнти можуть мати будь-які значення, тобто рекурентне співвідношення має нескінченну кількість розв'язків. І ці розв'язки утворюють k-вимірний лінійний простір.

Лінійні неоднорідні рекурентні співвідношення зі сталими коефіцієнтами

Лінійним неоднорідним рекурентним співвідношенням зі сталими коефіцієнтами порядку k називається рівняння

$a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=d_{n},$

де всі коефіцієнти $c_{1},c_{2},\dots ,c_{k}$ — сталі, $\{d_{n}\}$ — деяка відома ненульова послідовність.

Загальний розв'язок такого співвідношення дорівнює сумі його частинного розв'язку і загального розв'язку відповідного лінійного однорідного співвідношення

$a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=0.$

Для відшукання частинного розв'язку лінійного неоднорідного рекурентного співвідношення важливу роль відіграє принцип суперпозиції. Його застосування полягає в тому, що вільний член $d_{n}$ подається у вигляді суми, в певному сенсі, простіших функцій $d_{n}^{(1)},\dots ,d_{n}^{(m)}.$ Далі використовується твердження, що якщо послідовність $\{a_{n}^{(j)}\}$ є розв'язком рекурентного співвідношення

$a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=d_{n}^{(j)},$

де j = 1, ..., m, то розв'язок початкового лінійного неоднорідного рекурентного співвідношення має наступний вигляд:

$a_{n}=\sum \limits _{j=1}^{m}a_{n}^{(j)}.$

У випадку, коли $d_{n}=(e_{l}n^{l}+e_{l-1}n^{l-1}+\dots +e_{0})s^{n},$ де $e_{l},e_{l-1},\dots ,e_{0}$ та s — сталі, частковий розв'язок неоднорідного рекурентного співвідношення матиме вигляд $n^{r}(b_{l}n^{l}+b_{l-1}n^{l-1}+\dots +b_{0})s^{n},$ де $b_{l},b_{l-1},\dots ,b_{0}$ — деякі сталі, $r=0$, якщо s не дорівнює жодному кореню характеристичного рівняння відповідного лінійного однорідного співвідношення, інакше r дорівнює кратності кореня, з яким збігається s.

Лінійні рекурентні співвідношення з поліноміальними коефіцієнтами

Лінійним рекурентним співвідношенням з поліноміальними коефіцієнтами порядку k називається рівняння

$p_{0}(n)a_{n}+p_{1}(n)a_{n-1}+p_{2}(n)a_{n-2}+\cdots +c_{k}p_{k}(n)a_{n-k}=q_{n},$

де всі коефіцієнти $p_{0},p_{1},\dots ,p_{k}$ — відомі поліноми, причому p₀ і p_k ненульові, $\{q_{n}\}$ — деяка відома послідовність.

Методи розв'язання таких рекурентних співвідношень почали з'являтись з пізніх 1980-х. Сергій Абрамов спочатку розробив метод знаходження поліноміальних розв'язків, а потім — раціональних розв'язків. Останній метод отримав назву «алгоритм Абрамова». У 1992 Марко Петковшек знайшов алгоритм, названий пізніше його ім'ям, для знаходження розв'язків у більш специфічному класі послідовностей.

Нелінійні рекурентні співвідношення

Розв'язки нелінійних рекурентних співвідношень можна знаходити за допомогою генератрис.

Для цього нелінійне рекурентне співвідношення $a_{n}=R(n,a_{n-1},a_{n-2},\dots ,a_{n-k})$ помножимо на $t^{n}$, і отриману рівність просумуємо по всіх $n\geqslant 0.$ Після цього у лівій частині рівності отримаємо генератрису

$A(t)=\sum \limits _{n=0}^{\infty }a_{n}t^{n},$

а праву частину перетворимо так, щоб вона перетворилася у вираз від $A(t).$ Далі розв'язуємо отримане рівняння відносно $A(t).$

Потім розкладаємо $A(t)$ у степеневий ряд. Коефіцієнти отриманого ряду утворюють розв'язок початкового нелінійного рекурентного співвідношення.

Застосування

Аналіз алгоритмів

Рекурентні співвідношення мають принципове значення в аналізі алгоритмів. Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.

Простий приклад це час, необхідний алгоритму для пошуку елемента в масиві з $n$ елементів, в найгіршому випадку.

Примітивний алгоритм перебирає масив зліва направо. Найгіршим випадком, буде ситуація в якій потрібний елемент є останнім. В цьому випадку кількість порівнянь дорівнюватиме $n$.

Найкращим алгоритмом для цієї задачі є бінарний пошук. Однак для нього потрібен відсортований масив. Спочатку він перевіряє, чи знаходиться потрібний елемент в середині масиву. Якщо ні, то перевіряє, чи середній елемент більший або менший за шуканий елемент. Після цього половина масиву може бути відкинута, і алгоритм може працювати знову на половині, що залишилась. Кількість порівнянь при виконанні цього алгоритму описується наступним рекурентним співвідношенням:

$c_{1}=1$

$c_{n}=1+c_{[n/2]}.$

За допомогою цього співвідношення можна довести, що часова складність бінарного пошуку дорівнює $O(\log _{2}(n))$.

Економіка

Рекурентні співвідношення, особливо лінійні рекурентні співвідношення, використовуються як в теоретичній, так і в емпіричній економіці. Зокрема, в макроекономіці можна розробити модель різних широких секторів економіки (фінансовий сектор, сектор товарів, ринок праці тощо), в якій дії деяких агентів залежать від лагових змінних. Потім модель розв'язується для поточних значень ключових змінних (відсоткова ставка, реальний ВВП тощо) відносно минулих та поточних значень інших змінних.

Математична біологія

Деякі з найвідоміших рекурентних співвідношень беруть свій початок у спробі моделювання популяційної динаміки. Наприклад, числа Фібоначчі колись використовували як модель зростання популяції кроликів.

Логістичне відображення використовується або безпосередньо для моделювання зростання популяції, або як відправна точка для більш детальних моделей популяційної динаміки. У цьому контексті для моделювання взаємодії двох або більше популяцій часто використовують систему різницевих рівнянь.

Наприклад, модель Ніколсона-Бейлі для взаємодії «хазяїн-паразит» має вигляд

$\left\{{\begin{alignedat}{3}N_{t+1}&&\;=\;&&&\lambda N_{t}e^{-aP_{t}}\\P_{t+1}&&\;=\;&&&N_{t}(1-e^{-aP_{t}})\\\end{alignedat}}\right.,$

де N_t — кількість хазяїв, а P_t — кількість паразитів у момент часу t.

Для просторової екології корисними є інтегрорізницеві рівняння, які є формою рекурентних співвідношень. Ці та інші різницеві рівняння особливо добре підходять для моделювання одновікових популяцій.

Див. також

• Рекурсія
• Рекурсія (програмування)
• Різницеве рівняння
• Часова складність
• Динамічні системи

Література

Українською

• Олiйник А.С., Петравчук А.П. (2024). Дискретна математика. Навчальний посiбник для студентiв механiко-математичного факультету (PDF). Київ: Видавничо-поліграфічний центр "Київський університет". с. 177.
• Ганюшкін О.Г. (2024). Комбінаторний аналіз. Навчальний посiбник для студентiв механiко-математичного факультету (PDF). Київ: Видавничо-поліграфічний центр "Київський університет". с. 346.
• Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. (2024). Дискретна математика : підручник (вид. 7-ме, випр. та допов.). Львів: ПП "Магнолія 2006 ". с. 432. ISBN 978-617-574-266-2.

Іншими мовами

• V. K. Balakrishnan (1996). Introductory discrete mathematics (англ.). New York: Dover Publications. с. 236. ISBN 978-0486691152.
• Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications (англ.) (вид. 8). New York: McGraw Hill. с. 1120. ISBN 978-1259676512.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (англ.) (вид. 2). Addison-Wesley. ISBN 0-201-55802-5.
• Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996). A=B (англ.). A K Peters. ISBN 978-1568810638. OCLC 33898705.
• Enders, Walter (2014). Applied Econometric Times Series (англ.) (вид. 4). с. 496. ISBN 978-1-118-80856-6.
• Cull, Paul; Flahive, Mary; Robson, Robbie (2005). Difference Equations: From Rabbits to Chaos (англ.). Springer. с. 392. doi:10.1007/0-387-27645-9. ISBN 978-0-387-23233-1.
• Jacques, Ian (2006). Mathematics for Economics and Business (англ.) (вид. 5). Prentice Hall. с. 683. ISBN 978-0-273-70195-8.