Рекуррентные уравнения с переменными коэффициентами (7 видео)

Содержание

Рекуррентные соотношения и уравнения
Как решать рекуррентные соотношения?
Метод производящих функций
Метод характеристических функций
Решение для последовательности чисел Фибоначчи
Способ 1. Производящяя функция
Способ 2. Характеристическое уравнение
Примеры решений
Образовательный блог — всё для учебы
Дискретная математика — рекуррентное соотношение
Определение
Линейные рекуррентные отношения
Как решить линейное рекуррентное соотношение
🔍 Видео

Видео:21.04 - дискра, рекуррентные соотношенияСкачать

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

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

Видео:Райгородский А. М. - Комбинаторика - Линейные рекуррентные соотношенияСкачать

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

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

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

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

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

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

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

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

Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f to \ to p_ a_ + p_a_ + . + p_n a_n =0. $$
Выписать для него характеристическое уравнение и найти его корни $lambda_i$ $$ p_ lambda^ + p_lambda^ + . + p_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 nlambda_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_$ и получить значения констант $C_1, . C_k$.

Видео:16. Линейные неоднородные дифференциальные уравнения 2-го порядка с постоянными коэффициентамиСкачать

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$$1/z_1=-z_2, quad 1/z_2 = -z_1, quad z_1-z_2=sqrt $$ $$f_n=frac<sqrt>left( biggl( frac<1+sqrt> biggr)^n — biggl( frac<1-sqrt> 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$.

Видео:2. Линейные уравнения с переменными коэффициентами Скачать

Образовательный блог — всё для учебы

Определение: Уравнение L(x(k)) = x(k+n) + a₁(k)x(k+n-1) + … + a_n(k)x(k) = , причём: 0 – (R₀) однородное уравнение, F(k) – R₁ неоднородное уравнение.

где a_i(k) – функция в N→R, i = 1…n и F(k)≠0 (тривиально) – неизвестная функция, x(k) – неизвестная функция, называются линейными рекуррентными уравнениями (ЛРУ) однородными и неоднородными соответственно с переменными коэффициентами.

Число n в R₀ называется порядком уравнения.
Коэффициент a₀ при х(k+n) может быть ≠1, сделаем его таковым, разделив R₀(R₁) на а₀. Однородное ЛРУ L(x(k)) = 0 называется соответствующим неоднородному ЛРУ Lx(k)) = F(k).

Замечание: Последовательности, являющиеся решением ЛРУ иногда называют возвратными последовательностями.

Утверждение: Оператор L(x) линеен.

Доказательство:
Пусть x(k) и y(k) – произвольные функции и c∈R.
1. L(x+y) = (x(k+n) + y(k+n)) + a_i(x(k+n-1) + y(k+n-1) + … + a_n(x(k) + y(k)) = x(k+n) + a₁x(k+n-1) + … + a_nx(k) + y(k+n) + a₁(k+n-1) + … + a_ny(k) = L(x) + L(y)
2. L(cx) = cx(k+n) + ca₁x(k+n-1) + … + ca_nx(k) = c(x(k+n) + … + a_nx(k)) = cL(x)

Теорема: Множество всех решений однородного ЛРУ является ЛВП.

Доказательство:
Пусть х(к), y(k) – произвольное решение однородного ЛРУ R0 и c∈R => L(x(k))=0 и L(y(k))=0, тогда выполняются следующие операции:
1. L(x+y) = L(x) + L(y) (≡ 0 = 0+0)
2. L(cx) = cL(x) (≡ 0 = c0)

Мы получили, что множество М решений однородного ЛРУ замкнуто относительно линейных операций. Восемь аксиом ЛВП выполняются для М как для множества (подмножества) всех функций х(к) из ЛВП всех таких функций, следовательно, множество М есть ЛВП.

Теорема: Общее решение неоднородного ЛРУ есть сумма какого-либо его частного решения и общего решения соответствующего однородного ЛРУ.

Доказательство
Пусть x(k) и y(k) – пара решений неоднородного ЛРУ L(x(k)) = F(k), следовательно их разность есть решение соответствующего однородного ЛРУ L(x(k)) = 0, так как
L(x-y) = L(x) – L(y) = F(k) – F(k) = 0.

Пусть x_оо = G(c₁…c_n, k) – общее решение однородного ЛРУ и х_чн(л) – какое-либо частное решение неоднородного ЛРУ R₁. Покажем, что х_он = х_оо + х_чн
1. Функция х_он = х_оо + х_чн есть решение ЛРУ R₁ при ∀с₁…с_n, так как L(x_oн) = L(x_oo + x_чн) = L(x_oo) + L(x_чн) = 0 + F(k) = F(k)
2. Покажем, что для любого частного решения z(k) неоднородного ЛРУ R₁ найдутся числа с₁…с_n, для которых z(k) = G(c₁…c_n, k) + x_чн(к):
Зафиксируем числа d₁…d_n и построим функцию y(k) = G(d₁…d_n, k) + x_чн(k). Разность z(k)–y(k) есть решение однородного ЛРУ и потому найдутся числа l₁…l_n, для которых z(k)-y(k) = G(l₁…l_n, k). Отсюда
z(k) = y(k) + G(l₁…l_n, k) = G(d₁…d_n, k) + x_чн + G(l₁…l_n, k) = U(k) + x_чн(k), где Г = G(d₁…d_n, k) + G(l₁…l_n, k) как сумма двух решений для R₀ есть снова решение для R₀. Поэтому найдутся числа с₁…с_n, для которых U(k) = G(l₁…l_n, k), следовательно
z(k) = G(c₁…c_n, k) + x_чн(k).

Видео:ЛОДУ с переменными коэффициентами. Примеры.Скачать

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

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

Видео:Решение неоднородного рекуррентного уравненияСкачать

Определение

Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая 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 = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Число Фибоначчи
F _n = F _n-1 + F _n-2	а ₁ = 1, а ₂ = 3	Номер Лукаса
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Падовская последовательность
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Число Пелла

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

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — 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 $$