Рекурентним співвідношенням називається формула виду an+1=F(an,an-1,...,an-k+1), де F деяка функція від k аргументів, яка дозволяє обчислити наступні члени числової послідовності через значення попередніх членів. Рекурентне співвідношення однозначно визначає послідовність an, якщо вказано k перших членів послідовності. Рекурентне співвідношення є прикладом рекурсивного визначення послідовності.
Приклади Редагувати
- Рекурентне співвідношення арифметичної прогресії:
- Рекурентне співвідношення геометричної прогресії:
- Рекурентне співвідношення послідовності n!:
- Рекурентне співвідношення синуса фіксованого кута:
Лінійне однорідне рекурентне співвідношення з постійними коефіцієнтами Редагувати
Лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку є рівняння
де всі коефіцієнти постійні.
Ті ж самі коефіцієнти визначають характеристичний многочлен (або "допоміжний многочлен")
Згідно з основною теоремою алгебри існує коренів рівняння . Ці корені відіграють вирішальну роль в знаходженні послідовності, яка відповідає заданому рекурентному співвідношенню.
Якщо всі корені різні, то розв'язок рекурсії має вигляд:
де коефіцієнти визначаються в залежності від значень початкових елементів послідовності .
У випадку коли однакові корені присутні декілька разів (кратні корені) розв'язок рекурсії має інший вигляд. Якщо корінь кратності (для простого кореня ), тоді
де коефіцієнти визначаються з початкових елементів послідовності.
Як приклад можна зауважити, що послідовність Фібоначчі задається лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку два. Застосування наведеного методу дає формулу Біне.
У комбінаториці Редагувати
Метод розв'язання комбінаторної задачі зведенням до меншої задачі (або задач) називається методом рекурентних співвідношень, а менша задача найчастіше є задачею відносно меншої кількості предметів.
| Вікіпідручник має книгу на тему Розв'язник вправ по дискретній математиці/Комбінаторика/Вправи на рекурсію |
В інформатиці Редагувати
Рекурентні співвідношення мають принципове значення в аналізі алгоритмів. Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.
Простий приклад це час, необхідний алгоритму для пошуку елемента в упорядкованому векторі з елементів, в найгіршому випадку.
Примітивний алгоритм полягає в пошуку зліва направо. Найгіршим випадком,буде ситуація в якій потрібний елемент є останнім. В цьому випадку кількість порівнянь буде .
Найкращий алгоритм для цієї задачі є бінарний пошук. Він полягає в наступному. Треба спочатку перевірити, чи знаходиться елемент в середині вектора. Якщо ні, то будемо перевіряти, чи середній елемент більше або менше шуканого елемента. Після цього половина вектора може бути відкинута, і алгоритм може працювати знову на половині, що залишилась. Кількість порівнянь описується рекурентним співвідношенням:
що буде близько до функції .
Див. також Редагувати
Посилання Редагувати
- Карнаух Т.О. Комбінаторика [ 22 лютого 2014 у Wayback Machine.]
- Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009
- R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013
В іншому мовному розділі є повніша стаття Recurrence relation(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (квітень 2017)
|
| Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |