- •Глава 4. Рекуррентные уравнения (соотношения)
- •4.1. Основные понятия и определения
- •4.2. Линейные рекуррентные уравнения с постоянными коэффициентами
- •4.3. Построение общего решения однородного рекуррентного уравнения по корням характеристического многочлена
- •Нахождение частного решения неоднородного рекуррентного уравнения с помощью метода неопределенных коэффициентов
- •Определение решения рекуррентного уравнения, удовлетворяющего заданным начальным условиям
- •Примеры задач с решениями
Определение решения рекуррентного уравнения, удовлетворяющего заданным начальным условиям
Формулировка задачи. Пусть имеется линейное неоднородное рекуррентное уравнение и известно его общее решение
( 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 и, как следствие, все значения , входящие в правую часть системы, будут нулевыми.
Порядок нахождения решения линейного неоднородного рекуррентного уравнения по заданным начальным условиям:
Вычисляем значения последовательностей , для всех
значений 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,
в) 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,
представляющую искомое частное решение, удовлетворяющее заданным начальным условиям.