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

Например, последовательность

,…

явлеться одним из решений рекуррентного соотношения

f(n+2)=3f(n+1)-2f(n).

В самом деле, общий член этой последовательности имеет вид f(n)=

Значит . Но при любом nимеет место тождество . Поэтому являеться решением указанного соотношения.

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

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

Решение рекуррентного соотношения k-го порядка называються общим, если оно зависит отk произвольных постоянных и путем их подбора этих постоянных можно получить любое решение данного соотношения.

Пример:

Для соотношения   (5) общим решением будет  
(6)

В самом деле, легко проверить, что последовательность (6) обращает (5) в тождество. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде (6). Но любое решение соотношения (5) однозначно определяется значениями f(1) и f(2). Поэтому нам надо доказать, что для любых чисел a и b найдутся такие значения  и , что и

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

 

имеет решение. Поэтому (6) действительно является общим решением соотношения (5).

Частным решением рекуррентного соотношения является любая последовательность (), обращающая соотношение: (7) в тождество. Соотношение (7) имеет бесконечно много частных решений, таких как первые k элементов последовательности можно задать правильно.

Пример:

Последовательность явлется решением рекуррентного соотношения так как имеет место тождество

1.3. Виды рекуррентных соотношений

Для решения рекуррентных соотношений общих правил не существует. Однако существует весьма часто встречающийся класс соотношений, решаемый единообразным методом. Это-рекуррентные соотношения вид:

f(n+k)= 
где a1, a2, …, an – некоторые числа Такие соотношения называют однороднымилинейными рекуррентными соотношениями с постоянными коэффициентам n.

Неоднородное линейное рекуррентное соотношение имеет вид

f(n+k)=  (8)

где величина b(n) в общем случае является функцией от n. Общее решение соотношения (8) представляет собой сумму частного решения неоднородного уравнения (8) (то есть любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (8).

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

Для неоднородного линейного рекуррентного соотношения вида:

F(n+2)+pf(n+1)+qf(n)=n+(9)

где α, β, p, q – данные числа, справедливы следующие утверждения:

1) если х0 =1 не является корнем многочлена х2 +px+q, то частным решением рекуррентного соотношения (9) является последовательность f=an+b;

2) если х0 =1 является простым корнем многочлена х2 +px+q, частное решение рекуррентного соотношения (9) может быть найдено в виде f=n(аn+b);

3) если х0 =1 является кратным корнем многочлена х2 +px+q, частное решение рекуррентного соотношения (9) может быть найдено в виде f=n2 (аn+b).

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

1.1. Определение. Пусть () — некоторая числовая последовательность, и пусть

f(z) = …

есть формальный степенной ряд для этой последовательности, понимаемый как элемент кольцаC[[z]] . Производной ряда f(z) называется формальный степенной ряд вида

 

Иными словами, производной числовой последовательности () в кольце с операцией  умножения 
называется числовая последовательность:

 

1.2. Определение. Пусть

 

есть формальный степенной ряд для числовой последовательности (). Производнойэтого ряда называется формальный степенной ряд вида

 

Иными словами, “экспоненциальной” производной числовой последовательности () является сдвинутая на одну позицию влево числовая последовательность ().

1.3. Для операции  взятия производной в кольцах  C[[z]] и [[z]] формальных степенных рядов можно выводить свойства, аналогичные привычным нам свойствам производной из классического анализа. При этом вывод этих свойств зачастую оказывается даже более простым по сравнению с аналогичным выводом в курсе математического анализа.

 

 

 

2. Основные методы решения рекуррентных соотношений

 

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

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

PC вида

f (n + k) = d1f (n + k −1) + d2f (n + k − 2) +...+ dkf (n),          (2.1)

где d1, d 2, ..., dk – некоторые действительные (возможно, комплексные) числа, называются линейными однородными PC с постоянными коэффициентами.

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

Примерами возвратных последовательностей могут быть прогрессии:

1) геометрическая – a(0) = a, a(1) = aq, a(2) = aq2, ..., являющаяся решением PC f (n) = qf (n −1) при n ≥1 и f (0) = a;

