Викиконспекты - Вклад участника [ru]

Линейная регрессия

2019-03-12T11:56:48Z

Zem4ik: /* Дано */

'''Линейная регрессия''' (англ. ''linear regression'') — метод восстановления зависимости одной (объясняемой, зависимой) переменной <tex> y </tex> от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) <tex> x </tex> с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной <tex> y </tex> по значениям независимой переменной <tex> x </tex>.

== Задача ==

==== Дано ====

* <tex> f_1(x), \dots ,f_n(x) </tex> - числовые признаки
* модель многомерной линейной регрессии: <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, где <tex> a \in R^n </tex>
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>
* <tex> x_i </tex> - объекты из множества <tex> X = R^n </tex>
* <tex> y_i </tex> - объекты из множества <tex> X = R </tex>

==== Матричные обозначения ====

Перейдем к матричным обозначениям:

<tex>
\underset{l \times n}{F} =
\begin{pmatrix}
f_1(x_1) & \dots & f_n(x_1) \\
\dots & \dots & \dots \\
f_n(x_1) & \dots & f_n(x_l)
\end{pmatrix}
,

\underset{l \times 1}{y} =
\begin{pmatrix}
y_1 \\
\dots \\
y_l
\end{pmatrix},

\underset{n \times 1}{\alpha} =
\begin{pmatrix}
\alpha_1 \\
\dots \\
\alpha_l
\end{pmatrix}

</tex>

, где
* <tex> F </tex> - матрица объектов-признаков, где строки соответствуют объектам а столбцы - признакам
* <tex> y </tex> - вектор ответов, или целевой вектор
* <tex> \alpha </tex> - вектор коэффициентов

==== Постановка задачи ====

В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:

<tex> Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} </tex>

Необходимо найти вектор <tex> \alpha </tex> при известной матрице <tex> F </tex> и известном вектор-столбце <tex> y </tex>.

== Решение ==

=== Нормальная система уравнений ===

Запишем необходимые условия минимума в матричном виде.

<tex> \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 </tex>

Отсюда следует нормальная система задачи МНК:

<tex> F^T F \alpha = F^T y </tex>,

где <tex> F^T F - n \times n </tex> матрица

Мы получили систему уравнений, откуда можем выразить искомый вектор <tex> \alpha </tex>.

==== Решение системы ====
<tex> \alpha^* = (F^T F)^{-1} F^T y = F^+ y </tex>, где <tex> F^+ </tex> — псевдо-обратная матрица.

Значение функционала: <tex> Q(\alpha^*) = ||P_F y - y||^2 </tex>, где <tex> P_F = F F^+ = F (F^T F)^{-1} F^T </tex> - ''проекционная матрица''

==== Проблемы ====

В случае мультиколлинеарности (столбцы матрицы <tex> F </tex> линейно-зависимы) нам не удастся найти обратную матрицу к <tex> F^T F </tex> (она будет вырождена).

Если же столбцы матрицы <tex> F </tex> почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.

=== Сингулярное разложение ===

Воспользуемся понятием [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5/ сингулярного разложения ], которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:

<tex> F = V D U^T </tex>.

Основные свойства сингулярного разложения:

* <tex> l \times n </tex>-матрица <tex> V = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>, столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
* <tex> n \times n </tex>-матрица <tex> U = (u_1, \dots, u_n) </tex> ортогональна, <tex> U^T U = I_n </tex>, столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
* <tex> n \times n </tex>-матрица <tex> D </tex> диагональна, <tex> D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.

=== Решение МНК через сингулярное разложение ===

Найдем псевдо-обратную матрицу: <tex> F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j^T </tex>.

Теперь зная псевдо-обратную матрицу, найдем решение задачи наименьших квадратов: <tex> \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) </tex>.

Найдем вектор, которым наша линейная модель аппроксимирует целевой вектор <tex> y </tex>: <tex> F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) </tex>.

