Метод производящих функций для нахождения

Общего решения линейного однородного рекуррентного

Соотношения второго порядка

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

Для последовательности {u_n} введём в рассмотрение формальный степенной ряд u(x) = , называемый производящей функцией последовательности {u_n} . Ясно, что этот ряд хранит всю информацию об исходной последовательности.

Идея применения производящих функций для решения рекуррентных соотношений состоит в том, чтобы найти в явном виде производящую функцию решения соотношения, разложить её в ряд и получить формулы для коэффициентов этого ряда, которые совпадают с членами искомой последовательности. Эти вычисления выполняются с помощью простейших алгебраических операций над рядами: сложения и умножения на двучлены.

Рассмотрим линейное однородное рекуррентное соотношение с постоянными коэффициентами f(n + 2) = a₁×f(n + 1) + a₂×f(n), где a₂ ¹ 0 (иначе соотношение будет первого порядка).

Любое его решение {u_n} удовлетворяет соотношениям:

u₂ = a₁×u₁ + a₂×u₀ | ´ x⁰

u₃ = a₁×u₂ + a₂×u₁ | ´ x¹

. . .

u_i+2 = a₁×u_i+1 + a₂×u_i | ´ xⁱ

. . .

Умножая эти равенства на xⁱ и складывая, получим

u₂×x⁰ + u₃×x¹ + … + u_i+2×xⁱ + … = a₁×(u₁×x⁰ + u₂×x¹ + … + u_i+1×xⁱ + … ) +

+ a₂×(u₀×x⁰ + u₁×x¹ + … + u_i×xⁱ + … ),

которое эквивалентно системе написанных выше равенств: эти равенства немедленно получаются, если приравнять коэффициенты при одинаковых степенях переменной x в этих рядах. Далее,

u₂×x⁰ + u₃×x¹+u₄×x² + … = a₁×( u₁×x⁰ + u₂×x¹+u₃×x²+…)+a₂×(u₀×x⁰+u₁×x¹+ …) Û

Û u(x) – u₀ – u₁×x = a₁×x×(u(x) – u₀) +a₂×x²×u(x) Û

Û u(x)×(1 – a₁×x – a₂×x²) = u₀ + u₁×x – u₀×a₁×x,

т.е. .

Рассмотрим характеристическое уравнение c(x) = x² – a₁×x – a₂ = 0, которое всегда имеет корни в поле комплексных чисел C . При этом c(x) = x² – a₁×x – a₂ = (x – l₁)×(x – l₂). Теперь 1 – a₁×x – a₂×x² = = = (1–l₁×x)×(1 – l₂×x), так что

,

где U₀ = u₀ , U₁ = u₁ – a₁×u₀ .

Оказывается, что эту дробь можно разложить в сумму элементарных дробей. Под этим понимается разложение вида в случае l₁ ¹ l₂ и разложение при l₁ = l = l₂ .

В этом легко убедиться непосредственно, найдя числа A и B. В первом случае, умножив на общий знаменатель (1 – l₁×x)×(1 – l₂×x), получим равенство U₀ + U₁×x = A×(1 – l₂×x) + B×(1 – l₁×x). Приравнивая коэффициенты при одинаковых степенях x, приходим к системе уравнений относительно A и B, из которой находим .

Во втором случае кратного корня аналогично получаем:

U₀ + U₁×x = A×(1 – l×x) + B Û .

Здесь l ¹ 0, поскольку иначе a₂ = l₁×l₂ = 0 – противоречие.

Рассмотрим теперь два случая:

1. l₁ ¹ l₂ . Тогда , и для разложения в ряд можно применить легко доказываемую формулу = 1 + y + y² + … :

= 1 + y + y² + … Û (1 – y)×(1 + y + y² + …) = 1 Û

Û (1 + y + y² + … ) – y – y² – y³ – … = 1,

что верно.

Таким образом, в случае различных корней получим

.

Вспоминая определение производящей функции, получаем u_n = A×l₁ⁿ + B×l₂ⁿ , где A и B – некоторые комплексные постоянные.

2. l₁ = l = l₂ . Тогда . Для получения разложения в ряд второй дроби продифференцируем разложение = 1 + y + y² + … :

.

Таким образом,

Поэтому u_n = ((A+B) + B×n)×lⁿ , для некоторых констант A, B Î C .

Проверим теперь, что последовательности u_n = c₁×l₁ⁿ + c₂×l₂ⁿ (в случае l₁ ¹ l₂) и u_n = (c₁ + с₂×n)×lⁿ (для случая l₁ = l = l₂) с произвольными постоянными c₁ , c₂ Î C будут решениями линейного однородного рекуррентного соотношения f(n+2) = a₁×f(n+1) + a₂×f(n) второго порядка.

В первом случае: f(n+2) – a₁×f(n+1) + a₂×f(n) =

= c₁×l₁ⁿ⁺² + c₂×l₂ⁿ⁺² – a₁×(c₁×l₁ⁿ⁺¹ + c₂×l₂ⁿ⁺¹) – a₂×( c₁×l₁ⁿ + c₂×l₂ⁿ) =

= c₁×l₁ⁿ×(l₁² – a₁×l₁ – a₂) + c₂×l₂ⁿ×(l₂² – a₁×l₂ – a₂) = 0 + 0 = 0,

т.к. l₁ и l₂ – корни уравнения l² – a₁×l – a₂ .

Во втором случае f(n+2) – a₁×f(n+1) + a₂×f(n) =

= (с₁ + с₂×(n+2))×lⁿ⁺² – a₁×(с₁ + с₂×(n+1)) lⁿ⁺¹ – a₂×(с₁ + с₂×n) lⁿ =

= c₁×lⁿ×(l² – a₁×l – a₂) + c₂×lⁿ×((n+2)×l² – a₁×(n+1)×l – a₂×n) =

= c₁×lⁿ×0 + c₂×lⁿ×[n×(l² – a₁×l – a₂) +2×l² – a₁×l] = c₂×lⁿ×[n×0 + 0] = 0,

т.к. l² – a₁×l – a₂ = 0 и x² – a₁×x – a₂ = (x – l)×(x – l), т.е. a₁ = 2×l .

Итак, доказана

Теорема (об общем решении линейного однородного рекуррентного соотношения с постоянными коэффициентами). Следующие условия для последовательности {u_n} комплексных чисел эквивалентны:

(1) последовательность {u_n} является решением линейного однородного рекуррентного соотношения с постоянными коэффициентами

f(n + 2) = a₁×f(n + 1) + a₂×f(n).

(2) если характеристическое уравнение c(l) = 0, где c(l) = l² – a₁×l – a₂ , имеет два различных корня l₁ и l₂ , то u_n = l₁ⁿ×c₁ + l₂ⁿ×c₂ (c₁ , c₂ Î C);

если характеристическое уравнение c(l) = 0, где c(l) = l² – a₁×l – a₂ , имеет два совпавших корня l₁ = l = l₂ , то u_n = lⁿ×(c₁ + c₂×n) (c₁ , c₂ Î C).

Эта теорема даёт метод нахождения общего решения произвольного однородного линейного рекуррентного соотношения с постоянными коэффициентами:

Не нашли, что искали? Воспользуйтесь поиском по сайту: