Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Общие и частные решения рекуррентных соотношений




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

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

Пример 1¢. Последовательность an = a 0+ nd является общим решением соотношения an = an -1+ d. Это – формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a 0.

Пример 2¢. Последовательность bn = b 0× qn является общим решением соотношения bn = bn -1 ×q. Это – формула общего члена геометрической прогрессии со знаменателем q ¹0 и с начальным членом прогрессии b 0.

Пример 3¢. Так называемая формула Бине j n =является частным решением соотношения j n =j n -2+j n -1 при j0=j1=1.

3. Линейные рекуррентные соотношения. Соотношение вида

an + k + p 1 an + k -1+…+ pkan = h (n) (2)

где h (n) – функция от числа , а , называется линейным рекуррентным соотношением.

Линейное рекуррентное соотношение называют однородным, если f (n)=0:

an + k + p 1 an + k -1+…+ pkan =0. (3)

Многочлен xk + p 1 xk -1+…+ pk -1 x + pk называется характеристическим для соотношения (2).

Корень a многочлена называется простым, если делится на , но не делится на .

Корень a многочлена называется кратным, если делится на , но не делится на , .

При этом число называется кратностью корня .

Основная теорема алгебры: многочлен степени с комплексными коэффициентами имеет комплексных корней с учетом их кратности.

Теорема 1. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет n простых корней a1, …, a n. Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

, (4)

где c 1,…, ck Î C.

Доказательство. Легко проверить следующие два утверждения.

(a) Последовательность cxn, где c Î C, является решением рекуррентного соотношения (3).

(b) Если последовательности an и bn являются решениями соотношения (3), то последовательность an + bn также является решением соотношения (3).

Из (a) и (b) следует, что любая последовательность вида (4) является решением соотношения (3).

Обратно, любое решение соотношения (3) имеет вид (4).

При n =0,1,…, k -1, из равенства (4) мы получим систему линейных уравнений относительно c 1,…, ck:

(5)

Определитель системы (5) есть известный в алгебре определитель Вандермонда:

.

Так как простые корни x 1,…, xk попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение.

Задача 1. Найти общий член геометрической прогрессии по формуле (4).

Решение. Характеристический многочлен рекуррентного соотношения bn = qbn -1 имеет вид . Поэтому .

Задача 2. Найти общее решение соотношения Фибоначчи an +2= an + an +1.

Решение. Характеристический многочлен рекуррентного соотношения an +2= an + an +1 имеет вид . Поэтому .

Приведем без доказательства следующее обобщение теоремы 1.

Теорема 2. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a1 кратности , …, a k кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

, (6)

где .

Задача 3. Найти общее решение соотношения .

Решение. Характеристический многочлен имеет корень 2 кратности 3. Поэтому .

Замечание. Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).




Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 1560; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.007 сек.