数值分析-第3章函数逼近与快速傅里叶变换.ppt
2023/10/14,课件,1,第3章 函数逼近与快速傅里叶变换,3.1 函数逼近的基本概念3.2 正交多项式3.3 最佳平方逼近3.4 曲线拟合的最小二乘法3.5 有理逼近3.6 三角多项式与快速傅里叶变换,2023/10/14,课件,2,3.1 函数逼近的基本概念,函数逼近与函数空间,1、数值计算中经常要计算函数值，如计算机中计算 基本初等函数及其他特殊函数；,2、当函数只在有限点集上给定函数值，要在包含该 点集的区间上用公式给出函数的简单表达式.,问题,2023/10/14,课件,3,插值法就是函数逼近问题的一种.,记作，,本章讨论的函数逼近，是指“对函数类 中给定的函数,中求函数，,使 与 的误差在某种度量,要在另一类简单的便于计算的函数类,意义下最小”.,函数类 通常是区间 上的连续函数，记作，,称为连续函数空间.,2023/10/14,课件,4,函数类 通常为 次多项式，有理函数或分段低次多项式等.,2023/10/14,课件,5,类似地,记 为具有 阶连续导数的函数空间.,记作.,对次数不超过(为正整数)的实系数多项式全体，,2023/10/14,课件,6,定义1,设集合 是数域 上的线性空间，元素,如果存在不全为零的数，,（1.1）,则称 线性相关.,否则，若等式(1.1)只对 成立，,则称 线性无关.,使得,2023/10/14,课件,7,系数 称为 在基,并称空间 为 维空间，,若线性空间 是由 个线性无关元素 生成的，,即对 都有,则 称为空间 的一组基，,记为,下的坐标，,记作,2023/10/14,课件,8,（1.2）,它由 个系数 唯一确定.,考察次数不超过 次的多项式集合，,它是 的一组基，,是线性无关的，,且 是 的坐标向量，是 维的.,表示为,其元素,故,2023/10/14,课件,9,使误差,(为任给的小正数)，,这就是著名的魏尔斯特拉斯定理.,2023/10/14,课件,10,使,定理1,在 上一致成立.,伯恩斯坦1912年给出的证明是一种构造性证明.,他根据函数整体逼近的特性构造出伯恩斯坦多项式,（1.3）,2023/10/14,课件,11,为二项式展开系数，并证明了,在 上一致成立；,若 在 上 阶导数连续，则,其中,这个结果不但证明了定理1，而且由(1.3)给出了 的一个逼近多项式，但它收敛太慢，实际中很少使用.,2023/10/14,课件,12,更一般地，可用一组在 上线性无关的函数集合,来逼近，,可表示为,（1.4）,此时元素,2023/10/14,课件,13,范数与赋范线性空间,为了对线性空间中元素大小进行衡量，需要引进范数定义，它是 空间中向量长度概念的直接推广.,2023/10/14,课件,14,定义2 设 为线性空间，若存在唯一实数，满足条件：,（1）当且仅当 时，（正定性）,（2）(齐次性),（3）(三角不等式),则称为线性空间 上的范数，与一起称为赋范线性空间，记为,2023/10/14,课件,15,例如，在 上的向量 三种常用范数为,称为 范数或最大范数，,称为 1-范数，,称为 2-范数.,2023/10/14,课件,16,而满足1=1 的向量 则为对角线长度为1的菱形.,在 中，满足2=1，即 的向量为单位圆，,满足=1，即 的向量为单位正方形，,2023/10/14,课件,17,所以说，范数是对向量长度的度量，度量方式不同，,结果也不一样，但不同范数之间是存在等价关系的.,2023/10/14,课件,18,类似地，对连续函数空间，若,称为 范数，,称为 1-范数，,称为 2-范数.,可以验证这样定义的范数均满足定义2中的三个条件.,可定义三种常用范数如下：,2023/10/14,课件,19,内积与内积空间,若将它推广到一般的线性空间，则有下面的定义.,（1.5）,2023/10/14,课件,20,定义3,则称 为X上 与 的内积.,2023/10/14,课件,21,定义中（1）的右端 称为 的共轭，,当K为实数域R时.,如果，则称 与 正交，这是向量相互垂直概念的推广.,定义了内积的线性空间称为内积空间.,2023/10/14,课件,22,定理2,对 有,（1.6）,称为柯西-施瓦茨(Cauchy-Schwarz)不等式.,证明,当 时（1.6）式显然成立.,现设，,则，,且对任何数 有,取，,设X为一个内积空间，,代入上式右端，得,2023/10/14,课件,23,即得 时,2023/10/14,课件,24,定理3,（1.7）,称为格拉姆(Gram)矩阵，,则 非奇异的充分必要条件是 线性无关.,设X为一个内积空间，,矩阵,2023/10/14,课件,25,证明,只有零解；,（1.9）,（1.8）,而,2023/10/14,课件,26,从以上等价关系知，,而后者等价于从（1.9）推出,即 线性无关.,在内积空间X上，可以由内积导出一种范数，即对于,（1.10）,等价于从（1.8）推出,记,2023/10/14,课件,27,两端开方即得三角不等式,（1.11）,利用,2023/10/14,课件,28,例1,与 的内积.,设,（1.12）,向量2-范数为,2023/10/14,课件,29,相应的范数为,（1.13）,若给定实数,称 为权系数，,当 时，,上的加权内积为,（1.13）就是前面定义的内积.,2023/10/14,课件,30,如果，,（1.14）,这里 仍为正实数序列，为 的共轭.,在 上也可以类似定义带权内积.,带权内积定义为,2023/10/14,课件,31,定义4,（1）存在且为有限值,（2）对 上的非负连续函数，如果,则称 为 上的一个权函数.,则,2023/10/14,课件,32,例2,设,是 上给定的权函数,（1.15）,由此内积导出的范数为,称（1.15）和（1.16）为带权 的内积和范数.,上的内积.,则可定义内积,（1.16）,2023/10/14,课件,33,常用的是 的情形，即,2023/10/14,课件,34,若 是 中的线性无关函数族，,（1.17）,根据定理3可知 线性无关的充要条件是,它的格拉姆矩阵为,记,2023/10/14,课件,35,函数逼近主要讨论给定，求它的最佳逼近多项式的问题.,最佳逼近,若 使误差则称 是 在 上的最佳逼近多项式.,若 则称相应的 为最佳逼近函数.,通常将范数 取为 或,2023/10/14,课件,36,若取，即,（1.18）,则称 是 在 上的最优一致逼近多项式.,求 就是求 上使最大误差 最小的多项式.,2023/10/14,课件,37,若取，即,则称 是 在 上的最佳平方逼近多项式.,（1.19）,若 是 上的一个列表函数，在 上给出，要求 使,则称 为 的最小二乘拟合.,（1.20）,2023/10/14,课件,38,3.2 正交多项式,正交函数族与正交多项式,定义5,（2.1）,则称 与 在 上带权 正交.,2023/10/14,课件,39,若函数族 满足关系,则称 是 上带权 的正交函数族.,若，则称之为标准正交函数族.,（2.2）,2023/10/14,课件,40,三角函数族,就是在区间 上的正交函数族.,定义6,2023/10/14,课件,41,（2.3）,只要给定区间 及权函数，均可由一族线性无关的幂函数 利用逐个正交化手续构造出正交多项式序列：,2023/10/14,课件,42,正交多项式 的最高次项系数为1.而若 是正交多项式，则 在 上是线性无关的.,事实上，若,用 乘上式并积分得,2023/10/14,课件,43,利用正交性有,（1）任何 均可表示为 的线性组合.即,由于，故即 线性无关.,关于正交多项式，有,2023/10/14,课件,44,（2）与任一次数小于 的多项式 正交.即,除此之外，还有,2023/10/14,课件,45,这里,定理4 设 是 上带权 的正交多项式，对 成立关系,（2.4）,其中,2023/10/14,课件,46,定理5 设 是 上带权 的正交多项式，则 在区间 内有 个不同的零点.,证明 假定 在 内的零点都是偶数重的，则 在 符号保持不变，这与,矛盾.故 在 内的零点不可能全是偶数重的，现设 为 在 内的奇数重零点，不妨设,则 在 处变号.,2023/10/14,课件,47,令,于是 在 上不变号，则得,若，由 的正交性可知,这与 矛盾，故.而 只有 个零点，故，即 个零点都是单重的.,2023/10/14,课件,48,勒让德多项式,罗德利克(Rodrigul）给出了简单的表达式,（2.5）,2023/10/14,课件,49,由于 是 次多项式，,所以对其求 阶导数后得,最高项系数为1的勒让德多项式为,（2.6）,于是得首项 的系数,2023/10/14,课件,50,勒让德多项式重要性质：,性质1,（2.7）,证明,令，则,设 是在区间 上 阶连续可微的函数，由分部积分知,正交性,2023/10/14,课件,51,下面分两种情况讨论:,（1）若 是次数小于 的多项式，,则,故得,2023/10/14,课件,52,则,（2）若,于是,由于,故,2023/10/14,课件,53,性质2,（2.8）,由于 是偶次多项式，经过偶次求导仍为偶次多项式，经过奇次求导则为奇次多项式，故 为偶数时 为偶函数，为奇数时 为奇函数，于是（2.8）成立.,奇偶性,2023/10/14,课件,54,性质3,考虑 次多项式,两边乘 并从-1到1积分，,递推关系,它可表示为,得,故得,2023/10/14,课件,55,当 时，,其中,左端积分仍为0，,故,于是,为奇函数，,2023/10/14,课件,56,由,从而得到以下的递推公式,（2.9）,利用上述递推公式就可推出,2023/10/14,课件,57,图3-1,图3-1给出了 的图形.,2023/10/14,课件,58,在区间 内有 个不同的实零点.,性质4,2023/10/14,课件,59,切比雪夫多项式,当权函数，区间为 时，由序列 正交化得到的正交多项式就是切比雪夫(Chebyshev)多项式.,它可表示为,（2.10）,若令，,则,2023/10/14,课件,60,性质1,切比雪夫多项式有很多重要性质：,这只要在三角恒等式,中，,令 即得.,递推关系,（2.11）,2023/10/14,课件,61,由（2.11）可推出,的函数图形见图3-2.,2023/10/14,课件,62,图3-2,由递推关系（2.11）还可得到 的最高次项系数是,2023/10/14,课件,63,性质2,（2.12）,令，,则，,于是,2023/10/14,课件,64,若令，则 是首项系数为1的切比雪夫多项式.,性质4,在区间 上有 个零点,性质3,这个性质由递推关系直接得到.,性质5 的首项 的系数为,2023/10/14,课件,65,若记 为所有次数小于等于 的首项系数为1的多项式集合，对 有以下性质：,定理6 设 是首项系数为1的切比雪夫多项式，则,且,2023/10/14,课件,66,定理6表明在所有首项系数为1的 次多项式集合 中，所以 是 中最大值最小的多项式，即,（2.13）,利用这一结论，可求 在 中的最佳（一致）逼近多项式.,2023/10/14,课件,67,由定理6可知，,多项式 与零偏差最小，,解,由题意，所求最佳逼近多项式 应满足,当,时，,故,例3,2023/10/14,课件,68,就是 在 上的最佳2次逼近多项式.,由于切比雪夫多项式是在区间 上定义的，对于一般区间，要通过变量替换变换到，可令,（2.14）,则可将 变换到,2023/10/14,课件,69,切比雪夫多项式 在区间 上有 个零点,切比雪夫多项式零点插值,和 个极值点（包括端点）,这两组点称为切比雪夫点，它们在插值中有重要作用.,2023/10/14,课件,70,从图3-3可以看到切比雪夫点恰好是单位圆周上等距分布点的横坐标，这些点的横坐标在接近区间 的端点处是密集的.,图3-3,利用切比雪夫点做插值，可使插值区间最大误差最小化.,设插值点 为相应的 次拉格朗日插值多项式，则余项,2023/10/14,课件,71,于是,其中,是由被插函数决定的.,如果插值节点为 的零点,2023/10/14,课件,72,则由（2.13）可得,由此可导出插值误差最小化的理论.,定理7 设插值节点 为切比雪夫多项式 的零点，被插函数 为相应的插值多项式，则,（2.15）,2023/10/14,课件,73,对于一般区间 上的插值只要利用变换（2.14）则可得到相应结果，此时插值节点为,2023/10/14,课件,74,例4 求 在 上的四次拉格朗日插值多项式，插值节点用 的零点并估计误差,解 利用 的零点和区间变换可知节点,即,对应的拉格朗日插值多项式为,2023/10/14,课件,75,利用（2.15）可得误差估计,而,于是有,2023/10/14,课件,76,在第2章中曾经指出，高次插值会出现龙格现象，一般 不收敛于，因此并不适用.但若用切比雪夫多项式零点插值却可避免龙格现象，可保证整个区间上收敛.,2023/10/14,课件,77,例5 设，在 上利用 的零点作插值点，构造10次拉格朗日插值多项式.与第2章得到的等距节点造出的 近似 作比较.,解 在 上的10次切比雪夫多项式 的零点为,作变换 它们是 内的插值点，由此得到 在 上的拉格朗日插值多项式,2023/10/14,课件,78,的图形见图3-4，从图上可见 没有出现龙格现象.,图3-4,2023/10/14,课件,79,其他常用的正交多项式,区间 及权函数 不同，则得到的正交多项式也不同.,除上述两种最重要的正交多项式外，下面是三种较常用的正交多项式.,1.第二类切比雪夫多项式,在区间 上带权 的正交多项式称为第二类切比雪夫多项式.,2023/10/14,课件,80,表达式为,（2.16）,令，,即 是 上带权 的正交多项式族.,可得,2023/10/14,课件,81,递推关系,2023/10/14,课件,82,2.拉盖尔多项式,在区间 上带权 的正交多项式称为拉盖尔(Laguerre)多项式.,其表达式为,（2.17）,正交性质,2023/10/14,课件,83,递推关系,2023/10/14,课件,84,表达式,（2.18）,正交关系,3.埃尔米特多项式,2023/10/14,课件,85,递推关系,2023/10/14,课件,86,3.3 最佳平方逼近,2023/10/14,课件,87,最佳平方逼近及其计算,对 及 中的一个子集,若存在，使,（3.1）,则称 是 在子集 中的最佳平方逼近函数.,2023/10/14,课件,88,由（3.1）可知该问题等价于求多元函数,（3.2）,的最小值.,是关于 的二次函数，,即,利用多元函数求极值的必要条件,2023/10/14,课件,89,于是有,（3.3）,这个关于 的线性方程组，称为法方程.,由于 线性无关，故,于是方程组（4.3）有唯一解,从而得到,2023/10/14,课件,90,即对任何,下面证明 满足（3.1），,（3.4）,为此只要考虑,有,2023/10/14,课件,91,由于 的系数 是方程（3.3）的解，,从而上式第二个积分为0，,故（3.4）成立.,这就证明了 是 在 中的最佳平方逼近函数.,故,于是,2023/10/14,课件,92,若令,（3.5）,则平方误差为,2023/10/14,课件,93,此时,若用 表示 对应的矩阵，,（3.6）,称为希尔伯特(Hilbert)矩阵.,即,2023/10/14,课件,94,记,（3.7）,的解 即为所求.,则,2023/10/14,课件,95,例6,设,解,得方程组,利用（3.7），得,2023/10/14,课件,96,解之,故,平方误差,最大误差,2023/10/14,课件,97,用正交函数族作最佳平方逼近,设,若 是满足条件(2.2)的正交函数族，,而,故法方程（3.3）的系数矩阵,则,2023/10/14,课件,98,为非奇异对角阵，,（3.8）,于是 在 中的最佳平方逼近函数为,（3.9）,且方程（3.3）的解为,2023/10/14,课件,99,由（3.5）可得均方误差为,（3.10）,由此可得贝塞尔(Bessel)不等式,（3.11）,2023/10/14,课件,100,若，,按正交函数族 展开，,（3.12）,称这个级数为 的广义傅里叶(Foureir)级数，,讨论特殊情况，设 是正交多项式，可由 正交化得到，则有下面的收敛定理.,得级数,系数,按（3.8）计算，,系数,称为广义傅里叶系数.,它是傅里叶级数的直接推广.,2023/10/14,课件,101,定理8,设,考虑函数,（3.13）,则有,展开，,由(3.8)，(3.9)可得,按勒让德多项式,2023/10/14,课件,102,根据均方误差公式(3.10)，平方误差为,（3.15）,由定理8可得,其中,（3.14）,2023/10/14,课件,103,如果 满足光滑性条件,还有 一致收敛于 的结论.,公式(2.6)给出了首项系数为1的勒让德多项式，,定理9,则对任意 和,当 充分大时有,设,由(3.13)给出，,它具有以下性质.,2023/10/14,课件,104,证明,定理10,勒让德多项式 在 上与零的平方误差最小.,在所有最高次项系数为1的 次多项式中，,它可表示为,2023/10/14,课件,105,于是,当且仅当 时等号才成立，,即当,时平方误差最小.,2023/10/14,课件,106,求 在 上的三次最佳平方逼近多项式.,例7,解,先计算,2023/10/14,课件,107,由(3.14)得,代入(3.13)得三次最佳平方逼近多项式,2023/10/14,课件,108,最大误差,如果 求 上的最佳平方逼近多项式，,均方误差,做变换,2023/10/14,课件,109,于是,在 上可用勒让德多项式做最佳平方逼近多项式,从而得到区间 上的最佳平方逼近多项式,2023/10/14,课件,110,直接通过解法方程得到 中的最佳平方逼近多项式是一致的.,只是当 较大时法方程出现病态，计算误差较大，不能使用，而用勒让德展开不用解线性方程组，不存在病态问题，因此通常都用这种方法求最佳平方逼近多项式.,2023/10/14,课件,111,切比雪夫级数,如果，按 展成广义傅里叶级数，由（3.12）可得级数,（3.16）,其中系数根据（3.8）式，由（2.12）得到,（3.17）,这里,级数（3.16）称为 在 上的切比雪夫级数.,2023/10/14,课件,112,若令，则（3.16）就是 的傅里叶级数，其中,（3.18）,根据傅里叶级数理论，只要 在 上分段连续，则 在 上的切比雪夫级数（3.16）一致收敛于.从而,（3.19）,2023/10/14,课件,113,（3.20）,取部分和,其误差为,在 上 是均匀分布的，它的最大值 最小，因此 可作为 在 上的近似最佳一致逼近多项式.,2023/10/14,课件,114,例8 求 在 上的切比雪夫部分和.,解 由（3.18）得,利用第4章的数值积分法得,由（3.20）及 的表达式有,及,2023/10/14,课件,115,3.4 曲线拟合的最小二乘法,最小二乘法及其计算,在函数的最佳平方逼近中 如果 只在一组离散点集 上给定，这就是科学实验中经常见到的实验数据 的曲线拟合.,2023/10/14,课件,116,记误差,2023/10/14,课件,117,设 是 上线性无关函数族，,在 中找一函数，,使误差平方和,（4.1）,这里,（4.2）,2023/10/14,课件,118,这个问题称为最小二乘逼近，几何上称为曲线拟合的最小二乘法.,用最小二乘求拟合曲线时,首先要确定 的形式.,确定 的形式问题不仅是数学问题,还与问题的实际背景有关.,通常要用问题的运动规律及给定的数据进行数据描图,确定 的形式,然后通过实际计算选出较好的结果.,2023/10/14,课件,119,为了使问题的提法更有一般性，通常在最小二乘法中考虑加权平方和,（4.3）,这里 是 上的权函数，它表示不同点 处的数据比重不同.,就是 次多项式.,若 是 次多项式，,的一般表达式为（4.2）表示的线性形式.,2023/10/14,课件,120,这样，最小二乘问题就转化为求多元函数,（4.4）,的极小点 问题.,由求多元函数极值的必要条件，有,使（4.3）取得最小.,2023/10/14,课件,121,若记,（4.5）,上式可改写为,（4.6）,这方程称为法方程，,可写成矩阵形式,2023/10/14,课件,122,其中,（4.7）,要使法方程(4.6)有唯一解，就要求矩阵 非奇异，,2023/10/14,课件,123,显然 在任意 个点上满足哈尔条件.,函数 的最小二乘解为,定义7,方程(5.6)存在唯一的解,从而得到,于是,2023/10/14,课件,124,这样得到的，,对任何形如(4.2)的，,都有,故 确是所求最小二乘解.,2023/10/14,课件,125,一般可取，但这样做当 时，,通常对 的简单情形都可通过求法方程（4.6）得到,给定 的离散数据，,例如，,求解法方程（4.6）将出现系数矩阵 为病态的问题，,若两边取对数得,2023/10/14,课件,126,这样就变成了形如（4.2）的线性模型.,此时，若令,则,2023/10/14,课件,127,例9,已知一组实验数据如下，求它的拟合曲线.,解,将所给数据在坐标纸上标出，见图3-5.,图3-5,2023/10/14,课件,128,从图中看到各点在一条直线附近，故可选择线性函数作拟合曲线，,令,这里,故,2023/10/14,课件,129,解得,由（4.6）得方程组,于是所求拟合曲线为,2023/10/14,课件,130,关于多项式拟合，Matlab中有现成的程序,其中输入参数 为要拟合的数据，为拟合多项式的次数，,输出参数 为拟合多项式的系数.,利用下面的程序，可在Matlab中完成上例的多项式拟合.,2023/10/14,课件,131,x=1 1 2 3 3 3 4 5;f=4 4 4.5 6 6 6 8 8.5;aa=poly(x,f,1);y=polyval(aa,x);plot(x,f,r+,x,y,k)xlabel(x);ylabel(y);gtext(y=s1(x)）,2023/10/14,课件,132,结果如下：,2023/10/14,课件,133,例10,设数据 由表3-2给出，,用最小二乘法确定 及.,表中第4行为,通过描点可以看出数学模型为,2023/10/14,课件,134,若令,先将 转化为,为确定，,根据最小二乘法，取,则得,数据表见表3-2.,得,解,它不是线性形式.,用给定数据描图可确定拟合曲线方程为,两边取对数得,2023/10/14,课件,135,故有法方程,解得,于是得最小二乘拟合曲线为,2023/10/14,课件,136,利用下面的程序，可在Matlab中完成曲线拟合.,x=1.00 1.25 1.50 1.75 2.00;y=5.10 5.79 6.53 7.45 8.46;y1=log(y);aa=poly(x,y1,1);a=aa(1);b=exp(aa(2);y2=b*exp(a*x);plot(x,y,r+,x,y2,k)xlabel(x);ylabel(y);gtext(y=a*exp(bx);,2023/10/14,课件,137,结果如下：,2023/10/14,课件,138,用正交多项式做最小二乘拟合,如果 是关于点集,（4.8）,用最小二乘法得到的法方程组（4.6），其系数矩阵 是病态的.,2023/10/14,课件,139,（4.9）,则方程（4.6）的解为,且平方误差为,2023/10/14,课件,140,接下来根据给定节点 及权函数,构造带权 正交的多项式.,注意，用递推公式表示，即,（4.10）,这里 是首项系数为1的 次多项式，,2023/10/14,课件,141,（4.11）,下面用归纳法证明这样给出的 是正交的.,2023/10/14,课件,142,假定 对 及,要证 对 均成立.,由（4.10）有,由（4.10）第二式及（4.11）中 的表达式，有,均成立，,（4.12）,2023/10/14,课件,143,而，,于是由（4.12），当 时，,另外，是首项系数为1的 次多项式，它可由,由归纳法假定，,当 时,的线性组合表示.,由归纳法假定又有,2023/10/14,课件,144,由假定有,再考虑,（4.13）,利用（4.11）中 表达式及以上结果，得,2023/10/14,课件,145,至此已证明了由（4.10）及（4.11）确定的多项式,组成一个关于点集 的正交系.,用正交多项式 的线性组合作最小二乘曲线拟合，,只要根据公式（4.10）及（4.11）逐步求 的同时，,相应计算出系数,最后，由 和 的表达式（4.11）有,2023/10/14,课件,146,并逐步把 累加到 中去，最后就可得到所求的,用这种方法编程序不用解方程组，只用递推公式，并且当逼近次数增加一次时，只要把程序中循环数加1，其余不用改变.,这里 可事先给定或在计算过程中根据误差确定.,拟合曲线,2023/10/14,课件,147,3.5 有 理 逼 近,有理逼近与连分式,有理函数逼近是指用形如,的函数逼近,与前面讨论一样，如果 最小就可得到最佳有理一致逼近.,（5.1）,2023/10/14,课件,148,如果 最小则可得到最佳有理平方逼近函数.,本节主要讨论利用函数的泰勒展开获得有理逼近函数的方法.,对函数 用泰勒展开得,（5.2）,取部分和,2023/10/14,课件,149,（5.3）,2023/10/14,课件,150,（5.4）,（5.3）右端为 的无穷连分式的前5项，最后式子,若取（5.3）的前2，4，6，8项，则可分别得到 的以下有理逼近,是它的紧凑形式.,2023/10/14,课件,151,若用同样多项的泰勒展开部分和 逼近,并计算 处的值 及，计算结果见表3-3.,的准确值为,从表3-1可以看出，,2023/10/14,课件,152,但它们的计算量是相当的，这说明用有理逼近比多项式逼近好得多.,由此看出 的精度比 高出近10万倍，,2023/10/14,课件,153,例11,用辗转相除法将它化为连分式并写成紧凑形式.,解 用辗转相除可逐步得到,给出有理函数,2023/10/14,课件,154,本例中用连分式计算 的值只需3次除法，1次乘法和7次加法.,2023/10/14,课件,155,若直接用多项式计算的秦九韶算法则需6次乘法和1次除法及7次加法.,可见将 化成连分式可节省计算乘除法次数.,对一般的有理函数,（5.1）可转化为一个连分式,它的乘除法运算只需 次.,而直接用有理函数（5.1）计算乘除法次数为 次.,2023/10/14,课件,156,帕德逼近,利用函数 的泰勒展开可以得到它的有理逼近.,设 在 的泰勒展开为,（5.5）,它的部分和记作,（5.6）,2023/10/14,课件,157,定义8,设,其中 无公因式，且满足条件,（5.8）,则称 为函数 在 处的 阶帕德逼近，,记作,简称 的帕德逼近.,如果有理函数,（5.7）,2023/10/14,课件,158,根据定义，若令,则满足条件（5.8）等价于,即,由于 应用莱布尼兹求导公式得,2023/10/14,课件,159,这里 是由（5.6）得到的，,上式两端除，,并由 可得,（5.9）,及,（5.10）,注意当 时,故（5.10）可写成,2023/10/14,课件,160,（5.11）,其中 时，,若记,（5.12）,2023/10/14,课件,161,则方程组（5.11）的矩阵形式为,定理11,2023/10/14,课件,162,根据定理11,求 的帕德逼近时，,首先要由（5.11）解出 的系数，,再由（5.9）直接算出 的系数.,的各阶帕德逼近可列成一张表，称为帕德表（见表3-4）.,2023/10/14,课件,163,例12,求 的帕德逼近 及.,解,由 的泰勒展开,得,当 时，由（5.11）得,求得,再由（5.9）得,2023/10/14,课件,164,于是得,当 时，由（5.11）得,2023/10/14,课件,165,代入（5.9）得,解得,于是得,2023/10/14,课件,166,为了求帕德逼近 的误差估计，由(5.9)及(5.11)求得的 系数 及，直接代入则得,将 除上式两端，即得,2023/10/14,课件,167,（5.13）,其中,当 时可得误差近似表达式,2023/10/14,课件,168,3.6 三角多项式逼近与快速傅里叶变换,当模型数据具有周期性时，用三角函数特别是正弦和余弦函数作为基函数是合适的，这时前面讨论的用多项式、分段多项式或有理函数作基函数都是不适合的.用正弦函数和余弦函数级数表示函数称为傅里叶变换（简称傅氏变换）.,2023/10/14,课件,169,最佳平方三角逼近与三角插值,设 是以 为周期的平方可积函数，用三角多项式,（6.1）,做最佳平方逼近函数.,由于三角函数族,在 上是正交函数族，于是 在 上的最小平方三角逼近多项式 的系数是,2023/10/14,课件,170,称为傅里叶系数.,函数 按傅里叶系数展开得到的级数,（6.3）,就称为傅里叶级数.,（6.2）,2023/10/14,课件,171,只要 在 上分段连续，则级数（6.3）一致收敛到.,对于最佳平方逼近多项式（6.1）有,由此可以得到相应于（3.11）的贝塞尔不等式,因为右边不依赖于，左边单调有界，所以级数,2023/10/14,课件,172,当 只在给定的离散点集,上已知时，则可类似得到离散点集正交性与相应的离散傅里叶系数.,下面只给出奇数个点的情形.,收敛，并有,2023/10/14,课件,173,可以证明对任何 成立,令,2023/10/14,课件,174,这表明函数族 在点集,上正交.,若令,其中,2023/10/14,课件,175,当 时,于是,（6.4）,就是三角插值多项式，系数仍由（6.4）表示.,2023/10/14,课件,176,由于,所以函数族 在区间 上是正交的.,2023/10/14,课件,177,当 时，个复向量 具有如下正交性：,（6.5）,2023/10/14,课件,178,事实上，令,于是,即,若,若,则有,则,从而,2023/10/14,课件,179,于是,若,这就证明了（6.5）成立.,即 是正交的.,则,于是,因此，在 个点 上的最小二乘傅里叶逼近为,2023/10/14,课件,180,（6.6）,其中,（6.7）,于是由（6.6）得,即,（6.8）,2023/10/14,课件,181,而（6.8）是由 求 的过程，称为反变换.,2023/10/14,课件,182,点DFT与FFT算法,不论是按（6.7）式由 求，,由 求，,（6.9）,其中 为已知的输入数据，为输出数据，而,还是由（6.4）计算傅里叶逼近系数,都可归结为计算,或是按（6.8）,2023/10/14,课件,183,当 较大且处理数据很多时，就是用高速的电子计算机，很多实际问题仍然无法计算，,（6.9）式称为 点DFT，表面上看计算 需要 次复数乘法和 次复数加法，称为 个操作，计算全部 共要 个操作.,直到20世纪60年代中期产生了FFT算法，大大提高了运算速度，才使DFT得到更广泛的应用.,FFT是快速算法的一个典范，其基本思想就是尽量减少乘法次数.,2023/10/14,课件,184,对于任意正整数，成立,由周期性可知所有 中，做多有 个不同的值.特别地，有,当 时，只有 个不同的值.,利用这些性质可将（6.9）式对半折成两个和式，再将对应项相加，有,2023/10/14,课件,185,依下标奇、偶分别考察，则,若令,则可将 点DFT归结为两个 点的DFT：,如此反复施行二分手续即可得到FFT算法.,2023/10/14,课件,186,以 为例说明FFT的计算方法，此时在（6.9）中将 记为，于是（6.9）式的和为,（6.10）,将 用二进制表示为,其中 只能取0或1.,例如,根据 表示法，有,2023/10/14,课件,187,公式（6.10）可表示为,（6.11）,若引入记号,（6.12）,2023/10/14,课件,188,则（6.11）变成,若注意 公式（6.12）还可进一步简化为,2023/10/14,课件,189,将这表达式中二进制表示还原为十进制表示：,（6.13）,即 得,同样（6.12）中的 也可简化为,即,2023/10/14,课件,190,把二进制表示还原为十进制表示，得,（6.14）,同理（6.12）中 可简化为,即,2023/10/14,课件,191,表示为十进制，有,（6.15）,根据公式(6.13)，(6.14)，(6.15)，由,逐次计算到,见表3-5(略）.,从表3-5中看到计算全部8个 只用8次乘法运算和24次加法运算.,2023/10/14,课件,192,上面推导的 的计算公式可类似地推广到 的情形.,根据公式(6.13)，(6.14)，(6.15)，一般情况的FFT计算公式如下：,（6.16）,其中,括号内的数代表它的位置，在计算机中代表存放数的地址.,2023/10/14,课件,193,从 出发，由 到 算到,一组 占用 个复数单元，计算时需给出两组单元，,即为所求.,计算过程中只要按地址号存放 则最后得到的就是所求离散频谱的次序.,这个计算公式除了具有不倒地址的优点外，计算只有两重循环.,外循环 由 计算到，内循环 由 计算到,由 计算到 更重要的是整个计算过程省计算量.,2023/10/14,课件,194,由公式看到算一个 共做 次复数乘法，,而最后一步计算 时，由于,当 时比值是 它比一般FFT的计算量（次乘法）也快一倍.,我们称（6.16）的计算公式为改进的FFT算法.,2023/10/14,课件,195,解 先将 变换为，可令，故输入数据为,例13 设.给定数据 确定三角插值多项式.,给定8个点可确定8个参数的4次三角插值多项式,（6.17）,这里,（6.18）,2023/10/14,课件,196,与（6.10）式比较可先计算,这里 代替（6.10）式的，,对每个 有,2023/10/14,课件,197,所以,即,显然，用FFT算法求出，也就得到（6.18）式的系数，从而得到（6.17）式的4次三角插值多项式,2023/10/14,课件,198,将 代入 可以得到 上的三角多项式,图3-6给出了 及 的图形.,表3-6给出了在点 处 与 的值.,图3-6,