2) арифметическая – a(0) = a, a(1) = a + d, a(2) = a + 2d, ..., являющаяся решением PCf (n)= 2f (n −1)− f (n − 2) при n ≥ 2 и f (0) = a, f (1) = a + d.

Теорема 2.1 (о сумме двух решений). Если a(n) и b(n) являются частными решениями PC (2.1), то для любых действительных чисел m и r последовательность m⋅ a(n) + r ⋅b(n) также есть решение PC (2.1).

Доказательство. Пусть последовательности a(n) и b(n) есть частные решения PC (4.7), т. е.

a(n + k) − d1a(n + k −1) − d2a(n + k − 2) −...− dka(n) = 0

иb(n + k) − d1b(n + k −1) − d2b(n + k − 2) −...− dkb(n) = 0.

Тогда, умножив эти равенства на числа m и r соответственно и сложив их, получаем

m× (a(n + k) – d1a(n + k – 1) – d2a(n + k – 2) – … – dka(n)) + r × (b(n + k) –

-d1b(n + k – 1) – d2b(n + k – 2) - dkb(n)) = m × 0 + r × 0 = 0

т. е. последовательность m⋅a(n) + r⋅b(n) также является решением PC (2.1). Доказательство завершено.

Для PC (2.1) составим алгебраическое уравнение

p(x) ºxk– d1xk-1 – d2xk-2 – … – dk-1x – dk = 0,                           (2.2)

которое называется его характеристическим уравнением.

Теорема 2.2 (о корне характеристического уравнения). Пусть r есть корень характеристического уравнения (2.2).

1. Тогда функция rn является решением PC (2.2).

2. Если же r есть корень  кратности d (d ≥ 2), то каждая из  функций nrn, n2rn, ... , nd −1rn также является решением PC (2.1).

Доказательство. Пусть выполняются условия этой теоремы. Сначала рассмотрим случай, когда r есть корень кратности 1 уравнения (2.2). Тогда выполняется равенство

rk– d1rk-1 – d2rk-2 – … – dk-1r – dk = 0,            

или

rk= d1rk-1 + d2rk-2 + … + dk-1r + dk.           

Умножая последнее равенство на rn, получим равенство

rk+n= d1rn+k-1 + d2rn+k-2 + … + dk-1rn+1 + dkrn,

что означает: функция rn есть решение PC (2.1).

Теперь пусть r есть корень уравнения (2.2) и его кратность равна d (d ≥ 2) и для простоты выкладок полагаем, что d = 2. В этом случае требуется доказать, что и функция nrn также есть решение PC (2.1).

Построим два выражения:

rk − d1rk-1 − d2rk-2 − … − dk-1r − dkrn − dk

и

krk-1 − d1(k-1)rk-2 − d2(k-2)rk-3 − … − dk-1,

первое из которых есть значение полинома p(x) в точке r, т. е. p(r), а второе – значение первой производной по x этого же полинома в точке r, т. е. p′(r). Так как r есть корень полинома p(x), то p(r) = 0 и p′(r) = 0, потому что r есть корень кратности 2. Теперь построим выражение nrn p(r) + rn−1p′(r), которое эквивалентно преобразуется в равенство

(n + k) rk+n = d1(n + k-1)rn+k-1 + … + dknrn.

Но это равенство означает, что nrn действительно есть решение PC (2.1). Доказательство завершено.

Из теоремы 2.2 следует, что решений линейного однородного PC с постоянными коэффициентами столько, сколько корней имеет его характеристическое уравнение с учетом их кратности, и это число равно его порядку. К тому же, все решения линейно независимы, так как имеют различные порядки роста в бесконечности, и таковыми должны быть согласно определению общего решения PC. А согласно теореме 2.1 каждое решение рассматриваемого PC должно быть выражено в виде линейных комбинаций частных решений вида по теореме 2.2. Следовательно, верно.

Следствие 2.1. Пусть линейное однородное PC с постоянными коэффициентами (2.1) такое, что его характеристическое уравнение имеет корни ri (1≤ i ≤ s) кратности di соответственно. Тогда общее решение a(n) такого линейного однородного PC с постоянными коэффициентами представляется в виде

 

Использование начальных значений f (0) = a0, f (1) = a1, ..., f (k −1) = ak−1 PC (2.1) приводит к системе из k линейных уравнений

 

