卷积与多项式-MATLAB指令引出的思考

这家伙很懒，除了美貌与智慧什么都没有留下...

引子

在MATLAB中，对于卷积与多项式的计算使用的一个指令： ^[1]

conv(p1,p2)

创建包含多项式 x^2+1 和 2x+7 的系数的向量 u 和 v 。

u = [1 0 1];
v = [2 7];
w = conv(u,v)
w = 1×4
     2     7     2     7

两个向量 u 和 v 的卷积，表示 v 滑过 u 时依据这些点确定的重叠部分的面积。从代数方法上讲，卷积是与将其系数为 u 和 v 元素的多项式相乘相同的运算。
m = length(u) 和 n = length(v) 。则 w 是长度为 m+n-1 且第 k 个元素为
w(k)=\sum_ju(j)v(k-j+1).
详情看官方文档.

多项式定义 ^[2]

多项式 （Polynomial）是代数学中的基础概念，是由称为 未知数 的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式。多项式是整式的一种。未知数只有一个的多项式称为一元多项式；例如 x^2-3x+4 就是一个三项一元二次多项式。未知数不止一个的多项式称为多元多项式，例如 x^{3}+2y-3z 就是一个三项三元三次多项式，一个多项式就几次取决于最高的那个项的次数。( xy 属于二次)可以写成只由一项构成的多项式也称为 单项式 。如果一项中不含未知数，则称之为 常数项 。

多项式的定义较为简单，下面来看看它的运算。

多项式运算

多项式 A_k(x)=a_0x^0+a_1x^1+a_2x^2+...+a_kx^k=\sum_{i=0}^ka_ix^i

多项式 B_k(x)=b_0x^0+b_1x^1+b_2x^2+...+b_kx^k=\sum_{i=0}^kb_ix^i

多项式的乘法 A_k(x)\cdot B_k(x)=(\sum_{i=0}^ka_ix^i)\cdot(\sum_{i=0}^kb_ix^i) ，就是下面的运算：

(a_0x^0+a_1x^1+a_2x^2+...+a_kx^k)\cdot(b_0x^0+b_1x^1+b_2x^2+...+b_kx^k) ，这个运算是把同幂次的项目，结果为：

a_0b_0x^0+(a_0b_1+a_1b_0)x^1+(a_0b_2+a_1b_1+a_2b_0)x^2+...+\sum_{i+j=k}(a_ib_j)x^k+... ，即 A(x)\cdot B(x)=\sum_{i=0}^{2k}\sum_{u+v=i}(a_ub_v)x^i ，这个是说明，对于固定的幂次 i 而言，把这个幂次 i 无需拆分为两部分的和也就是最终的结果。上面的结果也可以写成下面的形式：

A(x)\cdot B(x)=\sum_{i=0}^{2k}\sum_{j=0}^i(a_jb_{i-j})x^i

很有趣的一点是，多项式串起来是幂级数，在组合数学里面有一种特殊的幂级数称为形式幂级数，这些运算都是一致的。

卷积定义 ^[3]

卷积是数学分析中一种重要的运算。设： f(x) 、 g(x) 是 \mathbb {R} 上的两个可积函数，作积分：
\int _{-\infty }^{\infty }f(\tau )g(x-\tau )\,\mathrm {d} \tau
可以证明，关于几乎所有的 x\in (-\infty ,\infty ) ，上述积分是存在的。这样，随着 x
的不同取值，这个积分就定义了一个新函数 h(x) ，称为函数 f 与 g 的卷积，记为 h(x)=(f*g)(x) 。我们可以轻易验证： (f*g)(x)=(g*f)(x) ，并且 (f*g)(x) 仍为可积函数。这就是说，把卷积代替乘法， L^{1}(R^{1}) 空间是一个代数，甚至是巴拿赫代数。虽然这里为了方便我们假设 f,g\in L^{1}(\mathbb {R} ) ，不过卷积只是运算符号，理论上并不需要对函数 f,g 有特别的限制，虽然常常要求 f,g 至少是可测函数（measurable function）（如果不是可测函数的话，积分可能根本没有意义），至于生成的卷积函数性质会在运算之后讨论。
卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，利用此一性质，能简化傅里叶分析中的许多问题。
由卷积得到的函数 f*g 一般要比 f 和 g 都光滑。特别当 g 为具有紧支集的光滑函数， f 为局部可积时，它们的卷积 f*g 也是光滑函数。利用这一性质，对于任意的可积函数 f ，都可以简单地构造出一列逼近于 f 的光滑函数列 f_s ，这种方法称为函数的光滑化或正则化。卷积的概念还可以推广到数列、测度以及广义函数上去。

