2.3.1. Понятие свертки

Определение. Пусть даны два массива:

a = (…,a_-1, a₀, a₁, a₂, …), b = (…,b_-1 ,b₀,b₁, b₂, …) – конечные или бесконечные в одну или в обе стороны. Тогда сверткой последовательности a и b называется массив

c = (.., c_-1, c₀, c₁, c₂, …), где (2.5a)

т.е. суммирование производится по всевозможным сочетаниям, в которых k + l = i. Обозначается свёртка как: c = a*b.

В случае, когда последовательности (массивы) a и b бесконечны в обе стороны, выражение для c_i можно представить в виде

(2.5б)

Аналогичным образом определяется свертка для конечных массивов (в формулу (2.5.б) подставляются конечные пределы суммирования).

Пример. Даны два массива:

a = (a₀, a₁);

b = (b₀, b₁, b₂).

Определим свёртку этих массивов , используя формулу (2.5а):

c₀ = a₀b₀,

c₁ = a₀b₁ + a₁b₀,

c₂ = a₁b + a₀b₂,

c₃ = a₁b₂.

Рассмотрим классический пример свёртки.

1. При умножении многочленов:

a(x) = a₀ + a₁x + … + a_n-1 x^n-1,

bx) = b₀ + b₁x + … + b_n-1- x^n-1.

a(x)*b(x) = c(x) = c₀ + c₁x₁ + … + c_2n-2 x^{2n – 2},

c = a*b.

2. При перемножении числе столбиком (если не делать переносы в старшие разряды).

3. Пусть a и b – дискретные независимые случайные величины, такие что P(a = i) = a_i, P(b = i) = b_i. Причем a и b – обязательно независимые случайные величины (независимые случайные величины – те, для которых справедливо высказывание: P((xA) и (y B)) = P(xA) · P(y B), где x, y – значения случайных величин, А и В – некоторые множества из области значений соответствующих случайных величин).

Тогда, случайная величина c = a + b имеет распределение, которое есть ни что иное, как всёртка массивов a_i и b_i.

.