Calculadora de convolução

(a * b)[k] = Σᵢ a[i] × b[k − i] comprimento = m + n − 1

a, b

As duas sequências, digitadas como números separados por ponto e vírgula. A ordem delas não importa — a convolução é comutativa, então trocar as duas caixas devolve um resultado idêntico. Elas não precisam ter o mesmo comprimento, e qualquer uma das duas pode conter decimais ou valores negativos. Cada caixa aceita até duzentos termos.

k

O índice do termo que está sendo produzido, indo de 0 até o comprimento do resultado menos um. Ele não é impresso ao lado de cada valor, porque uma linha separada por vírgulas já tem uma ordem: o primeiro número é k = 0, o segundo é k = 1. A tabela de referência abaixo escreve os índices por extenso para o par padrão, uma linha para cada, e é lá que se olha quando a conferência é das posições.

a[i] × b[k − i]

Um produto da soma. Para cada k o índice i percorre todas as posições em que as duas sequências têm um termo, então a quantidade de produtos somados sobe de um nas pontas até o comprimento da sequência mais curta no meio. O padrão de sobreposição é a ideia inteira: uma sequência desliza ao longo da outra e os produtos são recolhidos coluna por coluna.

Σᵢ

A soma sobre esses produtos, que é um termo do resultado. Cada termo é arredondado em seis casas decimais, e a soma relatada ao lado da sequência é a soma desses termos já arredondados, e não dos não arredondados — por isso somar os números impressos no painel dá exatamente o total impresso.

m + n − 1

O comprimento do resultado, relatado como uma leitura própria. Duas sequências de três dão cinco termos; um único número convoluído com uma sequência de três termos dá três. Os termos extras além da mais longa das duas são o que fazem desta a convolução completa, e não daquele tipo que guarda apenas a parte em que as sequências se sobrepõem por inteiro.

Use esta página quando duas sequências precisarem ser combinadas em uma distribuição: o número de maneiras de dois dados somarem cada total, o efeito de uma janela deslizante de média móvel sobre uma série, os coeficientes do produto de dois polinômios. Quando a pergunta for sobre uma sequência sozinha — os termos dela, a soma dela, o padrão dela —, a calculadora de sequências cobre isso, e quando o que você está escolhendo é a janela de uma média móvel, a calculadora de média é a página que dá nome a ela.

1. Um, dois, três contra quatro, cinco, seis

   1. k = 0: só os primeiros termos se sobrepõem, então 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: só os últimos termos se sobrepõem, 3 × 6 = 18
   6. O resultado é 4, 13, 28, 27, 18 e o total dele é 90, que também é 6 × 15

   A última linha é a conferência que torna esta página fácil de confiar: a soma de uma convolução é sempre o produto das somas das duas sequências, aqui 1 + 2 + 3 = 6 contra 4 + 5 + 6 = 15. Isso cai da própria álgebra, porque cada produto do resultado é o produto de um termo de cada sequência e cada par possível aparece exatamente uma vez.

2. Dois dados e o formato dos totais deles

   1. Um dado tem uma maneira de mostrar cada uma das seis faces, então cada sequência é seis uns
   2. Convoluí-las conta os pares que somam cada total: k = 0 dá 1 × 1 = 1 maneira de rolar uma soma 2
   3. k = 1 dá 1 + 1 = 2 maneiras de rolar uma soma 3, e a contagem segue subindo
   4. O pico é 6, no termo do meio, que é a soma 7
   5. O resultado é 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, e o total dele é 36

   Esta é a ilustração padrão do teorema central do limite em miniatura: duas distribuições planas convoluídas dão uma triangular, e convoluir um terceiro dado arredondaria mais um pouco na direção de um sino. O total de 36 é também a conferência — o produto das duas somas é 6 × 6, que é todo par ordenado de faces, um resultado para cada.

