资源描述：
《算法分析与设计2005春.课件.第12讲 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、内容提要•多项式的表示方式多项式与FFT–系数–值•多项式的基本运算清华大学–加减乘除宋斌恒•运算的效率分析•FFT思想与实现多项式多项式加法n−1n−1jjA(x)=∑ajxB(x)=∑bjxj=0j=0•在代数域F上的变量为x的多项式n−1•n是幂次（degree）的上界，我们称k是上述多项C(x)=∑cxj式的幂次，如果幂次最大的非零系数是a，jkj=0C=A+B示例1•若A(x)=6x3+7x2-10x+9•B(x)=-2x3+4x-5,•则C(x)=4x3+7x2-6x+4.c=a+bforj=0,.
2、..,n−1jjj1示例2：乘法乘法公式•6x3+7x2-10x+9•-2x3+4x-5•------------------------------------------------------------C(x)=A(x)B(x)•-30x3-35x2+50x-45•24x4+28x3-40x2+36x•-12x6-14x5+20x4-18x3n−1•------------------------------------------------------------cj=∑akbj−k,j=0,...
3、,2n−2•-12x6-14x5+44x4-20x3-75x2+86x-45k=0多项式表示法系数表示法宜于求值和加法n−1•计算A(x)在点x0的值A(x0).jA(x)=∑ax•Horner‘srule方法计算时间复杂度θ(n):j•A(x0)j=0=a0+x0(a1+x0(a2+...+x0(an-2+x0(an-1))...)).•加法就是向量相加•a=(a0,a1,...,an-1).可以用一个n维向量来表示。而对于乘法点值表示法•对于由系数表示的多项式A(x)和B(x)，其•点值表示（point-v
4、aluerepresentation）乘法复杂度是θ(n2),幂次为n-1的多项式A(x)可以由点值对•其积的系数向量c,被称为是a和b的卷积（point-valuepairs）convolution并记做c=a*b.•{(x0,y0),(x1,y1),...,(xn-1,yn-1)}来表示•由于多项式乘法和卷积运算都是基本运•其中xk互不相等，yk=A(xk)算，我们重点来计算卷积的高效率算法2进一步思路点表示定理•一个问题可能有多种等价表示方法。而不•对于{(x0,y0),(x1,y1),...,(xn-1
5、,yn-1)}存在同的表示方法对思考、解决问题有极大的唯一幂次的上界为n的多项式A(x)使得影响。•yk=A(xk)对于k=0,1,...,n–1成立.•我们可以从各种角度去观察、度量一个物体，只要我们的观察数据可以完全唯一地反映这个物体的本身，我们就可以认为这些度量就是这个物体的一个表示。证明：Vandermonde矩阵•上面提到的矩阵是Vandermonde矩阵，它可逆，其determinant【行列式】不为零。•以上事实表明，点表示和系数表示是等价的。•Lagrange公式：Lagrange公式分析由此引
6、发问题•复杂度θ(n2)•科学计算需要注意的问题•稳定性：如果点选择不好，结果会非常–正确性–稳定性差！！！–精确度–截断误差–舍入误差–计算溢出–误差放大–……3点表示法的操作点表示的乘法•加法：只要是degree－bound【幂次的上•类似地点表示法也可以方便地进行乘法，界】一样的具有相同点表示的多项式的加若C(x)=A(x)B(x),则C(xk)=A(xk)B(xk)对法，可以直接把其相关点的值相加即可。于所有xk都成立•其复杂度为θ(n)•但我们必须面临一个问题：即C的degree－bound是A和B的
7、和。•我们需要扩充A和B的点值对。乘法（续）系数表示多项式的快速乘法•扩充A的点对,•我们可以利用线形复杂度的点对表示多项•{(x0,y0),(x1,y1),...,(x2n-1,y2n-1)},式的乘法来实现系数表示多项式的快速乘法。•扩充B的点对–计算给定点集的值【如果选用合适点，其复杂•{(x0,y'0),(x1,y'1),...,(x2n-1,y'2n-1)},度θ(nlgn）】•则C的点对表示–计算点值的乘法【θ(n）】•{(x0,y0y'0),(x1,y1y'1),...,(x2n-1,y2n-1y
8、'2n-1)}.–点值表示插值成系数表示法【如果选用合适算法，其复杂度θ(nlgn）】示意图DFT和FFT离散和快速傅立叶变换•对于多项式，我们取x的值为xi=ωni，其中ωn是方程•xn＝1•的第一个根 ωn＝e2πι/n•theprincipalnthrootofunity:n阶主根4主根的一些性质DFTdkk多项式ω=ωdnnn−1n/2jωn=ω2=−1A(x)=∑ajxk+n
