第三章函数逼近与傅里叶变换.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017/3/21,#,求解以下线性方程组,X=2.5,时,Y=?,X=2.5,时,Y=?,传输以下数据，需要多少流量,插值,有限节点上给定函数值，在包含该节点集的区间上用多项,式的值近似求函数值,插值问题的外延,给定函数表，用简单函数计算函数值,用简单函数表示复杂函数,-,函数逼近,第三章 函数逼近与快速傅里叶变换,函数逼近的概念,函数逼近,在特定区间上用简单函数逼近已知复杂函数,-,函数逼近,插值法就是一种函数逼近,对函数类,A,中给定的函数,f(,x,),，记作,要求在另一类简单的便于计算的函数类,B,中求函数,使,p(,x,),与,f(,x,),的误差在某种度量意义下最小。,A,在区间,a,b,上连续（连续函数空间,）,B,多项式、有理函数、分段低次多项式,11,（,1.2,）,它由 个系数 唯一确定,.,考察次数不超过 次的多项式集合 ，,它是 的一组基，,是线性无关的，,且 是 的坐标向量，是 维的,.,表示为,其元素,故,12,使误差,对连续函数 ，它不能用有限个线性无关的,函数表示，故 是无限维的，但它的任一元素,均可用有限维的 逼近，,(,为给定的任意小正数,),，,-,魏尔斯,特拉斯定理,.,13,使,定理,1,总存在一,设 ，,则对任何 ，,个代数多项式 ，,在 上一致成立,.,伯恩斯坦,1912,年给,出了一,种构造性证明,.,根据,函数整体逼近的特性,构造伯恩斯坦多项式,（,1.3,）,14,为二项式展开系数,，,在 上一致成立；,若 在 上 阶导数连续，则,其中,伯恩斯坦多项式证明定理,1,的同时还给,出了,的一个逼近多项式，但它收敛太慢，实际中很少使用,.,15,更一般地，可用一组在 上线性无关的函数集合,来逼近 ，,可表示为,（,1.4,）,此时元素,函数逼近问题就是对任何 ，,找一个元素 ，,使 在某种意义下最小,.,在子空间,中,范数与赋范线性空间,定义,2,设 为线性空间，若存在唯一实数,，,满足条件：,（,1,）,当且仅当 时，（正定性）,（,2,）,(,齐次性,),（,3,）,(,三角不等式,),则称,为线性空间 上的范数，与,一起称为赋范,线性空间，记为,范数是 空间中向量长度概念的推广,17,在,上的向量 三种常,用范数为,称为 范数或最大范数，,称为,1-,范数，,称为,2-,范数,.,例,设向量,x,（,1,，,3,，,2,，,0,）,T,，求,向量范数,|,x,|,p,，,P,1,，,2,，。,例,设向量,x,（,1,，,3,，,2,，,0,）,T,，求,向量范数,|,x,|,p,，,P,1,，,2,，。,解：,|,x|,1,|1|,|,3|,|2|,|0|,6,实际上,任何向量的实值函数，只要,满足正定性、齐次性、,三角不等式三,个条件,，就可以定义成一种向量范数,20,而满足,1,=1,的向量 则为对角线长,度为,1,的菱形,.,在 中，满足,2,=1,，即,的向量,为单位圆，,满足,=1,，即 的向量为单位正,方形，,所以说，范数是对向量长度的度量，度量方式不同,，,结果也不一样，但不同范数之间是存在等价关系的,.,定理,（范数的等价性）对于,R,n,上任何两种范数,|,和,|,，存,在正,常数,m,，,M,，使得：,范数的等价性表明，一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量,。,可证，,常用的三种向量范数满足下述等价关系。,|x|,|x|,1,n|x|,22,类似地，对连续函数空间 ，若,称为 范数，,称为,1-,范数，,称为,2-,范数,.,可定义三种常用范数如下,：,内积与内积空间,在线性代数中，中两个向量 及,的内积定义为,推广,到一般的线性空间 ，则有下面的定义,.,24,定义,3,则称 为,X,上 与 的内积,.,定义了内积的线性空间,称为内积空间,X,是数域,K,(,R,或,C,),上的线性空间，对,有,K,中一个数与之对应，记为 ，它满足,以下条件：,如果 ，则称 与,正交,，这是向量相互垂,直概念的推广,.,25,定理,2,对 有,（,1.6,）,称为柯西,-,施瓦茨,(,Cauchy-Schwarz,),不等式,.,证明,当 时（,1.6,）式显然成立,.,现设 ，,则 ，,且对任何数 有,取 ，,设,X,为一个内积空间，,代入上式右端，得,即得 时,26,定理,3,（,1.7,）,称为格拉姆,(,Gram,),矩阵,，,则 非奇异的充分必要条件是 线性无关,.,设,X,为一个内积空间，,矩阵,27,证明,只有零解；,（,1.9,）,G,非奇异等价于 ，其充要条件是齐,次,方程组,（,1.8,）,而,从以上等价关系知，,而后者等价于从（,1.9,）推出,即 线性无关,.,等价于从（,1.8,）推出,28,在内积空间,X,上，可以由内积导出一种范数，即,对于,（,1.10,）,记,两端开方即得三角不等式,（,1.11,）,利用,29,例,1,与 的内积,.,设,（,1.12,）,向量,2-,范数为,相应的范数为,（,1.13,）,若给定实数,称 为权系数，,当 时，,上的加权内积为,（,1.13,）就是前面定义的内积,.,30,如果 ，,（,1.14,）,这里 仍为正实数序列，为 的共轭,.,在 上也可以类似定义带权内积,.,带权内积定义为,31,定义,4,设 是有限或无限区间，在 上的非负,函数 满足条件：,（,1,）,存在且为有限值,（,2,）对 上的非负连续函数 ，如果,则称 为 上的一个,权函数,.,则,32,例,2,设,是 上给定的权函数,（,1.15,）,由此内积导出的范数为,称（,1.15,）和（,1.16,）为带权 的内积和范数,.,上的内积,.,则可定义内积,（,1.16,）,33,若 是 中的线性无关函数族，,（,1.17,）,根据定理,3,可知 线性无关的充要条件是,它的格拉姆矩阵为,记,34,函数逼近主要讨论给定 ，求它的最佳逼近多项式的问题,.,最佳逼近,若 使误差,则称 是 在 上的,最佳逼近多项式,.,若 则称相应的,为最佳逼近函数,.,通常将范数 取为 或,35,若取 ，即,（,1.18,）,则称 是 在 上的,最优一致逼近多项式,.,求 就是求 上使最大误差,最小的多项式,.,36,若取 ，即,则称 是 在 上的,最佳平方逼近多项式,.,（,1.19,）,若 是 上的一个列表函数，在,上给出 ，要求 使,则称 为 的,最小二乘拟合,.,（,1.20,）,函数逼近,-,找与给定函数,误差最小,的,简单函数线性组合,。,X=2.5,时,Y=?,f,(,x,i,)-,P,(,x,i,),曲线,1,曲线,2,曲线,n,最佳平方逼近,最佳平方逼近及其计算,对 及 中的一个子集,若存在 ，使,（,3.1,）,则称 是 在子集 中的,最佳平方逼近,函数,.,该,问题等价于求多元函数,（,3.2,）,的最小值,.,是关于 的二次函数，,即,利用多元函数求极值的必要条件,于是有,（,3.3,）,这个关于 的线性方程组，称为,法方程,.,由于 线性无关，故,于是方程组（,4.3,）有唯一解,从而,得到,即对任何,下面证明 满足（,3.1,），,（,3.4,）,为此考虑,有,由于 的系数 是方程（,3.3,）的解，,从而第二,个积分为,0(,几何解释），,故（,3.4,）成立,.,这就证明了 是 在 中的最佳平方逼近函数,.,于是,（因为 仍可以由 的线性组合表示）,44,若令,（,3.5,）,则平方误差为,若取,中求 次最佳平方逼近多项式,则要在,此时,若用 表示 对应的矩阵,，,（,3.6,）,称为,希尔伯特,(,Hilbert,),矩阵,.,46,记,（,3.7,）,的解 即为所求,.,则,47,例,6,设,解,得方程组,求 上的一次最佳平方,逼近多项式,.,利用,，,得,48,解之,故,平方误差,最大误差,用 作基函数，求最佳平方逼近多项式，,当,n,较大时，希尔伯特矩阵是高度病态的，,即当某个元素有微小变化时,引起解的变化很大,且当,n,越大时，病态愈严重,。当,n,很大时它的精度便由舍入误差影响而迅速恶化。,因此直接求解,法方程,相当困难，解决方法,-,采用正交多项式作基函数,.,正交多项式,正交函数族与正交多项式,（,2.1,）,则称 与 在 上带权,正交,.,若,上的权函数且满足,为,定义,5,若函数族 满足关系,则称 是 上带权 的,正交函数族,.,若 ，则称之为,标准正交函数族,.,（,2.2,）,三角函数,族,就是在区间 上的正交函数族,.,定义,6,设,是 上首项系数 的 次多,项式，为 上权函数，,满足关系式,(2.2),，,则称多项式序列 为在 上,带权,正交,，称 为 上带权 的 次,正交多项式,.,如果多项式序列,52,（,2.3,）,只要给定区间 及权函数 ，均可由一族线性,无关的幂函数 利用逐个正交化手续构造,出正交多项式序列 ：,最高项系数为,1,53,若,是,正交多项式，则 在 上,是线性无关,的,.,事实上，若,用 乘上式并积分得,正交多项式的性质：,对任何,均可以表示为,的线性组合，即,与任何次数小于,n,的多项式,正交，即,设,是,上带权,的正交多项式，对,成立递推关系,这里,55,4.,定理,5,设 是 上带权 的正交多项式，则 在区间 内有 个不同的零点,.,证明,假定 在 内的零点都是偶数重的，则,在 符号保持不变，这与,矛盾,.,故 在 内的零点不可能全是偶数重的，现,设,为 在 内的奇数重零点，不妨设,则 在 处变号,.,56,令,于是 在 上不变号，则得,若 ，由 的正交性可知,这与 矛盾，故,.,而 只有 个零点，故 ，即 个零点都是单重的,.,勒让德多项式,罗德利克,(,Rodrigul,）给出了简单的表达式,（,2.5,）,当区间为 ，权函数 时，,并用 表示,.,正交化得到的多项式就称为,勒让德,(,Legendre,),多项式,，,由,（,2.6,）,58,勒让德多项式的性质,：,性质,1,（,2.7,）,证明,令 ，,则,设 是在区间 上 阶连续可微的函数，由分部,积分知,正交性,59,则,（,2,）若,于是,由于,故,（,1,）若 是次数小于 的多项式，,则,60,性质,2,（,2.8,）,由于 是偶次多项式，经过偶次求导仍为,偶次多项式，经过奇次求导则为奇次多项式，故 为偶数时,为偶函数，为奇数时 为奇函数，于是（,2.8,）成,立,.,奇偶性,61,性质,3,考虑 次多项式,两边乘 并从,-1,到,1,积分，,递推关系,它可表示为,得,故得,当 时，,次数小于等于 ，,为,0,，,上式左端积分,62,当 时，,其中,左端积分仍为,0,，,故,于是,为奇函数，,63,由,从而得到以下的递推公式,（,2.9,）,利用上述递推公式就可推出,64,图,3,-,1,图,3-1,给出了 的图形,.,65,在区间 内有 个不同的实零点,.,性质,4,66,切比雪夫多项式,当权函数 ，区间为 时，由序,列 正交化得到的正交多项式就是,切比雪夫,(,Chebyshev,),多项式,.,（,2.10,）,若令 ，,则,67,性质,1,切比雪夫多项式性质,：,根据三,角恒等式,令 即得,.,递推关系,（,2.11,）,图,3-2,68,性质,2,（,2.12,）,令 ，,则 ，,切比雪夫多项式 在区间 上带权,正交，且,于是,69,若令 ，则,是首项系数为,1,的切比雪夫多项式,.,性质,4,在区间 上有 个零点,性质,3,只含 的偶次幂，,只含 的奇次幂,.,由,递推关系直接得到,.,性质,5,的首项 的系数为,70,若记 为所有次数小于等于 的首项系数为,1,的多项,式集合，对 有以下性质：,定理,6,设 是首项系数为,1,的切比雪夫多项式，则,且,在,所有首项系数为,1,的,次,多项式集合 中，,所以 是 中最大值最小的多项式,，即,利用这一结论，可求 在 中的最佳（一致）逼近多项式,.,71,由定理,6,可知，,多项式 与零偏差最小,，,解,由题意，所求最佳逼近多项式 应满足,当,时，,故,例,3,求 在 上的最佳,2,次逼,近多项式,.,就是 在 上的最佳,2,次逼近多项式,.,72,由于切比雪夫多项式是在区间 上定义的，对于,一般区间 ，要通过变量替换变换到 ，可令,（,2.14,）,则可将 变换到,73,切比雪夫多项式 在区间 上有 个零点,切比雪夫多项式,零点插值,和 个极值点（包括端点）,这两组点称为,切比雪夫点,，它们在插值中有重要作用,.,74,切比雪夫,点恰好是单位圆周上等距,分布,点的横坐标,，,这些,点的横坐标在接近区间 的,端点处,是密集的,.,图,3-3,利用切比雪夫点做插值，可使插值区间最大误差最小化,.,设插值点,为相应的 次拉格朗日插值多项式，则余项,75,于是,其中,是由被插函数决定的,.,如果插值节点为 的零点,则由（,2.13,）可得,从而导出,插值误差最小化,的,结,论,.,76,定理,7,设插值节点 为切比雪夫多项式 的零点，被插函数 为相应的插值多项式，则,（,2.15,）,对于一般区间 上的插值只要利用变换（,2.14,）则,可得到相应结果，此时插值节点为,77,例,4,求 在 上的四次拉格朗日插值多项式,，插值节点用 的零点并估计误差,解,利用 的零点和区间变换可知节点,即,对应的拉格朗日插值多项式为,78,利用（,2.15,）可得误差估计,而,于是有,79,例,5,设 ，在 上利用 的零点,作插值点，构造,10,次拉格朗日插值多项式,.,与第,2,章,得到的等距节点造出的 近似 作比较,.,解,在 上的,10,次切比雪夫多项式 的零点为,作变换 它们是 内的插值点，,由此得到 在 上的拉格朗日插值多项式,80,的图形见图,3-4,，从图上可见,没有出现龙格现象,.,图,3-4,81,其他,常用的正交多项式,区间 及权函数 不同，则得到的正交多项式也,不同,.,1,.,第二类切比雪夫多项式,在区间 上带权 的正交多项式,称为,第二类切比雪夫多项式,.,（,2.16,）,令 ，,可得,82,递推关系,83,2.,拉盖尔多项式,在区间 上带权 的正交多项式称为,拉,盖尔,(,Laguerre,),多项式,.,（,2.17,）,正交性质,递推关系,84,（,2.18,）,正交关系,在区间 上带权 的正交多项式称,为,埃尔米特多项式,.,3.,埃尔米特多项式,递推关系,用正交函数族作最佳平方逼近,设,若 是满足,条件,的,正交函数族，,而,故法方程（,3.3,）的系数矩阵,则,（,2.2,）,86,为非奇异对角阵,，且方程（,3.3,）,（,3.8,）,于是 在 中的最佳平方逼近函数为,（,3.9,）,的,解为,（,3.3,）,平方逼近的误差,由此得贝塞尔不等式,若 ，按正交函数族 展开，系数,按 计算，得级数,称其为 的,广义傅里叶级数,，系数,-,广义傅,里叶系数。,定理,8,设 ，是由,给出的 的最佳平方逼近多项式，其中,是正交多项式族，则有,若 ，按勒让德多项式,展开，,其中,平方逼近的误差,且,若,f(x),光滑，则 一致收敛于,f(x),定理,9,设 ，由,给出，则对任意 和 ，当,n,充分大时,有,对于首项系数为,1,的勒让德多项式 有：,定理,10,在所有最高项系数为,1,的,n,次多项式中，勒让德,多项式 在 上与零的平方逼近误差最小。,证明：设 是任意一个最高次项系数为,1,的,n,次多,项式,于是,等号成立条件,在,-1,，,1,上,3,次,最佳平方逼近多项式。,例,7,解：,法方程组为,平方误差,法方程组为,若 ，求 上的最佳平方逼近多项式，,首先变换,获得,然后在 上用勒让德多项式做最佳平方逼近多项,式 ，从而得到,勒让德展开部分和得到最佳平方逼近多项式与由,直接解方程得到 中的最佳平方逼近多项式是一致的。,只是后者在,n,较大时法方程出现病态，计算误差大；而,勒让德展开不解线性方程组，不存在病态问题，计算公,式也简单。,切比雪夫级数,如果 ，按 展开成广义傅里叶级数，,（,3.16,）,其中，,这里,级数（,3.16,）称为 在 上的,切比雪夫级数。,若 则（,3.16,）式就是 的傅,里叶级数，其中,只要 在 上分段连续，则 在,上的切比雪夫级数一致收敛于 ，表示为,其部分和,其误差,在 上 是均匀分布的，其最大值,最小，因此 可作为 在 上的近似最佳一,致逼近多项式。,例,8,求 在 上的切比雪夫级数部分和,解：由,得,求积分得：,由,则,且,曲线拟合的最小二乘法,最小二乘法及其计算,-,最佳平方逼近,离散情况,-,最小二乘逼近,实验数据,的曲线拟合 ，这里,记误差,设 是 上线性无关函数族，,在,中找函数 使误差,平方和,其中,-,最小二乘逼近、曲线拟合的最小二乘法,S,(,x,),的选择,通常考虑加权平方和,从而问题转化为求多元函数,的极小点,记,则,法方程,（,1.7,）,要使法方程有唯一解，矩阵,G,必须非奇异。,在 上线性无关，不能推出,G,非奇异。,定义,7,设 的任意线性组合在,点集,上至多只有,n,个不同的零点，,则称,在点集上满足,哈尔（,Harr,）,条件,。,如果,在 上满足,Harr,条,件，则系数矩阵,G,非奇异。法方程存在唯一解,且,是最小二乘解。,例,9,已知一组实验数据，求拟合曲线。,解：线性函数拟合，令,x,i,1,2,3,4,5,f,i,4,4.5,6,8,8.5,w,i,2,1,3,1,1,例,10,表中第四行为 ，数学模型为,用最小二乘法确定,a,b,解：,不是线性。,但,令,取,i,0,1,2,3,4,x,i,1.00,1.25,1.50,1.75,2.00,y,i,5.10,5.79,6.53,7.45,8.46,1.629,1.756,1.876,2.008,2.135,正交多项式作最小二乘拟合,最小二乘法得到的法方程，系数矩阵,G,是病态的，但,若,是关于点集,带权,正交的函数族，即,则法方程的解,平方误差,根据给定节点,、权函数,，用递推公,式构造带权正交多项式 。,可用数学归纳法证明正交性，略,用正交多项式作最小二乘拟合,习题,上机：,P95,：,1,2,上机实例,对于给定的函数,在区间,上取,试求,3,次曲线拟合，并与第二章的插值结果比较。,解：离散观测数据的最小二乘拟合问题,基函数选择（,1,）,-,求解线性方程组,G,矩阵病态,（,2,）正交多项式如勒让德多项式,不需解方程,本题中，,n=3,，,m=11,（见上机,ex3_1,）,与插值的比较,（,ex2_2,）,插值相当于解方程,而最小二乘拟合对误差的,2-,范数求极值，求解法方程,有理逼近,问题的提出：,当函数在某点附近无界时，多项式逼近效果很差。而,有理函数逼近则可获得较好效果。,有理逼近,指用形如,的函数逼近,f(x),。,最佳有理一致逼近,-,最小,最佳有理平方逼近,-,最小,连分式,利用泰勒展开获得有理逼近函数,例如：,1.,取部分和,2.,利用辗转相除，可得到连分式,取（,5.3,）的前,2,4,6,8,项,泰勒展开部分和与有理逼近的比较,n,1,0.50,0.19,0.667,0.026,2,0.58,0.11,0.69231,0.00084,3,0.617,0.076,0.693122,0.000025,4,0.634,0.058,0.69314642,0.00000076,例,11,对于有理函数,用辗转相除法将它化为连分式。,解：,对一般的有理函数（,5.1,）可转化为连分式，其乘除法,运算只需,次，而直接用（,5.1,）计算，乘除,法次数为,次。,119,帕德（,Pade,）逼近,利用,函数 的泰勒展开可以得到它的有理逼近,.,设 在 的泰勒展开为,（,5.5,）,它的部分和记作,（,5.6,）,120,定义,8,设,其中 无公因式，且满足条件,（,5.8,）,则称 为函数 在 处的 阶,帕德逼近,，,记作,简称 的帕德逼近,.,如果有理函数,（,5.7,）,121,根据定义，若令,则满足条件,（,5.8,）等价于,即,由于 应用莱布尼兹求导公式得,122,这里 是由,（,5.6,）得到的，,上式两端除 ，,并由 可得,（,5.9,）,及,（,5.10,）,注意当 时,故（,5.10,）可写成,123,（,5.11,）,其中 时,若记,（,5.12,）,则方程组（,5.11,）的矩阵形式为,定理,11,（,5.7,）的有理函数 是 的 阶帕德逼近的,充分必要条件是多项式 的系数,及 满足方程组（,5.9,）及（,5.11,）,.,设,则形如,125,根据定理,11,求 的帕德逼近时，首先要由（,5.11,）,解出 的系数 ，,的系数,.,的各阶帕德逼近可列成,再由（,5.9,）直接算出,一张表，称为帕德表（见表,3-4,）,.,126,例,12,求 的帕德逼近 及,.,解,由 的泰勒展开,得,当 时，由（,5.11,）得,求得,再由（,5.9,）得,127,于是得,当 时，由（,5.11,）得,代入（,5.9,）得,解得,于是得,可以看到这里得到的 及 与 的前面,为了求帕德逼近 的误差估计，由,(5.9),及,(5.11),求得的 系数 及 ，直,接代入则得,将 除上式两端，即得,连分式展开得到的有理逼近（,5.4,）结果一样,.,（,5.13,）,其中,当 时可得误差近似表达式,习题,P94-95:3,，,4,，,8,，,11,12,15,16,18,19,回顾,对连续函数作最佳平方逼近，对离散的观测数据作最小二乘曲线拟合，利用辗转相除连分式、帕德逼近作有理逼近,基函数：,线性无关函数族，如,正交函数族，如勒让德多项式,有理函数,问题提出：,前面的例子中，对区间的限定,周期性振动,-,若要反映其周期性，多项式、分段多项式、有理函数等作为基函数已不适用,正、余弦函数族,18,世纪,50,年代,19,世纪,离散傅里叶变换（,DFT,）,快速傅里叶变换（,FFT,）,1965,三角多项式逼近与快速傅里叶变换,最佳平方三角逼近与三角插值,设 是以 为周期的平方可积函数，用三角多项式,做最佳平方逼近函数，系数为,称为,傅里叶系数,，函数 按傅里叶系数展开得到,的级数,称为,傅里叶级数,。只要 在 上分段连续，则,级数（,6.3,）一致收敛到 。,对于最佳平方逼近,有,相应的贝塞尔不等式,故,与,n,无关,当 只在给定的离散点集,上已知时，可类似得到离散点集正交性和相应的傅里叶,级数。,令,对任何,可证明下式成立,上式表明函数族,在点集,上正交。若令,则 的最小二乘三角逼近为,其中,当,，可证明,于是,三角插值多项式,一般化，若 是以 为周期的复函数，给定,在,N,个等分点,上的值,由于,函数族,在区间,上是正交的。,函数 在等距点集,上的值,组成的向量记作,当,，,N,个复向量,具有,正交性,证明：令,，若,则,于是,即,若,，则,，从而,于是,若,，则,，于是,证毕,因此，在,N,个点,上的,最小二乘傅里叶逼近为,其中,若,，则 是 在点,上的插值函数，,于是,离散傅立叶变换,DFT,反变换,IDFT,N,点,DFT,其中，为已知的输入（观测）数据，为输出数据，,计算量,-,每个,N,个操作（,N,次复数乘法、,N,次加法）,所有,个操作,N,很大时，计算量难以承受,N,点,DFT,快速傅立叶变换（,FFT,）算法,减少乘法次数,对于任意正整数,成立,由周期性知，所有,中，最多,N,个,不同的值,，特别地，有,当,时，由对称性，,只有 个不同的值。,将（,6.9,）式对半折成两个和式，再将对应项相加,区分奇、偶下标,令,2,j,-,j,2,j+,1-,j,以,为例，,将 用二进制表示为,则,引入记号,则,注意,（,6.12,）式可简化为,还原成,10,进制,类似地,码,0,000,1,001,2,010,3,011,4,100,5,101,6,110,7,111,乘法,8,次、加法,24,次,推广,一个,-,次乘法,所有,-,次乘法,又因为,所以总共只需,次乘法,内存空间,-,两个长度为,N,的数组,例,13,：设,区间,给定数据,确定三角插值多项式。,解：区间变换，令,m=7,，最多确定,8,个参数，,4,次三角插值多项式,考虑,，这里,对,有,应用,FFT,算法求,从而得到,4,次三角插值多项式,习题,P95:23,P96:3,