第三章3 函数逼近与快速Fourier变换3.5~3.6.ppt

《第三章3 函数逼近与快速Fourier变换3.5~3.6.ppt》由会员分享，可在线阅读，更多相关《第三章3 函数逼近与快速Fourier变换3.5~3.6.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、13.5 3.5 有有 理理 逼逼 近近 3.5.1 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万倍，例例1111用辗转相除法将它化为连分式并写成紧凑形式.解解给出有理函数用辗转相除可逐步得到7 本例中用连分式计算 的值只需3次除法，1次乘法和7次加法.8 若直接用多项式计算的秦九韶算法则需6次乘法和1次除法及7次加法.可见将 化成连分式可节省计算乘除法次数.对一般的有理函数（7.1）可转化为一个连分式它的乘除法运算只需 次.而直接用有理函数（7.1）计算乘除法次数为 次.9 3.5.2 3.5.

3、2 帕德（帕德（PadePade）逼近）逼近 利用函数 的泰勒展开可以得到它的有理逼近.设 在 的泰勒展开为（5.5）它的部分和记作（5.6）10 定义定义8 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）的矩阵形式为 定理定理1010（5.7）的有理

4、函数 是 的 阶帕德逼近的充分必要条件是多项式 的系数 及 满足方程组（5.9）及（5.11）.设则形如15 根据定理10,求 的帕德逼近时，首先要由（5.11）解出 的系数 ，的系数 .的各阶帕德逼近可列成再由（5.9）直接算出一张表，称为帕德表（见表3-4）.16 例例1212求 的帕德逼近 及 .解解由 的泰勒展开得 当 时，由（5.11）得 求得再由（5.9）得17于是得 当 时，由（5.11）得 18代入（5.9）得 解得 于是得 19可以看到这里得到的 及 与 的前面 为了求帕德逼近 的误差估计，由(5.9)及(5.11)求得的 系数 及 ，直接代入则得 将 除上式两端，即得 连分

5、式展开得到的有理逼近（5.4）结果一样.20（5.13）其中 当 时可得误差近似表达式 213.6 3.6 最佳平方三角逼近与快速傅里叶变换最佳平方三角逼近与快速傅里叶变换 当 是周期函数时，显然用三角多项式逼近 比用代数多项式更合适，本节主要讨论用三角多项式做最小平方逼近及快速傅里叶变换，快速傅里叶变换，简称FFT算法.22 3.6.1 3.6.1 最佳平方三角逼近与三角插值最佳平方三角逼近与三角插值 设 是以 为周期的平方可积函数，用三角多项式（6.1）做最佳平方逼近函数.由于三角函数族 在 上是正交函数族，于是 在 上的最小平方三角逼近多项式 的系数是 23 称为傅里叶系数.函数 按傅里

6、叶系数展开得到的级数（6.3）就称为傅里叶级数.（6.2）24 只要 在 上分段连续，则级数（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 3.6.2 N点点DFT 与快速傅氏变换（与快速傅氏变换（FFT）不论是按（

8、6.7）式由 求 ，由 求 ，（6.9）其中 (正变换)或 (反变换)，还是由（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算法算法.