Лінійною рекурентною послідовністю (лінійною рекурентою) називається будь-яка числова послідовність , задана лінійним рекурентним співвідношенням:
- для всіх
з заданими початковими членами , де d — фіксоване натуральне число, — задані числові коефіцієнти, . При цьому число d називається порядком послідовності.
Лінійні рекурентні послідовності іноді називають зворотними послідовностями.
Теорія лінійних рекурентних послідовностей є точним аналогом теорії лінійних диференціальних рівнянь з постійними коефіцієнтами.
Приклади
Частковими випадками лінійних рекурентних послідовностей є послідовності:
Формула загального члена
Для лінійних рекурентних послідовностей існує формула, яка виражає загальний член послідовності через корені її характеристичного многочлена
А саме, загальний член виражається у вигляді лінійної комбінації послідовностей виду
де — корінь характеристичного многочлена і
— ціле невід'ємне число, що не перевищує кратності
.
Для чисел Фібоначчі такою формулою є формула Біне.
Приклад
Для знаходження формули загального члена послідовності , що задовольняє лінійне рекурентне рівняння другого порядку
з початковими значеннями
,
, слід розв'язати характеристичне рівняння
.
Якщо рівняння має два різні корені і
, відмінні від нуля, то для довільних сталих
і
, послідовність
задовольняє рекурентне співвідношення; залишається знайти числа і
, такі, що
і
.
Якщо ж дискримінант характеристичного рівняння дорівнює нулю і отже, рівняння має єдиний корінь , то для довільних сталих
і
, послідовність
задовольняє рекурентне співвідношення; залишається знайти числа і
, такі, що
і
.
Зокрема, для послідовності, яка визначається таким лінійним рекурентним рівнянням другого порядку
;
,
.
коренями характеристичного рівняння є
,
. Тому
.
Остаточно:
Застосування
Лінійні рекурентні послідовності над кільцями вирахувань традиційно використовуються для генерування псевдовипадкових чисел.
Історія
Основи теорії лінійних рекурентних послідовностей були дані в двадцятих роках вісімнадцятого століття Абрахамом де Муавром і Даніелем Бернуллі. Леонард Ейлер виклав її у тринадцятій главі свого «Вступу до аналізу нескінченно малих» (1748). Пізніше Пафнутій Львович Чебишов і ще пізніше [ru] виклали цю теорію в своїх курсах числення скінченних різниць.
Див. також
Примітки
- Л. Эйлер, Введение в анализ бесконечно-малых, т. I, M. — Л., 1936, стр. 197—218
- П. Л. Чебышев, Теория вероятностей, лекции 1879—1880 гг., М. — Л., 1936, стр. 139—147
- А. А. Марков, Исчисление конечных разностей, 2-е изд., Одесса, 1910, стр. 209—239
Література
- [ru]. Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — ().
- М. М. Глухов, В. П. Елизаров, А. А. Нечаев. Глава XXV. Линейные рекуррентные последовательности // Алгебра. — Учебник. В 2-x томах. — М. : Гелиос АРВ, 2003. — Т. 2. — .
- А. Егоров. Числа Пизо // Квант. — 2005. — № 5. — С. 8—13.
- Чебраков Ю. В. Глава 2.7. Рекуррентные уравнения // Теория магических матриц. Выпуск ТММ-1. — СПб, 2010.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет