нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет

• Название: Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
• Дата: 23.12.2020
• Размер: 0.65 Mb.
• Имя файла: Teoria_avtomatov.docx
• Тип: Учебное пособие; #163524
• страница: 5 из 17

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

1.4.1. Определение рекуррентного уравнения

Рекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида

,

которое позволяет вычислить все члены последовательности a₀,a_1,a₂,.., если заданы её первые kчленов.

k – порядок рекуррентного уравнения.

Примеры. 1) a_n+1 = a_n + d -–арифметическая прогрессия.

2) a_n+1 = q ∙ a_n -–геометрическая прогрессия.

3) a_n+2 = a_n + a_n+1 -–последовательность чисел Фибоначчи.
1.4.2. Решение линейного однородного рекуррентного уравнения
В
(1)
случае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида

Последовательность a₀,a_1,a₂,.., удовлетворяющая данному уравнению называется возвратной.

М
(2)
ногочлен

называется характеристическим многочленом для возвратной последовательности .

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

Общее решение однородного линейного рекуррентного уравнения имеет аналогию с решением линейного дифференциального уравнения. А именно, справедливы теоремы.

Теорема 1. Пусть - корень характеристического многочлена (2), тогда последовательность , где c – производная константа, удовлетворяет уравнению (1).

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

,

где c₁,c₂,..,c_k – произвольные константы.

Теорема 3. Если - корень кратности (i= 1,2,..,s) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c_ij– произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям a₀, a₁,.., a_k-1, можно найти неопределенные постоянные c_ij, и, тем самым, получить частное уравнении (1) с данными начальными условиями.

Пример. Найти последовательность {a_n}, удовлетворяющую рекуррентному уравнению

Характеристический многочлен


1
(2)
.4.3. Решение линейного неоднородного рекуррентного уравнения
Рассмотрим линейное неоднородное рекуррентное уравнение

a_n+k + p₁a_n+k-1 + … + p_ka_n = f(n), (n = 0, 1, 2,…) (3)

Пусть {b_n} – общее решение однородного уравнения (1). {c_n} – частное (конкретное) решение неоднородного уравнения (3).

Тогда последовательность {b_n + c_n} образует общее решение уравнения (3). Таким образом, справедлива теорема.

Теорема 4. Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения.

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

1сли f(n) = βⁿ, (где β не является корнем характеристического уравнения), то частное решение следует искать в виде c_n = Cβⁿ. Тогда, подставляя его в (3), получаем:

1. 
   
   

.

Отсюда

В результате, частное решение задаётся формулой


2) Пусть f(n)–многочлен степени rот переменной n, и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде

Подставляя c_n в (3) вместо a_n, получаем

Сравнивая коэффициенты левой и правой частей полученного равенства, найдём соотношения для чисел d_i, позволяющие эти числа определить.

Пример. Найти решение рекуррентного уравнения

с начальным условием .

Решение. Рассмотрим характеристический многочлен данного рекуррентного уравнения

.

Его корень . Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения
задаётся формулой , где – произвольная константа.

Так как , т.е. единица не является корнем характеристического многочлена, а правая часть есть многочлен первой степени, то частное решение неоднородного уравнения ищется в виде полинома первой степени с неопределёнными коэффициентами , где и – неизвестные коэффициенты. Подставив вместо в исходное уравнение, получим или . Приравнивая коэффициенты левой и правой части последнего равенства, получаем систему уравнений для определения неизвестных и :

.

Отсюда, находим: и . Таким образом, частное решение исходного уравнения имеет вид . По теореме 4 получаем общее решение неоднородного рекуррентного уравнения . Из начального условия . В результате, окончательно имеем: .