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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Общий алгоритм)
 
(не показаны 102 промежуточные версии 4 участников)
Строка 5: Строка 5:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Рациональная функция''' это функция вида:
+
'''Рациональная функция''' (англ. ''Rational function'') {{---}} это функция вида:
 
<center>
 
<center>
 
<tex>G(z)=\dfrac{P(z)}{Q(z)}</tex>,  
 
<tex>G(z)=\dfrac{P(z)}{Q(z)}</tex>,  
 
</center>
 
</center>
где <tex>P</tex> и <tex>Q</tex> - полиномы.  
+
где <tex>P</tex> и <tex>Q</tex> {{---}} полиномы.  
 
}}
 
}}
  
Строка 17: Строка 17:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Элементарными дробями''' будем называть дроби вида:
+
'''Элементарными дробями''' (англ. ''Simple partial fractions'') будем называть дроби вида:
 +
 
 
<center>
 
<center>
<tex>\dfrac{A}{(x-a)^n}, \qquad  \dfrac{Bx + C}{(x^2 + px + q)^m}</tex>,  
+
<tex>\dfrac{A}{(x-a)^n}, \qquad  \dfrac{P(x)}{(Q(x))^m}</tex>,  
 
</center>
 
</center>
где <tex> m, n \geqslant 1</tex>, и <tex>p^2 - 4q < 0</tex>  
+
где <tex> m, n \geqslant 1</tex>, <tex>P(x), Q(x)</tex> {{---}} полиномы, причем <tex>Q(x)</tex> {{---}} полином, не имеющий рациональных корней и <tex>\deg(P) < \deg(Q)</tex>.
 
}}
 
}}
<br>
 