Квадрат нормы вектора коэффициентов: <tex> || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 </tex>.

В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.

== Проблема мультиколлинеарности и переобучения ==

Если имеются сингулярные числа, близкие к 0, то:

* матрица <tex> \sum = F^T F </tex> плохо обусловлена;
* решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты <tex> || \alpha_j || </tex> разных знаков;
* возникает переобучение: на обучении <tex> Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 </tex> мало; на контроле <tex> Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 </tex> велико.

Стратегии устранения мультиколлинеарности и переобучения:

* отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми: <tex> f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n </tex>;
* регуляризация (накладываем дополнительные ограничения на вектор коэффициентов): <tex> || \alpha || \rightarrow min </tex>;
* преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные: <tex> f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n </tex>.

== Пример кода для Scikit-learn ==

'''import''' matplotlib.pyplot '''as''' plt
'''from''' sklearn '''import''' datasets, linear_model

# generate dataset
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)

# test and train data sizes
train_size = 700
test_size = 300

# split the data into training/testing sets
X_train = X[:-train_size]
X_test = X[-test_size:]

# split the targets into training/testing sets
y_train = y[:-train_size]
y_test = y[-test_size:]

# create linear regression object
regr = linear_model.LinearRegression()

# train the model using the training sets
regr.fit(X_train, y_train)

# make predictions using the testing set
y_pred = regr.predict(X_test)

# plot outputs
plt.scatter(X_test, y_test, color='red', s=5)
plt.plot(X_test, y_pred, color='blue', linewidth=2)

plt.xticks(())
plt.yticks(())

plt.show()

Возможный результат исполнения программы:

[[Файл: Linear_regression_example.png]]

==См. также==

* [[Общие понятия]]
* [[Вариации регрессии]]
* [[Логистическая регрессия]]
* [[Обзор библиотек для машинного обучения на Python]]

==Источники информации==
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F machinelearning.ru {{---}} Многомерная линейная регрессия]
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29 machinelearning.ru {{---}} Линейная регрессия (пример)]
* [https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie/home/info Coursera {{---}} "Введение в машинное обучение", Неделя 4, ]
* [http://www.ccas.ru/voron/download/Regression.pdf Лекции по алгоритмам восстановления регрессии К. В. Воронцов]
* [https://scikit-learn.org/stable/auto_examples/linear_model/plot_ols.html#sphx-glr-auto-examples-linear-model-plot-ols-py Scikit-Learn {{---}} Linear Regression Example]

[[Категория: Машинное обучение]]
[[Категория: Регрессия]]

Линейная регрессия

2019-03-12T11:54:22Z

Zem4ik:

'''Линейная регрессия''' (англ. ''linear regression'') — метод восстановления зависимости одной (объясняемой, зависимой) переменной <tex> y </tex> от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) <tex> x </tex> с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной <tex> y </tex> по значениям независимой переменной <tex> x </tex>.

== Задача ==

==== Дано ====

* <tex> f_1(x), \dots ,f_n(x) </tex> - числовые признаки
* модель многомерной линейной регрессии:
<center> <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, </center>
где <tex> a \in R^n </tex>
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>
* <tex> x_i </tex> - объекты из множества <tex> X = R^n </tex>
* <tex> y_i </tex> - объекты из множества <tex> X = R </tex>

==== Матричные обозначения ====

Перейдем к матричным обозначениям:

<tex>
\underset{l \times n}{F} =
\begin{pmatrix}
f_1(x_1) & \dots & f_n(x_1) \\
\dots & \dots & \dots \\
f_n(x_1) & \dots & f_n(x_l)
\end{pmatrix}
,

\underset{l \times 1}{y} =
\begin{pmatrix}
y_1 \\
\dots \\
y_l
\end{pmatrix},

\underset{n \times 1}{\alpha} =
\begin{pmatrix}
\alpha_1 \\
\dots \\
\alpha_l
\end{pmatrix}

</tex>

, где
* <tex> F </tex> - матрица объектов-признаков, где строки соответствуют объектам а столбцы - признакам
* <tex> y </tex> - вектор ответов, или целевой вектор
* <tex> \alpha </tex> - вектор коэффициентов

==== Постановка задачи ====

В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:

<tex> Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} </tex>

