Комбинаторные алгоритмы для программистов



             

Действия над степенными рядами


Перейдем теперь к действиям над степенными рядами. Пусть функции

f(x)
и
\varphi (x)
разложены в степенные ряды

 f\left( x \right) = a_0 + a_1 x + \ldots a_n x^n + \ldots

(9.12)

 \varphi (x) = b_0 + b_1 x + \ldots b_n x^n \ldots

(9.13)

Тогда

 f(x) + \varphi (x) = (a_0 + a_1 x + \ldots a_n x^n + \ldots )+(b_0 + b_1 x + \ldots b_n x^n \ldots ).

Оказывается, что слагаемые в правой части равенства можно переставить и сгруппировать вместе члены с одинаковыми степенями

x
. Это утверждение совсем не так очевидно, как кажется на первый взгляд. Ведь в правой части равенства у нас бесконечные суммы, а в бесконечных суммах переставлять слагаемые можно далеко не всегда. После этой перегруппировки мы получим

 f(x) + \varphi (x) = (a_0 + b_0 ) + (a_1 + b_1 )x + \ldots + (a_n + b_n )x^n + \ldots

(9.14)

Ряд, стоящий в правой части равенства (9.14), называется суммой степенных рядов (9.12) и (9.13).

Посмотрим теперь, как разлагается в степенной ряд произведение функций

f(x)
и
\varphi (x)
. Мы имеем

 f(x)\varphi (x) = (a_0 + a_1 x + \ldots a_n x^n + \ldots ) \times (b_0 + b_1 x + \ldots b_n x^n \ldots ).

(9.15)

Оказывается, что как и в случае многочленов, ряды, стоящие в правой части равенства (9.15), можно почленно перемножать. Мы опускаем доказательство этого утверждения. Найдем ряд, получающийся после почленного перемножения. Свободный член этого ряда равен

a_0 b_0
. Члены, содержащие
x
, получатся дважды: при умножении
a_0
на
b_1 x
и при умножении
a_1^{} x
на
b_0
. Они дают

 a_0^{} b_1 x + a_1 b_0 x = (a_0 b_1 + a_1 b_0 )x.

Точно так же вычисляются члены, содержащие

x^2
. Таким образом,

f(x)\varphi (x) = a_0 b_0 + (a_0 b_1 + a_1 b_0 )x + \ldots + (a_0 b_n + \ldots + a_n b_0 )x^n + \ldots

(9.16)

Ряд, стоящий в правой части равенства (9.16), называется произведением рядов(9.12) и (9.13).

В частности, возводя ряд (9.12) в квадрат, получаем

 f^2 (x) = a_0^2 + 2a_0^{} a_1 x + (a_1^2 + 2a_0 a_2 )x^2 + 2(a_0 a_3^{} + a_1 a_2 )x^3 + \ldots

(9.17)

Посмотрим теперь, как делят друг на друга степенные ряды. Пусть свободный член ряда (9.13) отличен от нуля. Покажем, что в этом случае существует такой степенной ряд

c_0+c_1x+\ldots+c_nx^n+\ldots,

(9.18)

что

 (b_0 + b_1 x + \ldots + b_n x^n + \ldots ) \times (c_0^{} + c_1 x + \ldots + c_n x^n + \ldots ) = a_0 + a_1 x + \ldots + a_n x^n + \ldots

(9.19)

Для доказательства перемножим ряды в левой части этого равенства. Мы получим ряд

b_0 c_0 + (b_0 c_1 + b_1 c_0 )x + \ldots + (b_0 c_n + \ldots + b_n c_0 )x^n + \ldots

Для того чтобы этот ряд совпадал с рядом (9.12), необходимо и достаточно, чтобы выполнялись равенства

 b_0 c_0 = a_{\begin{subarray}{l} 0 \\ \end{subarray}},

b_0 c_1 + b_1 c_0 = a_1,

..........

b_0 c_n + \ldots + b_n c_0 = a_n,

..........

Эти равенства дают бесконечную систему уравнений для отыскания коэффициентов Из первого уравнения системы получаем

c_0 = \frac{{a_0 }} {{b_0 }}
. Подставим полученное значение во второе уравнение. Мы получим уравнение

b_0 c_1 = a_1 - \frac{{b_1 a_0 }}{{b_0 }},

из которого находим, что

c_1 = \frac{{a_1 b_0 - b_1 a_0 }} {{b_0^2 }}
. Вообще, если уже найдены коэффициенты
c_0,\ldots,c_{n - 1}
, то для отыскания
c_n
имеем уравнение

b_0 c_n = a_n - b_1 c_{n - 1} - \ldots - b_n c_0.

Это уравнение разрешимо, поскольку

b_0 \ne 0
.Итак, мы доказали существование ряда (9.18), удовлетворяющего соотношению (9.19). Ряд (9.18) называют частным при делении рядов (9.12) и (9.13). Можно доказать, что он получается при разложении функции
f(x)/\varphi (x)
. Таким образом, степенные ряды можно складывать, умножать и делить (последнее - при условии, что свободный член делителя отличается от нуля). Эти действия соответствуют действиям над разлагаемыми функциями.




Содержание  Назад