Характеристическое уравнение для рекуррентных соотношений

Рекуррентные соотношения и уравнения

В этом разделе вы найдете бесплатные примеры решений рекуррентных соотношений методом характеристического уравнения и подбора частного решения по правой части. Также приведены краткие алгоритмы решения для двух методов и пример их использования для последовательности Фибоначчи.

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

• Метод производящих функций
• Метод характеристического уравнения

В следующем разделе мы сравним, как выглядит процесс решения для одной и той же последовательности двумя методами.

Метод производящих функций

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k$$
2. Домножить каждую строчку на $z$ в соответствующей степени $z^ \cdot a_$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
3. Решить полученное уравнение относительно $G(z)$.
4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:

1. Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_a_ + . + p_n a_n =0. $$
2. Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_ \lambda^ + p_\lambda^ + . + p_\lambda + p_n =0. $$
3. Выписать согласно полученным корням $\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. $$
4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
6. Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$\begin 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_+f_)\cdot z^n, \quad n\geq2.\\ \end $$

Складываем все строчки:

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

откуда выводим искомое выражение для производящей функции:

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

Преобразуем данное выражение, используя то, что

$$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). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Примеры решений

Задача 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_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Дискретная математика — рекуррентное соотношение

В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.

Определение

Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая F n как некоторую комбинацию F i с i n ).

Пример — ряд Фибоначчи — F n = F n − 1 + F n − 2 , Ханойская башня — F n = 2 F n − 1 + 1

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате x n = A 1 x n − 1 + A 2 x n − 1 + A 3 x n − 1 + d o t s A k x n k ( A n — константа, а A k n e q 0 ) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений —

Как решить линейное рекуррентное соотношение

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — F n = A F n − 1 + B F n − 2 , где A и B — действительные числа.

Характеристическое уравнение для вышеуказанного рекуррентного соотношения —

x 2 − A x e − B = 0

Три случая могут возникнуть при поиске корней —

Случай 1 — Если это уравнение учитывается как ( x − x 1 ) ( x − x 1 ) = 0 и оно дает два различных реальных корня x 1 и x 2 , то F n = a x n 1 + b x n 2 является решение. [Здесь a и b являются константами]

Случай 2 — Если это уравнение вычисляется как ( x − x 1 ) 2 = 0 , и оно порождает один действительный корень x 1 , то решением является F n = a x n 1 + b n x n 1 .

Случай 3 — Если уравнение дает два различных комплексных корня, x 1 и x 2 в полярной форме x 1 = r a n g l e t h e t a и x 2 = r a n g l e ( − t h e t a ) , то F n = r n ( a c o s ( n t h e t a ) + b s i n ( n t h e t a ) ) является решением.

Решите рекуррентное соотношение F n = 5 F n − 1 − 6 F n − 2 , где F 0 = 1 и F 1 = 4 .

Характеристическое уравнение рекуррентного соотношения —

Итак, ( x − 3 ) ( x − 2 ) = 0

x 1 = 3 и x 2 = 2

Корни реальны и различны. Итак, это в форме дела 1

F n = a x n 1 + b x n 2

Здесь F n = a 3 n + b 2 n ( A s x 1 = 3 a n d x 2 = 2 )

1 = F 0 = a 3 0 + b 2 0 = a + b

4 = F 1 = a 3 1 + b 2 1 = 3 a + 2 b

Решая эти два уравнения, мы получаем a = 2 и b = − 1

Следовательно, окончательное решение —

$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$

Решите рекуррентное соотношение — F n = 10 F n − 1 − 25 F n − 2 , где F 0 = 3 и F 1 = 17 .

Характеристическое уравнение рекуррентного соотношения —

x 2 − 10 x − 25 = 0

Итак, ( x − 5 ) 2 = 0

Следовательно, существует один действительный корень x 1 = 5

Поскольку существует единый действительный корень, он имеет вид случая 2

F n = a x n 1 + b n x n 1

3 = F 0 = a .5 0 + b .0 .5 0 = a

17 = F 1 = a .5 1 + b .1 .5 1 = 5 a + 5 b

Решая эти два уравнения, мы получаем a = 3 и b = 2 / 5

Следовательно, окончательное решение — F n = 3.5 n + ( 2 / 5 ) . n .2 n

Решите рекуррентное соотношение F n = 2 F n − 1 − 2 F n − 2 , где F 0 = 1 и F 1 = 3

Характеристическое уравнение рекуррентного соотношения —

Характеристическим уравнением рекуррентного соотношения (3) является уравнение вида

Рекуррентное соотношение — это соотношение(равенство, система равентсв) позволяющее свести решение комбинационной задачи для некоторого числа предметов к аналогичной задаче с меньшей размерностью. Решение комбинационных задач с помощью рекуррентных соотношений — это метод рекуррентных соотношений.

Рекуррентное соотношение

Пример 1: На плоскости нарисовано n — прямых, причем все прямые попарно не параллельны и никакие три прямые не пересекаются в одной точке. На сколько полуплоскостей они разобьют нашу плоскость?

Решение: Рассмотрим пару тривиальных случая и пусть функция f(n) равняется количеству полуплоскостей образованных n — прямыми. Рассмотрим сначала тривиальные случаи:

Теперь пусть на плоскости n прямых и мы проводим (n + 1) — прямую. Получим, что после проведения нашей (n + 1) — прямой общая численность полуплоскостей увеличиться на (n + 1) — полуплоскость. Отсюда получаем:

при

при

при

Выражаем сначала через и получаем и подставляем полученное равенство в последнее уравнение и получаем

Теперь выражаем через и т. д. В итоге получим следующее равенство

Пусть — решение комбинаторной задачи для n — предметов и для этой задачи известно рекуррентное соотношение вида

(1)

Некоторая функция k — переменных. (1) — рекуррентное соотношение k — го порядка. Последовательность чисел — решение (1), если при подстановке в (1) получается верное равенство.

Если первые k элементов рекуррентного соотношения (1) заданы произвольно(т.е. между ними нет соотношений), то (1) имеет бесконечно много решений. Если же первые k элементов определены однозначно, то все остальные элементы определяются однозначно.

Определение 1: Пусть — общее решение (1), если оно зависит от k прозвольных постоянных, т.е. . И для любого решения существуют такие постоянные значения , что

Характеристическое уравнение

Определение 2: Линейным однородным рекуррентным соотношением второго порядка с постоянными коэффициентами называется рекуррентное соотношение вида:

(2)

Нейкие коэффициенты, причем отлично от нуля. Уравнение вида

Характеристическое уравнение рекуррентного соотношения (2).

Теорема 1: Если характеристическое уравнение рекуррентного соотношения (2) имеет два различных корня , то общее решение рекуррентного соотношения (2) имеет вид

Если рекуррентное соотношение имеет два равных корня , то общее решение рекуррентного соотношения (2) имеет следующий вид

Утверждение 1: Пусть последовательности и являются решениями рекуррентного соотношения (2), тогда для \forall A,B

Является решением рекуррентного соотношения (2).

Утверждение 2: Если корень характеристического уравнения рекуррентного соотношения (2), то последовательность является решениемрекуррентного соотношения (2).

Определение 3: Линейным рекуррентным соотношением k — го порядка(k — фиксировано) с постоянными коэффициентами называется рекуррентное соотношение следующего вида:

(3)

Постоянные .

Характеристическим уравнением рекуррентного соотношения (3) является уравнение вида

Теорема 2: Пусть — все попарно различные корни характеристического уравнения рекурретного соотношения (3) — кратность корня . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид: