Перегляд вихідного коду сторінки Рекурентне співвідношення

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

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

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

== Основні поняття і означення ==
''Рекурентним співвідношенням'' для послідовності <math>\{a_n\}</math> називається рівняння, яке виражає <math>a_{n}</math> через індекс {{mvar|n}} та {{mvar|k}} попередніх членів даної послідовності, а саме: <math>a_{n-1}, a_{n-2}, \dots, a_{n-k}</math>, для всіх цілих чисел {{mvar|n}}, не менших за {{mvar|k}}, де {{mvar|k}}&nbsp;— натуральне число, яке є константою або залежить від {{mvar|n}}.

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

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

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

== Приклади ==

* [[Послідовність Фібоначчі]]:
: <math>a_{n} = a_{n-1} + a_{n-2}, a_{0} = 1, a_{1} = 1.</math>
* Рекурентне співвідношення [[арифметична прогресія|арифметичної прогресії]]:
: <math>a_{n} = a_{n-1} + d.</math>
* Рекурентне співвідношення [[геометрична прогресія|геометричної прогресії]]:
: <math>a_{n} = q a_{n-1}.</math>
* Рекурентне співвідношення послідовності [[факторіал|n!]]:
: <math>a_{n} = n a_{n-1}, a_{0} = 1.</math>
* [[Число Каталана|Числа Каталана]]:
: <math>a_{n} = \sum\limits_{i=0}^{n-1}a_{i}a_{n-i-1}, a_{0} = 1.</math>
* Рекурентне співвідношення [[Список тригонометричних тотожностей#Ітераційні формули|синуса фіксованого кута]]:
: <math>\sin (n+1)\alpha=2\sin \alpha\cos n\alpha+\sin(n-1)\alpha.</math>

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

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

: <math>a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2}+\cdots+c_{k}a_{n-k} = 0,</math>

де всі коефіцієнти <math>c_1, c_2, \dots, c_{k}</math>&nbsp;— сталі.

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

: <math>p(\lambda)= \lambda^k + c_1\lambda^{k-1} + c_2\lambda^{k-2}+\cdots+c_{k}</math>.
Згідно з [[Основна теорема алгебри|основною теоремою алгебри]] рівняння <math>p(\lambda)=0</math>, яке називається ''характеристичним'', має <math>k</math> коренів. Ці корені відіграють вирішальну роль в знаходженні невідомої послідовності.

Якщо всі корені <math>\lambda_{1}, \lambda_{2}, \dots, \lambda_{k}</math> [[кратність (математика)|прості]], то загальний розв'язок такого рекурентного співвідношення має вигляд:
: <math>a_n = B_1 \lambda_{1}^n + B_2 \lambda_{2}^n + \cdots + B_k \lambda_{k}^n,</math>
де <math>B_i</math>&nbsp;— сталі.

У випадку коли характеристичне рівняння має багатократні корені <math>\lambda_{1}, \lambda_{2}, \dots, \lambda_{s}</math> загальний розв'язок матиме вигляд:
: <math>a_n =\sum_{i=1}^{s} (B_{i1} + B_{i2}n +\cdots + B_{il_i}n^{l_i-1})\lambda_i^n,</math>
де <math>l_i</math>&nbsp;— кратність кореня <math>\lambda_i</math>, <math>B_{ij}</math>&nbsp;— сталі.

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

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

: <math>a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2}+\cdots+c_{k}a_{n-k} = d_{n},</math>

де всі коефіцієнти <math>c_1, c_2, \dots, c_{k}</math>&nbsp;— сталі, <math>\{d_{n}\}</math>&nbsp;— деяка відома ненульова послідовність.

Загальний розв'язок такого співвідношення дорівнює сумі його часткового розв'язку і загального розв'язку відповідного лінійного однорідного співвідношення
: <math>a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2}+\cdots+c_{k}a_{n-k} = 0.</math>

Для відшукання часткового розв'язку лінійного неоднорідного рекурентного співвідношення важливу роль відіграє [[принцип суперпозиції]].<ref>{{sfn0|Balakrishnan|1996|с=97-98}}</ref> Його застосування полягає в тому, що вільний член <math>d_n</math> подається у вигляді суми, в певному сенсі, простіших функцій <math>d_{n}^{(1)}, \dots, d_{n}^{(m)}.</math> Далі використовується твердження, що якщо послідовність <math>\{a_{n}^{(j)}\}</math> є розв'язком рекурентного співвідношення
: <math>a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2}+\cdots+c_{k}a_{n-k} = d_{n}^{(j)},</math>
де {{math|''j'' {{=}} 1, ..., ''m''}}, то розв'язок початкового лінійного неоднорідного рекурентного співвідношення має наступний вигляд:
: <math>a_n = \sum\limits_{j=1}^{m}a_{n}^{(j)}.</math>

