函数逼近与快速傅里叶变换

第3章函数逼近与快速傅里叶变换3.1函数逼近的基本概念3.2正交多项式3.3最佳平方逼近3.4曲线拟合的最小二乘法3.5有理逼近3.6三角多项式与快速傅里叶变换ApproximationofFunctionandFastFourierTransform1/15/20231函数逼近与快速傅立叶变换问题的提出在实际问题中,函数解析式未知，函数往往通过实验观测得到的一组数据，即仅仅已知某个区间[a,b]上的一系列点的函数值。y=f(x)f(x)解析式未知或计算复杂插值问题问题的提出问题1：如何根据实验观测数据，在某个区间[a,b]上给出其他点的函数值。问题2：如何求出函数，使其在“一定意义下”逼近实验观测数据。曲线拟合问题数值逼近（Approximation）逼近理论是研究如何将函数利用一组简单函数近似表征，并定量分析逼近过程中产生的误差。（

Approximationtheoryisconcernedwithhowfunctionscanbestbeapproximatedwithsimplerfunctions,andwithquantitativelycharacterizingtheerrorsintroducedthereby.）数值逼近包括两大类：插值和拟合定义：插值（interpolate）

已知函数在xi处的值为yi

，求p(x)，使之满足：

yi

=p(xi)

其中，p(x)为插值函数，xi处为插值节点，插值节点的区间称为插值区间，yi

=p(xi)为插值条件。插值函数必须经过插值点。拟合函数不必经过拟合点。拟合（fit）已知函数在xi处的值为yi

，求p(x)，使之满足：e=‖yi

-p(xi)‖在给定的准则下最小。差异：1/15/20235函数逼近与快速傅立叶变换函数插值存在的问题：举例：存在的问题(1)观测数据yi

本身有误差，不准确，即yi

f(xi)。若仍要求函数在每个节点与实验数据相符，显然不合理。(2)为了使所找的函数更准确，常采用很多观测数据，即n

很大，会产生多节点实际问题低次数的矛盾；1/15/20237函数逼近与快速傅立叶变换10次多项式插值样条插值当观测点数大于问题的次数时，插值为超定方程，可能无解。当误差存在时，要求逼近函数必须经过观测点不合理。1/15/20238函数逼近与快速傅立叶变换曲线拟合问题解决思路：求一函数，使其在“一定意义下”逼近实验观测数据。当数据有误差及数据点太多，这时没必要取P(xi)=yi,而要使P(xi)yi

总体上尽可能小。曲线拟合放松了逼近函数必须经过观测点的要求，而求一函数，使其在“一定意义下”逼近实验观测数据。常见做法：

使最小(使最大值最小化问题)

太复杂使最小不可导，求解困难使最小（最小二乘方法）3.1函数逼近的基本概念

3.1.1函数逼近与函数空间

1、数值计算中经常要计算函数值，如计算机中计算基本初等函数及其他特殊函数；

2、当函数只在有限点集上给定函数值，要在包含该点集的区间上用公式给出函数的简单表达式.函数逼近在区间上用简单函数逼近已知复杂函数的问题对函数类A中给定的函数f(x)，要求在另一类简单的便于计算的函数类B中，求函数p(x)BA，使p(x)与f(x)之差（误差）在某种度量意义下最小。

A:C[a,b]B:代数多项式，有理分式函数，三角多项式.连续函数空间1/15/202311函数逼近与快速傅立叶变换函数空间线性空间—数域上的非空集合定义了加法和数乘，满足

8条运算规律；1)

、

实数域上的全体矩阵，对矩阵的加法和数乘运算构成实数域上的线性空间，记作．2)、

次数不超过n的多项式全体，对多项式的加法和数乘多项式运算构成线性空间，记作．3)、

在区间上全体实连续函数，对函数的加法与数和函数的数量乘法，构成实数域上的线性空间．1/15/202312函数逼近与快速傅立叶变换定义1设集合是数域上的线性空间，元素如果存在不全为零的数，（1.1）则称线性相关.否则，则称线性无关.使得(2)对都有则称为空间的一组基，

(1)是线性空间中个线性无关的元素记系数称为在基并称空间为维空间，下的坐标，记作如果中有无限个线性无关元素则称为无限维线性空间.线性空间的基、维数及向量的坐标是无限维的1/15/202313函数逼近与快速傅立叶变换（1.2）它由个系数唯一确定.它是的一组基，是线性无关的，且是的坐标向量，是维的.表示为故Hn={次数不超过(≤)n的代数多项式}C[a,b],魏尔斯特拉斯定理使

