Изменения

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

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

2307 байт добавлено, 19:22, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Рекуррентная формула''' (англ. ''Recurrence recurrence relation'') — формула вида <tex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </tex>, выражающая каждый следующий член последовательности <tex>a_n</tex> через <tex>p</tex> предыдущих членов и возможно номер члена последовательности <tex>n</tex>, вместе с заданными первыми p членами, где <tex>p</tex> — порядок рекуррентного соотношения.
}}
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекуррентного соотношения, задающего числа Фибоначчи:
Во многих задачах полезно знать<tex>F_0 = 0,\qquad F_1 = 1, есть ли у рекурсивной функции нерекурсивная или как еще говорят замкнутая форма (англ. ''Closed\qquad F_{n} = F_{n-1} + F_{n-form'')2}, то есть получение <tex>f(\quad n\geqslant 2, \quad n)\in Z</tex> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:
<tex> f a_n</tex> член может быть записан следующим образом: <tex>a_n= \begindfrac{cases1}{\sqrt{5} f}\left(0)=0; \biggl( \dfrac{1+\sqrt{5}}{2} \ f(nbiggr) = n + f(^n-1),\quad n biggl( \gt 0 dfrac{1-\endsqrt{5}}{cases2}\biggr)^n \right).</tex>
может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''Generating Function Methodgenerating function method'').
==Общая схемаМетод производящих функций==Пусть последовательность Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex>шагов.#Записать рекуррентное соотношение и начальные данные для него в следующем виде (a_0если порядок соотношения равен <tex>k</tex>):#:<tex>a_{0} = …, a_1\\ a_{1} = …, a_2\\ a_{k-1} = …, \\ … \\ a_{n} = ), n\geqslant k</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для #Домножить каждую строчку на <tex>a_nz</tex> в соответствующей степени (при <tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n\geq in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex>— это производящая функция, назовем ее <tex>G(z) </tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде .#Разложить <tex>G(если это возможноz)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.  ==Примеры=====<tex>1</tex> пример===[[Производящая_функция| Производящие функции]] позволяют делать эту работу почти решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
Задано линейное однородное рекуррентное соотношение порядка <tex>2</tex> с постоянными коэффициентами:
a_0&{}={}&0,\\
a_1&{}={}&1,\\
a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
<br><tex>\begin{array}{rcl}
1\cdot a_0&{}={}&0\cdot 1,\\
z\cdot a_1&{}={}&01\cdot 1z,\\z^n\cdot a_n&{}={}&(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
</tex><br>
Левая часть уравнения в точности равна <tex>G(z)</tex>, а в правой части есть суммы, очень похожие на функцию <tex>G(z)</tex>, но не равные ей. Эти суммы нужно любым законным способом привести к виду <tex>G(z)</tex>. Начнём с первой:
<br><tex>
\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\biggr( \underbrace{ z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)=z(G(z)-a_0)\stackrel{(4)}{=}zGz G(z).
</tex><br>
</tex><br>
откуда получаем производящую функцию последовательности в замкнутом виде :
<br><tex>
G(z) = \dfrac{z}{1-5z+6z^2}.
</tex><br>
Вспомним [[Производящая_функция#Приложения | разложение для простейшей рациональной функции]]:
<br><tex>
\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n,
</tex><br>
поэтому, в силу равенства рядов, <tex>a_n=3^n-2^n</tex> (для <tex>n\geq geqslant 0</tex>). ==Метод производящих функций==Алгоритм получения замкнутого выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.<ol><li>Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):<br><tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ a_{n} = …, n\geq k</tex></li> <li>Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n\geq0</tex>.</li><li>В полученном уравнении привести все суммы <tex>&sum;</tex> к замкнутому виду. Получить уравнение для производящей функции.</li><li>Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.</li></ol>
==Примеры======Числа <tex>2</tex> пример: числа Фибоначчи====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br><tex>\begin{array}{rcl}
f_0&{}={}&0,\\
f_1&{}={}&1,\\
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
1\cdot f_0&{}={}&0\cdot 1,\\
z\cdot f_1&{}={}&1\cdot z,\\
z^n\cdot f_n&{}={}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
<br><tex>\begin{array}{rcl}
G(z) &{}={}& z + z\displaystyle\sum_{n=2}^{\infty}f_{n-1}z^{n-1}+z^2\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^{n-2}, \\G(z) &{}={}& z + z\displaystyle\sum_{n=1}^{\infty}f_{n}z^n+z^2\displaystyle\sum_{n=0}^{\infty}f_{n}z^n, \\
G(z)&{}={}& \displaystyle z + z(G(z)-f_0)+z^2G(z),\\
G(z)&{}={}& \displaystyle z + zG(z)+z^2G(z),\\
</tex><br>
Данное выражение можно упростить, если обратить внимание на то, что <tex>1/z_1=-z_2</tex>, <tex>1/z_2=-z_1</tex> и <tex>z_1-z_2=√5</tex>. Подставим <tex>z_1</tex> и <tex>z_2</tex> в предыдущее выражение:
<br><tex>
f_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).
</tex><br>
===<tex>3</tex> пример=Произвольное ==Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$. По определению последовательности Фибоначчи выполняется:<br><tex>\left\{ \begin{array}{ll} f_{n+2} = f_{n+1} + f_n \\ f_{n-1} = f_{n+1} - f_n \end{array} \right.</tex><br>Возведя в квадрат и сложив, получим:<br><tex>\begin{array}{rcl}f_{n+2}^2 + f_{n-1}^2 = 2f_{n+1}^2 + 2f_n^2, \\f_{n+2}^2 = 2f_{n+1}^2 + 2f_n^2 - f_{n-1}^2, \\f_{n}^2 = 2f_{n-1}^2 + 2f_{n-2}^2 - f_{n-3}^2.\\\end{array}</tex><br>Обозначим рассматриваемую последовательность <tex>A</tex>, а её члены <tex>a_n</tex>, тогда:<br><tex>a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}</tex><br> Рекуррентное соотношение:<br><tex>\begin{array}{ll}a_0 = f_0^2 = 1 \\a_1 = f_1^2 = 1 \\a_2 = f_2^2 = 4 \\a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}, \quad n\geqslant3.\\\end{array}</tex><br> Приведём суммы к замкнутому виду:<br><tex>\begin{array}{ll}A(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_{n=3}^{\infty}(2a_{n-1} + 2a_{n-2} - a_{n-3})z^n, \\A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_{n=3}^{\infty}a_{n-1}z^n + 2\displaystyle\sum_{n=3}^{\infty}a_{n-2}z^n - \displaystyle\sum_{n=3}^{\infty}a_{n-3}z^n, \\A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\displaystyle\sum_{n=1}^{\infty}a_nz^n - z^3\displaystyle\sum_{n=0}^{\infty}a_nz^n, \\A(z) = 1 + z + 4z^2 + 2z(A(z) - 1 - z) + 2z^2(A(z) - 1) - z^3A(z), \\A(z) = 1 + z + 4z^2 + 2zA(z) - 2z - 2z^2 + 2z^2A(z) - 2z^2 - z^3A(z), \\A(z)(1 - 2z - 2z^2 + z^3) = 1 + z + 4z^2 - 2z - 2z^2 - 2z^2 = 1 - z, \\\end{array}</tex><br>откуда получаем замкнутое выражение для производящей функции:<br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex><br> ===<tex>4</tex> пример===
Рассмотрим следующее рекуррентное соотношение:
<br><tex>\begin{array}{rcl}
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_8a_{n-2}+n, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
\dfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
</tex><br>
 
==См. также==
1632
правки

Навигация