О разложении рациональной функции в ряд

Рациональная функция — это функция вида

\begin{displaymath} G(z) = \frac{P(z)}{Q(z)}, \end{displaymath}

где P и Q — полиномы. Например,

\begin{displaymath} G(z)=\frac{8+4z}{1-z-z^2+z^3}. \end{displaymath}

При работе с производящими функциями, полином лучше выписывать, начиная от младших степеней z. Замечено, что ученики часто ошибаются в дальнейших вычислениях, если поступают наоборот. Врочем, это не важно, если Вы отдаёте себе отчет в том, что делаете и уверены, что не запутаетесь.

Рациональные производящие функции получаются при решении линейных рекуррентных соотношений. По этой причине актуальной является задача о разложении рациональной функции в ряд по степеням переменной z.

Чтобы разложить дробь в ряд, необходимо разбить её (если это возможно) на сумму «более простых» дробей: таких дробей, разложение которых мы можем посмотреть в таблице или вывести из каких-то элементарных соображений. Такая процедура назвается разбиением на элементарные дроби.

Вернёмся к нашему примеру. Дробь G(z) можно разбить на сумму дробей (пока без пояснений):

\begin{displaymath} G(z)=\frac{8+4z}{1-z-z^2+z^3} = \frac{1}{1+z} + \frac{7}{(1-z)^2} - \frac{z}{(1-z)^2}. \end{displaymath}

Эти дроби, в свою очередь, лекго разложить в ряд, пользуясь таблицей производящих функций и формулами преобразования:

\begin{displaymath}\begin{array}{rcl} \displaystyle\frac{1}{1+z} &\displaystyl... ...{}& \displaystyle \sum_{n=0}^{\infty} nz^n \\ \end{array} \end{displaymath}

То есть

\begin{displaymath} G(z)=\frac{8+4z}{1-z-z^2+z^3} = \sum_{n=0}^{\infty}\left(7... ...n\right)z^n= \sum_{n=0}^{\infty}\left(6n+7+(-1)^n\right)z^n. \end{displaymath}

Или, что то же самое,

\begin{displaymath}[z^n]G(z) = 6n+7+(-1)^n, \quad n \geq 0. \end{displaymath}

Теперь ответим на самые главные вопросы: когда возможно разложить дробь на более простые дроби и как это сделать?

Общие размышления

Давайте начнём размышлять теоретически и заведём себя этими размышлениями в тупик. Это сделать необходимо, чтобы стала понятной вся глубина рассматриваемой проблемы.

Во-первых, для определённости будем считать, что deg P(z) < deg Q(z), а иначе мы могли бы записать

\begin{displaymath} G(z) = \frac{P(z)}{Q(z)}=R(z) + \frac{P_0(z)}{Q(z)}, \end{displaymath}

где deg P0(z) < deg Q(z), и далее работать с только что полученной дробью.

Во-вторых, отметим, что разбивать дробь вида

\begin{displaymath} G(z) = \frac{\alpha z^m}{(1-rz)^{k}},\quad r \in \mathbb c, m, k\geq 1.\ \end{displaymath}

на сумму дробей с более простым знаменателем нет необходимости (да и не получится), так как она сама по себе легко раскладывается в ряд путем несложных преобразований. (см. «Таблица производящих функций» и «Преобразование производящих функций»):

\begin{displaymath} \frac{\alpha z^m}{(1-rz)^{k}} = \alpha \sum_{n=0}^{\infty} (-1)^nr^n\binom{n+k-1}{n} z^{n+m}, \end{displaymath}

а дальнейшие преобразования ряда зависят уже от исходной задачи.

Если знаменатель Q(z) имеет более сложную структуру, мы должны каким-то образом разбить его на множители. Конечно, мы можем это сделать, например, так:

\begin{displaymath} G(z) = \frac{P(z)}{(z_1-z)^{k_1}(z_2-z)^{k_2}\cdots(z_s-z)^{k_s}}, \end{displaymath}

вспомнив, что полином Q(z) имеет deg Q(z) корней (пусть даже и комплексных). Эти корни у нас обозначены z1, z2, ..., zs. При этом, k1+k2+⋅⋅⋅+ks=deg Q. После разбиения знаменателя на множители, получаем

\begin{displaymath} G(z) = \frac{P(z)}{(z_1-z)^{k_1}(z_2-z)^{k_2}\cdots(z_s-z)^{k_s}}=\sum_{j=1}^{s}\frac{P_j(z)}{(z_j-z)^{k_j}}, \end{displaymath}

