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

Материал из Викиконспекты
Перейти к: навигация, поиск

Определения

Определение:
Рекуррентная формула — формула вида [math]a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) [/math], выражающая каждый член последовательности [math]a_n[/math] через [math]p[/math] предыдущих членов и возможно номер члена последовательности [math]n[/math].


Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма, т.е. получение [math]f(n)[/math] в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

[math] f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n \gt 0 \end{cases}[/math]

может быть переведена в замкнутую форму: [math]f = \frac{n(n+1)}{2}[/math]. Для этого можно использовать метод производящих функций.

Метод производящих функций

Алгоритм получения замкнутого выражения для чисел [math]a_{n}[/math], удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из 4 шагов.

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен [math]k[/math]): [math]a_{0} = ...,\lt br\gt a_{1} = ...,\lt br\gt a_{k-1} = ...,\lt br\gt a_{n} = ..., n≥k[/math]
  2. Домножить каждую строчку на [math]z[/math] в соответствующей степени и просуммировать строчки для всех [math]n≥0[/math].
  3. В полученном уравнениипривести все суммы [math]∑[/math] к замкнутому виду. Получить уравнение для производящей функции.
  4. Выразить [math]G(z)[/math] в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням [math]z[/math].

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

по построению

Примеры

ЧИСЛА ФИБОНАЧЧИ

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
Img39.png
Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:
Img40.png
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
Img45.png
Складываем все строчки:
Img46.png
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
Img47.png
откуда получаем замкнутое выражение для производящей функции:
Img48.png
Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
Img49.png
Таким образом,
Img50.png
Нам известно разложение только следующей рациональной функции:
Img31.png
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на [math]z1[/math]:
Img52.png
Аналогично (но с делением на [math]z2[/math]) поступим со второй дробью:
Img53.png
Таким образом,
Img54.png
и, следовательно,
Img55.png
Данное выражение можно упростить, если обратить внимание на то, что [math]1/z1=-z2[/math], [math]1/z2=-z1[/math] и [math]z1-z2=√5[/math]:
Img59.png

БОЛЕЕ СЛОЖНОЕ СООТНОШЕНИЕ