Необходимо найти вектор <tex> \alpha </tex> при известной матрице <tex> F </tex> и известном вектор-столбце <tex> y </tex>.

== Решение ==

=== Нормальная система уравнений ===

Запишем необходимые условия минимума в матричном виде.

<tex> \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 </tex>

Отсюда следует нормальная система задачи МНК:

<tex> F^T F \alpha = F^T y </tex>,

где <tex> F^T F - n \times n </tex> матрица

Мы получили систему уравнений, откуда можем выразить искомый вектор <tex> \alpha </tex>.

==== Решение системы ====
<tex> \alpha^* = (F^T F)^{-1} F^T y = F^+ y </tex>, где <tex> F^+ </tex> — псевдо-обратная матрица.

Значение функционала: <tex> Q(\alpha^*) = ||P_F y - y||^2 </tex>, где <tex> P_F = F F^+ = F (F^T F)^{-1} F^T </tex> - ''проекционная матрица''

==== Проблемы ====

В случае мультиколлинеарности (столбцы матрицы <tex> F </tex> линейно-зависимы) нам не удастся найти обратную матрицу к <tex> F^T F </tex> (она будет вырождена).

Если же столбцы матрицы <tex> F </tex> почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.

=== Сингулярное разложение ===

Воспользуемся понятием [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5/ сингулярного разложения ], которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:

<tex> F = V D U^T </tex>.

Основные свойства сингулярного разложения:

* <tex> l \times n </tex>-матрица <tex> V = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>, столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
* <tex> n \times n </tex>-матрица <tex> U = (u_1, \dots, u_n) </tex> ортогональна, <tex> U^T U = I_n </tex>, столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
* <tex> n \times n </tex>-матрица <tex> D </tex> диагональна, <tex> D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.

=== Решение МНК через сингулярное разложение ===

Найдем псевдо-обратную матрицу: <tex> F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j^T </tex>.

Теперь зная псевдо-обратную матрицу, найдем решение задачи наименьших квадратов: <tex> \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) </tex>.

Найдем вектор, которым наша линейная модель аппроксимирует целевой вектор <tex> y </tex>: <tex> F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) </tex>.

Квадрат нормы вектора коэффициентов: <tex> || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 </tex>.

В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.

== Проблема мультиколлинеарности и переобучения ==

Если имеются сингулярные числа, близкие к 0, то:

* матрица <tex> \sum = F^T F </tex> плохо обусловлена;
* решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты <tex> || \alpha_j || </tex> разных знаков;
* возникает переобучение: на обучении <tex> Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 </tex> мало; на контроле <tex> Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 </tex> велико.

Стратегии устранения мультиколлинеарности и переобучения:

* отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми: <tex> f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n </tex>;
* регуляризация (накладываем дополнительные ограничения на вектор коэффициентов): <tex> || \alpha || \rightarrow min </tex>;
* преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные: <tex> f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n </tex>.

== Пример кода для Scikit-learn ==

'''import''' matplotlib.pyplot '''as''' plt
'''from''' sklearn '''import''' datasets, linear_model

# generate dataset
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)

# test and train data sizes
train_size = 700
test_size = 300

# split the data into training/testing sets
X_train = X[:-train_size]
X_test = X[-test_size:]

# split the targets into training/testing sets
y_train = y[:-train_size]
y_test = y[-test_size:]

# create linear regression object
regr = linear_model.LinearRegression()

# train the model using the training sets
regr.fit(X_train, y_train)

# make predictions using the testing set
y_pred = regr.predict(X_test)

# plot outputs
plt.scatter(X_test, y_test, color='red', s=5)
plt.plot(X_test, y_pred, color='blue', linewidth=2)

