Реккурентные соотношения с постоянными коэффициентами

1 2 3 4 5 6 7

Однородные реккурентные соотношения

- реккурентное соотношение глубины 1

Решение однородных реккурентных соотношений

с_ka_n+k + c_k-1a_n+k-1+ … + c₁a_n₊₁ + c₀a_n = 0 – общийвидо.р.с. глубины k

с_i - константы

a_i - искомая последовательность

Сделаем переход к характеристическому уравнению:

с_kxⁿ⁺^k + c_k_-1xⁿ⁺^k^-1+ … + c₁xⁿ⁺¹ + c₀xⁿ = 0

с_kx^k + c_k_-1x^k^-1+ … + c₁x + c₀ = 0 – хар. уравнение

1) Все корни разные

Пусть корни будут такие: a₁, a₂, …, a_k - k – штук

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

x_n = A₁ + A₂ + … + A_k

где константы A_i можно найти, исходя из начальных условий(например a₀ = 1, a₁ = 2)

2) Характеристическое уравнение имеет кратные корни, например хар-кое уравнение (x - 1)³ = 0 имеет 1 корень кратности 3.

Пусть хар-кое уравнение имеет корни a₁, a₂, …, a_m кратности r₁, r₂, …, r_m. Тогда общий вид решения будет следующим:

x_n = P₁(n) + P₂(n) + … + P_m(n)

где P_i(n) – многочлен степени(r_i - 1). Коэффициенты многочленов P₁(n), P₂(n), …, P_m(n) находятся из начальных условий.

Решение неоднородных реккурентны соотношений

с_ka_n+k + c_k-1a_n+k-1+ … + c₁a_n₊₁ + c₀a_n = f(n) – общийвиднеоднородных рек.с.

Рассмотрим метод решения, когда f(n):

1) f(n) = P(n) - многочлен

2) f(n) = caⁿ, где с – константа, a ≠ 1

3)f(n) = P(n)aⁿ, где P(n) - многочлен

Решение состоит из 2х этапов:

I) Решение однородного реккурентного соотношения без учета начальных условий

II) Находим частные решения неоднородного реккурентного соотношения(неопределенные коэффициенты ищутся подстановкой ч. решения в неод. рек. соотношение)

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