3. Um único número escala a sequência inteira

   1. Uma sequência de um termo não tem com o que se sobrepor, então cada termo do resultado é esse termo vezes um termo da outra sequência
   2. k = 0: 2 × 1 = 2
   3. k = 1: 2 × 2 = 4
   4. k = 2: 2 × 3 = 6
   5. O resultado é 2, 4, 6 e o total é 12, que é 2 × 6

   Vale rodar o caso degenerado uma vez, porque ele mostra que a imagem do deslizamento tem fim: com uma sequência de comprimento um nunca há mais de um produto para somar, e a convolução se reduz a uma multiplicação. É a mesma razão pela qual a fórmula do comprimento m + n − 1 dá 1 + 3 − 1 = 3, e não algo maior.

Esta página calcula a convolução completa, e apenas a completa. As duas variantes que guardam só parte do resultado não são oferecidas: a que devolve uma sequência do comprimento da entrada mais longa e a que devolve apenas as posições em que as sequências se sobrepõem por inteiro. Nenhuma das duas está bem definida para duas sequências de comprimento par, e o resultado completo é o que contém as duas — as variantes mais curtas são fatias dele, e não cálculos diferentes. Cada sequência pode ter no máximo duzentos termos, e cada valor é limitado a 1.000.000 em módulo, o que é um limite de exibição: uma convolução multiplica e depois soma, então termos grandes estouram a faixa legível muito antes de estourarem um double. Todo termo do resultado é arredondado em seis casas decimais, e o total relatado é a soma dos termos arredondados, de modo que somar os números impressos à mão reproduz o total impresso, e não um total ligeiramente diferente. O resultado é uma linha de números separada por vírgulas e não é localizado: o separador entre um termo e o seguinte é uma vírgula, o separador decimal continua sendo um ponto e não há separador de milhar nenhum, então um termo de quatro dígitos é impresso como 1000 enquanto a soma logo ao lado, essa sim formatada para o português, aparece como 1.000,000000. As posições carregam os índices e não são rotuladas uma a uma; a tabela de referência dá os índices explicitamente para o par padrão.

Como convoluir duas sequências à mão?

Deslize uma sequência ao longo da outra e some os produtos em cada posição. Com 1, 2, 3 e 4, 5, 6 o primeiro termo é 1 × 4 = 4, o segundo é 1 × 5 + 2 × 4 = 13, e assim por diante até 3 × 6 = 18 na outra ponta. O resultado tem cinco termos, já que duas sequências de três convoluem para um comprimento de 3 + 3 − 1.

Como conferir se uma convolução está certa?

Some o resultado e compare com o produto das somas das duas sequências. Para 1, 2, 3 contra 4, 5, 6 isso é 90 contra 6 × 15, e os dois têm de coincidir. A razão é que cada termo do resultado é uma soma de produtos aos pares, e todo par possível das duas sequências aparece em exatamente uma dessas somas.

Por que o resultado tem mais termos do que qualquer uma das sequências?

Porque a convolução completa guarda as posições em que as sequências se sobrepõem apenas em parte. Com 1, 2, 3 contra 4, 5, 6 são cinco posições assim: uma em cada ponta, onde um único par se encontra, e três no meio, onde vários se encontram. As duas variantes mais curtas da operação — a que tem o comprimento da entrada mais longa e a que guarda só as sobreposições completas — são ambas fatias deste resultado.

O que convoluir dois dados tem a ver com probabilidade?

Ela conta os resultados. Um dado é uma sequência de seis uns, um para cada face, e convoluir essa sequência com ela mesma conta os pares ordenados que somam cada total: uma maneira de fazer 2, duas de fazer 3, subindo até seis maneiras de fazer 7 e caindo de novo. O total do resultado, 36, é o número de pares ordenados, e é por isso que dividir cada termo por ele dá a probabilidade.

Uma média móvel é uma convolução?

É. Uma média móvel pega uma janela de pesos iguais — cinco dias valendo um quinto cada, por exemplo — e a desliza ao longo da série, o que é exatamente uma convolução com essa janela como uma das duas sequências. É por isso que a operação aparece em suavização, em filtros e em processamento de imagem: o que desliza é um conjunto de pesos, e o que é suavizado é a sequência.

• 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)