где Pj(z) — полином, причем deg Pj(z)<kj. Каждая из дробей под знаком суммы раскладывается в ряд без особых усилий — с помощью той же таблицы производящих функций:

\begin{displaymath} \frac{P_j(z)}{(z_j-z)^{k_j}} = \frac{ 1/z_j^{k_j} \cdot P_j(z)}{(1-z/z_j)^{k_j}} = \mbox { \ldots}. \end{displaymath}

и далее как было показано выше.

Осталось ответить на главный вопрос: как получить полиномы Pj(z)?

Правило разложения
на элементарные дроби

Вернёмся к примеру, с которого начали:

\begin{displaymath} G(z)=\frac{8+4z}{1-z-z^2+z^3}=\frac{8+4z}{(1+z)(1-z)^2}. \end{displaymath}

Что дальше? Дальше мы знаем, что дробь должна разложиться на сумму двух дробей, причем у первой в числителе будет полином степени 0, а у второй — 1. Это означает, что разложение будет иметь вид

\begin{displaymath} G(z)=\frac{8+4z}{1-z-z^2+z^3}=\frac{A}{(1+z)}+\frac{Bz+C}{(1-z)^2}, \end{displaymath}

где A, B и C — некоторые константы. Для того, чтобы найти эти константы, нужно снова сложить дроби:

\begin{displaymath}\displaylines{ \ig{0.2}\frac{A}{(1+z)}+\frac{Bz+C}{(1-z)^2}... ...(A+C)}{(1+z)(1-z)^2}=\frac{8+4z}{(1+z)(1-z)^2}. \ig{0.2} } \end{displaymath}

Из последнего равенства, если сравнить коэффициенты при соответствующих степенях в числителе, становится очевидным, что