定理1总存在一个代数设，则对任何，在上一致成立.多项式，(Weierstrass定理)Weierstrass,德，1885年提出，时年70岁；1912年Bernstein(俄)证明1/15/202314函数逼近与快速傅立叶变换注:1.设f(x)C[0,1],

伯恩斯坦1912年给出的证明是一种构造性证明.2.则在[0,1]上一致成立。若f(x)在[0,1]m阶导数连续，则当，有只要，则与lagrange插值相比稳定性较好，但收敛较慢。1/15/202315函数逼近与快速傅立叶变换是逼近f(x)的函数类，（1.4）设，在上线性无关，使在某种意义下最小.找一个元素，在子空间Φ中连续函数最佳逼近的一般提法2、逼近条件的度量标准1、确定函数类逼近条件1/15/202316函数逼近与快速傅立叶变换3.1.2范数与赋范线性空间

赋范线性空间（1）当且仅当时，（正定性）（2）(齐次性)（3）(三角不等式)则称‖·‖为线性空间上的范数，与‖·‖一起称为赋范线性空间，记为

定义2

设为线性空间，，若存在唯一实数‖·‖，满足条件：

几种常用线性空间的范数1)、在上的向量三种常用范数为范数或最大范数，1-范数，2-范数.1/15/202317函数逼近与快速傅立叶变换在中，满足‖·‖2=1，即的向量为单位圆;满足‖·‖∞=1，即的向量为单位正方形.2)、连续函数空间的范数，若,范数，

1-范数，

2-范数.定义三种常用范数如下：线性空间+赋范数=赋范线性空间线性空间+赋内积=内积空间3.1.3内积与内积空间中两个向量及内积（1.5）1/15/202318函数逼近与快速傅立叶变换

内积空间定义3则称为X上与的内积.X

是数域K(R或C)上的线性空间，对有K中一个数与之对应，记为，它满足条件定义了内积的线性空间称为内积空间.-的共轭当K为实数域R时

.如果，则称与正交.向量相互垂直概念的推广1/15/202319函数逼近与快速傅立叶变换（1.6）称为柯西-施瓦茨(Cauchy-Schwarz)不等式.定理2对有设X为一个内积空间，证明当时（1.6）式显然成立.现设，则，且对任何数有取，代入上式右端，得即得时

内积空间的性质1/15/202320函数逼近与快速傅立叶变换定理3（1.7）线性无关.设X为一个内积空间，矩阵称为格拉姆(Gram)矩阵，则非奇异的充分必要条件是1/15/202321函数逼近与快速傅立叶变换在内积空间X上，由内积定义的范数，即对于（1.10）记范数三角不等式（1.11）利用

内积范数

几种线性空间中的内积及其内积范数1)、与的内积.设（1.12）1/15/202322函数逼近与快速傅立叶变换相应的范数为（1.13）若给定实数称为权系数，上的加权内积为（1.14）这里仍为正实数序列，为的共轭.如果，带权内积向量2-范数

2)、上的内积.设是上给定的权函数,（1.15）带权内积（1.16）范数1/15/202323函数逼近与快速傅立叶变换定义4设是有限或无限区间，在上的非负函数满足条件：（1）存在且为有限值（2）对上的非负连续函数，如果则称为上的一个权函数.则不同线性空间中的Cauchy-Schwarz不等式1/15/202324函数逼近与快速傅立叶变换（1.17）由定理3可知线性无关的充要条件是

它的格拉姆矩阵为若是中的线性无关函数族，定理31/15/202325函数逼近与快速傅立叶变换3.1.4最佳逼近若使误差则称是在上的最佳逼近多项式.最佳逼近函数及其多项式若，使误差则称相应的

为最佳逼近函数.连续函数的最佳一致逼近多项式（1.18）1/15/202326函数逼近与快速傅立叶变换（1.19）称为的最小二乘拟合.（1.20）若是上的一个列表函数，在

上给出，要求使连续函数的最佳平方逼近多项式求就是求上使最大误差最小的多项式.离散数据的最小二乘拟合1/15/202327函数逼近与快速傅立叶变换3.2正交多项式

3.2.1正交函数族与正交多项式定义5(2.1)则称与在上带权正交.若上的权函数且满足为若函数族满足关系(2.2)则称是上带权的正交函数族.

