Изменения

Перейти к: навигация, поиск

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

4609 байт добавлено, 19:23, 4 сентября 2022
м
rollbackEdits.php mass rollback
__TOC__
 
==Определения==
 
{{Определение
|definition=
'''Рациональная функция''' (англ. ''Rational function'') {{---}} это формальный функция вида:
<center>
<tex>G(z)=\dfrac{P(z)}{Q(z)}</tex>,
</center>
где <tex>P </tex> и <tex>Q </tex> {{- --}} полиномы.
}}
Рациональные производящие функции получаются при [[Производящая функция#Решение рекуррентных соотношений|решении линейных рекуррентных соотношений]]. По этой причине актуальной является задача о разложении рациональной функции в ряд по степеням переменной <tex>z</tex>.
<br>
Чтобы разложить дробь в ряд, необходимо разбить её на сумму элементарных дробей.
{{Определение
|definition=
'''Элементарными дробями''' (англ. ''Simple partial fractions'') будем называть дроби вида: <center><tex>\dfrac{A}{(x-a)^n}</tex>, <tex>\qquad \dfrac{Bx + CP(x)}{(Q(x^2 + px + q))^m}</tex>, </center>где <tex> m, n \geqslant 1</tex>, <tex>P(x), Q(x)</tex>= 1и {{---}} полиномы, причем <tex>Q(x^2 + px + q) </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{P0P_0(z)}{Q(z)},</tex>, где <tex>\deg(P0P_0) < \deg(Q)</tex>.# Разобьем знаменатель Отыскать корни уравнения <tex>Q(z) =0</tex> и разбить знаменатель на множители Qвида <tex>(z_s-z) = ^{k_s}</tex> (здесь <tex>z_s</tex> — корень кратности <tex>k_s</tex>).# Записать сумму дробей, знаменатили которых будут иметь вид <tex>(zkz_s-z)^k1 *.{k_s}</tex>, а числители — полиномы с неопределёнными коэффициентами, имеющие степень <tex>k_s-1</tex>.# Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням <tex>z</tex>.# Приравнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома <tex>P(z)</tex>, где z1составив, z2таким образом, систему линейных уравнений.# Решить систему и получить значения неопределённых коэффициентов.# Представить получившиеся дроби в виде рядов, пользуясь [[Арифметические действия с формальными степенными рядами|формулами преобразования производящих функций]] и [[Производящая функция#Примеры простых производящих функций|таблицей производящих функций]]., zs - корни уравнения Q ===Примеры=== #Разложить в ряд функцию <tex> G(z) = 0\dfrac{8+4z}{1-z-z^2+z^3}. При этом</tex>#:Разложим знаменатель функции на множители: <tex> 1-z-z^2+z^3=(1+z)(1-z)^2</tex>, k1тогда <tex>G(z)=\dfrac{8+k24z}{1-z-z^2+z^3}=\dfrac{8+⋅⋅⋅4z}{(1+ks=deg Q После разбиения знаменателя z)(1-z)^2}.</tex>#:Представим функцию на множители получимсумму двух дробей, причем у первой в числителе будет полином степени <tex>0</tex>, а у второй степени <tex>1</tex>:#: <tex>G(z)=\dfrac{P8+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)}{(z11+z)(1-z)^k1 *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 (zs-1)^n z^n </tex>#:<tex>\dfrac{7}{(1-z)^ks2}=\sum_{n=0}^\infty 7(n+1) z^n </tex> #:<tex>\dfrac{z}{(k1, ks 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+(zj−z-1)^n)z^n</tex>#:или <tex>[z^kj, а числители — полиномы Pjn]G(z), причем deg Pj= 6n+7+(z-1)^n, \qquad n \geqslant 0<kj/tex>. #Разложить в ряд рациональную функцию <tex>G(z)=\dfrac{P8-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}{(z11-z)(1-2z)^k1 *.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(zsz)= \dfrac{4}{1-z} + \dfrac{3z}{(1-2z)^ks2} -\dfrac{1}{(1-2z)^2} + \dfrac{5}{1-3z}.</tex>#:Теперь каждую дробь можно разложить в ряд, пользуясь таблицей:#:<tex>G(z) = 4\sumsum_{n=0}^\limits infty z^n + 3\dfracsum_{n=0}^\infty n2^{n-1}z^n-\sum_{n=0}^\infty (n+1) 2^n z^n+5\sum_{Pjn=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(zj-z)= 8+18z+49z^kj2+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>. Найдем Pj<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> ==См. также==* [[Производящая функция]]* [[Арифметические действия с помощью формальными степенными рядами]]* [[Разложение рациональной Производящие функции в ряд#Метод неопределенных коэффициентов|метода неопределенных коэффициентовнескольких переменных]].  == Примечания ==<brreferences/>
==Метод неопределенных коэффициентовИсточники информации ==# Записать сумму дробей, знаменатили которых будут иметь вид (zs−z)ks, а числители — полиномы с неопределёнными коэффициентами, имеющие степень ks−1* [http://www.# Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням z.# Прировнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома P(z), составив, таким образом, систему линейных уравнений.# Решить систему и получить значения неопределённых коэффициентовgenfunc.ru/ Производящие функции]
==Примеры==[[Категория: Дискретная математика и алгоритмы]][[Категория: Производящая функция]]
1632
правки

Навигация