из которой коэффициенты cij (1≤ i ≤ s, 1≤ j ≤ di) решения a(n) находятся однозначно.

Пример 2.1. Найти решение линейного однородного PC с постоянными коэффициентами f (n + 2) = 5 f (n +1) − 6 f (n), удовлетворяющее начальным значениям f (0) = 5, f (1) =12.

Характеристическое уравнение этого PC x2 − 5x + 6 = 0 имеет корни 2 и 3, кратность каждого из которых есть 1. Следовательно, общее решение данного PC есть c12n + c23n. Используя начальные значения, составляем систему уравнений

 

решение которой – c1 = 3, c2 = 2. Значит, требуемое решение есть последовательность 3⋅ 2n + 2⋅3n , n ≥ 0.

Пример 2.2. Найти решение линейного однородного PC

f (n + 3) = 9 f (n + 2) − 24 f (n +1) + 20 f (n),

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

Характеристическое уравнение этого PC x3 − 9x2 + 24x − 20 = 0 имеет корни 2 и 5, причем кратность первого равна 2, а второго – 1.

Тогда общее решение данного PC есть (c1 + c2n)2n + c35n.

Используя начальные значения, составляем систему уравнений

 

корни которой есть c1 = 2, c2 = 3, c3 = 4. Следовательно, требуемым решением является (2 + 3n)2n + 4⋅5n , n ≥ 0.

Пример 2.3. Найдем решение линейного однородного PC

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

удовлетворяющее начальным значениям f (0) = f (1) =1, которое задает последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, … .

Его характеристическое уравнение x2 − x −1= 0 имеет корни

.

Значит, общее решение этого PC есть c1r1n + c2r2n. Используя начальные значения, составляем систему уравнений

 

корни которой

.

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

 

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

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

PC вида

f (n + k) = d1f (n + k −1) +...+ dk f (n) + v(n),         (2.3)

где d1, ..., dk– некоторые числа, а v(n) – функция от n, не равная 0, называются линейными PC с постоянными коэффициентами. Примерами таких PC являются

g(n) = g(n −1) + g(n − 2) +1

и

f (n +1) = f (n) + n +1(2.4)

с заданными начальными значениями g(0) и g(1), f (0).

Теорема 2.3 (об общем решении линейного PC с постоянными коэффициентами). Общее решение рекуррентного соотношения(2.3) может быть представлено в виде суммы общего решения линейного однородного рекуррентного соотношения (2.1) и какого-либо решения рекуррентного соотношения (2.3).

Доказательство. Пусть b(c1, ...,ck,n) есть общее решение линейного однородного PC (2.1), a d(n) – одно из решений PC (2.3).

Докажем, что последовательность b(c1, ...,ck,n) + d(n) является общим решением PC (2.3). Имеем

(b(c1, ...,ck,n + k) + d(n + k)) −

         −d1(b(c1, ...,ck,n + k −1) + d(n + k −1)) −...−

−dk(b(c1, ..., ck,n) + d(n)) − v(n) =

= (b(c1, ..., ck,n + k) − d1b(c1, ..., ck,n + k −1) −...−

−dkb(c1, ...,ck,n)) + (d(n + k) − d1d(n + k −1) −

−...− dkd(n) − v(n)) = 0 + 0 = 0,

т. е. указанная последовательность действительно есть решение PC (2.3).

Осталось доказать, что если a(n) есть решение PC (2.3), то можно так подобрать параметры c1′, ..., ck′ , что при всех n будет выполняться равенство a(n) = b(c1′, ...,ck′ ,n) + d(n). Согласно тому, что a(n) и d(n) являются решениями PC (2.3), имеем

a(n + k) = d1a(n + k −1) +...+ dka(n) + v(n)

и

d(n + k) = d1d(n + k −1) +...+ dkd(n) + v(n),

откуда

a(n + k) − d(n + k) = d1(a(n + k −1) − d(n + k −1)) +...+ dk(a(n) − d(n)).

Следовательно, последовательность a(n) − d(n) есть решение линейного однородного PC (2.3). Значит, можно так подобрать параметры c1′, ...,ck′ , что при всех n будет выполняться равенство