plt.xticks(())
plt.yticks(())

plt.show()

Возможный результат исполнения программы:

[[Файл: Linear_regression_example.png]]

==См. также==

* [[Общие понятия]]
* [[Вариации регрессии]]
* [[Логистическая регрессия]]
* [[Обзор библиотек для машинного обучения на Python]]

==Источники информации==
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F machinelearning.ru {{---}} Многомерная линейная регрессия]
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29 machinelearning.ru {{---}} Линейная регрессия (пример)]
* [https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie/home/info Coursera {{---}} "Введение в машинное обучение", Неделя 4, ]
* [http://www.ccas.ru/voron/download/Regression.pdf Лекции по алгоритмам восстановления регрессии К. В. Воронцов]
* [https://scikit-learn.org/stable/auto_examples/linear_model/plot_ols.html#sphx-glr-auto-examples-linear-model-plot-ols-py Scikit-Learn {{---}} Linear Regression Example]

[[Категория: Машинное обучение]]
[[Категория: Регрессия]]

Линейная регрессия

2019-03-12T11:47:51Z

Zem4ik:

'''Линейная регрессия''' (англ. ''linear regression'') — метод восстановления зависимости одной (объясняемой, зависимой) переменной <tex> y </tex> от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) <tex> x </tex> с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной <tex> y </tex> по значениям независимой переменной <tex> x </tex>.

== Задача ==

==== Дано ====

* <tex> f_1(x), \dots ,f_n(x) </tex> - числовые признаки
* модель многомерной линейной регрессии:
<center> <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, </center>
где <tex> a \in R^n </tex>
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>
* <tex> x_i </tex> - объекты из множества <tex> X = R^n </tex>
* <tex> y_i </tex> - объекты из множества <tex> X = R </tex>

==== Матричные обозначения ====

Перейдем к матричным обозначениям:

<tex>
\underset{l \times n}{F} =
\begin{pmatrix}
f_1(x_1) & \dots & f_n(x_1) \\
\dots & \dots & \dots \\
f_n(x_1) & \dots & f_n(x_l)
\end{pmatrix}
,

\underset{l \times 1}{y} =
\begin{pmatrix}
y_1 \\
\dots \\
y_l
\end{pmatrix},

\underset{n \times 1}{\alpha} =
\begin{pmatrix}
\alpha_1 \\
\dots \\
\alpha_l
\end{pmatrix}

</tex>

, где
* <tex> F </tex> - матрица объектов-признаков, где строки соответствуют объектам а столбцы - признакам
* <tex> y </tex> - вектор ответов, или целевой вектор
* <tex> \alpha </tex> - вектор коэффициентов

==== Постановка задачи ====

В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:

<tex> Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} </tex>

Необходимо найти вектор <tex> \alpha </tex> при известной матрице <tex> F </tex> и известном вектор-столбце <tex> y </tex>.

== Решение ==

=== Нормальная система уравнений ===

Запишем необходимые условия минимума в матричном виде.

<tex> \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 </tex>

Отсюда следует нормальная система задачи МНК:

<tex> F^T F \alpha = F^T y </tex>,

где <tex> F^T F - n \times n </tex> матрица

Мы получили систему уравнений, откуда можем выразить искомый вектор <tex> \alpha </tex>.

==== Решение системы ====
<tex> \alpha^* = (F^T F)^{-1} F^T y = F^+ y </tex>, где <tex> F^+ </tex> — псевдо-обратная матрица.

Значение функционала: <tex> Q(\alpha^*) = ||P_F y - y||^2 </tex>, где <tex> P_F = F F^+ = F (F^T F)^{-1} F^T </tex> - ''проекционная матрица''

==== Проблемы ====

В случае мультиколлинеарности (столбцы матрицы <tex> F </tex> линейно-зависимы) нам не удастся найти обратную матрицу к <tex> F^T F </tex> (она будет вырождена).

