Рекуррентные соотношения и уравнения
В этом разделе вы найдете бесплатные примеры решений рекуррентных соотношений методом характеристического уравнения и подбора частного решения по правой части. Также приведены краткие алгоритмы решения для двух методов и пример их использования для последовательности Фибоначчи.
Как решать рекуррентные соотношения?
Для решения рекуррентных соотношений применяют один из двух основных способов:
- Метод производящих функций
- Метод характеристического уравнения
В следующем разделе мы сравним, как выглядит процесс решения для одной и той же последовательности двумя методами.
Метод производящих функций
- Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k$$
- Домножить каждую строчку на $z$ в соответствующей степени $z^{k} \cdot a_{k}$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_{n=0}^{\infty} a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
- Решить полученное уравнение относительно $G(z)$.
- Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.
Метод характеристических функций
Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:
- Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_{n+k} a_{n+k} + p_{n+k-1}a_{n+k-1} + ... + p_n a_n =f \to \\ \to p_{n+k} a_{n+k} + p_{n+k-1}a_{n+k-1} + ... + p_n a_n =0. $$
- Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_{n+k} \lambda^{k} + p_{n+k-1}\lambda^{k-1} + ... + p_{n-1}\lambda + p_n =0. $$
- Выписать согласно полученным корням $\lambda_1, ...,\lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +...+C_k \lambda_k^n \, \mbox { для случая различных простых корней}, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +...+C_m n^m \lambda_1^n+...+C_k \lambda_k^n \mbox { для случая корня }\, \lambda_1 \, { кратности }\, m. $$
- Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ - многочлен от $n$).
- Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
- Подставить начальные условия $a_0, a_1, ..., a_{k-1}$ и получить значения констант $C_1, ..., C_k$.
Решение для последовательности чисел Фибоначчи
Последовательность чисел Фибоначи - это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:
$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , ... $$Числа Фибоначчи растут быстро: $f_{10}=55$, $f_{20}=6765$, а $f_{100}=354224848179261915075$.
Общая формула данной рекуррентной последовательности имеет вид6
$$\begin{array}{rcl} f_0&{}={}&0,\\ f_1&{}={}&1,\\ f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2.\\ \end{array} $$Способ 1. Производящяя функция
Начинаем с второго шага алгоритма, домножаем на $z^n$:
$$\begin{array}{rcl} 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geq2.\\ \end{array} $$Складываем все строчки:
$$f_0 + f_1 z + \sum_{n=2}^{\infty}f_nz^n = z + \sum_{n=2}^{\infty}f_{n-1}z^n+\sum_{n=2}^{\infty}f_{n-2}z^n. $$На третьем шаге алгоритма приводим все суммы к замкнутому виду:
$$\begin{array}{rcl} G(z) &=& z + z\sum_{n=2}^{\infty}f_{n-1}z^{n-1}+z^2 \sum_{n=2}^{\infty}f_{n-2}z^{n-2},\\ G(z) &=& z + z\sum_{n=1}^{\infty}f_{n}z^{n}+z^2 \sum_{n=0}^{\infty}f_{n}z^{n},\\ G(z) &=& z + z(G(z)-f_0)+z^2 G(z),\\ G(z) &=& z + zG(z)+z^2G(z),\\ \end{array} $$откуда выводим искомое выражение для производящей функции:
$$ G(z) = \frac{z}{1-z-z^2}. $$Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:
$$1-z-z^2 = 0,\\ z_1=-\frac{1-\sqrt{5}}{2}, z_2=-\frac{1+\sqrt{5}}{2}.$$Таким образом,
$$G(z) = \frac{z}{1-z-z^2}=\frac{-z}{(z_1-z)(z_2-z)} = \frac{z_1/(z_1-z_2)}{z_1-z} + \frac{z_2/(z_2-z_1)}{z_2-z}. $$Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:
$$\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.$$Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:
$$ \frac{z_1/(z_1-z_2)}{z_1-z} = \frac{1}{z_1-z_2} \frac{1}{1-\frac{z}{z_1}} = \frac1{z_1-z_2}\sum_{n=0}^{\infty}\frac{z^n}{z_1^n}. $$Аналогично (но с делением на $z_2$) действуем со второй дробью:
$$\frac{z_2/(z_2-z_1)}{z_2-z} = \frac{1}{z_2-z_1}\frac{1}{1-\frac{z}{z_2}} = \frac{1}{z_2-z_1}\sum_{n=0}^{\infty}\frac{z^n}{z_2^n}. $$Таким образом,
$$G(z)=\sum_{n=0}^{\infty} f_nz^n =\sum_{n=0}^{\infty}\biggl (\frac{1}{z_1-z_2} \frac{1}{z_1^n} + \frac{1}{z_2-z_1}\frac{1}{z_2^n} \biggr)z^n, $$и, следовательно,
$$f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}. $$Преобразуем данное выражение, используя то, что
$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt{5} $$ $$f_n=\frac{1}{\sqrt{5}}\left( \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n \right). $$И окончательно,
$$ f_n = \frac1{2^n\sqrt{5}} \bigl( (1+\sqrt{5})^n - (1-\sqrt{5})^n \bigr). $$Способ 2. Характеристическое уравнение
Запишем характеристический многочлен для $f_n=f_{n-1}+f_{n-2}$, и найдем его корни:
$$ x^2=x+1,\\ D=1+4=5, \\ x_{1,2}=\frac{1\pm \sqrt{5}}{2}. $$Тогда общее решение однородного рекуррентного уравнения имеет вид:
$$ f_n=C_1 \biggl(\frac{1- \sqrt{5}}{2} \biggr)^n+C_2 \biggl(\frac{1+ \sqrt{5}}{2} \biggr)^n. $$Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.
$$ f_0=C_1 +C_2 =0,\\ f_1=C_1 \bigl(\frac{1- \sqrt{5}}{2} \bigr)+C_2 \bigl(\frac{1+ \sqrt{5}}{2} \bigr)=1. $$Решая систему, найдем
$$ C_1 =-1/\sqrt{5},\\ C_2 = 1/\sqrt{5}. $$Итоговое выражение для последовательности чисел Фибоначчи:
$$ f_n= -\frac{1}{\sqrt{5}} \bigl(\frac{1- \sqrt{5}}{2} \bigr)^n +\frac{1}{\sqrt{5}} \bigl(\frac{1+ \sqrt{5}}{2} \bigr)^n = \\ =\frac1{2^n\sqrt{5}} \bigl( (1+\sqrt{5})^n - (1-\sqrt{5})^n \bigr). $$Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.
Примеры решений
Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку
Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку
Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$
с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.
Задача 4. Найти последовательность ${a_n}$, удовлетворяющую рекуррентному соотношению $a_{n+2} + 4 a_{n+1} + 3 a_{n} = 0$ и начальным условиям $a_1=2$, $a_2=4$.
Полезные ссылки
- Рекуррентные последовательности, ЛОРУ, ЛНРУ Краткое изложений лекций по ДМ для 1 курса МГУ
- Решение рекуррентных соотношений Краткая теория и примеры, метод производящих функций
- Разностное уравнение и рекуррентная последовательность Более продвинутый материал
- Примеры: примитивно-рекурсивные функции
- Примеры: разностные уравнения