У випадку, коли <math>d_n = (e_{l}n^{l} + e_{l-1}n^{l-1} + \dots + e_0) s^n,</math> де <math>e_{l}, e_{l-1}, \dots, e_0</math> та {{math|''s''}}&nbsp;— сталі, частковий розв'язок неоднорідного рекурентного співвідношення матиме вигляд <math>n^{r}(b_{l}n^{l} + b_{l-1}n^{l-1} + \dots + b_0) s^{n},</math> де <math>b_{l}, b_{l-1}, \dots, b_0</math>&nbsp;— деякі сталі, <math>r = 0</math>, якщо {{math|''s''}} не дорівнює жодному кореню характеристичного рівняння відповідного лінійного однорідного співвідношення, інакше {{math|''r''}} дорівнює кратності кореня, з яким збігається {{math|''s''}}.<ref>{{sfn0|Kenneth|2019|с=549}}</ref>

=== Лінійні рекурентні співвідношення з поліноміальними коефіцієнтами ===
{{main|{{нп|Лінійне рекурентне співвідношення з поліноміальними коефіцієнтами|Лінійне рекурентне співвідношення з поліноміальними коефіцієнтами|en|P-recursive equation}}}}
''Лінійним рекурентним співвідношенням з поліноміальними коефіцієнтами порядку {{math|k}}'' називається рівняння

: <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},</math>

де всі коефіцієнти <math>p_0, p_1, \dots, p_{k}</math>&nbsp;— відомі поліноми, причому {{math|''p''<sub>0</sub>}} і {{math|''p''<sub>''k''</sub>}} ненульові, <math>\{q_{n}\}</math>&nbsp;— деяка відома послідовність.

