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

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

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

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

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

Рекурентним співвідношенням для послідовності $\{a_n\}$ називається рівняння, яке виражає $a_n$ через індекс Шаблон:Mvar та Шаблон:Mvar попередніх членів даної послідовності, а саме: $a_{n-1},a_{n-2},\dots ,a_{n-k}$, для всіх цілих чисел Шаблон:Mvar, не менших за Шаблон:Mvar, де Шаблон:Mvar — натуральне число, яке є константою або залежить від Шаблон:Mvar.

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

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

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

Приклади

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

$a_n=a_{n-1}+a_{n-2},a_0=1,a_1=1.$

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

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

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

$a_n=q{a}_{n-1}.$

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

$a_n=n{a}_{n-1},a_0=1.$

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

$a_n=\sum _{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 .$

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

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

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

$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_{i{l}_i}{n}^{l_i-1}){\lambda }_i^n,$

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

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

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

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

$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)},$

де Шаблон:Math, то розв'язок початкового лінійного неоднорідного рекурентного співвідношення має наступний вигляд:

$a_n=\sum _{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$ та Шаблон:Math — сталі, частковий розв'язок неоднорідного рекурентного співвідношення матиме вигляд $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$, якщо Шаблон:Math не дорівнює жодному кореню характеристичного рівняння відповідного лінійного однорідного співвідношення, інакше Шаблон:Math дорівнює кратності кореня, з яким збігається Шаблон:Math.

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

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

$p_0(n)a_n+p_1(n)a_{n-1}+p_2(n)a_{n-2}+\cdots +p_k(n)a_{n-k}=q_n,$

де всі коефіцієнти $p_0,p_1,\dots ,p_k$ — відомі поліноми, причому Шаблон:Math і Шаблон:Math ненульові, $\{q_n\}$ — деяка відома послідовність.

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

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

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

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

$A(t)=\sum _{n=0}^{\mathrm{\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))$.

Економіка

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

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

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

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

Наприклад, Шаблон:Нп для взаємодії «хазяїн-паразит» має вигляд

$\{\begin{array}{cccccc}{N}_{t+1}& & =& & & \lambda N_t{e}^{-a{P}_t}\\ P_{t+1}& & =& & & N_t(1-e^{-a{P}_t})\\ \end{array},$

де Шаблон:Math — кількість хазяїв, а Шаблон:Math — кількість паразитів у момент часу Шаблон:Math.

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

Див. також

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

Література

Українською

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book

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

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book