《第三章3函数逼近与快速Fourier变换3.53.6.ppt》由会员分享，可在线阅读，更多相关《第三章3函数逼近与快速Fourier变换3.53.6.ppt（49页珍藏版）》请在三一办公上搜索。
1、1,3.5 有 理 逼 近,3.5.1 有理逼近与连分式,有理函数逼近是指用形如,的函数逼近,与前面讨论一样，如果 最小就可得到最佳有理一致逼近.,（5.1）,2,如果 最小则可得到最佳有理平方逼近函数.,本节主要讨论利用函数的泰勒展开获得有理逼近函数的方法.,对函数 用泰勒展开得,（5.2）,取部分和,3,另一方面若对（5.2）式用辗转相除可得到 的,一种连分式展开,（5.3）,4,（5.4）,（5.3）右端为 的无穷连分式的前5项，最后式子,若取（5.3）的前2，4，6，8项，则可分别得到 的以下有理逼近,是它的紧凑形式.,5,若用同样多项的泰勒展开部分和 逼近,并计算 处的值 及，计算结
2、果见表3-3.,的准确值为,从表3-3可以看出，,6,但它们的计算量是相当的，这说明用有理逼近比多项式逼近好得多.,由此看出 的精度比 高出近10万倍，,例11,用辗转相除法将它化为连分式并写成紧凑形式.,解,给出有理函数,用辗转相除可逐步得到,7,本例中用连分式计算 的值只需3次除法，1次乘法和7次加法.,8,若直接用多项式计算的秦九韶算法则需6次乘法和1次除法及7次加法.,可见将 化成连分式可节省计算乘除法次数.,对一般的有理函数（7.1）可转化为一个连分式,它的乘除法运算只需 次.,而直接用有理函数（7.1）计算乘除法次数为 次.,9,3.5.2 帕德（Pade）逼近,利用函数 的泰勒展
3、开可以得到它的有理逼近.,设 在 的泰勒展开为,（5.5）,它的部分和记作,（5.6）,10,定义8,设,其中 无公因式，且满足条件,（5.8）,则称 为函数 在 处的 阶帕德逼近，,记作,简称 的帕德逼近.,如果有理函数,（5.7）,11,根据定义，若令,则满足条件（7.8）等价于,即,由于 应用莱布尼兹求导公式得,12,这里 是由（7.6）得到的，,上式两端除，,并由 可得,（5.9）,及,（5.10）,注意当 时,故（5.10）可写成,13,（5.11）,其中 时，,若记,（5.12）,14,则方程组（5.11）的矩阵形式为,定理10,（5.7）的有理函数 是 的 阶帕德逼近的,充分必要
4、条件是多项式 的系数,及 满足方程组（5.9）及（5.11）.,设,则形如,15,根据定理10,求 的帕德逼近时，首先要由（5.11）,解出 的系数，,的系数.,的各阶帕德逼近可列成,再由（5.9）直接算出,一张表，称为帕德表（见表3-4）.,16,例12,求 的帕德逼近 及.,解,由 的泰勒展开,得,当 时，由（5.11）得,求得,再由（5.9）得,17,于是得,当 时，由（5.11）得,18,代入（5.9）得,解得,于是得,19,可以看到这里得到的 及 与 的前面,为了求帕德逼近 的误差估计，由(5.9)及(5.11)求得的 系数 及，直接代入则得,将 除上式两端，即得,连分式展开得到的有
5、理逼近（5.4）结果一样.,20,（5.13）,其中,当 时可得误差近似表达式,21,3.6 最佳平方三角逼近与快速傅里叶变换,当 是周期函数时，显然用三角多项式逼近 比用代数多项式更合适，本节主要讨论用三角多项式做最小平方逼近及快速傅里叶变换，简称FFT算法.,22,3.6.1 最佳平方三角逼近与三角插值,设 是以 为周期的平方可积函数，用三角多项式,（6.1）,做最佳平方逼近函数.,由于三角函数族,在 上是正交函数族，于是 在 上的最小平方三角逼近多项式 的系数是,23,称为傅里叶系数.,函数 按傅里叶系数展开得到的级数,（6.3）,就称为傅里叶级数.,（6.2）,24,只要 在 上分段连
6、续，则级数（6.3）一致收敛到.,对于最佳平方逼近多项式（6.1）有,由此可以得到相应于（4.11）的贝塞尔不等式,因为右边不依赖于，左边单调有界，所以级数,25,当 只在给定的离散点集,上已知时，则可类似得到离散点集正交性与相应的离散傅里叶系数.,下面只给出奇数个点的情形.,收敛，并有,26,可以证明对任何 成立,令,27,这表明函数族 在点集,上正交.,若令,则 的最小二,其中,乘三角逼近为,28,当 时,于是,（6.4）,就是三角插值多项式，系数仍由（6.4）表示.,29,由于,所以函数族 在区间 上是正交的.,一般情形，假定 是以 为周期的复函数，给定,在 个等分点 上的值,函数 在等
7、距点集 上的值,组成的向量记作,30,当 时，个复向量 具有如下正交性：,（6.5）,31,事实上，令,于是,即,若,若,则有,则,从而,32,于是,若,这就证明了（6.5）成立.,即 是正交的.,则,于是,因此，在 个点 上的最小二乘傅里叶逼近为,33,（6.6）,其中,（6.7）,在（6.6）中，,若，,则 为 在点,上的插值函数，,于是由（6.6）得,即,（6.8）,34,（6.7）是由 求 的过程，,称为 的离散,而（6.8）是由 求 的过程，称为反变换.,傅里叶变换.简称DFT，,35,3.6.2 N点DFT 与快速傅氏变换（FFT）,不论是按（6.7）式由 求，,由 求，,（6.9
8、）,其中(正变换),或(反变换)，,还是由（6.4）计算傅里叶逼近系数,都可归结为计算,是已知复数序列.,或是按（6.8）,36,当 较大且处理数据很多时，就是用高速的电子计算机，很多实际问题仍然无法计算，,如直接用（6.9）计算，需要 次复数乘法和 次,复数加法，称为 个操作，计算全部 共要 个操作.,1965年产生了FFT算法，大大提高了运算速度，从而使DFT得到广泛的应用.,FFT算法的基本思想就是尽量减少乘法次数.,37,用（6.9）计算全部，,表面看要做 个乘法，,实际上所有 中，,只有 个不,同的值,特别当 时，只有 个不同的值.,因此可把同一个 对应的 相加后再乘，这就能大量减少
9、乘法次数.,38,设正整数 除以 后得商 及余数，,则，,称为 的 同余数，以 表示.,由于,因此计算 时可用 的 同余数 代替，从而推出FFT算法.,以 为例.说明FFT的计算方法.,由于 则（6.9）的和是,（6.10）,故有,39,将 用二进制表示为,其中 只能取0或1，,例如,根据 表示法，有,公式（6.10）可表示为,40,（6.11）,若引入记号,（6.12）,41,则（6.11）变成,它说明利用 同余数可把计算 分为 步，用公式（6.12）计算.,每计算一个 只用2次复数乘法，计算一个 用,次复数乘法，计算全部 共用 次复数乘法.,若注意 公式（6.12）还可进一步简化为,42,
10、将这表达式中二进制表示还原为十进制表示：,43,（6.13）,同样（6.12）中的 也可简化为,即,即 得,44,把二进制表示还原为十进制表示，得,（6.14）,同理（6.12）中 可简化为,即,45,表示为十进制，有,（6.15）,46,根据公式(6.13)，(6.14)，(6.15)，由,逐次计算到,见表3-5(略）.,上面推导的 的计算公式可类似地推广到 的情形.,根据公式(6.13)，(6.14)，(6.15)，一般情况的FFT计算公式如下：,47,（6.16）,其中,从 出发，由 到 算到,一组 占用 个复数单元，计算时需给出两组单元，,括号内的数代表它的位置，在计算机中代表存放数的地址.,即为所求.,48,这个计算公式除了具有不倒地址的优点外，计算只有两重循环，,计算过程中只要按地址号存放 则最后得到的,就是所求离散频谱的次序.,外循环 由 计算到，内循环 由 计算到,由 计算到,更重要的是整个计算过程省计算量.,由公式看到算一个 共做 次复数乘法，,而最后一步计算 时，由于,49,（注意 时 故），因此，总共要算,次复数乘法，它比直接用（6.9）需 次乘法,当 时比值是 它比一般FFT的计算量（次乘法）也快一倍.,快得多，计算量比值是,我们称（6.16）的计算公式为改进的FFT算法.,
