Курсовая работа по «Методам решений рекуррентных соотношений»

a(n) − d(n) = b(c1′, ..., ck′, n), т. е. a(n) = b(c1′, ...,ck′, n) + d(n).

Таким образом, последовательность b(c1,…,ck,n) + d(n), зависящая от k произвольных параметров, есть общее решение PC (2.3).

Доказательство завершено.

Согласно теореме 2.3 можно найти общее решение PC (2.3), если найдем какое-нибудь его решение, ибо известно как находить общее решение PC (2.1) (это линейное однородное PC (2.1) в дальнейшем будем называть соответствующим PC (2.3)). Некоторое решение PC (2.3) зависит от функции v(n). Мы остановимся на том случае функции v(n), которая указана в [8, теорема 2.6, с. 89].

Пусть функция v(n) из PC (2.3) есть  Rm(n)λn где Rm(n) – многочлен от n степени m и λ ≠ 0. В таком случае некоторое решение PC (2.3) имеет вид, Qm(n)λn где Qm(n) – многочлен от n степени m, если λ не является корнем характеристического уравнения (2.2), и вид nrQm(n)λn когда λ – корень этого уравнения кратности r (r ≥1).

Пример 2.4. Найти решение PC

f (n +1) = 3 f (n) + 2,   (2.5)

удовлетворяющее начальному значению f (0) = 6.

Характеристическое уравнение соответствующего однородного PC, т. е.       f (n +1) = 3 f (n), есть x − 3 = 0, откуда x = 3. Значит, общее решение этого однородного РС есть c13n.

В рассматриваемом неоднородном РС v(n) = 2, т. е. v(n) = 2, т. е.  Rm(n)λn = 2, и значит, Rm(n) = 2 и λ =1. Так как 1 не является корнем указанного характеристического уравнения, то должно существовать решение PC (2.4) вида Q0(n)1n, где Q0(n) – многочлен нулевой степени, т. е. в виде c ⋅1n= c; подставляя в (2.5), имеем c = 3c + 2, откуда c = −1. Итак, общее решение PC (2.5) есть c13n−1. Из начального значения f (0) = 6 находим, что c130 −1= 6 и c1 = 7. Таким образом, искомое решение есть 7 ⋅ 3n −1.

Пример 2.5. Найти решение PC (2.4), удовлетворяющее начальному значению f (0) =1. (Величину f (n) из этого PC можно интерпретировать как наибольшее число частей, на которые делят плоскость n прямых.)

Общее решение соответствующего однородного PC f (n +1) − f (n) = 0 есть произвольная константа c, ибо его характеристическое уравнение x −1= 0 своим корнем имеет число 1.

Частное решение PC (2.4) будем искать в виде n(an+ b), поскольку в рассматриваемом случае v(n) = R1(n) ⋅1n и 1 – корень характеристического уравнения. Подставляяn(an + b) висходное PC, (n +1)(a(n +1) + b) = n(a ⋅n + b) + + n +1 или 2an + a + b = n +1.

Отсюда

  и a = b =0,5.

Итак, общее решение n/2(n+1)+c. Из начального значения f (0) =1 находим, что c =1. Тогда требуемое решение есть n(n+1)/2+1, n ≥ 0.

3. . Методы решения линейных рекуррентных соотношений с переменными коэффициентами

В отличие от выше рассмотренных линейных однородных и неоднородных PC с постоянными коэффициентами, исследуемые здесь линейные РС будут иметь своими коэффициентами функции от n. Можно указать несколько видов таких линейных PC с переменными коэффициентами, для нахождения решений которых используются уже рассмотренные методы решений PC.

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

Пример 2.6. PC f(n) = 2(1+1/n) f (n−1) при n >1 и f (1) = 4 не является линейным однородным PC с постоянными коэффициентами, ибо 2(1+1/n) есть функция от n. Но разделив обе его части на n +1, получим PC f(n)/(n+1) = 2(1+1/n)/n при n >1, а затем, вводя новую функцию g(n) = f(n)/(n+1), последнее PC перепишется в виде g(n) = 2g(n −1) при n >1 и g(1) = f(1)/(1+1) = 2, т. е. мы имеем линейное однородное PC с постоянными коэффициентами.

Общее решение полученного PC есть a(n) = c ⋅2n , а из a(1) = g(1) следует c = 1, т. е. искомым решением линейного однородного PC с постоянными коэффициентами будет g(n) = 2n. А так как f (n) = (n +1)g(n), то f (n) = (n +1)2n – решение исходного PC с переменными коэффициентами.

