函数逼近与快速Fourier变换.ppt

事实上，令*于是即若若则有则从而于是若因此，在个点上的最小二乘傅里叶逼近为则这就证明了（6.5）成立.于是即是正交的.（6.6）其中（6.7）在（6.6）中，若，则为在点上的插值函数，于是由（6.6）得即（6.8）傅里叶变换.简称DFT，称为的离散（6.7）是由求的过程，而（6.8）是由求的过程，称为反变换.3.6.2N点DFT与快速傅氏变换（FFT）不论是按（6.7）式由求，由求，（6.9）其中(正变换)或(反变换)，还是由（6.4）计算傅里叶逼近系数都可归结为计算是已知复数序列.或是按（6.8）当较大且处理数据很多时，就是用高速的电子计算机，很多实际问题仍然无法计算，如直接用（6.9）计算，需要次复数乘法和次复数加法，称为个操作，计算全部共要个操作.1965年产生了FFT算法，大大提高了运算速度，从而使DFT得到广泛的应用.FFT算法的基本思想就是尽量减少乘法次数.3.5有理逼近*3.5.1有理逼近与连分式有理函数逼近是指用形如的函数逼近与前面讨论一样，如果最小就可得到最佳有理一致逼近.（5.1）如果最小则可得到最佳有理平方逼近函数.本节主要讨论利用函数的泰勒展开获得有理逼近函数的方法.对函数用泰勒展开得（5.2）取部分和另一方面若对（5.2）式用辗转相除可得到的一种连分式展开（5.3）是它的紧凑形式.（5.3）右端为的无穷连分式的前5项，最后式子（5.4）若取（5.3）的前2，4，6，8项，则可分别得到的以下有理逼近从表3-3可以看出，并计算处的值及，计算结果见表3-3.若用同样多项的泰勒展开部分和逼近的准确值为但它们的计算量是相当的，这说明用有理逼近比多项式逼近好得多.由此看出的精度比高出近10万倍，例11用辗转相除法将它化为连分式并写成紧凑形式.解给出有理函数用辗转相除可逐步得到本例中用连分式计算的值只需3次除法，1次乘法和7次加法.若直接用多项式计算的秦九韶算法则需6次乘法和1次除法及7次加法.可见将化成连分式可节省计算乘除法次数.对一般的有理函数（7.1）可转化为一个连分式它的乘除法运算只需次.而直接用有理函数（7.1）计算乘除法次数为次.3.5.2帕德（Pade）逼近利用函数的泰勒展开可以得到它的有理逼近.设在的泰勒展开为（5.5）它的部分和记作（5.6）定义8设其中无公因式，且满足条件（5.8）则称为函数在处的阶帕德逼近，记作,简称的帕德逼近.如果有理函数（5.7）由于应用莱布尼兹求导公式得则满足条件（7.8）等价于根据定义，若令即这里是由（7.6）得到的，上式两端除，并由可得（5.9）及（5.10）注意当时故（5.10）可写成其中时，*（5.11）若记（5.12）则方程组（5.11）的矩阵形式为定理10（5.7）的有理函数是的阶帕德逼近的充分必要条件是多项式的系数及满足方程组（5.9）及（5.11）.设则形如的系数.*根据定理10,求的帕德逼近时，首先要由