Линейные рекуррентные уравнения

Глава 4. Рекуррентные уравнения (соотношения)

Основные понятия и определения

Рекуррентные уравнения (соотношения), которые ранее уже неоднократно встречались (в том числе получались, строились), являются дискретными аналогами обыкновенных дифференциальных уравнений. Они, в отличие от дифференциальных, используемых в качестве математических моделей непрерывных систем, описывают динамику дискретных (импульсных) систем (одна из таких простейших систем фигурирует, в частности, в задаче Фибоначчи, рассмотренной в главе 2).

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

Если для некоторой задачи удалось получить рекуррентное уравнение относительно f(n), то в принципе эта задача уже решена, так как можно одно за другим вычислять значения f(i) для последовательных значений индекса i = 1,2,3,... Недостаток такого решения состоит в том, что нет аналитического выражения (формулы) общего члена f(n) числовой последовательности. Это не дает возможности до расчетов оценить поведение f(n) как функции натурального аргумента n.

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

Отличия рекуррентных уравнений от дифференциальных проявляются прежде всего в основных понятиях и определениях, которые, с одной стороны, во многом схожи с аналогичными понятиями из теории обыкновенных дифференциальных уравнений, а с другой стороны, отражают специфику дискретных систем (объектов, процессов).

Общий вид рекуррентного уравнения, разрешенного относительно старшего члена (элемента последовательности) - функции натурального аргумента f (n), можно записать следующим образом

f (n+k) = F[ g (n), f (n+k–1), f (n+k–2),...,f (n) ], (n = 0,1,2,...), (4.1)

где

k – порядок уравнения (k > 0), характеризующий глубину (продолжительность) связей между элементами искомой последовательности;

g (n) – заданная, как правило, аналитическим выражением последовательность – возмущающая функция натурального аргумента (ее присутствие в рекуррентном уравнении необязательно).

Так, например, три соотношения

f (n+1) = f (n) + 2 sin nb,

f (n+2) = f (n) – f (n+1) - 5 n ∙ exp (- n),

f (n+3) = f (n) + 3 f (n+1) ∙ f (n+2)

являются соответственно рекуррентными уравнениями 1-го, 2-го и 3-го порядков. При этом в первых двух уравнениях роль возмущающей функции g (n) выполняют две последовательности

{ 2 sin nb }, { -5 n ∙ exp (- n) },

а в третьем уравнении функция g (n) отсутствует, т.е. g (n) = 0.

Частное решение (или просто решение) рекуррентного уравнения - любая последовательность (решетчатая функция), удовлетворяющая уравнению (4.1), т.е. приводящая после ее подстановки в рекуррентное уравнение к тождеству.

Так, например, последовательность y (n) = { 2,4,8,..., ,... } является одним из частных решений рекуррентного уравнения

f (n+2) = 10 f (n) – 3 f (n+1),

в чем легко убедиться, если подставить y (n) в это уравнение.

Начальные условия рекуррентного уравнения. Если в (4.1) n = 0, то будем иметь соотношение для k -го элемента последовательности

f (k) = F [ g (0), f (k-1), f (k-2),..., f (0) ],

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

= { f (0), f (1),..., f (k-1) }. (4.2)

Эти значения (по аналогии с теорией дифференциальных уравнений, когда интегрирование сводится к решению задачи Коши) называются начальными условиями рекуррентного уравнения (4.1).

Общее решение рекуррентного уравнения - последовательность

f (n) = f (n ,C), (4.3)

зависящая от k произвольных постоянных (j = 1,2,..., k) и отвечающая двум требованиям (см. пример 4.1):

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

2) для любой заданной совокупности начальных условий (4.2) найдутся такие постоянные , что последовательность (4.3) будет удовлетворять этим условиям, т.е. системе k уравнений

, (i = 0,1,2 ,...,k- 1)

относительно k искомых значений постоянных .

Линейные рекуррентные уравнения