Пример 2.7. Найти решение PC

(n +1) f (n) = 2(n −1) f (n −1) +1 при n >1 и f (1) =1.

Умножая это PC на n, получим PC

n(n +1) f (n) = 2n(n −1) f (n −1) + n при n >1 и f (1) =1.

Теперь введем новую функцию h(n) = n(n +1) f (n), и следовательно, будем иметь линейное неоднородное PC с постоянными коэффициентами h(n) = 2h(n −1) + n при n >1 и h(1) =1(1+1) f (1) = 2.

Общее решение соответствующего однородного PC с постоянными коэффициентами есть c ⋅ 2n. Частное решение полученного неоднородного PC ищем в виде d(n) = a ⋅ n + b, поэтому d(n) = 2d(n −1) + n, т. е. a⋅n + b = 2(a(n −1) + + b) + n или a⋅n + b = (2a +1)n + 2b − 2a, откуда

 

Значит, a = −1, b = −2 и общее решение этого неоднородного PC есть c2n − n  − 2. Используя начальное значение h(1) = 2, находим c = 5/2 т. е. требуемое решение указанного линейного неоднородного PC есть                       h(n) = 5⋅ 2n−1 – n − 2. Тогда

f (n) = h(n) n(n +1) = (5⋅ 2n−1 − n − 2) / n(n +1).

Приведем еще два класса PC, для которых определяются их решения. Первым из них является PC с переменными коэффициентами a(n +1) f (n +1) = b(n) f (n) + c(n) при n ≥ 0, где b(n) ≠ 0 при всех n.

Умножив обе его части на функцию , которая везде определена согласно условию, наложенному на функцию b(n), получим PC

b(n +1)F(n +1) f (n +1) = b(n)F(n) f (n) + c(n)F(n).

Теперь, делая в нем замену b(n)F(n) f (n) на d(n), придем к линейному неоднородному PC с постоянными коэффициентами d(n +1) = d(n) + c(n)F(n) при n ≥ 0, в котором вид функции c(n)F(n) не известен. Поэтому применим метод соседних разностей, заключающийся в построении следующих равенств:

d(n) – d(n−1) = c (n −1)F(n−1);

d(n–1) – d(n−2) = c (n −2)F(n−2);

d(1) – d(0) = c (0)F(0);

(Метод соседних разностей  удобно применять ко всем таким PC, в которых коэффициенты при  неизвестной функции в точках n +1и n совпадают; в нашем случае  они равны 1.)

Сложив эти n равенств, получим

 

и значит,

 

Отметим, что в этом решении найти входящую в него сумму иногда весьма затруднительно, хотя не всегда. Вот подтверждающий пример.

Рассмотрим PC (n+1) f (n+1)=(n+3) f (n)+1 при n ≥ 0 и f (0) =1. В этом PC a(n) = n +1, b(n) = n + 3 ≠ 0 для всех n, c(n) =1. Для этого PC

 

Далее, d(n) = b(n)F(n) f (n) и d(0) =1, а при всех n выполняется равенство

 

т. е. в данном случае d(n) легко находится.

Второй класс линейных PC с переменными коэффициентами есть при любом фиксированном k (k ≥ 0) PC

(n +1) f (n +1) − (n + k) f (n) = 0

при n ≥1, для которых строится решение f(n) = Cnn+k−1. Но указанное решение не является корректным при k = 0 (и не только из-за отсутствия постоянного множителя).

В самом деле, при k = 0 имеем следующее линейное PC с переменными коэффициентами:

(n +1) f (n +1) – n f (n) = 0 при n ≥1.

Сделав замену n f (n) = g(n), получим линейное однородное PC с постоянными коэффициентами g(n +1) − g(n) = 0 при n ≥1, общим решением которого является функция g(n) = C. Следовательно, решение исходного PC есть функция f (n) = C/n. При k = 0 имеем f(n) = Cnn−1 = 0.

Еще заметим, что указанное линейное PC с переменными коэффициентами можно записать в виде

 

правая часть которого при k ≥ 2 подсказывает искать его решение в виде биномиального коэффициента.

2.3  Некоторые другие рекуррентные соотношения и методы их решения

Вероятно, самыми простыми (с точки зрения поиска решений) PC являются те, которые непосредственно сводятся к сумме или произведению. Например, PC

S(n) = S(n −1) + anпри n > 0 и S(0) = 0

имеет решение

 

а следующее PC

