Русская Википедия:Линейная рекуррентная последовательность
Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность <math>x_0,x_1,\dots</math>, задаваемая линейным рекуррентным соотношением:
- <math>x_n= a_1\cdot x_{n-1}+\dots+a_d\cdot x_{n-d}</math> для всех <math>n\geqslant d</math>
с заданными начальными членами <math>x_0,\dots,x_{d-1}</math>, где d — фиксированное натуральное число, <math>a_1,\dots,a_d</math> — заданные числовые коэффициенты, <math>a_d\ne 0</math>. При этом число d называется порядком последовательности.
Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.
Теория линейных рекуррентных последовательностей является точным аналогом теории линейных дифференциальных уравнений с постоянными коэффициентами.
Примеры
Частными случаями линейных рекуррентных последовательностей являются последовательности:
- последовательности Люка, удовлетворяющие <math>x_n= P\cdot x_{n-1} - Q\cdot x_{n-2}</math>, в частности:
- арифметические прогрессии с <math>(P,Q) = (2,1)</math>;
- геометрическая прогрессия с <math>Q=0</math>;
- числа Фибоначчи с <math>(P,Q) = (1,-1)</math>;
- числа Люка с <math>(P,Q) = (1,-1)</math>;
- числа трибоначчи, удовлетворяющие <math>x_n= x_{n-1} + x_{n-2} + x_{n-3}</math>.
Формула общего члена
Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена
- <math>\lambda^d-a_1 \lambda^{d-1}-\dots-a_{d-1}\lambda - a_d.</math>
А именно, общий член выражается в виде линейной комбинации <math>d</math> последовательностей вида
- <math>x_n=\lambda_k^n\cdot n^m,</math>
где <math>\lambda_k</math> — корень характеристического многочлена и <math>m</math> — целое неотрицательное число меньшее, чем кратность <math>\lambda_k</math>.
Для чисел Фибоначчи такой формулой является формула Бине.
Пример
Для нахождения формулы общего члена последовательности <math>F_n</math>, удовлетворяющей линейному рекуррентному уравнению второго порядка <math>F_n=b\cdot F_{n-1}+c\cdot F_{n-2}</math> с начальными значениями <math>F_1</math>, <math>F_2</math>, следует решить характеристическое уравнение
- <math>q^2-bq-c=0</math>.
Если уравнение имеет два различных корня <math>q_1</math> и <math>q_2</math>, отличных от нуля, то для произвольных постоянных <math>A</math> и <math>B</math>, последовательность
- <math>F_n=A\cdot q_1^n+ B\cdot q_2^n,</math>
удовлетворяет рекурентному соотношению; остаётся найти числа <math>A</math> и <math>B</math>, что
- <math>F_1=A\cdot q_1+ B\cdot q_2</math> и <math>F_2=A\cdot q_1^2+ B\cdot q_2^2</math>.
Если же дискриминант характеристического уравнения равен нулю и значит уравнение имеет единственный корень <math>q_1</math>, то для произвольных постоянных <math>A</math> и <math>B</math>, последовательность
- <math>F_n=(A+B\cdot n)\cdot q_1^{n}</math>
удовлетворяет рекурентному соотношению; остаётся найти числа <math>A</math> и <math>B</math>, что
- <math>F_1=(A+B)\cdot q_1</math> и <math>F_2=(A+B\cdot 2)\cdot q_1^{2}</math>.
В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка
- <math>F_n=5\cdot F_{n-1}-6\cdot F_{n-2}</math>; <math>F_1=1</math>, <math>F_2=-2</math>.
корнями характеристического уравнения <math>q^2-5\cdot q+6=0</math> являются <math>q_1=2</math>, <math>q_2=3</math>. Поэтому
- <math>F_n=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}).</math>.
Окончательно:
- <math>F_n=5\cdot 2^{n-1}-4\cdot 3^{n-1}.</math>
Приложения
Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.
История
Основы теории линейных рекуррентных последовательностей были даны в двадцатых годах восемнадцатого века Абрахамом де Муавром и Даниилом Бернулли. Леонард Эйлер изложил её в тринадцатой главе своего «Введения в анализ бесконечно-малых» (1748).[1] Позднее Пафнутий Львович Чебышёв и ещё позже Андрей Андреевич Марков изложили эту теорию в своих курсах исчисления конечных разностей.[2][3]
См. также
Примечания
Литература
Шаблон:Последовательности и ряды
