Разложение рациональной функции в ряд — различия между версиями
(→Примеры) |
м (rollbackEdits.php mass rollback) |
||
(не показано 88 промежуточных версий 5 участников) | |||
Строка 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{ | + | <tex>\dfrac{A}{(x-a)^n}, \qquad \dfrac{P(x)}{(Q(x))^m}</tex>, |
</center> | </center> | ||
− | где <tex> m, n \geqslant 1</tex>, и | + | где <tex> m, n \geqslant 1</tex>, <tex>P(x), Q(x)</tex> {{---}} полиномы, причем <tex>Q(x)</tex> {{---}} полином, не имеющий рациональных корней и <tex>\deg(P) < \deg(Q)</tex>. |
}} | }} | ||
− | |||
− | |||
− | |||
==Общий алгоритм== | ==Общий алгоритм== | ||
Строка 34: | Строка 32: | ||
# Приравнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома <tex>P(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/> | ||
− | == | + | == Источники информации == |
+ | * [http://www.genfunc.ru/ Производящие функции] | ||
− | + | [[Категория: Дискретная математика и алгоритмы]] | |
+ | [[Категория: Производящая функция]] |
Текущая версия на 19:23, 4 сентября 2022
Определения
Определение: |
Рациональная функция (англ. Rational function) — это функция вида:
, |
Рациональные производящие функции получаются при решении линейных рекуррентных соотношений. По этой причине актуальной является задача о разложении рациональной функции в ряд по степеням переменной .
Чтобы разложить дробь в ряд, необходимо разбить её на сумму элементарных дробей.
Определение: |
Элементарными дробями (англ. Simple partial fractions) будем называть дроби вида:
, |
Общий алгоритм
- Привести дробь к такому виду, чтобы степень числителя была меньше степени знаменателя. Если , то можем записать где .
- Отыскать корни уравнения и разбить знаменатель на множители вида (здесь — корень кратности ).
- Записать сумму дробей, знаменатили которых будут иметь вид , а числители — полиномы с неопределёнными коэффициентами, имеющие степень .
- Сложить выписанные дроби и сгруппировать слагаемые в числителе по степеням .
- Приравнять полученные выражения с неопределёнными коэффициентами к соответсвующим коэффициентам полинома , составив, таким образом, систему линейных уравнений.
- Решить систему и получить значения неопределённых коэффициентов.
- Представить получившиеся дроби в виде рядов, пользуясь формулами преобразования производящих функций и таблицей производящих функций.
Примеры
- Разложить в ряд функцию
- Разложим знаменатель функции на множители: , тогда
- Представим функцию на сумму двух дробей, причем у первой в числителе будет полином степени , а у второй степени :
- , где и — некоторые константы.
- Для того, чтобы найти эти константы, нужно сложить дроби:
- Из последнего равенства, сравниваем коэффициенты при соответствующих степенях в числителе
- — это коэффициент при .
- Решая систему из трех уравнений, находим
- .
- Получаем:
- Эти дроби разложим в ряд, пользуясь таблицей производящих функций и формулами преобразования:
- Тогда
- или .
- Разложить в ряд рациональную функцию
- Разбив знаменатель на множители, получаем:
- Приведём все дроби к общему знаменателю:
- Решаем систему линейных уравнений:
- Решение этой системы:
- Это означает, что
- Теперь каждую дробь можно разложить в ряд, пользуясь таблицей:
- То есть
Проблема
На практике могут появиться рациональные функции, знаменатели которых не имееют действительных корней, тогда разбить эти фукции на более простые части не получится, что усложнит разложение в ряд.
Например, производящая функция, генерирующая количество гамильтоновых циклов на прямоугольной решётке размером [1].