Затем, элементарные дроби сможем разложить в ряд, пользуясь [[Арифметические действия с формальными степенными рядами|формулами преобразования производящих функций]] и [[Производящая функция#Примеры простых производящих функций|таблицей производящих функций]].
 
<br>
 
  
 
==Общий алгоритм==
 
==Общий алгоритм==
 
# Привести дробь <tex>\dfrac{P(z)}{Q(z)}</tex> к такому виду, чтобы степень числителя была меньше степени знаменателя. Если <tex>\deg(P) > \deg(Q)</tex>, то можем записать <tex>G(z)=\dfrac{P(z)}{Q(z)} = R(z)+\dfrac{P_0(z)}{Q(z)},</tex> где <tex>\deg(P_0) < \deg(Q)</tex>.
 
# Привести дробь <tex>\dfrac{P(z)}{Q(z)}</tex> к такому виду, чтобы степень числителя была меньше степени знаменателя. Если <tex>\deg(P) > \deg(Q)</tex>, то можем записать <tex>G(z)=\dfrac{P(z)}{Q(z)} = R(z)+\dfrac{P_0(z)}{Q(z)},</tex> где <tex>\deg(P_0) < \deg(Q)</tex>.
# Разобьем знаменатель <tex>Q(z)</tex> на множители <tex>Q(z) = (z_k-z)^{k_s} *...</tex>, где <tex>z1, z2, ..., z_s</tex> - корни уравнения <tex>Q(z) = 0</tex>. При этом, k1+k2+⋅⋅⋅+ks=deg Q После разбиения знаменателя на множители получим: <tex>G(z)=\dfrac{P(z)}{(z1-z)^k1 *...(zs-z)^ks}</tex> (k1, ks - сделать индексами)  
+
# Отыскать корни уравнения <tex>Q(z)=0</tex> и разбить знаменатель на множители вида <tex>(z_s-z)^{k_s}</tex> (здесь <tex>z_s</tex> — корень кратности <tex>k_s</tex>).
# Приведем G(z) к сумме дробей, знаменатели которых будут иметь вид (zj−z)^kj, а числители — полиномы Pj(z), причем deg Pj(z)<kj. <tex>G(z)=\dfrac{P(z)}{(z1-z)^k1 *...(zs-z)^ks} = \sum\limits \dfrac{Pj(z)}{(zj-z)^kj}</tex>. Найдем Pj(z) с помощью [[Разложение рациональной функции в ряд#Метод неопределенных коэффициентов|метода неопределенных коэффициентов]].
+
# Записать сумму дробей, знаменатили которых будут иметь вид <tex>(z_s-z)^{k_s}</tex>, а числители — полиномы с неопределёнными коэффициентами, имеющие степень <tex>k_s-1</tex>.
<br>
+
# Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням <tex>z</tex>.
 +
# Приравнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома <tex>P(z)</tex>, составив, таким образом, систему линейных уравнений.
 +
# Решить систему и получить значения неопределённых коэффициентов.
 +
# Представить получившиеся дроби в виде рядов, пользуясь [[Арифметические действия с формальными степенными рядами|формулами преобразования производящих функций]] и [[Производящая функция#Примеры простых производящих функций|таблицей производящих функций]].
 +
 
 +
===Примеры===
 +
 
 +
#Разложить в ряд функцию  <tex> G(z)=\dfrac{8+4z}{1-z-z^2+z^3}.</tex>
 +
#:Разложим знаменатель функции на множители: <tex> 1-z-z^2+z^3=(1+z)(1-z)^2</tex>, тогда <tex>G(z)=\dfrac{8+4z}{1-z-z^2+z^3}=\dfrac{8+4z}{(1+z)(1-z)^2}.</tex>
 +
#:Представим функцию на сумму двух дробей, причем у первой в числителе будет полином степени <tex>0</tex>, а у второй степени <tex>1</tex>:
 +
#:<tex>G(z)=\dfrac{8+4z}{1-z-z^2+z^3}=\dfrac{A}{(1+z)}+\dfrac{Bz+C}{(1-z)^2}</tex>, где <tex>A, B</tex> и <tex>C</tex> — некоторые константы.
 +
#:Для того, чтобы найти эти константы, нужно сложить дроби:
 +
#:<tex>\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}.</tex>
 +
#:Из последнего равенства, сравниваем коэффициенты при соответствующих степенях в числителе<br>
 +
#:<tex>A+B=0</tex> {{---}} это коэффициент при <tex>z^2</tex>,<br>
 +
#:<tex>B+C-2A=4</tex> {{---}} это коэффициент при <tex>z^1</tex>,<br>
 +
#:<tex>A+C=8</tex> {{---}} это коэффициент при <tex>z^0</tex>.
 +
#:Решая систему из трех уравнений, находим <br>
 +
#:<tex>A=1</tex>,<br>
 +
#:<tex>B=-1</tex>,<br>
 +
#:<tex>C=7</tex>.
 +
#:Получаем: <tex>\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}.</tex>
 +
#:Эти дроби разложим в ряд, пользуясь таблицей производящих функций и формулами преобразования:
 +
#:<tex>\dfrac{1}{1+z}=\sum_{n=0}^\infty (-1)^n z^n </tex>
 +
#:<tex>\dfrac{7}{(1-z)^2}=\sum_{n=0}^\infty 7(n+1) z^n </tex>
 +
#:<tex>\dfrac{z}{(1-z)^2}=\sum_{n=0}^\infty n z^n .</tex>
 +
#:Тогда <tex> G(z)=\sum_{n=0}^\infty (7(n+1)-n+(-1)^n)z^n=\sum_{n=0}^\infty (6n+7+(-1)^n)z^n</tex>
 +
#:или <tex>[z^n]G(z) = 6n+7+(-1)^n, \qquad n \geqslant 0</tex>.
 +
#Разложить в ряд рациональную функцию <tex>G(z)=\dfrac{8-46z+89z^2-59z^3}{1-8z+23z^2-28z^3+12z^4}.</tex>
 +
#:Разбив знаменатель на множители, получаем: <tex>\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}.</tex>
 +
#:Приведём все дроби к общему знаменателю: <tex>\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)}.</tex>
 +
#:Решаем систему линейных уравнений:
 +
#:<tex>-12A+3B-4D=-59</tex>
 +
#:<tex>16A-4B+3C+8D=89</tex>
 +
#:<tex>-7A+B-4C-5D=-46</tex>
 +
#:<tex>A+C+D=8</tex>
 +
#:Решение этой системы:
 +
#:<tex>A=4, B=3, C=−1, D=5.</tex>
 +
#:Это означает, что <tex>G(z)= \dfrac{4}{1-z} + \dfrac{3z}{(1-2z)^2} -\dfrac{1}{(1-2z)^2} + \dfrac{5}{1-3z}.</tex>
 +
#:Теперь каждую дробь можно разложить в ряд, пользуясь таблицей:
 +
#:<tex>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.</tex>
 +
#:То есть
 +
#:<tex>[z^n]G(z) = 5\cdot3^n + 3n2^{n-1} - (n+1)2^n+4= 5\cdot3^n+n2^{n-1}-2^n+4</tex>
 +
#:<tex>G(z) = 8+18z+49z^2+143z^3+425z^4+1267z^5+3777z^6+11259z^7+O(z^{8}).</tex>
 +
 
 +
==Проблема==
 +
На практике могут появиться рациональные функции, знаменатели которых не имееют действительных корней, тогда разбить эти фукции на более простые части не получится, что усложнит разложение в ряд. <br>
 +
Например, производящая функция, генерирующая количество гамильтоновых циклов на прямоугольной решётке размером <tex>6 \times n</tex> <ref>[http://oeis.org/ The On-Line Encyclopedia of Integer Sequences]</ref>.
 +
<center>
 +
<tex>
 +
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}.
 +
</tex>
 +
</center>
 +
 
 +
==См. также==
 +
* [[Производящая функция]]
 +
* [[Арифметические действия с формальными степенными рядами]]
 +
* [[Производящие функции нескольких переменных]]
 +
 
 +
== Примечания ==
 +
<references/>
  
==Метод неопределенных коэффициентов==
+
== Источники информации ==  
# Записать сумму дробей, знаменатили которых будут иметь вид (zs−z)ks, а числители — полиномы с неопределёнными коэффициентами, имеющие степень ks−1.
+
* [http://www.genfunc.ru/ Производящие функции]
# Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням z.
 
# Прировнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома P(z), составив, таким образом, систему линейных уравнений.
 
# Решить систему и получить значения неопределённых коэффициентов.
 
  
==Примеры==
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Производящая функция]]

Текущая версия на 23:31, 2 июня 2017

Определения[править]

Определение:
Рациональная функция (англ. Rational function) — это функция вида:

[math]G(z)=\dfrac{P(z)}{Q(z)}[/math],

где [math]P[/math] и [math]Q[/math] — полиномы.


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

Определение:
Элементарными дробями (англ. Simple partial fractions) будем называть дроби вида:

[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] [1].

[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]

См. также[править]

Примечания[править]

Источники информации[править]