Если же столбцы матрицы <tex> F </tex> почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.

=== Сингулярное разложение ===

Воспользуемся понятием [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5/ сингулярного разложения ], которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:

<tex> F = V D U^T </tex>.

Основные свойства сингулярного разложения:

* <tex> l \times n </tex>-матрица <tex> V = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>, столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
* <tex> n \times n </tex>-матрица <tex> U = (u_1, \dots, u_n) </tex> ортогональна, <tex> U^T U = I_n </tex>, столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
* <tex> n \times n </tex>-матрица <tex> D </tex> диагональна, <tex> D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.

=== Решение МНК через сингулярное разложение ===

Найдем псевдо-обратную матрицу: <tex> F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j^T </tex>.

Теперь зная псевдо-обратную матрицу, найдем решение задачи наименьших квадратов: <tex> \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) </tex>.

Найдем вектор, которым наша линейная модель аппроксимирует целевой вектор <tex> y </tex>: <tex> F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) </tex>.

Квадрат нормы вектора коэффициентов: <tex> || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 </tex>.

В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.

== Проблема мультиколлинеарности и переобучения ==

Если имеются сингулярные числа, близкие к 0, то:

* матрица <tex> \sum = F^T F </tex> плохо обусловлена;
* решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты <tex> || \alpha_j || </tex> разных знаков;
* возникает переобучение: на обучении <tex> Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 </tex> мало; на контроле <tex> Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 </tex> велико.

Стратегии устранения мультиколлинеарности и переобучения:

* отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми: <tex> f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n </tex>;
* регуляризация (накладываем дополнительные ограничения на вектор коэффициентов): <tex> || \alpha || \rightarrow min </tex>;
* преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные: <tex> f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n </tex>.

== Пример кода для Scikit-learn ==

'''import''' matplotlib.pyplot '''as''' plt
'''from''' sklearn '''import''' datasets, linear_model

# generate dataset
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)

# test and train data sizes
train_size = 700
test_size = 300

# split the data into training/testing sets
X_train = X[:-train_size]
X_test = X[-test_size:]

# split the targets into training/testing sets
y_train = y[:-train_size]
y_test = y[-test_size:]

# create linear regression object
regr = linear_model.LinearRegression()

# train the model using the training sets
regr.fit(X_train, y_train)

# make predictions using the testing set
y_pred = regr.predict(X_test)

# plot outputs
plt.scatter(X_test, y_test, color='red', s=5)
plt.plot(X_test, y_pred, color='blue', linewidth=2)

plt.xticks(())
plt.yticks(())

plt.show()

Возможный результат исполнения программы:

[[Файл: Linear_regression_example.png]]

==См. также==

* [[Общие понятия]]
* [[Вариации регрессии]]
* [[Логистическая регрессия]]
* [[Обзор библиотек для машинного обучения на Python]]

Линейная регрессия

2019-03-12T11:44:20Z

Zem4ik: /* Пример кода для Scikit-learn */

'''Линейная регрессия''' (англ. ''linear regression'') — метод восстановления зависимости одной (объясняемой, зависимой) переменной <tex> y </tex> от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) <tex> x </tex> с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной <tex> y </tex> по значениям независимой переменной <tex> x </tex>.

== Задача ==

==== Дано ====

* <tex> f_1(x), \dots ,f_n(x) </tex> - числовые признаки
* модель многомерной линейной регрессии:
<center> <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, </center>
где <tex> a \in R^n </tex>
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>
* <tex> x_i </tex> - объекты из множества <tex> X = R^n </tex>
* <tex> y_i </tex> - объекты из множества <tex> X = R </tex>

==== Матричные обозначения ====

Перейдем к матричным обозначениям:

<tex>
\underset{l \times n}{F} =
\begin{pmatrix}
f_1(x_1) & \dots & f_n(x_1) \\
\dots & \dots & \dots \\
f_n(x_1) & \dots & f_n(x_l)
\end{pmatrix}
,

