Калькулятор свёртки

(a * b)[k] = Σᵢ a[i] × b[k − i] длина = m + n − 1

a, b

Две последовательности, записанные числами через точку с запятой. Порядок не важен — свёртка коммутативна, поэтому перестановка двух полей даёт тот же результат. Они не обязаны быть одной длины, и в любой из них допустимы дробные и отрицательные значения. В каждое поле помещается до двухсот чисел.

k

Индекс получаемого члена, пробегающий значения от 0 до длины результата минус один. Рядом с каждым значением он не печатается, потому что строка через запятую и так имеет порядок: первое число — это k = 0, второе — k = 1. Справочная таблица ниже выписывает индексы для пары по умолчанию, по строке на каждый, и именно туда стоит смотреть, если проверяются позиции.

a[i] × b[k − i]

Одно произведение в сумме. Для каждого k индекс i пробегает все позиции, где у обеих последовательностей есть член, поэтому число складываемых произведений растёт от единицы на концах до длины более короткой последовательности в середине. Узор перекрытия и есть вся идея: одна последовательность скользит мимо другой, а произведения собираются столбец за столбцом.

Σᵢ

Сумма этих произведений, то есть один член результата. Каждый член округляется до шести знаков после запятой, и сумма, сообщённая рядом с последовательностью, — это сумма уже округлённых членов, а не неокруглённых, поэтому сложение напечатанных на панели чисел даёт ровно напечатанную сумму.

m + n − 1

Длина результата, сообщаемая отдельным показанием. Две последовательности по три дают пять членов; одно число, свёрнутое с последовательностью из трёх членов, даёт три. Лишние члены за пределами более длинной из двух — это и есть то, что делает свёртку полной, а не той, которая оставляет только участок полного перекрытия.

Берите эту страницу, когда две последовательности нужно объединить в распределение: сколько способов у двух игральных костей дать в сумме каждое значение, как окно скользящего среднего влияет на ряд, каковы коэффициенты произведения двух многочленов. Когда вопрос про одну последовательность саму по себе — её члены, её сумму, её закономерность, — им занимается калькулятор последовательностей, а когда выбирается именно ширина окна скользящего среднего, это уже калькулятор средних.

1. Один, два, три против четырёх, пяти, шести

   1. k = 0: перекрываются только первые члены, поэтому 1 × 4 = 4
   2. k = 1: 1 × 5 + 2 × 4 = 5 + 8 = 13
   3. k = 2: 1 × 6 + 2 × 5 + 3 × 4 = 6 + 10 + 12 = 28
   4. k = 3: 2 × 6 + 3 × 5 = 12 + 15 = 27
   5. k = 4: перекрываются только последние члены, 3 × 6 = 18
   6. Результат — 4, 13, 28, 27, 18, а его сумма равна 90, то есть 6 × 15

   Последняя строка — та проверка, ради которой этой странице легко доверять: сумма свёртки всегда равна произведению сумм двух последовательностей, здесь 1 + 2 + 3 = 6 против 4 + 5 + 6 = 15. Это следствие самой алгебры: каждое произведение в результате составлено из одного члена одной последовательности и одного члена другой, и каждая такая пара встречается ровно один раз.

2. Две игральные кости и форма их сумм

   1. У игральной кости по одному способу выпасть каждой из шести граней, поэтому каждая последовательность — это шесть единиц
   2. Свёртка считает пары, дающие в сумме каждое значение: k = 0 даёт 1 × 1 = 1 способ выбросить в сумме 2
   3. k = 1 даёт 1 + 1 = 2 способа выбросить в сумме 3, и дальше количество растёт
   4. Пик равен 6, он стоит в середине и соответствует сумме 7
   5. Результат — 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, а его сумма равна 36

   Это стандартная иллюстрация центральной предельной теоремы в миниатюре: две плоские распределения после свёртки дают треугольное, а третья кость, добавленная в свёртку, скруглила бы его дальше в сторону колокола. Сумма 36 — это тоже проверка: произведение двух сумм равно 6 × 6, то есть все упорядоченные пары граней, по одному исходу на каждую.

