首页 > 技术文章 > 向量卷积与多项式乘法
larch18 2015-06-11 16:36 原文
对于两个离散序列f[n],g[m],可以将卷积定义为
s[k]=∑f[j]g[k-j]
回忆我们学过的多项式乘法，比如(x2+2x+1)(3x+2)
一般的计算方式是
(x2+2x+2)(3x+2) = (x2+2x+2)*3x+(x2+2x+2)*2
= 3x3+6x2+6x+2x2+4x+4
合并同类项之后
得到 3x3
6x2+2x2
6x+4x
4
----------------
3x3+8x2+10x+4
从线性代数的角度来看，多项式可以构成一个向量空间，通过选定一组基底
{1，x，x2，x3……}
就可以很容易将多项式与某维度的坐标向量相对应，这里采用降幂
1.(x2+2x+2)—>(1 2 2) ;
2.(3x+2)-à(3 2)
通过上面的卷积定义，可以得到向量卷积的定义
对于长度为m的向量u与长度为n的向量v的卷积
w(k)= ∑(u(j)*v(k+1-j)) 向量w的长度为m+n-1
ps:向量u对应的多项式最高次幂为xm-1，向量v的是 xn-1，两个多项式相乘之后最高次幂为xm+n-2，最低次幂为x0 ，也就是1，所以得到的长度为m+n-1
根据上面的向量卷积的形式来重新处理坐标向量1,2(将1倒置)
(2 2 1)*(3 2)
计算方式：
A = x =(0 0 3 2 0 0)'
b = Ax=(3 8 10 4)'
A的每一行都代表序列(2 2 1)移动一位，然后与x做内积，通过一系列的向量内积，这样也得到了多项式相乘的结果。