\underset{l \times 1}{y} =
\begin{pmatrix}
y_1 \\
\dots \\
y_l
\end{pmatrix},

\underset{n \times 1}{\alpha} =
\begin{pmatrix}
\alpha_1 \\
\dots \\
\alpha_l
\end{pmatrix}

</tex>

, где
* <tex> F </tex> - матрица объектов-признаков, где строки соответствуют объектам а столбцы - признакам
* <tex> y </tex> - вектор ответов, или целевой вектор
* <tex> \alpha </tex> - вектор коэффициентов

==== Постановка задачи ====

В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:

<tex> Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} </tex>

Необходимо найти вектор <tex> \alpha </tex> при известной матрице <tex> F </tex> и известном вектор-столбце <tex> y </tex>.

== Решение ==

=== Нормальная система уравнений ===

Запишем необходимые условия минимума в матричном виде.

<tex> \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 </tex>

Отсюда следует нормальная система задачи МНК:

<tex> F^T F \alpha = F^T y </tex>,

где <tex> F^T F - n \times n </tex> матрица

Мы получили систему уравнений, откуда можем выразить искомый вектор <tex> \alpha </tex>.

==== Решение системы ====
<tex> \alpha^* = (F^T F)^{-1} F^T y = F^+ y </tex>, где <tex> F^+ </tex> — псевдо-обратная матрица.

Значение функционала: <tex> Q(\alpha^*) = ||P_F y - y||^2 </tex>, где <tex> P_F = F F^+ = F (F^T F)^{-1} F^T </tex> - ''проекционная матрица''

==== Проблемы ====

В случае мультиколлинеарности (столбцы матрицы <tex> F </tex> линейно-зависимы) нам не удастся найти обратную матрицу к <tex> F^T F </tex> (она будет вырождена).

Если же столбцы матрицы <tex> F </tex> почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.

=== Сингулярное разложение ===

Воспользуемся понятием [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5/ сингулярного разложения ], которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:

<tex> F = V D U^T </tex>.

Основные свойства сингулярного разложения:

* <tex> l \times n </tex>-матрица <tex> V = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>, столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
* <tex> n \times n </tex>-матрица <tex> U = (u_1, \dots, u_n) </tex> ортогональна, <tex> U^T U = I_n </tex>, столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
* <tex> n \times n </tex>-матрица <tex> D </tex> диагональна, <tex> D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.

=== Решение МНК через сингулярное разложение ===

Найдем псевдо-обратную матрицу: <tex> F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j^T </tex>.

Теперь зная псевдо-обратную матрицу, найдем решение задачи наименьших квадратов: <tex> \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) </tex>.

Найдем вектор, которым наша линейная модель аппроксимирует целевой вектор <tex> y </tex>: <tex> F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) </tex>.

Квадрат нормы вектора коэффициентов: <tex> || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 </tex>.

В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.

== Проблема мультиколлинеарности и переобучения ==

Если имеются сингулярные числа, близкие к 0, то:

* матрица <tex> \sum = F^T F </tex> плохо обусловлена;
* решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты <tex> || \alpha_j || </tex> разных знаков;
* возникает переобучение: на обучении <tex> Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 </tex> мало; на контроле <tex> Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 </tex> велико.

Стратегии устранения мультиколлинеарности и переобучения:

* отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми: <tex> f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n </tex>;
* регуляризация (накладываем дополнительные ограничения на вектор коэффициентов): <tex> || \alpha || \rightarrow min </tex>;
* преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные: <tex> f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n </tex>.

== Пример кода для Scikit-learn ==

'''import''' matplotlib.pyplot '''as''' plt
'''from''' sklearn '''import''' datasets, linear_model

# generate dataset
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)

# test and train data sizes
train_size = 700
test_size = 300

# split the data into training/testing sets
X_train = X[:-train_size]
X_test = X[-test_size:]