3. Одно число масштабирует всю последовательность

   1. У последовательности из одного члена не с чем перекрываться, поэтому каждый член результата — это тот единственный член, умноженный на один член другой последовательности
   2. k = 0: 2 × 1 = 2
   3. k = 1: 2 × 2 = 4
   4. k = 2: 2 × 3 = 6
   5. Результат — 2, 4, 6, а сумма равна 12, то есть 2 × 6

   Вырожденный случай стоит прогнать один раз: он показывает, что у картинки со скольжением есть край. Когда одна последовательность имеет длину один, складывать всегда нечего, кроме одного произведения, и свёртка сводится к умножению. По той же причине формула длины m + n − 1 даёт 1 + 3 − 1 = 3, а не что-то большее.

Эта страница считает полную свёртку и только её. Два варианта, оставляющие от результата часть, не предлагаются: тот, что возвращает последовательность длиной с более длинный вход, и тот, что оставляет только позиции полного перекрытия. Ни один из них не определён толком для двух последовательностей чётной длины, а полный результат содержит их оба — короткие варианты это его срезы, а не другие вычисления. Каждая последовательность может содержать не больше двухсот чисел, а каждое значение ограничено по модулю миллионом; это ограничение показа, потому что свёртка сначала умножает, а потом складывает, и крупные члены выходят за читаемый диапазон задолго до того, как переполнят число двойной точности. Каждый член результата округляется до шести знаков после запятой, и сообщённая сумма — это сумма округлённых членов, поэтому сложение напечатанных чисел вручную воспроизводит напечатанную сумму, а не слегка другую. Результат — это строка чисел через запятую, и она не локализуется, поэтому десятичная точка остаётся точкой в любом языке. Позиции несут индексы и по отдельности не подписаны; индексы для пары по умолчанию явно выписаны в справочной таблице. И отдельно про ввод: запятая, после которой стоит ровно три цифры, не принимается, если целая часть не ноль, — запись 1,500 одинаково похожа и на 1,5, и на тысячу пятьсот, и поле отказывается угадывать, так что пишите 1500 или 1,5.

Как свернуть две последовательности вручную?

Сдвигайте одну последовательность мимо другой и складывайте произведения в каждом положении. С 1, 2, 3 и 4, 5, 6 первый член — это 1 × 4 = 4, второй — 1 × 5 + 2 × 4 = 13, и так до 3 × 6 = 18 на дальнем конце. В результате пять членов, потому что две последовательности по три дают свёртку длиной 3 + 3 − 1.

Как проверить, что свёртка посчитана верно?

Сложите результат и сравните с произведением сумм двух последовательностей. Для 1, 2, 3 против 4, 5, 6 это 90 против 6 × 15, и эти два числа обязаны совпасть. Причина в том, что каждый член результата — это сумма попарных произведений, а каждая возможная пара из двух последовательностей попадает ровно в одну из таких сумм.

Почему в результате больше членов, чем в любой из последовательностей?

Потому что полная свёртка сохраняет и те позиции, где последовательности перекрываются лишь частично. У 1, 2, 3 против 4, 5, 6 таких позиций пять: по одной на каждом конце, где встречается единственная пара, и три в середине, где пар несколько. Два коротких варианта этой операции — тот, что оставляет длину более длинного входа, и тот, что оставляет только полные перекрытия, — оба являются срезами этого результата.

При чём тут вероятность, когда сворачивают две игральные кости?

Свёртка считает исходы. Одна кость — это последовательность из шести единиц, по одной на грань, и свёртка этой последовательности с самой собой считает упорядоченные пары, дающие в сумме каждое значение: один способ получить 2, два способа получить 3, вплоть до шести способов получить 7 и дальше на спад. Сумма результата, 36, — это число упорядоченных пар, поэтому деление каждого члена на неё и даёт вероятность.

Скользящее среднее — это тоже свёртка?

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

• Convolution — the definition, the sum over overlapping products, and the length of the result — Wolfram MathWorld (United States)
• Cauchy Product — the same rule applied to the coefficients of two power series, which is what convolving two polynomial coefficient lists computes — Wolfram MathWorld (United States)
• Convolution Theorem — why the transform of a convolution is the product of the transforms, and where the operation is met in signal processing — Wolfram MathWorld (United States)