若，则称之为标准正交函数族.三角函数族区间上的正交函数族.正交函数族1/15/202328函数逼近与快速傅立叶变换定义6设是上首项系数的次多项式，为上权函数，则称多项式序列为在上带权正交，称为上带权的次正交多项式.如果多项式序列关系式(2.2)，满足给定区间及权函数，可由一族线性无关的幂函数利用Schemite正交化过程构造出正交多项式序列：（2.3）正交多项式在C[a,b]中构造正交多项式最高次项系数为1.1/15/202329函数逼近与快速傅立叶变换例3求区间[-1,1]上,权函数(x)=1的正交多项式.

解

p0(x)=1,按Schemite正交化过程有1/15/202330函数逼近与快速傅立叶变换若是正交多项式，则在上是线性无关的.设用乘上式并积分得利用正交性由于，故正交多项式的性质(1)即线性无关.1/15/202331函数逼近与快速傅立叶变换(2)

任何均可表示为的线性组合.即

(3)

与任一次数小于的多项式正交.即这里（2.4）其中定理4

设是上带权的首项系数为1的正交多项式，对成立关系(4)1/15/202332函数逼近与快速傅立叶变换证明：1/15/202333函数逼近与快速傅立叶变换故在内的零点不可能全是偶数重的。则在处变号.证明现设为在内的奇数重零点，不妨设

令于是在上不变号，则得定理5

设是上带权的正交多项式，则在区间内有个不同的零点.(5)由若，由的正交性可知,0)()()(),(==òdxxqxxqbannjrj矛盾1/15/202334函数逼近与快速傅立叶变换3.2.2勒让德多项式（2.5）表达式最高项系数为1的勒让德多项式为（2.6）正交化由于是次多项式，所以对其求阶导数后得首项系数1/15/202335函数逼近与快速傅立叶变换勒让德多项式的性质性质1（2.7）证明正交性令，则设是在区间上阶连续可微的函数，由分部积分知

（1）若是次数小于的多项式，则故得

（2）若1/15/202336函数逼近与快速傅立叶变换由于故性质2（2.8）奇偶性则于是性质3递推关系考虑次多项式可表示为1/15/202337函数逼近与快速傅立叶变换两边乘并从-1到1积分，故得当时，次数小于等于，为0，上式左端积分当时，左端积分仍为0，故为奇函数，其中于是1/15/202338函数逼近与快速傅立叶变换递推公式（2.9）由可推出图3-1在区间内有个不同的实零点.性质41/15/202339函数逼近与快速傅立叶变换3.2.3切比雪夫多项式（2.10）若令，则性质1递推关系（2.11）三角恒等式表达式切比雪夫多项式的性质1/15/202340函数逼近与快速傅立叶变换图3-2（2.11）的最高次项系数是的函数图形见右.在[-1，1]上有n+1个极值点1/15/202341函数逼近与快速傅立叶变换（2.12）性质2切比雪夫多项式在区间上带权正交，且令，则，于是性质3只含的偶次幂，只含的奇次幂.性质4在区间上有个零点1/15/202342函数逼近与快速傅立叶变换性质5

的首项的系数为记为所有次数小于等于的首项系数为1的多项式集合，定理6

设是首项系数为1的切比雪夫多项式，则且首项系数为1的切比雪夫多项式及其性质（2.13）是中最大值最小的多项式，即—最小零偏差多项式在区间[-1,1]上，n次首1的Chebyshev多项式是零函数的最佳一致逼近多项式求在中的最佳一致逼近多项式.应用1/15/202343函数逼近与快速傅立叶变换多项式与零偏差最小，解由题意，所求最佳逼近多项式应满足当故例1求在上的2次最佳一致逼近多项式。就是在上的2次最佳一致逼近多项式.即有限区间的转化问题有限区间经过下列变换可变为区间（2.14）1/15/202344函数逼近与快速傅立叶变换3.2.4切比雪夫多项式零点插值切比雪夫点零点极值点插值最大误差最小化—切比雪夫零点插值设插值点为相应的次拉格朗日插值多项式，则余项其中是由被插函数决定的.在[-1,1]上如何选取节点使得插值误差最小？1/15/202345函数逼近与快速傅立叶变换则插值误差最小化如果插值节点为的零点定理7

设插值节点为切比雪夫多项式的零点，被插函数为相应的插值多项式，则（2.15）一般区间上的插值利用变换1/15/202346函数逼近与快速傅立叶变换选插值节点相应地这时1/15/202347函数逼近与快速傅立叶变换例2

求在上的四次拉格朗日插值多项式，插值节点用的零点并估计误差解即利用这些节点构造差商表，得到插值多项式作变换将[0,1]变换到[-1,1]误差估计而故插值节点为1/15/202348函数逼近与快速傅立叶变换

例3

设，在上利用的零点作插值点，构造10次拉格朗日插值多项式.与第2章得到的等距节点造出的近似作比较.在上的11次切比雪夫多项式的零点为作变换它们是内的插值点，由此得到在上的拉格朗日插值多项式在第2章中曾经指出，高次插值会出现龙格现象，一般不收敛于，因此并不适用.但若用切比雪夫多项式零点插值却可避免龙格现象，可保证整个区间上收敛.解1/15/202349函数逼近与快速傅立叶变换的图形见图3-4，从图上可见没有出现龙格现象.图3-41/15/202350函数逼近与快速傅立叶变换1/15/202351函数逼近与快速傅立叶变换3.3.1最佳平方逼近及其计算3.3最佳平方逼近连续函数最佳平方逼近问题的一般提法—内积空间带权内积范数对及中的一个子集若存在，使（3.1）则称是在子集中的最佳平方逼近函数.1/15/202352函数逼近与快速傅立叶变换问题1)、是否存在？唯一？2)、如何构造？3)、误差举例选取常数a,b使达到最小解答设确定a,b使最小，必须满足即1/15/202353函数逼近与快速傅立叶变换问题等价于求多元函数（3.2）的最小值.最佳平方逼近函数的存在性是关于的二次函数，即利用多元函数求极值的必要条件（3.3）这个关于的线性方程组，称为法方程.

