Дифференцирование и интегрирование производящих функций
| Определение: |
| Пусть [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] — производящая функция.
Производной этой функции называется функция
- [math]A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots[/math]
Интегралом называется функция
- [math]\int\limits A(s) = a_0 s + a_1 \dfrac{s^2}{2} + a_2 \dfrac{s^3}{3} + \dots + a_n \dfrac{s^{n+1} }{n + 1} + \dots[/math]
|
Операция дифференцирования обратна операции интегрирования:
- [math](\int\limits A(s))' = A(s)[/math].
Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.
- [math] \int\limits A'(s) = A(s) - A(s) [/math]
Замечание
| Утверждение: |
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
- [math] \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi [/math].
|
Примеры
Пример 1
Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию
- [math] f(s) = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} s + \dfrac{1}{3 \times 4} s^2 + \dots + \dfrac{1}{(n + 1)(n + 2)} s^n + \dots [/math]
Умножая функцию [math] f [/math] на [math] s^2 [/math] и дифференцируя, получаем
- [math](s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln \dfrac{1}{1 -
s}[/math],
откуда
- [math] f(s) = s^{-2} \int\limits \ln \dfrac{1}{1 - s} = s^{-1} ((s - 1) \ln \dfrac{1}{1 - s} + s) [/math].
Пример 2
Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:
- [math] g_0 = 1[/math]
- [math] g_1 = 1[/math]
- [math] g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n[/math]
Умножим обе части всех равенств на z в соответствующей степени и просуммируем:
- [math] z^0 g_0 = 1[/math]
- [math] z^1 g_1 = z[/math]
- [math] z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n[/math]
- [math] g_0 + g_1 z + \sum\limits_{n = 2}^{\infty} g_n z^n = 1 + z + \sum\limits_{n = 2}^{\infty} g_{n - 1} z^n + 2 \sum\limits_{n = 2}^{\infty} g_{n - 2} z^n + \sum\limits_{n = 2}^{\infty} (-1)^n z^n [/math]
Левая часть [math] G(z) = g_0 + g_1 z + \sum\limits_{n = 2}^{\infty} g_n z^n = \sum\limits_{n = 0}^{\infty} g_n z^n [/math] представляет собой производящую функцию в бесконечном виде.
Попытаемся выразить правую часть через [math]G(z)[/math]. Рассмотрим каждое слагаемое:
- [math]\sum\limits_{n = 2}^{\infty} g_{n - 1} z^n = z \sum\limits_{n = 2}^{\infty} g_{n - 1} z^{n - 1} = z (G(z) - g_0) = z(G(z) - 1)[/math]
- [math]\sum\limits_{n = 2}^{\infty} g_{n - 2} z^n = z^2 \sum\limits_{n = 2}^{\infty} g_{n - 2} z^{n - 2} = z^2 G(z)[/math]
- [math]\sum\limits_{n = 2}^{\infty} (-1)^n z^n = z^2 - z^4 + z^6 - z^8 + \dots = 1 - z + z^2 -z^4 + z^6 -z^8 + \dots -1 + z = \sum\limits_{n = 0}^{\infty} (-1)^n z^n - 1 + z = \dfrac{1}{1 + z} - 1 + z[/math]
Составляем уравнение:
- [math]G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z[/math]
- [math]G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z[/math]
- [math]G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}[/math]
- [math]G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}[/math]
Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений [math]z[/math]), получаем:
- [math]G(z) = \dfrac{1}{3} \times \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \times \dfrac{1}{1 + z} + \dfrac{7}{9} \times \dfrac{1}{1 - 2 z}[/math]
Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:
- [math]\dfrac{1}{(1 + z)^2} = (- \dfrac{1}{1 + z})' = (\sum\limits_{n = 0}^{\infty} (-1)^{n + 1} z^n)' = \sum\limits_{n = 0}^{\infty} (-1)^{n + 1} n z^{n - 1} = \sum\limits_{n = 0}^{\infty} (-1)^n (n + 1) z^n[/math]
Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:
[math]G(z) = \dfrac{1}{3} \sum\limits_{n = 0}^{\infty} (-1)^n (n + 1) z^n - \dfrac{1}{9} \sum\limits_{n = 0}^{\infty} (-1)^n z^n + \dfrac{7}{9} \sum\limits_{n = 0}^{\infty} 2^n z^n = \sum\limits_{n = 0}^{\infty} (\dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})) z^n[/math]
Мы искали G(z) в виде [math]G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n[/math], значит
- [math]g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})[/math]
Пример 3
Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся разложением экспоненты:
- [math]e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n[/math]
Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:
- [math]ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots[/math]
(свободный член в разложении равен [math]0[/math], поскольку [math]ln(1) = 0[/math]). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают [math]1[/math]. Поскольку [math]\dfrac{d}{ds} e^s = e^s[/math], получаем
- [math]\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots[/math],
откуда, интегрируя,
- [math]ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots[/math]
Чаще используется следующий вариант:
- [math]-ln(1 - t) = ln \dfrac{1}{1 - t} = t + \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 + \dfrac{1}{4}t^4 + \dots[/math]
Решение обыкновенных дифференциальных уравнений на производящие функции
| Теорема (О существовании и единственности решения): |
Рассмотрим обыкновенное дифференциальное уравнение
- [math]f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)[/math]
на производящую функцию [math]f(s)[/math], где [math]F = F(s, t)[/math] — производящая функция двух переменных, являющаяся многочленом по [math]t[/math] (т.е. степень [math]F[/math] по [math]t[/math] конечна). Тогда для каждого [math]f_0[/math] уравнение [math](1)[/math] имеет единственное решение, удовлетворяющее условию [math]f(0) = f_0[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции [math]f[/math]. Пусть степень [math]F[/math] по [math]t[/math] равна [math]n[/math] и
- [math]F(s, t) = (F_{00} + F_{10} s + F_{20} s^2 + \dots) + (F_{01} + F_{11} s + F_{21} s^2 + \dots) t + \dots + (F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) t^n, f(s) = f_0 + f_1 s + f_2 s^2 + \dots[/math]
Приравнивая коэффициенты при [math]s^0[/math] в левой и правой частях уравнения [math](1)[/math]
Возьмем с первого слагаемого:
- [math](F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}[/math]
Возьмем со второго слагаемого:
- [math](F_{01} + F_{11} s + F_{21} s^2 + \dots) t = (F_{01} + F_{11} s + F_{21} s^2 + \dots) (f_0 + f_1 s + f_2 s^2 + \dots) \rightarrow F_{01} f_0[/math]
Возьмем со n-го слагаемого:
- [math](F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) t^n = (F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) (f_0 + f_1 s + f_2 s^2 + \dots)^n \rightarrow F_{0n} f_0^n[/math]
Итого выходит:
- [math]f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n[/math]
Аналогично, равенство коэффициентов при [math]s^1[/math] дает
- [math]2 f_2 = F_{10} + F_{01} f_1 + F_{11} f_0 + \dots + F_{0n} f_0^{n - 1} f_1 + F_{1n} f_0^n[/math]
Вообще, [math]f_n[/math] находится из уравнения
- [math]n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)[/math],
где точками обозначен многочлен от коэффициентов функции F и коэффициентов [math]f_0, f_1, \dots, f_{n-1}[/math] функции [math]f[/math]. При каждом [math]n \gt 0[/math] уравнение [math](2)[/math] имеет единственное решение, и теорема доказана. Значит уравнение [math](1)[/math] имеет однозначное решение для каждого [math]f_0[/math]. |
| [math]\triangleleft[/math] |
См. также
Источники информации
- Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144с. ISBN 978-5-94057-042-4
