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

Формулировка задачи. Пусть имеется линейное неоднородное рекуррентное уравнение и известно его общее решение

( 4.21 )

в котором - любое частное решение, а (j = 1,2,...,k) – решения, образующие фундаментальную систему решений однородного уравнения .

Требуется среди всего множества решений, составляющих общее решение (4.21), выделить (найти) единственное решение , удовлетворяющее заданным начальным условиям f (i) ( i = 0,1,...,k-1).

Система уравнений  для нахождения решения - линейная неоднородная алгебраическая система k уравнений относительно совокупности неизвестных постоянных

(4.22 )

квадратная матрица которой составлена из значений = элементов последовательностей ( j = 1,2,...,k ), входящих в фундаментальную систему решений.

Замечание 1. Система всегда совместна и имеет единственное решение, так как ее квадратная матрица является (в силу независимости фундаментальной системы решений) невырожденной, т.е. определитель матрицы не равен нулю.

Замечание 2. Ясно, что в ситуации, когда исходное рекуррентное уравнение однородное, частное решение = 0 и, как следствие, все значения , входящие в правую часть системы, будут нулевыми.

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

1. Вычисляем значения последовательностей , для всех

значений n = i (i = 0,1,...,k-1) и записываем систему (4.22).

2. Решая алгебраическую систему, находим неизвестные постоянные (j = 1,2,...,k).

3. Подставляя в общее решение (4.21) вместо найденные значения постоянных , получаем конечный аналитический вид искомого решения f (n, ).

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

Примеры задач с решениями

Пример 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,

3. в) 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 четыре линейно независимые функции натурального аргумента

в которых  = , составляют фундаментальную систему решений.

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

.

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

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

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

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

.

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

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

в которых  =  , и общее решение однородного рекуррентного уравнения имеет вид

.

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

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

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

б) а = - 2, d (n) = 4 (30n + 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 + ( 2A + B ),

D ( n + 3 ) = A∙n + ( 3A + 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) = 6n, 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 - двукратный корень характеристического уравнения.

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

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

.

После преобразования имеем 6A∙n + 6A + 2B = 6n. Приравнивая коэффициенты при одинаковых степенях 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,

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