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

Определения

Определение:

Рациональная функция — это функция вида: [math]G(z)=\dfrac{P(z)}{Q(z)}[/math], где [math]P[/math] и [math]Q[/math] - полиномы.

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

Определение:

Элементарными дробями будем называть дроби вида: [math]\dfrac{A}{(x-a)^n}, \qquad \dfrac{P(x)}{(Q(x))^m}[/math], где [math] m, n \geqslant 1[/math], [math]P(x), Q(x)[/math] - полиномы, причем [math]Q(x)[/math] - полином, не имеющий рациональных корней и [math]\deg(P) \lt \deg(Q)[/math].

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

1. Привести дробь [math]\dfrac{P(z)}{Q(z)}[/math] к такому виду, чтобы степень числителя была меньше степени знаменателя. Если [math]\deg(P) \gt \deg(Q)[/math], то можем записать [math]G(z)=\dfrac{P(z)}{Q(z)} = R(z)+\dfrac{P_0(z)}{Q(z)},[/math] где [math]\deg(P_0) \lt \deg(Q)[/math].
2. Отыскать корни уравнения [math]Q(z)=0[/math] и разбить знаменатель на множители вида [math](z_s-z)^{k_s}[/math] (здесь [math]z_s[/math] — корень кратности [math]k_s[/math]).
3. Записать сумму дробей, знаменатили которых будут иметь вид [math](z_s-z)^{k_s}[/math], а числители — полиномы с неопределёнными коэффициентами, имеющие степень [math]k_s-1[/math].
4. Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням [math]z[/math].
5. Приравнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома [math]P(z)[/math], составив, таким образом, систему линейных уравнений.
6. Решить систему и получить значения неопределённых коэффициентов.
7. Представить получившиеся дроби в виде рядов, пользуясь формулами преобразования производящих функций и таблицей производящих функций.

Примеры

Пример 1

Разложить в ряд функцию [math] G(z)=\dfrac{8+4z}{1-z-z^2+z^3}.[/math] Разложим знаменатель функции на множители [math] 1-z-z^2+z^3=(1+z)(1-z)^2,[/math] тогда [math]G(z)=\dfrac{8+4z}{1-z-z^2+z^3}=\dfrac{8+4z}{(1+z)(1-z)^2}.[/math]

Представим функцию на сумму двух дробей, причем у первой в числителе будет полином степени [math]0[/math], а у второй степени [math]1[/math]

[math]G(z)=\dfrac{8+4z}{1-z-z^2+z^3}=\dfrac{A}{(1+z)}+\dfrac{Bz+C}{(1-z)^2},[/math]

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

[math]\dfrac{A}{(1+z)}+\dfrac{Bz+C}{(1-z)^2}=\dfrac{A(1-z)^2+(Bz+C)(1+z)}{(1+z)(1-z)^2}=\dfrac{(A+B)z^2+(B+C-2A)z+(A+C)}{(1+z)(1-z)^2}=\dfrac{8+4z}{(1+z)(1-z)^2}.[/math]

Из последнего равенства, сравниваем коэффициенты при соответствующих степенях в числителе
[math]A+B=0[/math] - это коэффициент при [math]z^2[/math],
[math]B+C-2A=4[/math] - это коэффициент при [math]z^1[/math],
[math]A+C=8[/math] - это коэффициент при [math]z^0[/math].

Решая систему из трех уравнений, находим
[math]A=1[/math],
[math]B=-1[/math],
[math]C=7[/math].

Получаем

[math] \dfrac{A}{(1+z)}+\dfrac{Bz+C}{(1-z)^2} =\dfrac{1}{1+z}+\dfrac{-z+7}{(1-z)^2}=\dfrac{1}{1+z}+\dfrac{7}{(1-z)^2}-\dfrac{z}{(1-z)^2}. [/math]

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

[math]\dfrac{1}{1+z}=\sum_{n=0}^\infty (-1)^n z^n [/math]

[math]\dfrac{7}{(1-z)^2}=\sum_{n=0}^\infty 7(n+1) z^n [/math]

[math]\dfrac{z}{(1-z)^2}=\sum_{n=0}^\infty n z^n .[/math]

Тогда

[math] G(z)=\sum_{n=0}^\infty (7(n+1)-n+(-1)^n)z^n=\sum_{n=0}^\infty (6n+7+(-1)^n)z^n[/math]

Или

[math] [z^n]G(z) = 6n+7+(-1)^n, \qquad n \geqslant 0. [/math]

Пример 2

Разложить в ряд рациональную функцию

[math] G(z)=\dfrac{8-46z+89z^2-59z^3}{1-8z+23z^2-28z^3+12z^4}. [/math]

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

[math] \dfrac{8-46z+89z^2-59z^3}{1-8z+23z^2-28z^3+12z^4}=\dfrac{A}{1-z}+\dfrac{Bz+C}{(1-2z)^2}+\dfrac{D}{1-3z}. [/math]

Приведим все дроби к общему знаменателю:

[math] \dfrac{(-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)}. [/math]

Решаем систему линейных уравнений:

[math]-12A+3B-4D=-59[/math]

[math]16A-4B+3C+8D=89[/math]

[math]-7A+B-4C-5D=-46[/math]

[math]A+C+D=8[/math]

Решение этой системы:

[math]A=4, B=3, C=−1, D=5.[/math]

Это означает, что

[math]G(z)= \dfrac{4}{1-z} + \dfrac{3z}{(1-2z)^2} -\dfrac{1}{(1-2z)^2} + \dfrac{5}{1-3z}.[/math]

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

[math] G(z) = 4\sum_{n=0}^\infty z^n + 3\sum_{n=0}^\infty n2^{n-1}z^n-\sum_{n=0}^\infty (n+1) 2^n z^n+5\sum_{n=0}^\infty 3^n z^n. [/math]

То есть

[math] [z^n]G(z) = 5\cdot3^n + 3n2^{n-1} - (n+1)2^n+4= 5\cdot3^n+n2^{n-1}-2^n+4 [/math]

[math] G(z) = 8+18z+49z^2+143z^3+425z^4+1267z^5+3777z^6+11259z^7+O(z^{8}). [/math]

Проблема

На практике могут появиться рациональные функции, знаменатели которых не имееют действительных корней, тогда разбить эти фукции на более простые части не получится, что усложнит разложение в ряд.
Например, производящая функция, генерирующая количество гамильтоновых циклов на прямоугольной решётке размером [math]6 \times n[/math] .

[math] G(z)=\dfrac{z(1-z)(z^{11}-z^{10}+3z^9+12z^8-3z^7-3z^4+21z^3-3z^2-1)}{2z^{14}-4z^{13}+28z^{12}+42z^{11}-82z^{10}-8z^9+118z^8-66z^7-35z^6+90z^5+12z^4-63z^3+14z^2+5z-1}. [/math]

См. также

• Производящая функция
• Арифметические действия с формальными степенными рядами
• Производящие функции нескольких переменных

Источники информации

• Производящие функции