这一讲介绍卷积的计算，卷积的计算呢
可以有蛮力的算法。这是两个向量， 如果这两个向量要做卷积计算的时候，
就可以把它看成两个多项式， 就是A（x）和B（x）两个多项式。
因为卷积它的分量正好是这两个多项式相乘的系数。
那这里边就是产生的那个C（x）这个多项式。
它这个多项式的0次方就是a0 b0 x
1次方的系数正好是卷积的 一个分量，就是C1。
那么一直到它最后的这个系数，啊，
把这个系数都计算出来以后呢，相当于我们就知道了这个卷积的值。
下面看一下这个结果，我们就把卷积计算 整个看作多项式相乘做计算就可以了。
而这个多项式相乘呢，它的时间呢是n平方，因为
这里边的每个系数和这里边的每个系数都要乘一次，至少要做n平方次乘法。
下面考虑一下计算2n减1次多项式的算法。
首先先选择2n的值，对A和B这两个多项式
在这2n个值上进行求值，这是第一步。
第二步，对刚才得到这些个值对应的做乘法，
得到C（x）在这2n个 数上的值。大家可以看到这里边的A
和B的这些个值，A（xj）和B（xj）刚才都计算过了。
我只要做一次乘法就得到一个C
在xj的值，那么你换了xj以后就得到另外的xj的值。
这就是它的乘积来计算C 的值。那么这是一个多项式，C（x）这个多项式
在这2n个数的值可以通过这个办法得到了。
那么知道一个多项式在这些个数的值可以使用插值的办法，
把这个多项式的系数算出来。那么通常的插值呢，
比如说m次的多项式，我只要知道它的m加1个值，
就可以把这个多项式的系数算出来。因此我们通过插值的办法呢可以把C（x）的系数算出来。
那这三步最终做了什么事情呢，就是已知A（x）和B（x）这两个多项式，
我们最终计算了它的乘积C（x），啊，这就是它的算法的过程。
那这里边有主要的操作，一个是这个是多项式求值，A和B都需要对
这2n个数来进行求值。
下面就是，第二个是多项式插值的操作。插值的操作
它也可以通过多项式求值来做到，因此 这个算法的关键是这些个x值怎么选
使得你后面的插值可以通过插值的办法把多项式的系数算出来，
这是一个问题。第二个问题呢就是它主要的操作是多项式求值的操作，第一步是
这一步插值的办法，还是多项式求值的操作，因此它需要
找一个高效的多项式求值的算法。这里是一个
高斯滤波的权函数，这个权函数是一个ex的函数 那么它的中间会很高，边上的点会比较低。
在这个情况下，就是说我们把中间这个值作为主要的成分，而边上
点的影响是一个次要的成分。那整个这个权函数呢，就是体现在
这个量上，一共是2k加1个分量， 用这个分量对原来的这个信号进行平滑。
那这里边的这个z它是一个归一化处理的参数。
通过这个z使得所有的权值，就这些个 权值的总和加起来正好等于1。
那第i个分量通过这样的 权值平滑处理以后它得到的是ai’。
ai’呢正好是一个卷积运算，就是把这个权值
和原来的向量进行卷积运算就可以得到它的处理的这个结果。
下面我们看一下这2n个数的选择。
2n个的选择呢选的是1的2n次根。
这是在iii中去
求根计算，它可以根据这个公式来算，这个i是 根号负1，那么这里边的j
可以取得0到2n减1，有2n种取值。
那么每取一个值就得到一个根，一共是2n个根。
如果看一个具体的例子，当n等于4的时候，应该是
开8次方，有8个根，这个8个根分布在这个复平面上，
正好构成一个单位圆上的八个点，这是第一个根w0、w1，一直到w7。
这就是按照刚才的公式把这八个根给算出来了，这是w0，w1，
啊，一直到最后，w7，啊，正好是单位圆上的八个点。
下面我们看到这个快速傅立叶变换，它的
设计思想。首先呢是刚才讲到的要对这样的
2n个数进行求值，这2n个数是什么呢？ 是1开2n次方的2n个根。
计算多项式A在这些个 数上的值，计算多项式B在这些个数上的值，这是第一步。
第二步呢，我们利用这些个得到的A的值和B的值，每个都是2n个值，
对应相乘得出C这个 多项式在这些个数上的值。
那么得到的这个第一个就是
A的第一个值和B的第一个值，得到的就是 d0，然后这个w1上的
两个对应的Aw1和Bw1乘起来就是C的值，d1。
同样的，到最后一个，就是在最后这个w 2n减1，
A在它的值和B在它的值乘起来 就是得到的就是C在w
2n减1的值，这是d 2n减1。
那这一步的做法主要是做乘法，就是把A的每个值和B的每个值
乘一次就得到一个C的值，一共要做2n次乘法。
下边看第三步。
当我得到了这些个d0、d1到d 2n减1，
它是多项式C在这些个数上的值。
然后利用插值的办法我们来计算C的系数。
这个插值的办法怎么做呢？我们拿刚才得到的这些d0、d1到 d
2n减1，把它作为系数先做一个新的多项式。
这个多项式叫D（x），刚好刚才这些个值，C的这些个值在这里边变成了系数。
当得到这个多项式以后，我们可以做下面的算法。对这个多项式
再计算这些d在这些个数上的值，再把它算出来。
那么这是它在第一个数1，在它的值，然后计算它在
w1的值，最后算它在w 2n减1也就是这个数的值，
把它算出来，所以还是做的多项式求值的工作。那么这样算出来，这些个值
和C的系数有什么关系呢？它存在着下边的关系。
可以证明，这是D刚才计算的 D这个多项式的值恰好和原来C多项式的那些个系数
成立着这样的等式关系。那么根据这个等式关系呢，我们只要把它
变形一下，通过左边的这些个数就可以把对应的c0到c1全部计算出来。
那这个c0呢就可以用D1除以2n，就是 它除它，同样的，c
2n减1这个数 等于Dw1除以2n就可以了。所以我们把左边的这个都，
对应的都除一次，所得到的c就出来了。
而这个c是什么呢？正是所需要的这个多项式的系数。
啊，也就是我们把这个数就算出来了。这个是具体的插值的方法。
算法的关键是什么呢？我们可以分析一下。
这个x是所需要的那2n个数。
在这个数的情况下，我们先对A（x），B（x）
来求值，在这2n个数中求值，所以这个求值是一个关键的步骤。
那么第二步呢，是做2n次乘法。
得到的那些个A和B的值，每一对值乘一次乘一次就得到了
Cx的在这些个数的值，这里边关键做的是乘法运算。
第三步呢，是对2n个x 做一个多项式D（x）。
那么做了D（x）以后，对D（x）再进行求值，
它要计算D（x）在这些个数上的值，
这是第三步。那么，D（x）这个多项式是怎么得到的呢，就是由刚才
计算出来的那个C的那些个值，把它作为D（x）的 系数得到的这个多项式，那么对这个多项式还要求值。
所以我们看到这里边的关键操作，这里是一个多项式求值操作，
在插值的时候也是多项式的求值操作，这个地方是乘法。
那么关键是我们要找一个对所有的x，对这么多个，2n个x
能够快速求值的多项式的算法，这是算法的关键。
下面把这一讲小结一下，这一讲呢讲的是
卷积计算，蛮力算法是n平方，这是一个慢的算法。
那么第二个算法呢是快速的傅立叶变换算法。
这个算法呢它有两个主要的过程，一个是 要确定x的值，在这个值上
来进行求值运算，这x值是什么呢？是1的2n次根。
然后我们设定的多项式要对这2n个根
代入多项式进行多项式的求值，所以关键步骤呢是多项式的求值运算。
那这个算法的主要 主要的效率影响是在有一个高效的多项式求值算法。
我们怎么设计这个高效的求值算法，就是算法有效率的关键。
Wanling QuProfessor
