Изменения

Перейти к: навигация, поиск

Производящая функция

545 байт добавлено, 03:54, 12 декабря 2011
Нет описания правки
== Решение рекуррентных соотношений ==
Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \ge 0</tex>) в замкнутом виде (то есть выразив лишь !!!!!!!!!!!! через номер члена последовательности).Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:  1)Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n, равно k):  <tex>a_0=...,</tex>  <tex>a_1=...,</tex>  <tex>a_{k-1}=...,</tex>  <tex>a_{n}=..., n \ge k.</tex>  2)Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n <tex> \ge 0 </tex>.  3)В полученном уравнении привести все суммы <tex>\sum</tex> к замкнутому виду. Получить уравнение для производящей функции.  4)Выразить <tex>G(z)<\tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z<\tex>. 
Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:
<tex>G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>
Теперь формализуем алгоритм, который мы использовали:
 
1)Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k):
2)Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n≥0.
3)В полученном уравнении привести все суммы ∑ к замкнутому виду. Получить уравнение для производящей функции.
4)Выразить G(z) в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням z.
== Ссылки ==
Анонимный участник

Навигация