# split the targets into training/testing sets
y_train = y[:-train_size]
y_test = y[-test_size:]

# create linear regression object
regr = linear_model.LinearRegression()

# train the model using the training sets
regr.fit(X_train, y_train)

# make predictions using the testing set
y_pred = regr.predict(X_test)

# plot outputs
plt.scatter(X_test, y_test, color='red', s=5)
plt.plot(X_test, y_pred, color='blue', linewidth=2)

plt.xticks(())
plt.yticks(())

plt.show()

Возможный результат исполнения программы:

[[Файл: Linear_regression_example.png]]

Файл:Linear regression example.png

2019-03-12T11:43:39Z

Zem4ik: Zem4ik загрузил новую версию Файл:Linear regression example.png

Файл:Linear regression example.png

2019-03-12T11:31:43Z

Zem4ik:

Интегрирование/дифференцирование производящих функций

2017-06-10T20:50:09Z

Zem4ik: изменение категории

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln \dfrac{1}{1 -
s}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln \dfrac{1}{1 - s} = s^{-1} ((s - 1) \ln \dfrac{1}{1 - s} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-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</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>

Возьмем с первого слагаемого:

:<tex>(F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}</tex>

Возьмем со второго слагаемого:

:<tex>(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</tex>

Возьмем со n-го слагаемого:

:<tex>(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</tex>

Итого выходит:

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_{n-1}</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение. Значит уравнение <tex>(1)</tex> имеет однозначное решение для каждого <tex>f_0</tex>.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Производящие функции]]

Интегрирование/дифференцирование производящих функций

2017-06-10T20:46:19Z

Zem4ik: /* Решение обыкновенных дифференциальных уравнений на производящие функции */

Интегрирование/дифференцирование производящих функций

2017-06-10T20:44:46Z

Zem4ik: /* Решение обыкновенных дифференциальных уравнений на производящие функции */ маленькие изменения

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln \dfrac{1}{1 -
s}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln \dfrac{1}{1 - s} = s^{-1} ((s - 1) \ln \dfrac{1}{1 - s} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-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</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>

Возьмем с первого слагаемого:

:<tex>(F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}</tex>

Возьмем со второго слагаемого:

:<tex>(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</tex>

Возьмем со n-го слагаемого:

:<tex>(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</tex>

Итого выходит:

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_{n-1}</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана. Значит уравнение <tex>(1)</tex> имеет однозначное решение для каждого <tex>f_0</tex>.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T20:35:54Z

Zem4ik: добавление дробей вместо указания степени (-1)

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln \dfrac{1}{1 -
s}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln \dfrac{1}{1 - s} = s^{-1} ((s - 1) \ln \dfrac{1}{1 - s} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-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</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>

Возьмем с первого слагаемого:

:<tex>(F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}</tex>

Возьмем со второго слагаемого:

:<tex>(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</tex>

Возьмем со n-го слагаемого:

:<tex>(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</tex>

Итого выходит:

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T20:12:10Z

Zem4ik: /* Решение обыкновенных дифференциальных уравнений на производящие функции */ добавление пояснения

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-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</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>

Возьмем с первого слагаемого:

:<tex>(F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}</tex>

Возьмем со второго слагаемого:

:<tex>(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</tex>

Возьмем со n-го слагаемого:

:<tex>(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</tex>

Итого выходит:

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T19:38:26Z

Zem4ik: /* Решение обыкновенных дифференциальных уравнений на производящие функции */ fix

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-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</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T19:16:31Z

Zem4ik: /* Пример 3 */ fix

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-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</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T19:04:36Z

Zem4ik: fix

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>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}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-ln(1 - t) = ln((1 - t)^{-1}) = t + \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 + \dfrac{1}{4}t^4 + \dots</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T17:18:41Z

Zem4ik: Добавлен источник

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> - производящая функция.

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>G(z) = \dfrac{1}{3} \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \dfrac{1}{1 + z} + \dfrac{7}{9} \dfrac{1}{1 - 2 z}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся разложением экспоненты:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-ln(1 - t) = ln(1 - t)^{-1} = t + \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 + \dfrac{1}{4}t^4 + \dots</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> --- производящая функция двух переменных, являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T17:05:56Z

Zem4ik: Добавление 3-го примера

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> - производящая функция.

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>G(z) = \dfrac{1}{3} \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \dfrac{1}{1 + z} + \dfrac{7}{9} \dfrac{1}{1 - 2 z}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

===Пример 3===

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся разложением экспоненты:

:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>

Разложение экспоненты начинается с 1, поэтому аргумент логарифма нужно сдвинуть в 1:

:<tex>ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>

(свободный член в разложении равен <tex>0</tex>, поскольку <tex>ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем

:<tex>\dfrac{d}{dt} ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,

откуда, интегрируя,

:<tex>ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>

Чаще используется следующий вариант:

:<tex>-ln(1 - t) = ln(1 - t)^{-1} = t + \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 + \dfrac{1}{4}t^4 + \dots</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> --- производящая функция двух переменных, являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T16:12:10Z

Zem4ik: small fix

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> - производящая функция.

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>G(z) = \dfrac{1}{3} \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \dfrac{1}{1 + z} + \dfrac{7}{9} \dfrac{1}{1 - 2 z}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|about= О существовании и единственности решения
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> --- производящая функция двух переменных, являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T16:09:25Z

Zem4ik: добавление теоремы о решении обыкновенных дифференциальных уравнений

==Дифференцирование и интегрирование производящих функций==

{{Определение
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> - производящая функция.

''Производной'' этой функции называется функция

:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>

''Интегралом'' называется функция

:<tex>\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</tex>
}}

Операция дифференцирования обратна операции интегрирования:

:<tex>(\int\limits A(s))' = A(s)</tex>.

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.

:<tex> \int\limits A'(s) = A(s) - A(s) </tex>

===Замечание===

{{Утверждение
|statement=
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
}}

==Примеры==

===Пример 1===

Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию

:<tex> 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 </tex>

Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем

:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
s)^{-1}</tex>,

откуда

:<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.

===Пример 2===

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:

:<tex> g_0 = 1</tex>
:<tex> g_1 = 1</tex>
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>

Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

:<tex> z^0 g_0 = 1</tex>
:<tex> z^1 g_1 = z</tex>
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>

:<tex> 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 </tex>

Левая часть <tex> 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 </tex> представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:

:<tex>\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)</tex>

:<tex>\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)</tex>

:<tex>\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</tex>

Составляем уравнение:

:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:

:<tex>G(z) = \dfrac{1}{3} \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \dfrac{1}{1 + z} + \dfrac{7}{9} \dfrac{1}{1 - 2 z}</tex>

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:

:<tex>\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</tex>

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

<tex>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</tex>

Мы искали G(z) в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит

:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>

==Решение обыкновенных дифференциальных уравнений на производящие функции==

{{Теорема
|statement=
Рассмотрим обыкновенное дифференциальное уравнение

:<tex>f'(s) = F(s, f(s)) (1)</tex>

на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> --- производящая функция двух переменных, являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>

|proof=
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и

:<tex>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</tex>

Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>, получаем

:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>

Аналогично, равенство коэффициентов при <tex>s^1</tex> дает

:<tex>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</tex>

Вообще, <tex>f_n</tex> находится из уравнения

:<tex>n f_n = \dots (2)</tex>,

где точками обозначен многочлен от коэффициентов функции F и коэффициентов <tex>f_0, f_1, \dots, f_n-1</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение, и теорема доказана.

}}

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Арифметические действия с формальными степенными рядами]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Интегрирование/дифференцирование производящих функций

2017-06-10T15:11:59Z

Zem4ik: структурные измененения (добавление примера 2 и удаление информации про сходимость)