Skip to main content
700 words4 min

数学：卷积

Summary

卷积由两个函数或数列生成第三者。给出连续积分与离散求和两种定义，用翻转、平移、逐点相乘再求和解释它的直观含义，并指出多项式相乘本质就是系数做卷积。列出交换律、结合律、分配律、数乘及作为单位元的 δ 函数，比较按定义计算的 O(mn) 与用快速傅里叶变换的 O((m+n)log(m+n))。最后推广到范德蒙德卷积、狄利克雷卷积以及位运算与子集卷积。

卷积（Convolution）是通过两个函数 ff 和 gg 生成第三个函数的一种数学算子。

参考资料​

定义​

卷积（Convolution）记作 f∗gf*g。

连续卷积​

对于实变量函数 ff 和 gg：

(f∗g)(t)=∫−∞+∞f(τ)g(t−τ)dτ(f*g)(t)=\int_{-\infty}^{+\infty}f(\tau)g(t-\tau)\mathrm{d}\tau

离散卷积​

对于数列 { fn }\set{f_n} 和 { gn }\set{g_n}：

(f∗g)n=∑k=−∞+∞fkgn−k(f*g)_n=\sum_{k=-\infty}^{+\infty}f_k g_{n-k}

若 { fn }\set{f_n} 仅在 [0,m][0,m] 上非零、{ gn }\set{g_n} 仅在 [0,n][0,n] 上非零，则结果仅在 [0,m+n][0,m+n] 上非零：

(f∗g)i=∑k=0ifkgi−k(f*g)_i=\sum_{k=0}^if_k g_{i-k}

直观​

「卷积」一词来自「卷 起 + 积 分」这一动作：

  1. 把 gg 沿 yy 轴翻转，得到 g(−τ)g(-\tau)；
  2. 平移 tt 个单位，得到 g(t−τ)g(t-\tau)；
  3. 与 f(τ)f(\tau) 逐点相乘；
  4. 对 τ\tau 求积分（离散时为求和）。

随着 tt 变化，g(t−τ)g(t-\tau) 沿 τ\tau 轴滑动，与 f(τ)f(\tau) 的重叠区域随之改变，积分值即为 (f∗g)(t)(f*g)(t)。

tip

「卷」描述翻转滑动，「积」描述逐点相乘后再求和。两个动作合起来正是「卷积」。

多项式乘法​

把数列 { fn }\set{f_n} 和 { gn }\set{g_n} 视为多项式的系数：

F(x)=∑k=0mfkxk,G(x)=∑k=0ngkxkF(x)=\sum_{k=0}^mf_k x^k,G(x)=\sum_{k=0}^ng_k x^k

它们的乘积 H(x)=F(x)G(x)H(x)=F(x)G(x) 是一个 m+nm+n 次多项式，xix^i 的系数为：

hi=∑k=0ifkgi−kh_i=\sum_{k=0}^if_k g_{i-k}

这正是 { fn }\set{f_n} 与 { gn }\set{g_n} 的离散卷积。

多项式相乘，就是系数做卷积。

性质​

对函数（或数列）f,g,hf,g,h 与标量 cc：

  • 交换律：f∗g=g∗ff*g=g*f；
  • 结合律：(f∗g)∗h=f∗(g∗h)(f*g)*h=f*(g*h)；
  • 分配律：f∗(g+h)=f∗g+f∗hf*(g+h)=f*g+f*h；
  • 数乘：(cf)∗g=c(f∗g)(cf)*g=c(f*g)。

证明从定义直接展开即可。

特别地，单位元 是 狄拉克 δ 函数（连续）或 克罗内克 δ 函数（离散）：

f∗δ=ff*\delta=f

计算复杂度​

按定义直接计算长度分别为 mm 和 nn 的数列的卷积，时间复杂度为 O(mn)O(mn)。

利用 快速傅里叶变换（Fast Fourier Transform，FFT）可以降至 O((m+n)log⁡(m+n))O((m+n)\log(m+n))，是处理大规模多项式乘法的标准做法。

例题​

求 { an }={ 1,2,3 }\set{a_n}=\set{1,2,3} 与 { bn }={ 4,5,6 }\set{b_n}=\set{4,5,6} 的卷积 { cn }\set{c_n}。

按定义：

c0=a0b0=1⋅4=4c1=a0b1+a1b0=1⋅5+2⋅4=13c2=a0b2+a1b1+a2b0=1⋅6+2⋅5+3⋅4=28c3=a1b2+a2b1=2⋅6+3⋅5=27c4=a2b2=3⋅6=18\begin{aligned} c_0 & =a_0 b_0=1\cdot 4=4 \\ c_1 & =a_0 b_1+a_1 b_0=1\cdot 5+2\cdot 4=13 \\ c_2 & =a_0 b_2+a_1 b_1+a_2 b_0=1\cdot 6+2\cdot 5+3\cdot 4=28 \\ c_3 & =a_1 b_2+a_2 b_1=2\cdot 6+3\cdot 5=27 \\ c_4 & =a_2 b_2=3\cdot 6=18 \end{aligned}

即 { cn }={ 4,13,28,27,18 }\set{c_n}=\set{4,13,28,27,18}。

也可用多项式乘法验证：

(1+2x+3x2)(4+5x+6x2)=4+13x+28x2+27x3+18x4(1+2x+3x^2)(4+5x+6x^2)=4+13x+28x^2+27x^3+18x^4

系数与卷积结果一致。

推广​

将「加法」换为其他运算、或将定义域换为其他结构，可以得到一系列推广：

  • 范德蒙德卷积：组合恒等式 ∑k(mk)(nr−k)=(m+nr)\displaystyle\sum_k\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}；
  • 狄利克雷卷积：数论中按因子求和的卷积 (f∗g)(n)=∑d∣nf(d)g(nd)\displaystyle(f*g)(n)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)；
  • 位运算卷积 与 子集卷积：将下标的加法替换为 or⁡\operatorname{or}、and⁡\operatorname{and}、xor⁡\operatorname{xor} 等位运算，详见 《题解：洛谷 P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)》。