Арифметические действия с формальными степенными рядами — различия между версиями
Penguinni (обсуждение | вклад) м (→См. также) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 23 промежуточные версии 6 участников) | |||
Строка 1: | Строка 1: | ||
==Простейшие операции== | ==Простейшие операции== | ||
Рассмотрим два [[Производящая функция|формальных степенных ряда]] <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex>. | Рассмотрим два [[Производящая функция|формальных степенных ряда]] <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex>. | ||
− | + | {{Определение | |
− | ''Суммой'' <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s) + B(s) = (a_0 + b_0) + (a_1 + b_1) s + (a_2 + b_2) s^2 + \dots</tex>. | + | |definition = '''Суммой''' (англ. ''addition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s) + B(s) = (a_0 + b_0) + (a_1 + b_1) s + (a_2 + b_2) s^2 + \dots</tex>. |
− | + | }} | |
− | ''Произведением'' <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s)B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0) s + (a_0 b_2 + a_1 b_1 + a_2 b_0) s^2 + \dots</tex>. | + | {{Определение |
− | + | |id=def_mul | |
+ | |definition = '''Произведением''' (англ. ''multiplication'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s)B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0) s + (a_0 b_2 + a_1 b_1 + a_2 b_0) s^2 + \dots</tex>. | ||
+ | }} | ||
Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны. | Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны. | ||
==Деление== | ==Деление== | ||
+ | {{Определение | ||
+ | |id = div | ||
+ | |definition= | ||
+ | '''Обратным по умножению''' (англ. ''multiplicative inverse'') к формальному степенному ряду <tex>A(s)</tex> называется такой ряд <tex>B(s)</tex>, что <tex>A(s)B(s) = 1</tex>. Обозначение: <tex>B(s) = A^{-1}(s)</tex>. | ||
+ | }} | ||
+ | |||
{{Лемма | {{Лемма | ||
− | + | |statement = Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots </tex> {{---}} формальный степенной ряд, причем <tex>A(0) \ne 0</tex>. Тогда существует единственный обратный по умножению к <tex>A(s)</tex> ряд <tex>B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots </tex>. | |
− | |statement = Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots </tex> {{---}} формальный степенной ряд, причем <tex>A(0) \ne 0</tex>. Тогда существует единственный | ||
|proof = | |proof = | ||
− | : | + | :Распишем <tex>A(s)B(s)</tex> по формуле произведения рядов: <tex>A(s)B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0)s + (a_0 b_2 + a_1 b_1 + a_2 b_0) s^2 + \dots</tex>. Заметим, что условие <tex>A(s)B(s) = 1</tex> выполнено только в том случае, если <tex>a_0 b_0 = 1</tex>, а все остальные слагаемые полученного ряда равны нулю. |
+ | :Докажем по индукции, что такой ряд <tex>B</tex> единственен. Нам известно, что <tex>b_0 = \dfrac{1}{a_0}</tex>. Пусть теперь все коэффициенты ряда <tex>B</tex> вплоть до степени <tex>n - 1</tex> однозначно определены. Коэффициент при <tex>s^n</tex> определяется из условия <tex>a_0 b_n + a_1 b_{n - 1} + \dots + a_n b_0 = 0</tex>. Это линейное уравнение на <tex>b_n</tex>, причем коэффициент <tex>a_0</tex> при <tex>b_n</tex> отличен от нуля. Такое уравнение имеет единственное решение. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | '''Делением''' (англ. ''division'') формальных степенных рядов <tex>A(s)</tex> и <tex>B(s)</tex> называется операция <tex>\dfrac{A(s)}{B(s)} = A(s) B(s)^{-1}</tex> (при условии существования у <tex>B(s)</tex> обратного). | ||
}} | }} | ||
+ | |||
+ | ===Примеры=== | ||
+ | #Допустим, надо построить обратный ряд для <tex>A(s) = 1 + s</tex>. Воспользуемся леммой: | ||
+ | #:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex> | ||
+ | #:<tex>a_0 b_1 + a_1 b_0 = 0 \Rightarrow b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{1 \cdot 1}{1} = -1</tex> | ||
+ | #:<tex>a_0 b_2 + a_1 b_1 + a_2 b_0 = 0 \Rightarrow b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{1 \cdot (-1) + 0}{1} = 1</tex> | ||
+ | #:<tex>\dots</tex> | ||
+ | #:<tex>b_n = - \dfrac{a_1 b_{n - 1}}{a_0} = -b_{n - 1}</tex> | ||
+ | #:<tex>B(s) = 1 - s + s^2 - s^3 + \dots</tex> | ||
+ | #Пусть теперь надо построить обратный ряд для <tex>A(s) = 1 - s - s^2</tex>: | ||
+ | #:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex> | ||
+ | #:<tex>b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{(-1) \cdot 1}{1} = 1</tex> | ||
+ | #:<tex>b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{(-1) \cdot 1 + (-1) \cdot 1}{1} = 2</tex> | ||
+ | #:<tex>b_3 = - \dfrac{a_1 b_2 + a_2 b_1}{a_0} = - \dfrac{(-1) \cdot 2 + (-1) \cdot 1}{1} = 3</tex> | ||
+ | #:<tex>\dots</tex> | ||
+ | #:<tex>b_n = - \dfrac{a_1 b_{n - 1} + a_2 b_{n - 2}}{a_0} = b_{n - 1} + b_{n - 2}</tex> | ||
+ | #:<tex>B(s) = 1 + s + 2 s^2 + 3 s^3 + \dots</tex> | ||
==Композиция== | ==Композиция== | ||
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex> {{---}} два формальных степенных ряда, причем <tex>B(0) = b_0 = 0</tex>. | Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex> {{---}} два формальных степенных ряда, причем <tex>B(0) = b_0 = 0</tex>. | ||
− | ''Композицией (подстановкой)'' рядов <tex>A</tex> и <tex>B</tex> называется | + | {{Определение |
− | + | |id=def_in | |
+ | |definition = | ||
+ | '''Композицией (подстановкой)''' (англ. ''composition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(B(t)) = a_0 + a_1 b_1 t + (a_1 b_2 + a_2 b_1^2) t^2 + (a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3) t^3 + \dots</tex>. | ||
+ | }} | ||
Если, например, <tex>B(t) = -t</tex>, то <tex>A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>. | Если, например, <tex>B(t) = -t</tex>, то <tex>A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>. | ||
− | Операция подстановки в случае, когда <tex>B(0) \ne 0</tex>, не определена. (При попытке подставить такой ряд возникает необходимость суммирования бесконечных числовых рядов). | + | Операция подстановки в случае, когда <tex>B(0) \ne 0</tex>, не определена. (При попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов). |
− | == | + | ==Обратный ряд== |
− | |||
− | |||
− | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | + | '''Левым обратным''' (англ. ''left inverse'') по операции подстановки формальным степенным рядом для ряда <tex>B(t)</tex> называется такой ряд <tex>A(s)</tex>, что <tex>A(B(t)) = t</tex>. Аналогично, '''правым обратным''' (англ. ''right inverse'') формальным степенным рядом для <tex>B(t)</tex> называется такой <tex>C(u)</tex>, что <tex>B(C(u)) = u</tex>. | |
}} | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |about = об обратном формальном степенном ряде | ||
+ | |statement = Пусть ряд <tex>B(t) = b_0 + b_1 t + b_2 t^2 + b_3 t^3 + \dots</tex> таков, что <tex>B(0) = b_0 = 0</tex>, а <tex>b_1 \ne 0</tex>. Тогда существуют такие ряды <tex> A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \dots</tex>, <tex>A(0) = 0</tex> и <tex>C(u) = c_1 u + c_2 u^2 + c_3 u^3 + \dots</tex>, <tex>C(0) = 0</tex>, что <tex>A(t)</tex> является левым обратным, а <tex>C(u)</tex> {{---}} правым обратным для <tex>B(s)</tex>. При этом, ряды <tex>A</tex> и <tex>C</tex> единственны. | ||
|proof = | |proof = | ||
− | :Докажем существование и единственность | + | :Докажем по индукции существование и единственность левого обратного ряда. Доказательство для правого аналогично. |
− | :Будем определять коэффициенты ряда <tex>A</tex> последовательно. | + | :Будем определять коэффициенты ряда <tex>A</tex> последовательно. Поскольку <tex>A(B(t)) = t</tex>, <tex>a_1 b_1 = 1</tex>, откуда <tex>a_1 = \dfrac{1}{b_1}</tex>. Все остальные коэффициенты результирующего ряда при этом равны нулю. |
− | :Предположим теперь, что коэффициенты <tex>a_1, a_2, \dots, a_n</tex> уже определены. Коэффициент <tex>a_{n+1}</tex> определяется из условия <tex>a_{n+1} b_1^{n+1} + \dots = 0</tex>, где точками обозначен | + | :Предположим теперь, что коэффициенты <tex>a_1, a_2, \dots, a_n</tex> уже определены. Коэффициент <tex>a_{n+1}</tex> определяется из условия <tex>a_{n+1} b_1^{n+1} + \dots = 0</tex>, где точками обозначен некоторый многочлен от <tex>a_1, \dots, a_n</tex> и <tex>b_1, \dots, b_n</tex>. Тем самым, условие представляет собой линейное уравнение на <tex>a_{n+1}</tex>, причем коэффициент <tex>b_1^{n+1}</tex> при <tex>a_{n+1}</tex> отличен от нуля. Такое уравнение имеет единственное решение, и теорема доказана. |
}} | }} | ||
+ | ===Пример=== | ||
+ | Найдем левый обратный ряд для <tex>B(t) = t + t^2</tex>: | ||
+ | :<tex>a_0 = 0</tex> | ||
+ | :<tex>a_1 = \dfrac{1}{b_1} = 1</tex> | ||
+ | :<tex>a_1 b_2 + a_2 b_1^2 = 0 \Rightarrow a_2 = - \dfrac{a_1 b_2}{b_1^2} = - \dfrac{1 \cdot 1}{1^2} = -1</tex> | ||
+ | :<tex>a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3 = 0 \Rightarrow a_3 = - \dfrac{a_1 b_3 + 2 a_2 b_1 b_2}{b_1^3} = - \dfrac{1 \cdot 0 + 2 \cdot (-1) \cdot 1}{1^3} = 2</tex> | ||
+ | :<tex>\dots</tex> | ||
+ | :<tex>A(s) = s - s^2 + 2 s^3 + \dots</tex> | ||
+ | |||
+ | ==Сдвиги== | ||
+ | ===Сдвиг вправо=== | ||
+ | Сдвиг ряда вправо на <tex>k</tex> получается домножением его на <tex>s^k</tex>. Например, пусть исходный ряд <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex>. Сдвинем его на <tex>k</tex> вправо: <tex>B(s) = s^k \cdot A(s) = a_0 s^k + a_1 s^{k + 1} + a_2 s^{k + 2} + \dots = 0 + 0 s + 0 s^2 + \dots + a_0 s^k + a_1 s^{k + 1} + \dots</tex>. | ||
+ | |||
+ | ===Сдвиг влево=== | ||
+ | Сдвинуть ряд влево на <tex>k</tex> можно, вычтя из него первые <tex>k</tex> слагаемых и затем разделив его на <tex>s^k</tex>. Например, сдвинем ряд <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> на <tex>k</tex> влево: <tex>B(s) = \dfrac{A(s) - (a_0 + a_1 s + a_2 s^2 + \dots + a_{k - 1} s^{k - 1})}{s^k} = a_k + a_{k + 1} s + a_{k + 2} s^2 + \dots</tex>. | ||
+ | |||
+ | |||
+ | Сдвиги могут быть полезны для упрощения вычисления производящих функций. | ||
+ | Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен <tex>F(s) = f_0 + f_1 s + f_2 s^2 + \dots</tex>, при этом <tex>f_0 = f_1 = 1</tex>, <tex>f_n = f_{n - 2} + f_{n - 1}, n > 1</tex>. Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на <tex>1</tex> вправо: <tex>F(s) + s \cdot F(s) = (f_0 + f_1 s + f_2 s^2 + f_3 s^3 + \dots) + (0 + f_0 s + f_1 s^2 + f_2 s^3 + \dots) = (f_0 + 0) + (f_1 + f_0) s + (f_2 + f_1) s^2 + (f_3 + f_2) s^3 + \dots = f_1 + f_2 s + f_3 s^2 + f_4 s^3 + \dots</tex>. Заметим, что результат равен сдвигу <tex>F(s)</tex> на <tex>1</tex> влево. Составим и решим уравнение: <tex>F(s) + s \cdot F(s) = \dfrac{F(s) - 1}{s}</tex>; <tex>F(s)(s^2 + s - 1) = -1</tex>; <tex>F(s) = \dfrac{1}{1 - s - s^2}</tex>. | ||
==См. также== | ==См. также== | ||
* [[Производящая функция]] | * [[Производящая функция]] | ||
+ | * [[Производящие функции нескольких переменных]] | ||
+ | * [[Разложение рациональной функции в ряд]] | ||
==Источники информации== | ==Источники информации== |
Текущая версия на 19:19, 4 сентября 2022
Простейшие операции
Рассмотрим два формальных степенных ряда и .
Определение: |
Суммой (англ. addition) формальных степенных рядов | и называется ряд .
Определение: |
Произведением (англ. multiplication) формальных степенных рядов | и называется ряд .
Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны.
Деление
Определение: |
Обратным по умножению (англ. multiplicative inverse) к формальному степенному ряду | называется такой ряд , что . Обозначение: .
Лемма: |
Пусть — формальный степенной ряд, причем . Тогда существует единственный обратный по умножению к ряд . |
Доказательство: |
|
Определение: |
Делением (англ. division) формальных степенных рядов | и называется операция (при условии существования у обратного).
Примеры
- Допустим, надо построить обратный ряд для
- Пусть теперь надо построить обратный ряд для
Композиция
Пусть
и — два формальных степенных ряда, причем .
Определение: |
Композицией (подстановкой) (англ. composition) формальных степенных рядов | и называется ряд .
Если, например,
, то .Операция подстановки в случае, когда
, не определена. (При попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов).Обратный ряд
Определение: |
Левым обратным (англ. left inverse) по операции подстановки формальным степенным рядом для ряда | называется такой ряд , что . Аналогично, правым обратным (англ. right inverse) формальным степенным рядом для называется такой , что .
Теорема (об обратном формальном степенном ряде): |
Пусть ряд таков, что , а . Тогда существуют такие ряды , и , , что является левым обратным, а — правым обратным для . При этом, ряды и единственны. |
Доказательство: |
|
Пример
Найдем левый обратный ряд для
:Сдвиги
Сдвиг вправо
Сдвиг ряда вправо на
получается домножением его на . Например, пусть исходный ряд . Сдвинем его на вправо: .Сдвиг влево
Сдвинуть ряд влево на
можно, вычтя из него первые слагаемых и затем разделив его на . Например, сдвинем ряд на влево: .
Сдвиги могут быть полезны для упрощения вычисления производящих функций.
Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен , при этом , . Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на вправо: . Заметим, что результат равен сдвигу на влево. Составим и решим уравнение: ; ; .
См. также
Источники информации
- Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144с. ISBN 978-5-94057-042-4