综上所述，也就是 h(x)=\int _{-\infty }^{\infty }f(\tau )g(x-\tau )\,\mathrm {d} \tau 这样的运算称为卷积， h(x) 是 f(x)、g(x) 卷积后的函数， h(x)=(f*g)(x) 。

二者之间的关系

设多项式为 A(x)=\sum_{i=0}^\infty a_ix^i 和 B(x)=\sum_{i=0}^\infty b_ix^i 观察两个表达式:

A(x)\cdot B(x)=\sum_{i=0}^{\infty}\sum_{j=0}^i(a_jb_{i-j})x^i 和 h(x)=\int _{-\infty }^{\infty }f(\tau )g(x-\tau )\,\mathrm {d} \tau

其实二者之间的运算是一样的形式，积分代表了无限小的求和，在计算机中的运算，分隔的足够小就可以作为积分运算的结果了。所以对于二者，仅仅定义域不同，多项式的定义域是在整数域 \mathbb {Z} ，卷积运算则定义在实数域 \mathbb{R} ，二者之间的算法是通用的。

算法

对于MATLAB的conv命令的用法，C=CONV（A，B，SHAPE）会返回二者卷积SHAPE大小的一段，SHAPE参数的取值如下：

full 全卷积（默认值）。

>> a=[0,1,2,3]
     0     1     2     3
>> b = [3,2,1]
     3     2     1
>> conv(a,b,'full')
ans =
     0     3     8    14     8     3
>> conv(a,b)
ans =
     0     3     8    14     8     3

same 与A 大小相同的卷积的中心部分。

>> conv(a,b,'same')
ans =
     3     8    14     8

valid 仅计算的没有补零边缘的卷积部分。使用此选项时，length(C) 是 max(length(A)-length(B)+1,0)，但 length(B) 为零时除外。如果length(B) = 0，则 length(C) = length(A)。

>> conv(a,b,'valid')
ans =
     8    14

上面的话虽然是人话，但是过程不是很容易懂，下面来看看卷积的过程。

从这个卷积过程可以看出，卷积的步骤首先要固定一个B不动，即conv的第二个参数，将conv的第一个参数A先进行逆序翻转，之后一步一步的滑动，之前有在其他的书上看过褶积，滑积的翻译，不过忘了哪本书了。接着不断滑动的过程也就是得到结果的步骤，结果是各个同列的数据的对应的乘积和，即图中的黄色的部分。在MATLAB中的 valid 参数也就是对于A来说，不需要补充0的部分， 即对于B中的每一个数字，都有一个A中的数字与其匹配 （在同一列）。这样从头滑到尾，很容易发现，滑动的次数也就是卷据的项数。

下面来看看MATLAB里面的关于conv的代码。

中间的那段注释的大致意思如下：CONV（Convolution and polynomial multiplication，卷积和多项式相乘）。C=CONV（A，B）会返回矢量A和B的乘积，结果向量的长度为MAX（[LENGTH(A)+LENGTH(B)-1,LENGTH(A),LENGTH(B)]）。如果A和B是多项式的系数，他们的卷积也就等于这两个多项式的乘积。