1/15/202354函数逼近与快速傅立叶变换由于线性无关，故于是法方程组有唯一解即对任何下面证明满足（3.1），（3.4）有考虑=0于是是最佳平方逼近函数1/15/202355函数逼近与快速傅立叶变换平方误差—最佳平方逼近误差令（3.5）平方误差为最大误差用多项式空间作为逼近函数类在Hn中求最佳平方逼近

若取中求次最佳平方逼近多项式则要在此时1/15/202356函数逼近与快速傅立叶变换若用表示对应的矩阵，（3.6）希尔伯特(Hilbert)矩阵.

即记（3.7）的解即为所求.则

Hilbert阵是一种典型的病态矩阵，随着n的增大病态越严重。法方程组是病态方程组，数值计算结果不稳定。

改用正交多项式构造最佳平方逼近多项式。1/15/202357函数逼近与快速傅立叶变换解得方程组例4设求上的一次最佳平方逼近多项式.解之故平方误差最大误差1/15/202358函数逼近与快速傅立叶变换3.3.2用正交函数族作最佳平方逼近设

若是满足条件(2.2)的正交函数族，而故法方程（3.3）的系数矩阵则为非奇异对角阵，（3.8）最佳平方逼近函数（3.9）且方程（3.3）的解为1/15/202359函数逼近与快速傅立叶变换均方误差（3.10）贝塞尔(Bessel)不等式（3.11）定理8设的最佳平方逼近多项式，是由（3.9）给出的其中是正交多项式族，则有收敛性用Legendre多项式求最佳平方逼近多项式由正交化得到的正交多项式1/15/202360函数逼近与快速傅立叶变换（3.13）由(3.8)，(3.9)可得勒让德多项式其中（3.14）考虑函数（3.15）平方误差由定理8定理9则对任意和当充分大时有设由(3.13)给出，1/15/202361函数逼近与快速傅立叶变换求在上的三次最佳平方逼近多项式.例5解先计算又代入1/15/202362函数逼近与快速傅立叶变换得三次最佳平方逼近多项式最大误差均方误差如果求上的最佳平方逼近多项式，做变换于是在上可用勒让德多项式做最佳平方逼近多项式从而得到区间上的最佳平方逼近多项式1/15/202363函数逼近与快速傅立叶变换首项系数为1的勒让德多项式，

