Решение рекуррентных соотношений — различия между версиями
Ilya b (обсуждение | вклад) (Добавлен пример) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 4 участников) | |||
Строка 44: | Строка 44: | ||
1\cdot a_0&{}={}&0\cdot 1,\\ | 1\cdot a_0&{}={}&0\cdot 1,\\ | ||
z\cdot a_1&{}={}&1\cdot z,\\ | z\cdot a_1&{}={}&1\cdot z,\\ | ||
− | z^n\cdot a_n&{}={}&5a_{n-1}-6a_{n-2}\cdot z^n, \quad n\geqslant2.\\ | + | z^n\cdot a_n&{}={}&(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geqslant2.\\ |
\end{array} | \end{array} | ||
</tex><br> | </tex><br> | ||
Строка 57: | Строка 57: | ||
\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^n \stackrel{(1)}{=}z\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^{n-1} \stackrel{(2)}{=} | \displaystyle\sum_{n=2}^{\infty}a_{n-1}z^n \stackrel{(1)}{=}z\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^{n-1} \stackrel{(2)}{=} | ||
z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n \stackrel{(3)}{=} | z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n \stackrel{(3)}{=} | ||
− | z\biggr( \underbrace{ \displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)\stackrel{(4)}{=} | + | z\biggr( \underbrace{ \displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)=z(G(z)-a_0) \stackrel{(4)}{=} z G(z). |
</tex><br> | </tex><br> | ||
Строка 224: | Строка 224: | ||
</tex><br> | </tex><br> | ||
+ | Приведём суммы к замкнутому виду: | ||
<br><tex> | <br><tex> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
Строка 235: | Строка 236: | ||
</tex><br> | </tex><br> | ||
откуда получаем замкнутое выражение для производящей функции: | откуда получаем замкнутое выражение для производящей функции: | ||
− | <br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 | + | <br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex><br> |
===<tex>4</tex> пример=== | ===<tex>4</tex> пример=== |
Текущая версия на 19:22, 4 сентября 2022
Определения
Определение: |
Рекуррентная формула (англ. recurrence relation) — формула вида | , выражающая каждый следующий член последовательности через предыдущих членов и номер члена последовательности , вместе с заданными первыми p членами, где — порядок рекуррентного соотношения.
Для рекуррентного соотношения, которому удовлетворяет последовательность
мы часто хотим получить выражение для . Например, для рекуррентного соотношения, задающего числа Фибоначчи:
член может быть записан следующим образом:
Для этого можно использовать метод производящих функций (англ. generating function method).
Метод производящих функций
Алгоритм получения выражения для чисел
, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из шагов.- Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен
- Домножить каждую строчку на в соответствующей степени ( ) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где . В левой части получится сумма — это производящая функция, назовем ее . Правую часть преобразовать так, чтобы она превратилась в выражение, включающее .
- Решить полученное уравнение, получив для выражение в замкнутом виде.
- Разложить в степенной ряд, коэффициент при будет искомым выражением для .
Примеры
пример
Производящие функции позволяют решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
Задано линейное однородное рекуррентное соотношение порядка
Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером
. В данном случае порядок равен , так как для вычисления требуется знать и .Будем искать производящую функцию последовательности в виде
с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на
Теперь сложим все уравнения для всех значений
Левая часть уравнения в точности равна
Равенство
получатся вынесением в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной и индекс переменной a внутри суммы. Действие — изменение индекса суммирования, которое позволяет избавиться от . Равенство получается, если прибавить и снова отнять значение , чтобы получить полную сумму от до . Равенство справедливо в силу того, что .Аналогичные манипуляции со второй суммой дают нам выражение
Теперь наше исходное уравнение для производящей функции принимает вид:
откуда получаем производящую функцию последовательности в замкнутом виде:
Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения
Теперь разобьём дробь на сумму простых дробей:
Вспомним разложение для простейшей рациональной функции:
Из этого разложения следует, что
Таким образом,
С другой стороны, мы искали
поэтому, в силу равенства рядов, (для ).
пример: числа Фибоначчи
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
Складываем все строчки:
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
откуда получаем замкнутое выражение для производящей функции:
Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
Таким образом,
Нам известно разложение следующей рациональной функции:
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на
Аналогично (но с делением на
Таким образом,
и, следовательно,
Данное выражение можно упростить, если обратить внимание на то, что
пример
Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$.
По определению последовательности Фибоначчи выполняется:
Возведя в квадрат и сложив, получим:
Обозначим рассматриваемую последовательность , а её члены , тогда:
Рекуррентное соотношение:
Приведём суммы к замкнутому виду:
откуда получаем замкнутое выражение для производящей функции:
пример
Рассмотрим следующее рекуррентное соотношение:
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
Вспомним, что
поэтому
Последняя сумма может быть свёрнута:
Подставив свёрнутое выражение обратно, имеем,
Таким образом, наше последнее уравнение примет вид
Это уравнение для производящей функции. Из него выражаем
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
Теперь соберём ответ:
Значит,