function c = conv(a, b, shape)
%CONV Convolution and polynomial multiplication.
%   C = CONV(A, B) convolves vectors A and B.  The resulting vector is
%   length MAX([LENGTH(A)+LENGTH(B)-1,LENGTH(A),LENGTH(B)]). If A and B are
%   vectors of polynomial coefficients, convolving them is equivalent to
%   multiplying the two polynomials.
%   C = CONV(A, B, SHAPE) returns a subsection of the convolution with size
%   specified by SHAPE:
%     'full'  - (default) returns the full convolution,
%     'same'  - returns the central part of the convolution
%               that is the same size as A.
%     'valid' - returns only those parts of the convolution 
%               that are computed without the zero-padded edges. 
%               LENGTH(C)is MAX(LENGTH(A)-MAX(0,LENGTH(B)-1),0).
%   Class support for inputs A,B: 
%      float: double, single
%   See also DECONV, CONV2, CONVN, FILTER, XCORR, CONVMTX.
%   Note: XCORR and CONVMTX are in the Signal Processing Toolbox.
if ~isvector(a) || ~isvector(b)
  error(message('MATLAB:conv:AorBNotVector'));
if nargin < 3
    shape = 'full';
if ~ischar(shape) && ~(isstring(shape) && isscalar(shape))
  error(message('MATLAB:conv:unknownShapeParameter'));
if isstring(shape)
    shape = char(shape);
% compute as if both inputs are column vectors
c = conv2(a(:),b(:),shape);
% restore orientation
if shape(1) == 'f' || shape(1) == 'F'  %  shape 'full'
    if length(a) > length(b)
        if size(a,1) == 1 %row vector
            c = c.';
        if size(b,1) == 1 %row vector
            c = c.';
    if size(a,1) == 1 %row vector
        c = c.';

分析

1-首先conv的参数应该是两个向量，不能是矩阵

if~isvector(a)||~isvector(b)
      error(message('MATLAB:conv:AorBNotVector'));
end

如果输入是矩阵那么报错：（x为矩阵）

>> conv(a,x)
错误使用 conv (line 28)
A 和 B 必须为向量。

2.可以接受三个参数，当接受两个参数的时候，默认第三个参数为 full ，并且

if nargin < 3
    shape = 'full';
if ~ischar(shape) && ~(isstring(shape) && isscalar(shape))
  error(message('MATLAB:conv:unknownShapeParameter'));
if isstring(shape)
    shape = char(shape);
end

3.MATLAB的conv2 函数是一个内置函数，意思也就是不提供源代码，是来返回两个矩阵的二维卷积。

%CONV2 Two dimensional convolution.
%   C = CONV2(A, B) performs the 2-D convolution of matrices A and B.
%   If [ma,na] = size(A), [mb,nb] = size(B), and [mc,nc] = size(C), then
%   mc = max([ma+mb-1,ma,mb]) and nc = max([na+nb-1,na,nb]).
%   C = CONV2(H1, H2, A) first convolves each column of A with the vector
%   H1 and then convolves each row of the result with the vector H2.  If
%   n1 = length(H1), n2 = length(H2), and [mc,nc] = size(C) then
%   mc = max([ma+n1-1,ma,n1]) and nc = max([na+n2-1,na,n2]).
%   CONV2(H1, H2, A) is equivalent to CONV2(H1(:)*H2(:).', A) up to
%   round-off.
%   C = CONV2(..., SHAPE) returns a subsection of the 2-D
%   convolution with size specified by SHAPE:
%     'full'  - (default) returns the full 2-D convolution,
%     'same'  - returns the central part of the convolution
%               that is the same size as A.
%     'valid' - returns only those parts of the convolution
%               that are computed without the zero-padded edges.
%               size(C) = max([ma-max(0,mb-1),na-max(0,nb-1)],0).

引子

多项式定义 [2]

多项式运算

卷积定义 [3]

二者之间的关系

算法

多项式定义 ^[2]

卷积定义 ^[3]