![]() КАТЕГОРИИ: Архитектура-(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=a0+nd является общим решением соотношения an=an-1+d. Это – формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a0. Пример 2¢. Последовательность bn=b0×qn является общим решением соотношения bn=bn-1×q. Это – формула общего члена геометрической прогрессии со знаменателем q¹0 и с начальным членом прогрессии b0. Пример 3¢. Так называемая формула Бине jn= 3. Линейные рекуррентные соотношения. Соотношение вида an+k+p1an+k-1+…+pkan=h(n) (2) где h(n) – функция от числа Линейное рекуррентное соотношение называют однородным, если f(n)=0: an+k+p1an+k-1+…+pkan=0. (3) Многочлен xk+p1xk-1+…+pk-1x+pk называется характеристическим для соотношения (2). Корень a многочлена Корень a многочлена При этом число Основная теорема алгебры: многочлен степени Теорема 1. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет n простых корней a1, …, an. Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
где c1,…,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) мы получим систему линейных уравнений относительно c1,…,ck:
Определитель системы (5) есть известный в алгебре определитель Вандермонда:
Так как простые корни x1,…,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 кратности
где Задача 3. Найти общее решение соотношения Решение. Характеристический многочлен Замечание. Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2). Поможем в написании учебной работы
Дата добавления: 2014-01-03; Просмотров: 1305; Нарушение авторских прав?; Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Читайте также:
|