Мегаобучалка Главная | О нас | Обратная связь


Решение рекуррентных соотношений



2015-12-07 7979 Обсуждений (0)
Решение рекуррентных соотношений 0.00 из 5.00 0 оценок




Рекуррентное соотношение имеет порядок k, если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1).

Пример.

f(n+2)=f(n)f(n+1)-3f2(n+1)+1 – рекуррентное соотношение второго порядка.

f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.

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

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

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

Пример. Последовательность 2, 4, 8, …, 2n является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство. Общий член последовательности имеет вид f(n)=2n. Значит, f(n+2)= 2n+2, f(n+1)= 2n+1. При любом n имеет место тождество 2n+2=3∙2n+1 – 2∙2n. Следовательно, при подстановке последовательности 2n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2n является решением указанного соотношения.

 

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

Пример. Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2n+ β3n .

1. Сначала докажем, что последовательность f(n)=α 2n+ β3n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.

f(n)= α 2n+ β 3n, значит, f(n+1)= (α 2n+1+ β 3n+1), f(n+2)= α 2n+2+ β 3n+2, тогда

5f(n+1)-6f(n)=5∙( α 2n+1+ β 3n+1)-6∙( α 2n+ β 3n)= α (5 2n+1 –6 2n)+ β (5 3n+1 –6 3n)= =α2n∙(10–6)+ β 3n∙(15 – 6)= α 2n+2+ β 3n+2= f(n+2).

Рекуррентное соотношение выполняется, следовательно, α 2n+ β 3n является решением данного рекуррентного соотношения.

2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2n+ β 3n. Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.

Таким образом, f(n)= α 2n+ β 3n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).

 

Линейные рекуррентные соотношения с постоянными коэффициентами

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

f(n+k)=c1f(n+k-1)+c2f(n+k-2)+…+ckf(n).

Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c2∙a, аналогично f(4)=c3∙a и так далее, заметим, что f(n)=cn-1∙f(1).

Докажем, что последовательность cn-1∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=cn-1∙f(1), значит, f(n+1)=cn f(1). Подставляя это выражение в соотношение, получим тождество cn f(1)=с∙ cn-1∙f(1).

Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка, то есть соотношения вида

f(n+2)=C1∙f(n+1)+C2∙f(n). (*).

Заметим, что все рассуждения сохраняются и для соотношений более высокого порядка.

Свойства решений:

1) Если последовательность xn является решением (*), то и последовательность a∙xn тоже является решением.

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

xn является решением (*), следовательно, выполняется тождество xn+2=C1xn+1+C2xn. Домножим обе части равенства на a. Получим a∙xn+2 =a∙(С1∙xn+12∙xn )= С1∙a∙xn+12∙a∙xn . Это означает, что axn является решением (*).

2) Если последовательности xn и yn являются решениями (*), то и последовательность xn+yn тоже является решением.

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

xn и yn являются решениями, следовательно, выполняются следующие тождества:

xn+2=C1xn+1+C2xn.

yn+2=C1yn+1+C2yn.

 

Выполним почленное сложение двух равенств:

xn+2+yn+21∙xn+12∙xn + С1∙yn+12∙yn= С1∙(xn+1+ yn+1)+С2∙(xn +yn). Это означает, что xn+yn является решением (*).

3) Если r1 является решением квадратного уравнения r21r+С2, то последовательность (r1)n является решением для соотношения (*).

r1 является решением квадратного уравнения r21r+С2, значит, (r1)2=C1 r1+C2. Помножим обе части равенства на (r1) n. Получим

r1 2 r1 n=(С1 r12) rn.

r1 n+21 r1 n+12 r1 n.

Это означает, что последовательность (r1)n является решением (*).

 

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

1. Составим характеристическое (квадратное) уравнение r21 r+С2. Найдём его корни r1, r2. Если корни различны, то общее решение имеет вид f(n)= ar1n+βr2n.

2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений

имеет решение при любых а и b. Этими решениями являются

Задача. Найдем формулу для общего члена последовательности Фибоначчи.

Решение. Характеристическое уравнение имеет вид х2=х+1 или х2-х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= . Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:

.

Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.

 



2015-12-07 7979 Обсуждений (0)
Решение рекуррентных соотношений 0.00 из 5.00 0 оценок









Обсуждение в статье: Решение рекуррентных соотношений

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...
Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (7979)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)