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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Рекурентним співвідношенням називається формула виду an+1=F(an,an-1,...,an-k+1), де F деяка функція від k аргументів, яка дозволяє обчислити наступні члени числової послідовності через значення попередніх членів. Рекурентне співвідношення однозначно визначає послідовність an, якщо вказано k перших членів послідовності. Рекурентне співвідношення є прикладом рекурсивного визначення послідовності.

Приклади[ред.ред. код]

an+1=an+an-1, a1=1, a2=1.
an+1=an+d.
an+1=an·q.
  • Рекурентне співвідношення послідовності n!:
an+1=an·(n+1).
\sin (n+1)\alpha=2\sin \alpha\cos n\alpha+\sin(n-1)\alpha,.

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

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

a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d},

де всі коефіцієнти c_i постійні.

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

p(t)= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d}.

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

Якщо всі корені r_1,r_2, \dots, r_d різні, то розв'язок рекурсії має вигляд:

a_n = k_1 r_1^n + k_2 r_2^n + \cdots + k_d r_d^n,

де коефіцієнти k_i визначаються в залежності від значень початкових елементів послідовності a_1,a_2, \dots, a_d.

У випадку коли однакові корені присутні декілька разів (кратні корені) розв'язок рекурсії має інший вигляд. Якщо r_i\ (i=1,\dots, s) корінь кратності l_i (для простого кореня l_i=1), тоді

a_n =\sum_{i=1}^{s} (k_{i1} +k_{i2}n +\cdots + k_{il_i}n^{l_i-1})r_i^n,

де коефіцієнти k_{ij} визначаються з початкових елементів послідовності.

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

В комбінаториці[ред.ред. код]

Метод розв'язання комбінаторної задачі зведенням до меншої задачі (або задач) називається методом рекурентних співвідношень, а менша задача найчастіше є задачею відносно меншої кількості предметів.[1]

В інформатиці[ред.ред. код]

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

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

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

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

c_1=1
c_n=1+c_{[n/2]},

що буде близько до функції \log_2(n).

Дивіться також[ред.ред. код]

Посилання[ред.ред. код]

  1. Карнаух Т.О. Комбінаторика
  2. Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009
  3. R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013