小平方逼近及快速傅里叶变换.PPT

3.5.2 用正交多项式做最小二乘拟合 3.6 最佳平方三角逼近与快速傅里叶变换 3.6.1 最佳平方三角逼近与三角插值 3.6.2 快速傅氏变换（FFT） 3.7 有 理 逼 近 3.7.2 帕德逼近 （6.13） 同样（6.12）中的 也可简化为 即 即 得 把二进制表示还原为十进制表示，得 （6.14） 同理（6.12）中 可简化为 即 表示为十进制，有 （6.15） 根据公式(6.13)，(6.14)，(6.15)，由 逐次计算到 见表3-2(略）. 上面推导的 的计算公式可类似地推广到 的情形. 根据公式(6.13)，(6.14)，(6.15)，一般情况的FFT 计算公式如下： （6.16） 其中 从 出发， 由 到 算到 一组 占用 个复数单元，计算时需给出两组单元， 括号内的数代表它的位置，在计算机中代表存放数的地址. 即为所求. 这个计算公式除了具有不倒地址的优点外，计算只有两 重循环， 计算过程中只要按地址号存放 则最后得到的 就是所求离散频谱的次序. 外循环 由 计算到 ，内循环 由 计算到 由 计算到 更重要的是整个计算过程省计算量. 由公式看到算一个 共做 次复数乘法， 而最后一步计算 时，由于 （注意 时 故 ），因此，总共要算 次复数乘法，它比直接用（6.9）需 次乘法 当 时比值是 它比一般FFT的 计算量（ 次乘法）也快一倍. 快得多，计算量比值是 我们称（6.16）的计算公式为改进的FFT算法 . 3.7.1 有理逼近与连分式 有理函数逼近是指用形如 的函数逼近 与前面讨论一样，如果 最小就可得到 最佳有理一致逼近. （7.1） 如果 最小则可得到最佳有理平方逼近 函数. 本节主要讨论利用函数的泰勒展开获得有理逼近函数 的方法. 对函数 用泰勒展开得 （7.2） 取部分和 另一方面若对（7.2）式用辗转相除可得到 的 一种连分式展开 （7.3） （7.4） （7.3）右端为 的无穷连分式的前5项，最后式子 若取（7.3）的前2，4，6，8项，则可分别得到 的以下有理逼近 是它的紧凑形式. 若用同样多项的泰勒展开部分和 逼近 并计算 处的值 及 ，计算结果见表3-3. 的准确值为 从表3-1可以看出， 但它们的计算量是相当的，这说明用有理逼近比多项式逼近好得多. 由此看出 的精度比 高出近10万倍， 例9 用辗转相除法将它化为连分式并写成紧凑形式. 解 给出有理函数 用辗转相除可逐步得到 本例中用连分式计算 的值只需3次除法，1次乘 法和7次加法. 若直接用多项式计算的秦九韶算法则需6次乘法和1次 除法及7次加法. 可见将 化成连分式可节省计算乘除法次数. 对一般的有理函数（7.1）可转化为一个连分式 它的乘除法运算只需 次. 而直接用有理函数（7.1）计算乘除法次数为 次.  利用函数 的泰勒展开可以得到它的有理逼近. 设 在 的泰勒展开为 （7.5） 它的部分和记作 （7.6） 如果 是关于点集 带权 正交的 （5.8） 用最小二乘法得到的法方程组（5.6），其系数矩阵 是病态的. 函数族，即 （5.9） 则方程（5.6）的解为 且平方误差为 接下来根据给定节点 及权函数 构造带权 正交的多项式 . 注意 ，用递推公式表示 ，即 （5.10） 根据 的 这里 是首项系数为1的 次多项式， 正交性，得 （5.11） 下面用归纳法证明这样给出的 是正交的. 假定