WikiSort.ru - Не сортированное

Однородные линейные рекуррентные уравнения

Предположим, что последовательность чисел ${\displaystyle f_{0},f_{1},\dots }$ удовлетворяет однородному линейному рекуррентному уравнению ${\displaystyle f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+\ldots +a_{r}f_{n}=0}$ , где ${\displaystyle n}$  — неотрицательные целые числа, ${\displaystyle a_{1},\ldots ,a_{r}}$  — заданные постоянные числа и ${\displaystyle a_{r}\neq 0}$ .

Обозначим через ${\displaystyle F(z)}$ производящую функцию последовательности ${\displaystyle f_{0},f_{1},\dots }$ . Построим многочлен ${\displaystyle K(z)=1+a_{1}z+a_{2}z^{2}+\ldots +a_{r}z^{r}}$ . Этот многочлен можно рассматривать как производящую функцию последовательности ${\displaystyle 1,a_{1},a_{2},\ldots ,a_{r},0,0,\dots }$ . Рассмотрим произведение производящих функций ${\displaystyle C(z)=F(z)K(z)}$ . Коэффициент ${\displaystyle c_{n+r}}$ при ${\displaystyle z^{n+r}}$ и ${\displaystyle n\geq 0}$ определяется соотношением ${\displaystyle c_{n+r}=f_{0}0+\ldots +f_{n-1}0+f_{n}a_{r}+\ldots +f_{n+r}1=f_{n+r}+a_{1}f_{n+r-1}+\ldots +a_{r}f_{n}}$ и равен нулю. Это означает, что многочлен ${\displaystyle C(z)}$ имеет степень самое большее ${\displaystyle r-1}$ , следовательно степень числителя рациональной функции ${\displaystyle F(z)={\frac {C(z)}{K(z)}}}$ меньше степени знаменателя.

Характеристическим многочленом линейного рекуррентного уравнения называется многочлен ${\displaystyle g(z)=z^{r}+a_{1}z^{r-1}+\ldots +a_{r}}$ . Корни этого многочлена называются характеристическими. Характеристический многочлен можно представить в виде ${\displaystyle g(z)=(z-\alpha _{1})^{e_{1}}(z-\alpha _{2})^{e_{2}}\cdots (z-\alpha _{s})^{e_{s}}}$ , где ${\displaystyle \alpha _{1},\ldots ,\alpha _{s}}$  — различные характеристические корни, ${\displaystyle e_{1},\ldots ,e_{s}}$  — кратности характеристических корней, ${\displaystyle e_{1}+e_{2}+\ldots +e_{s}=r}$ .

Характеристический многочлен ${\displaystyle g(z)}$ и многочлен ${\displaystyle K(z)}$ связаны между собой соотношением ${\displaystyle K(z)=z^{r}g\left({\frac {1}{z}}\right)}$ . Таким образом,

${\displaystyle K(z)=(1-\alpha _{1}z)^{e_{1}}(1-\alpha _{2}z)^{e_{2}}\cdots (1-\alpha _{s}z)^{e_{s}}.}$

Рациональную функцию можно представить в виде суммы дробей:

${\displaystyle F(z)={\frac {C(z)}{K(z)}}=\sum _{i=1}^{s}\sum _{k=1}^{e_{i}}{\frac {\beta _{ik}}{(1-\alpha _{i}z)^{k}}}.}$

Каждая дробь в этом выражении имеет вид ${\displaystyle \beta (1-\alpha z)^{-k}}$ , поэтому её можно разложить в степенной ряд следующего вида

${\displaystyle \beta (1-\alpha z)^{-k}=\beta \left[1+(-k)(-\alpha z)+\ldots +{\frac {(-k)\cdots (-k-n+1)}{n!}}(-\alpha z)^{n}+\ldots \right]}$ .

Коэффициент при ${\displaystyle z^{n}}$ в этом ряде равен

${\displaystyle {\frac {\beta (n+k-1)\cdots k}{n!}}\alpha ^{n}=\beta {\binom {n+k-1}{n}}\alpha ^{n}=\beta {\binom {n+k-1}{k-1}}\alpha ^{n}.}$

Следовательно, производящая функция ${\displaystyle F(z)=\sum _{n=0}^{\infty }(\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^{n})z^{n}}$ и ${\displaystyle f_{n}=\sum _{i=1}^{s}p_{i}(n)\alpha _{i}^{n}}$ является общим решением линейного рекуррентного уравнения, где ${\displaystyle p_{i}(n)}$  — многочлен от ${\displaystyle n}$ степени самое большее ${\displaystyle e_{i}-1}$ .

Пример

Пусть требуется найти решение уравнения ${\displaystyle f_{n+2}-f_{n+1}+f_{n}=0}$ c граничными условиями ${\displaystyle f_{0}=1}$ и ${\displaystyle f_{1}=1}$ .

Данное уравнение имеет характеристический многочлен ${\displaystyle z^{2}-z+1=(z-\alpha _{1})(z-\alpha _{2})}$ , где ${\displaystyle \alpha _{1}={\frac {1}{2}}+i{\frac {\sqrt {3}}{2}}=e^{i{\frac {\pi }{3}}}}$ , ${\displaystyle \alpha _{2}={\frac {1}{2}}-i{\frac {\sqrt {3}}{2}}=e^{-i{\frac {\pi }{3}}}}$ . Общее решение имеет вид ${\displaystyle f_{n}=c_{1}\alpha _{1}^{n}+c_{2}\alpha _{2}^{n}=c_{1}e^{\frac {i\pi n}{3}}+c_{2}e^{\frac {-i\pi n}{3}}}$ . Подставляя ${\displaystyle n=0,1}$ , получаем ${\displaystyle c_{1}+c_{2}=1}$ , ${\displaystyle c_{1}\alpha _{1}+c_{2}\alpha _{2}=1}$ . Получаем значения ${\displaystyle c_{1}={\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}}}$ , ${\displaystyle c_{2}={\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}}}$ . Таким образом ${\displaystyle f_{n}=({\frac {1}{2}}-i{\frac {1}{2{\sqrt {3}}}})(\cos({\frac {\pi n}{3}})+i\sin({\frac {\pi n}{3}}))+({\frac {1}{2}}+i{\frac {1}{2{\sqrt {3}}}})(\cos({\frac {\pi n}{3}})-i\sin({\frac {\pi n}{3}}))=\cos({\frac {\pi n}{3}})+{\frac {1}{\sqrt {3}}}\sin({\frac {\pi n}{3}})}$ .