Рекуррентное уравнение

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

Рекуррентное уравнение - уравнение, связывающее несколько подряд идущих членов некоторой числовой последовательности.

Линейное рекуррентное уравнение[править | править вики-текст]

Линейное рекуррентное уравнение с постоянными коэффициентами имеет вид:

f_{n+r}+a_{1}f_{n+r-1}+a_{2}f_{n+r-2}+...+a_{r}f_{n}=\varphi(n).

Здесь n - неотрицательные целые числа, f_{n} - последовательность чисел, a_{1}, a_{2}, ... , a_{r} - постоянные числа, a_{r} \ne 0, \varphi(n) - заданная функция от n.

Производящая функция[править | править вики-текст]

Производящей функцией называется степенной ряд F(z)=f_{0}+f_{1}z+f_{2}z^{2}+..., коэффициентами которого являются члены числовой последовательности f_{0}, f_{1}, f_{2}, ... .

Последовательность чисел однозначно определяет производящую функцию. Производящая функция однозначно определяет последовательность чисел лишь в случае, когда степенной ряд сходится в круге радиуса R>0.

Последовательности \mathcal{f} cf_{n}+dg_{n} \mathcal{g} соответствует производящая функция cF(z)+dG(z).

В случае произведения производящих функций H(z)=F(z)G(z)=h_{0}+h_{1}z+h_{2}z^{2}+... члены числовой последовательности \mathcal{f} h_{n} \mathcal{g} могут быть получены из членов числовых последовательностей \mathcal{f} f_{n} \mathcal{g} и \mathcal{f} g_{n} \mathcal{g} с помощью уравнения h_{n}=f_{0}g_{n}+f_{1}g_{n-1}+...+f_{n-1}g_{1}+f_{n}g_{0}.

Решение однородного линейного рекуррентного уравнения[править | править вики-текст]

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

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

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

Характеристический многочлен g(z) и многочлен K(z) связаны между собой соотношением K(z)=z^{r}g(\frac{1}{z}). Таким образом K(z)=(1-\alpha_{1}z)^{e_{1}}(1-\alpha_{2}z)^{e_{2}}...(1-\alpha_{s}z)^{e_{s}}. Рациональную функцию можно представить в виде суммы дробей F(z)=\frac{C(z)}{K(z)}=\sum_{i=1}^{s}\sum_{k=1}^{e_{i}}\frac{\beta_{ik}}{(1-\alpha_{i}z)^{k}}.

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

Коэффициент при z^n в этом ряде равен \frac{\beta(n+k-1)...k}{n!}\alpha^{n}=\beta\binom{n+k-1}{n}\alpha^{n}=\beta\binom{n+k-1}{k-1}\alpha^{n}.

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

Пример[править | править вики-текст]

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

Данное уравнение имеет характеристический многочлен z^{2}-z+1=(z-\alpha_{1})z-\alpha_{2}), где \alpha_{1}=\frac{1}{2}+i\frac{\sqrt{3}}{2}=e^{i \frac{\pi}{3}}, \alpha_{2}=\frac{1}{2}-i\frac{\sqrt{3}}{2}=e^{-i \frac{\pi}{3}}. Общее решение имеет вид 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}}. Подставляя n=0, 1, получаем c_{1}+c_{2}=1, c_{1}\alpha_{1}+c_{2}\alpha_{2}=1. Получаем значения c_{1}=\frac{1}{2}-i\frac{1}{2\sqrt{3}}, c_{2}=\frac{1}{2}+i\frac{1}{2\sqrt{3}}. Таким образом 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}).

Литература[править | править вики-текст]

  • Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М.: Радио и связь, 1984. — 240 с.