Примеры задач с решениями. Пример 4.1. Показать, что общее решение рекуррентного уравнения

Пример 4.1. Показать, что общее решение рекуррентного уравнения

f (n+2) = 7∙f (n+1) - 12∙f (n)

можно записать в виде

.

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

Чтобы убедиться в выполнении второго требования, выберем в качестве начальных условий произвольные числа A, B, т.е. f(0) = A,

f (1) = B. Так как из предполагаемого общего решения имеем

, ,

то для нахождения постоянных используем систему линейных уравнений

Решая эту систему, получим аналитические выражения для искомых величин

.

Из полученных выражений следует - для любых начальных условий A, B существует единственная последовательность

,

удовлетворяющая этим условиям и самому рекуррентному уравнению, что подтверждает выполнение второго требования к общему решению.

Пример 4.2. Найти общие решения однородных рекуррентных уравнений

a) f (n+3) – 9 f (n+2) + 26 f (n+1) – 24 f (n) = 0,

б) f (n+4) – f (n) = 0,

в) f (n+3) + 6 f (n+2) + 12 f (n+1) + 8 f (n) = 0,

г) f (n+4) + 2 f (n+2) + f (n) = 0.

a) Характеристическое уравнение, соответствующее первому из заданных рекуррентных уравненений,

,

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

.

В соответствии с правилом 1 функции натурального аргумента

составляют фундаментальную систему решений. В итоге общее решение рекуррентного уравнения имеет вид

.

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

имеет четыре различных корня:

два комплексных сопряженных ;

два действительных .

В соответствии с правилами 1, 2 четыре линейно независимые функции натурального аргумента

в которых b = p/2, составляют фундаментальную систему решений.

Следовательно, искомое общее решение рекуррентного уравнения имеет вид

.

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

имеет один корень h = - 2 кратности m = 3.

Согласно правилу 3, фундаментальную систему решений составляют три функции натурального аргумента

и, как следствие, искомое общее решение рекуррентного уравнения записывается в виде равенства

.

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

имеет два комплексных сопряженных корня кратности m = 2. В этом случае, согласно правилу 4, фундаментальная система решений включает четыре линейно независимые функции натурального аргумента

в которых b = p/2, и общее решение однородного рекуррентного уравнения имеет вид

.

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

для следующих вариантов правых частей:

a) а = 5, d (n) = 12,

б) а = - 2, d (n) = 4 (30 n + 7),

в) а = 3, d (n) = 2.

Запишем характеристический многочлен

,

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

.

а) Число а = 5 не относится к корням характеристического многочлена (R (5) = 6). Учитывая, что полином d (n) = 12 в правой части имеет нулевой порядок, записываем (в соответствии с правилом 1) аналитический вид частного решения и подставляем его в исходное уравнение. В результате будем иметь равенство

,

из которого находим D = 2, т.е. искомое частное решение можно записать в виде

.

б) Число а = - 2 также не относится к корням характеристического многочлена (R (-2) = - 120). В данном случае полином d (n) имеет первый порядок, т.е. согласно правилу 1, неизвестный полином D (n), входящий в частное решение, можно записать следующим образом

D (n) = An + B,

где A, B - неопределенные коэффициенты. Подставим частное решение в рекуррентное уравнение

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

D (n + 1) = A ∙ n + (A + B),

D (n + 2) = A ∙ n + (2 A + B),

D (n + 3) = A ∙ n + (3 A + B),

в результате чего будем иметь

.

Приравнивая коэффициенты при одинаковых степенях n (при нулевой и первой), получим систему уравнений

- 120 А = 120,

-148 А – 120В = 28,

разрешая которую, находим A = -1, B = 1, т.е. искомое частное решение можно записать следующим образом

.

в) Число а = 3 является простым (однократным) корнем характеристического многочлена. Для данного варианта исходный полином d (n) = 2.

Записываем, согласно правилу 2, аналитический вид частного решения и подставляем его в исходное уравнение

.

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

,

где R (3), - значения характеристического многочлена и его производной при h = 3.

Учитывая R (3) = 0, получаем , т.е. D существует, если значение отлично от нуля. Это подтверждает необходимость строгого соблюдения правила 2 (проверки и учета кратности корня).

Так как в рассматриваемом случае , то и искомое решение имеет вид

.

Пример 4.4. Найти решения рекуррентных уравнений с известными начальными условиями:

a) f (n +2) – f (n +1) – f (n) = 0, f (0) = 1, f (1) = 2,

б) f (n +2) – 2 f (n +1) + f (n) = 6 n, f (0) = 1, f (1) = 3.

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

имеет два действительных корня

, (А = ).

Следовательно, фундаментальную систему решений составляют две функции натурального аргумента

, ,

а общее решение имеет вид

.

Вычисляем необходимые значения функций (n = 0,1):

, , ,

и записываем систему линейных уравнений относительно неизвестных значений произвольных постоянных:

Решая эту систему, получим выражения для неизвестных величин

, .

После подстановки последних в общее решение записываем аналитический вид искомого решения, удовлетворяющего заданным начальным условиям:

.

На первый взгляд, кажется удивительным, что это выражение, с помощью которого получаются числа Фибоначчи, для любого n принимает целые значения.

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

имеет один действительный корень h = 1 кратности m = 2. Следовательно, фундаментальную систему решений составляют две функции

а общее решение однородного уравнения записывается следующим образом

.

Правая часть рекуррентного уравнения, согласно условиям примера, имеет вид (4.15) с параметрами

a = 1, d (n) = 6 n,

т.е. a = h = 1 - двукратный корень характеристического уравнения.

Исходя из этого, записываем аналитический вид частного решения

и подставляем его в исходное уравнение

.

После преобразования имеем 6 A ∙ n + 6 A + 2 B = 6 n. Приравнивая коэффициенты при одинаковых степенях n, получаем систему уравнений

6 A = 6,

6 A + 2 B = 0,

разрешая которую, находим A = 1, B = - 3, т.е. частное решение неоднородного уравнения удовлетворяет равенству

,

а с учетом ранее записанного его общее решение имеет вид

.

Для нахождения решения, удовлетворяющего начальным условиям, вычисляем значения функций , , (n = 0,1)

= 1, = 1, =0, =1, , ,

записываем систему линейных уравнений

и, решая эту систему, получаем .

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

f (n) = (n – 3)∙ + 4 n + 1,

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