证明定理10勒让德多项式在上与零的平方误差最小.在所有最高次项系数为1的次多项式中，设是任意一个最高次项系数为1的次多项式可表示为于是当且仅当时等号才成立，即当时平方误差最小.1/15/202364函数逼近与快速傅立叶变换若，按正交函数族展开，（3.12）称这个级数为的广义傅里叶(Foureir)级数，得级数系数按（3.8）计算，系数称为广义傅里叶系数.f(x)的广义傅氏展开练习求函数在[0,1]上的一次最佳平方逼近多项式。1/15/202365函数逼近与快速傅立叶变换3.3.3切比雪夫级数如果，按展成广义傅里叶级数，由（3.12）可得级数（3.16）其中系数（3.17）这里级数（3.16）称为在上的切比雪夫级数.根据傅里叶级数理论，只要在上分段连续，则在上的切比雪夫级数（3.16）一致收敛于.从而（3.19）1/15/202366函数逼近与快速傅立叶变换（3.20）取部分和其误差为在上是均匀分布的，它的最大值最小，因此可作为在上的近似最佳一致逼近多项式.函数在内积空间中的最佳平方逼近。对，用契比雪夫多项式构造的最佳平方逼近多项式是其近似的最佳一致逼近多项式。总结1/15/202367函数逼近与快速傅立叶变换例6

求在上的切比雪夫部分和.解利用第4章的数值积分法得由及由得及的表达式得1/15/202368函数逼近与快速傅立叶变换1/15/202369函数逼近与快速傅立叶变换1/15/202370函数逼近与快速傅立叶变换3.4曲线拟合的最小二乘法

3.4.1最小二乘法及其计算最小二乘法的背景和实例最小二乘法起源于以测量和观测为基础的天文学。

Gauss在1794年用最小二乘法解决了多余观测问题，当时他只有17岁。k12345678

xk01234567

yk1.41.31.41.11.31.81.62.3

假定通过观测或实验得到如下一组数据：

用一简单的式子表出这些数据之间的关系。分析：这些点差不多分布在一条直线上。用y=a+bx表示这些数据之间的关系。确定a、b。矛盾方程组的求解1/15/202371函数逼近与快速傅立叶变换假定用某种方法可以确定出a和b，则k12345678

xk01234567

yk1.41.31.41.11.31.81.62.3记误差最小二乘法就是确定参数a和b，使得最小。使最小，则有1/15/202372函数逼近与快速傅立叶变换设已知记误差

问题为利用求出一个函数与所给数据拟合.设是上线性无关函数族，在中找一函数，使误差平方和(4.1)这里(4.2)离散数据的最佳平方逼近问题的一般提法—最小二乘逼近xix0x1…

xmf(xi)f(x0)f(x1)…f(xm)1/15/202373函数逼近与快速傅立叶变换最小二乘法中通常考虑加权平方和（4.3）这里是上的权函数，它表示不同点处的数据比重不同.最小二乘法求拟合曲线就是在形如中求一函数，使取得最小.确定S(x)的方法——数据描图拟合标准1/15/202374函数逼近与快速傅立叶变换最小二乘曲线拟合问题的法方程最小二乘问题等价于求多元函数(4.4)的极小点问题.求多元函数极值的必要条件，有若记(4.5)

(4.6)法方程1/15/202375函数逼近与快速傅立叶变换其中(4.7)法方程的矩阵形式要使法方程而在上线性无关不能推出矩阵非奇异，必须加上另外的条件.有唯一解，就要求矩阵非奇异，(4.6)法方程的系数矩阵非奇异的条件1/15/202376函数逼近与快速傅立叶变换定义7设的任意线性组合在点集上至多只有个不同的零点，则称在点集上满足哈尔(Haar)条件.结论在任意个点上满足哈尔条件.哈尔条件，则法方程的系数矩阵非奇异，如果在上满足法方程存在唯一的解从而于是函数的最小二乘解为且故确是所求最小二乘解.一般取法1/15/202377函数逼近与快速傅立叶变换例7已知一组实验数据如下，求它的拟合曲线.

解将所给数据在坐标纸上标出，见图3-5.图3-5选线性函数作拟合曲线令这里故1/15/202378函数逼近与快速傅立叶变换解得法方程所求拟合曲线为多项式拟合的Matlab现程序其中输入参数为要拟合的数据，为拟合多项式的次数，输出参数为拟合多项式的系数.上例的Matlab多项式拟合x=[11233345];f=[444.566688.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)’）1/15/202379函数逼近与快速傅立叶变换结果如下：1/15/202380函数逼近与快速傅立叶变换

(1)

，两边取对数线性模型则令非线性拟合模型的线性化例8设数据由表3-2给，用最小二乘法确定及.表中第4行为通过描点可以看出数学模型为1/15/2023