\begin{displaymath} \begin{array}{ccc} A+B &{}={}& 0 \mbox{ --- это коэффици... ...{}& 8 \mbox{ --- это коэффициент при } z^0 \\ \end{array} \end{displaymath}

Решаем систему из трёх уравнений с тремя неизвестными: A=1, B=−1, C=7.

\begin{displaymath} \frac{A}{(1+z)}+\frac{Bz+C}{(1-z)^2} = \frac{1}{1+z} + \frac{-z+7}{(1-z)^2}. \end{displaymath}

Приведённый метод разложения называется Метод неопределённых коэффициентов.

Общий алгоритм:

  1. Привести дробь P(z)/Q(z) к такому виду, чтобы степень числителя была меньше степени знаменателя.
  2. Отыскать корни уравнения Q(z)=0 и разбить знаменатель на множители вида (zs−z)ks (здесь zs — корень кратности ks).
  3. Записать сумму дробей, знаменатили которых будут иметь вид (zs−z)ks, а числители — полиномы с неопределёнными коэффициентами, имеющие степень ks−1.
  4. Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням z.
  5. Прировнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома P(z), составив, таким образом, систему линейных уравнений.
  6. Решить систему и получить значения неопределённых коэффициентов.

Пример посложнее

Рассмотрим пример посложнее. Требуется разложить в ряд рациональную функцию

\begin{displaymath} G(z)=\frac{8-46z+89z^2-59z^3}{1-8z+23z^2-28z^3+12z^4}. \end{displaymath}

Разбив знаменатель на множители, получаем:

\begin{displaymath} \frac{8-46z+89z^2-59z^3}{(1-z)(1-2z)^2(1-3z)} = \frac{A}{1-z} + \frac{Bz+C}{(1-2z)^2} + \frac{D}{1-3z} \end{displaymath}

Теперь нужно снова «собрать» выражение, приведя все дроби к общему знаменателю:

\begin{displaymath} \frac{(-12A+3B-4D)z^3+(16A-4B+3C+8D)z^2+(-7A+B-4C-5D)z+A+C+D}{(1-z)(1-2z)^2(1-3z)} \end{displaymath}

Откуда легко получается система линейных уравнений:

\begin{displaymath} \begin{array}{rcl} -12A+3B-4D &{}={}& -59 \\ 16A-4B+3... ...+B-4C-5D &{}={}& -46 \\ A+C+D &{}={}& 8 \\ \end{array} \end{displaymath}

Решение этой системы [ проверьте ]: A=4, B=3, C=−1, D=5. Это означает, что

\begin{displaymath} G(z)= \frac{4}{1-z} + \frac{3z}{(1-2z)^2} -\frac{1}{(1-2z)^2} + \frac{5}{1-3z}. \end{displaymath}

Теперь каждую дробь можно разложить в ряд, пользуясь таблицей:

\begin{displaymath} G(z) = 4\sum_{n=0}^{\infty}z^n + 3\sum_{n=0}^{\infty}n2^{n... ... \sum_{n=0}^{\infty}(n+1)2^nz^n+5\sum_{n=0}^{\infty}3^nz^n. \end{displaymath}

То есть

\begin{displaymath}[z^n]G(z) = 5\cdot3^n + 3n2^{n-1} - (n+1)2^n+4= 5\cdot3^n+n2^{n-1}-2^n+4. \end{displaymath}

и

\begin{displaymath} G(z) = 8+18z+49z^2+143z^3+425z^4+1267z^5+3777z^6+11259z^7+O(z^{8}). \end{displaymath}

Пример ещё посложнее

Этот пример будет продемонстрирован без слов, так как поиск решения аналогичен предыдущему случаю:

\begin{displaymath} G(z) = \frac{16z^3-192z^2+769z-1029}{-4z^4+68z^3-432z^2+1216z-1280}. \end{displaymath}
\begin{displaymath} G(z) = \frac{-16z^3+192z^2-769z+1029}{4(5-z)(4-z)^3}=\frac{A}{4(5-z)}+\frac{Bz^2+Cz+D}{4(4-z)^3} \end{displaymath}
\begin{displaymath} \frac{()z^3+(12A+5/8B-1/8C)z^2+(-48A+5/8C-1/8D)z+64A+5/8D)}{4(5-z)(4-z)^3} \end{displaymath}
\begin{displaymath} \begin{array}{rcl} -A-B &{}={}& -16 \\ 12A+5B-C &{}={... ...C-D &{}={}& -769 \\ 64A+5D &{}={}& 1029 \\ \end{array} \end{displaymath}

A=16, B=0, C=0, D=1.

\begin{displaymath} G(z) = \frac{4}{5-z}+\frac{1}{4(4-z)^3}. \end{displaymath}
\begin{displaymath} \frac{4}{5-z} = \frac{4/5}{1-z/5}=\frac{4}{5}\sum_{n=0}^{\infty} \frac{z^{n}}{5^n} \end{displaymath}
\begin{displaymath} \frac{1}{4(4-z)^3} = \frac{1/256}{(1-z/4)^3}=\frac{1}{256}\sum_{n=0}^{\infty} \frac{(n+2)(n+1)}{2} \frac{z^n}{4^n}. \end{displaymath}
\begin{displaymath}[z^n]g(z) = \frac{4}{5^{n+1}} + \frac{(n+1)(n+2)}{2^{2n+9}}. \end{displaymath}
\begin{displaymath} G(z) = \frac{1029}{1280}+\frac{4171}{25600}z+\frac{8567}{256000}z^2+O(z^3). \end{displaymath}

Тупик

Красота голой теории заключается в том, что всё кажется простым и понятным. Теперь рассмотрим другой пример, против которого описанная только что теория совершенно бессильна.

\begin{displaymath} \frac{z(1-z)(z^{11}-z^{10}+3z^9+12z^8-3z^7-3z^4+21z^3-3z^2... ...^{10}-8z^9+118z^8-66z^7-35z^6+90z^5+12z^4-63z^3+14z^2+5z-1}. \end{displaymath}

Такая функция появилась в одном из моих исследований, и работать с ней дальше обычными методами невозможно. Эта производящая функция генирирует последовательность (an), где an — количество гамильтоновых циклов на прямоугольной решётке размером 6×n. Эту последовательность Вы можете отыскать в энциклопедии целочисленных последовательностей под номером A145401.

Проблема в том, что знаменатель этой функции не имеет рациональных корней. Поэтому разбить функцию на более простые не получится. Вообще говоря, 14-я степень полинома не мешает исследовать функцию дальше другими способами (выходящими за рамки данного раздела), однако, например, есть производящая функция для аналогичной задачи для решётки 10×n, степень знаменателя в ней равна 346. На сегодняшний день открытым остаётся вопрос: а что с ней делать?

Таким образом, теория говорит, что всякую рациональную функцию можно разложить в ряд, нужно только отыскать корни знаменателя, но практика показывает, что не всё так просто. Более того, в задачах, не являющихся упражнениями из учебника, этого сделать почти никогда нельзя. Даже в наших примерах числа были специально подобраны так, чтобы вычисления можно было проводить в уме, а в реальности такие задачи почти никогда не встречаются.

↑ наверх ↑
вернуться к содержанию