p(n) = bn⋅ p(n −1) при n > 0 и p(0) =1

имеет решение

 

Используемый для этих PC способ решения есть простой пример итерации: применяем данное PC к его правой части, пока не придем к начальным значениям. Так, в первом из этих PC, применив его один раз к правой части, получим

S(n) = S(n − 2) + an−1 + an,

а применение n раз дает указанное решение. В частности, если каждое ai =1, то S(n) = n; если же ai = i −1, то S(n) = Cn2.

Конечно, методом итераций можно решать и более сложные PC.

Например, решим методом итераций PC

h(n) = anh(n −1) + bn при n > 0 и h(0) = 0,

где для всех n числа an и bn – действительные, отличные от 0. (По сути, это серия (как и предыдущие два примера) PC, ибо, задав конкретные an и bn , получим конкретное PC.)

Имеем

h (n) = anh(n-1) + bn = an(an-1h (n-2) + bn-1) + bn =

= anan-1h (n-2) + anbn-1 + bn = anan-1(an -2h (n-3) + bn-2) +

+ anbn1 + bn= anan-1an-2h (n-3) + anan-1bn-2 + anbn1 + bn =

= … =

т. е. снова методом итераций получили решение

 

исходного PC.

Частным случаем этой серии PC является PC

t(n) = nt(n-1)/(n+1) + 1 при n > 0 и t(0) = 0, где an = n/(n+1), bn = 1.

Получаем

 

К частному случаю рассматриваемой серии PC относится и PC

n ⋅ r(n) = (n +1) ⋅ r(n −1) + 2n при n > 0 и r(0) = 0,

ибо при n > 0 его можно разделить на n и получить PC

r(n) = (n +1) ⋅ r(n −1)/n + 2 при n > 0.

Обратимся к нелинейным PC. Одним из таких (но более «коварным») является РС

r(n +1) = r2 (n) − 2 при n ≥ 0.

Оказывается, что:

1) если r(0) = 0 или r(0) = 2, то его  решением является функция r(n) = 2 при n >1;

2) r(0) =1, то в таком случае  решение – функция r(n) = −1 при n >1.

Для больших значений r(0) зависимость r(n) от r(0) более сложная. В общем случае решение этого PC получается при помощи метода введения новой функции t(n), полагая

r(n) = t(n) +1/t(n).

Действительно, при такой замене получаем PC

t(n +1) +1/ t(n) +1= t2 (n) +1/ t2 (n) при n ≥ 0,

а начальное значение t(0) находится из уравнения r(0) = t(0) +1/ t(0).

Но из полученного PC следует t(n +1) = t2 (n) и, значит, t (n) = (t(0))2n.

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

Например, для решения PC

f (n + 2) = (f (n +1) ⋅ f (n))m при n ≥ 0 и f (0) = f (1) =1,

или

f (n+ k) = (f (n+ k– r1) f (n+ k–r2)…f (n+ k–rs))m,

где 1 ≤ ri ≤ k (1≤ i ≤ s),

или

 

где m – положительное действительное число и m ≠1, следует обе его части прологарифмировать.

Для PC

  при n ≥ 0 и h(0) = 0,

где k – натуральное число, не меньшее 2, простой путь к решению лежит через возведение в степень k.

В заключение обратимся еще раз к линейным однородным PC с постоянными коэффициентами. Как мы уже знаем, чтобы найти их решение, следует искать корни их характеристических уравнений. Но если эти уравнения степени не менее чем 3, то поиск их корней может не быть простым. Оказывается, в некоторых случаях можно уменьшить степень характеристического уравнения.

Например, для линейного однородного PC с постоянными коэффициентами

f (n + 4) = 5 f (n + 3) − 9 f (n + 2) + 7 f (n +1) − 2 f (n)

при n ≥ 0 и заданными начальными значениями f (i), 0 ≤ i ≤ 3, вместо рассмотрения соответствующего его характеристического уравнения 4-й степени, следует переписать его в виде

f (n + 4) − f (n + 3) = 4(f (n + 3) − f (n + 2)) − 5(f (n + 2) − f (n + 1)) +

+ 2(f (n + 1) − f (n)).

Затем ввести новую функцию g(n) = f (n +1) − f (n) и получить следующее линейное однородное PC с постоянными коэффициентами:

g(n + 3) = 4g(n + 2) − 5g(n +1) + 2g(n),

характеристическое уравнение, которого имеет степень 3 (начальные значения полученного PC определяются по начальным значениям исходного PC).

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Примеры решение рекуррентных соотношений