Методи розв'язання таких рекурентних співвідношень почали з'являтись з пізніх 1980-х. Сергій Абрамов спочатку розробив {{нп|Поліноміальні розв'язки лінійних рекурентних рівнянь з поліноміальними коефіцієнтами|метод знаходження поліноміальних розв'язків|en|Polynomial solutions of P-recursive equations}}<ref>{{Cite journal|last=Abramov|first=Sergei A.|date=1989|title=Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations|journal=Moscow University Computational Mathematics and Cybernetics|volume=3}}</ref>, а потім&nbsp;— раціональних розв'язків.<ref>{{Cite journal|last=Abramov|first=Sergei A.|date=1989|title=Rational solutions of linear differential and difference equations with polynomial coefficients|journal=USSR Computational Mathematics and Mathematical Physics|volume=29|issue=6|pages=7–12|doi=10.1016/s0041-5553(89)80002-3|issn=0041-5553}}</ref> Останній метод отримав назву «{{нп|Алгоритм Абрамова|алгоритм Абрамова|en|Abramov's algorithm}}». У 1992 {{нп|Марко Петковшек|Марко Петковшек|en|Marko Petkovšek}} знайшов {{нп|алгоритм Петровшека|алгоритм|en|Petkovšek's algorithm}}, названий пізніше його ім'ям, для знаходження розв'язків у більш специфічному класі послідовностей.<ref>{{Cite journal|last=Petkovšek|first=Marko|date=1992|title=Hypergeometric solutions of linear recurrences with polynomial coefficients|journal=Journal of Symbolic Computation|volume=14|issue=2–3|pages=243–264|doi=10.1016/0747-7171(92)90038-6|issn=0747-7171|doi-access=free}}</ref>

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

Для цього нелінійне рекурентне співвідношення <math>a_{n} = R(n, a_{n-1}, a_{n-2}, \dots, a_{n-k})</math> помножимо на <math>t^n</math>, і отриману рівність просумуємо по всіх <math>n \geqslant 0.</math> Після цього у лівій частині рівності отримаємо генератрису
: <math>A(t) = \sum\limits_{n=0}^{\infty} a_n t^n,</math>
а праву частину перетворимо так, щоб вона стала виразом від <math>A(t).</math> Далі розв'язуємо отримане рівняння відносно <math>A(t).</math>

Потім розкладаємо <math>A(t)</math> у [[степеневий ряд]]. Коефіцієнти отриманого ряду утворюють розв'язок початкового нелінійного рекурентного співвідношення.<ref>{{sfn0|Ганюшкін|2024|с=156}}</ref>

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

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

Рекурентні співвідношення мають принципове значення в [[Аналіз алгоритмів|аналізі алгоритмів]].<ref>[[Томас Кормен|Cormen, T.]] et al, ''[[Вступ до алгоритмів|Introduction to Algorithms]]'', MIT Press, 2009</ref><ref>R. Sedgewick, F. Flajolet, ''An Introduction to the Analysis of Algorithms'', Addison-Wesley, 2013</ref> Якщо [[алгоритм]] влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.

Простий приклад це час, необхідний алгоритму для пошуку елемента в [[масив (структура даних)|масиві]] з <math>n</math> елементів, в найгіршому випадку.

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

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

: <math>c_1=1</math>
: <math>c_n=1+c_{[n/2]}.</math>
За допомогою цього співвідношення можна довести, що [[часова складність]] бінарного пошуку дорівнює <math>O(\log_2(n))</math>.

=== Економіка ===
{{Main|Часовий ряд}}
Рекурентні співвідношення, особливо лінійні рекурентні співвідношення, використовуються як в теоретичній, так і в емпіричній економіці.<ref>{{cite book |first1=Nancy L. |last1=Stokey | first2=Robert E. Jr. |last2=Lucas |author-link2=Роберт Емерсон Лукас |first3=Edward C. |last3=Prescott |author-link3=Едвард Прескотт |title=Recursive Methods in Economic Dynamics |location=Cambridge |publisher=Harvard University Press |year=1989 |isbn=0-674-75096-9 |url=https://books.google.com/books?id=BgQ3AwAAQBAJ }}</ref><ref>{{cite book |last2=Sargent |first2=Thomas J. |first1=Lars |last1=Ljungqvist |author-link=Томас Джон Сарджент |title=Recursive Macroeconomic Theory |location=Cambridge |publisher=MIT Press |edition=Second |year=2004 |isbn=0-262-12274-X |url=https://archive.org/details/recursivemacroec02edljun |url-access=registration }}</ref> Зокрема, в [[макроекономіка|макроекономіці]] можна розробити модель різних широких секторів економіки (фінансовий сектор, сектор товарів, [[ринок праці]] тощо), в якій дії деяких агентів залежать від [[лаг часовий|лагових]] змінних. Потім модель розв'язується для поточних значень ключових змінних ([[норма процента|відсоткова ставка]], реальний [[валовий внутрішній продукт|ВВП]] тощо) відносно минулих та поточних значень інших змінних.

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

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

Наприклад, {{нп|модель Ніколсона-Бейлі|модель Ніколсона-Бейлі|en|Nicholson–Bailey model}} для взаємодії «хазяїн-[[паразит]]» має вигляд
: <math>
\left\{
\begin{alignat}{3}
N_{t+1} &&\; = \;&&& \lambda N_t e^{-aP_t} \\
P_{t+1} &&\; = \;&&& N_t(1-e^{-aP_t})      \\
\end{alignat}
\right.
,</math>
де {{math|''N''<sub>''t''</sub>}}&nbsp;— кількість хазяїв, а {{math|''P''<sub>''t''</sub>}}&nbsp;— кількість паразитів у момент часу {{math|''t''}}.

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

== Див. також ==
{{Wikibooks|Розв'язник вправ по дискретній математиці/Комбінаторика/Вправи на рекурсію}}
* [[Рекурсія]]
* [[Рекурсія (програмування)]]
* [[Різницеве рівняння]]
* [[Часова складність]]
* [[Динамічні системи]]

== Примітки ==
{{reflist}}

== Література ==

=== Українською ===
* {{cite book
 |автор          = Олiйник А.С., Петравчук А.П.
 |назва          = Дискретна математика. Навчальний посiбник для студентiв механiко-математичного факультету
 |місце          = Київ
 |видавництво    = Видавничо-поліграфічний центр "Київський університет"
 |рік            = 2024
 |pages          = 177
 |url            = https://mechmat.knu.ua/wp-content/uploads/2024/03/dm_book.pdf
 |isbn           = 
 |ref            = 
}}
* {{cite book
 |автор          = Ганюшкін О.Г.
 |назва          = Комбінаторний аналіз. Навчальний посiбник для студентiв механiко-математичного факультету
 |місце          = Київ
 |видавництво    = Видавничо-поліграфічний центр "Київський університет"
 |рік            = 2024
 |pages          = 346
 |url            = https://mechmat.knu.ua/wp-content/uploads/2024/02/comb-anal.pdf
 |isbn           = 
 |ref            = {{sfnref|Ганюшкін|2024}}
}}
* {{cite book
 |автор          = Нікольський Ю.В., Пасічник В.В., Щербина Ю.М.
 |назва          = Дискретна математика : підручник
 |видання        = 7-ме, випр. та допов.
 |місце          = Львів
 |видавництво    = ПП "Магнолія 2006 "
 |рік            = 2024
 |pages          = 432
 |isbn           = 978-617-574-266-2
 |ref            = 
}}
* {{cite book
 |автор          = Андрiйчук В.I., Комарницький М.Я., Iщук Ю.Б.
 |назва          = Вступ до дискретної математики
 |місце          = Львів
 |видавництво    = Видавничий центр ЛНУ ім. І.Франка
 |рік            = 2003
 |pages          = 254
 |ref            = 
}}

=== Іншими мовами ===
* {{cite book
 |author         = V. K. Balakrishnan
 |title          = Introductory discrete mathematics
 |url            = https://archive.org/details/introductorydisc0000bala
 |url-access     = registration
 |place          = New York
 |publisher      = Dover Publications
 |year           = 1996
 |pages          = 236
 |language       = en
 |isbn           = 978-0486691152
 |ref            = {{sfnref|Balakrishnan|1996}}
}}
* {{cite book
 |author         = Kenneth H. Rosen
 |title          = Discrete Mathematics and Its Applications
 |edition        = 8
 |place          = New York
 |publisher      = McGraw Hill
 |year           = 2019
 |pages          = 1120
 |language       = en
 |isbn           = 978-1259676512
 |ref            = {{sfnref|Kenneth|2019}}
}}
* {{cite book
 |author         = Susanna S. Epp
 |title          = Discrete Mathematics with Applications
 |url            = https://archive.org/details/susanna-s.-epp-discrete-mathematics-with-applications-cengage-learning-2019
 |edition        = 5
 |place          = Boston
 |publisher      = Cengage Learning
 |year           = 2019
 |pages          = 984
 |language       = en
 |isbn           = 978-1-337-69419-3
 |ref            = {{sfnref|Susanna|2018}}
}}
* {{cite book
 |first1=Ronald L. |last1=Graham    | author1-link=Рональд Грем
 |first2=Donald E. |last2=Knuth     | author2-link=Дональд Кнут
 |first3=Oren      |last3=Patashnik
 |title=Concrete Mathematics: A Foundation for Computer Science
 |edition        = 2
 |publisher      = Addison-Wesley
 |language       = en
 |year           = 1994
 |isbn           = 0-201-55802-5
}}
* {{cite book
 |last1=Petkovšek  |first1=Marko
 |last2=Wilf       |first2=Herbert S.
 |last3=Zeilberger |first3=Doron
 |url            = https://www.math.upenn.edu/~wilf/Downld.html 
 |title          = A=B
 |date           = 1996
 |publisher      = A K Peters
 |language       = en
 |isbn           = 978-1568810638
 |oclc           = 33898705
}}
* {{cite book
 |year        = 2014
 |url         = 
 |first1      = Walter
 |last1       = Enders
 |title       = Applied Econometric Times Series
 |edition     = 4
 |pages       = 496
 |language    = en
 |isbn        = 978-1-118-80856-6
}}
* {{cite book
 |first1=Paul   | last1=Cull
 |first2=Mary   | last2=Flahive
 |first3=Robbie | last3=Robson
 |title       = Difference Equations: From Rabbits to Chaos
 |publisher   = Springer 
 |pages       = 392
 |year        = 2005 
 |language    = en
 |isbn        = 978-0-387-23233-1
 |doi         = 10.1007/0-387-27645-9
}}
* {{cite book
 |first=Ian | last=Jacques
 |title       = Mathematics for Economics and Business 
 |edition     = 5
 |publisher   = Prentice Hall
 |year        = 2006
 |pages       = 683
 |language    = en
 |isbn        = 978-0-273-70195-8
}}

{{Бібліоінформація}}
{{Портали|Математика}}
[[Категорія:Рекурентні співвідношення| ]]
[[Категорія:Комбінаторика]]