第三章 函数逼近与曲线拟合-上海海事大学

第三章函数逼近与计算与曲线拟合§1函数逼近的基本概念1.问题的提出通过观测、测量或试验得到某一函数在的函数值我们可以用插值的方法对这一函数进行近似,而插值方法要求所得到的插值多项式经过已知的这n＋1个插值结点;在n比较大的情况下,插值多项式往往是高次多项式,这也就容易出现振荡现象（龙格现象）:虽然在插值结点上没有误差,但在插值结点之外插值误差变得很大,从“整体”上看,插值逼近效果将变得“很差”。于是,我们采用函数逼近的方法。1所谓函数逼近是求一个简单的函数例如是一个低次多项式,这儿不要求通过已知的这n＋1个点,而是要求在整体上“尽量好”的逼近原函数。这时,在每个已知点上就会有误差数据拟合就是从整体上使误差尽量的小一些。22.数学描述“对函数类A中给定的函数

，要求在另一类较简单的便于计算的函数类B中，求函数使

与之差在某种度量意义下最小。”函数类A通常是区间[a,b]上的连续函数，记作C[a,b]；函数类B通常是代数多项式，分式有理函数或三角多项式。还可用一组C[a,b]上线性无关的函数集合所张成的子空间3度量标准最常用的有两种，一种是在这种度量意义下的函数逼近称为一致逼近或均匀逼近；另一种度量标准是用这种度量的函数逼近称为均方逼近或平方逼近这里符号是范数。本章主要研究在两种度量标准下用代数多项式及来逼近43.维尔斯特拉斯定理用Pn

(x)一致逼近f(x)，首先要解决存在性问题，即对[a,b]上的连续函数f(x),是否存在多项式Pn(x)一致收敛于f(x)？维尔斯特拉斯（Weierstrass）给出了下面定理：定理1设f(x)∈C[a,b]，则对任何ε>0总存在一个代数多项式P(x)，使在[a,b]上一致成立。伯恩斯坦构造性证明(P63)54.连续函数空间C[a,b]区间[a,b]上的所有实连续函数组成一个空间，记作C[a,b]。f∈C[a,b]的范数定义为称其为∞—范数，它满足范数的三个性质：III式称为三角不等式。III)对任意I)a为任意实数II)6伯恩斯坦构造性证明：假定函数的定义区间是[0,1],可通过线性代换：t=(b−a)x+a把x∈[0,1]映射到t∈[a,b]。对给定的f(x)∈C[0,1]，构造伯恩斯坦多项式,此为n次多项式:在[0,1]上一致成立7空间C[a,b]可与向量空间类比，函数f∈C[a,b]可看成向量。与向量空间类似，当f,g∈C[a,b]时定义f与g的距离为由III式可得到及8当k取所有合乎条件的正整数时，对于有[0,1]中的每一固定的x及任一固定正整数n，有其中

与分别表示对满足如下条件的一切k所取得和：9令M=maxf(x)，则有由10此不等式的右端与x无关,随着n的无限增大趋于零。这就证明了多项式序列对于f(x)的一致收敛性。这不但证明了定理1，而且给出了f(x)的一个逼近多项式它与拉格朗日插值多项式因此11是有界的，因而只要f(x)≤δ对任意x∈[0,1]成立，则有界，故是稳定的至于拉格朗日插值多项式由于无界，因而不能保证高阶插值的稳定性与收敛性。相比之下，多项式有良好的逼近性质，但它收敛太慢，比三次样条逼近效果差得多，实际中很少被使用。1213§2正交多项式系

不超过n次的多项式可以看成是幂函数基底｛1,x,x2,…,xn｝的线性组合.如果选择基函数为正交多项式系.可以有更好的性质.正交多项式系数值积分中也有重要用途.下面介绍正交多项式系.

正交函数系

定义

某函数系｛k(x)｝k=0,…,m.中每一个函数

k(x)都在［a,b］上连续且不恒为零，如果满足则称此函数系｛

k(x)｝为区间［a,b］上的正交函数系.更一般地，若有权函数ρ(x)≥0，即14则称此函数系｛k(x)｝,k=0,…,m,为区间［a,b］上关于权函数ρ(x)的正交函数系.例三角函数系：1，cosx，sinx，cos2x，sin2x，…是区间［-π，π］上的正交函数系，因为实际上，这就是付里叶(Fourier)逼近的基函数.15正交多项式系如果正交函数系为多项式系｛Pi(x)｝i=0,…,m，则称之为正交多项式系，即则称此多项式系为区间[a,b]上关于权函数ρ(x)的正交多项式系.只要给定区间及权函数

均可由线性无关的幂函数系｛1,x,x2,…,xn…..｝逐个正交化造出正交多项式系且性质见(P70)161.切比雪夫(Чебыщев)多项式当权函数区间为[-1,1]时,由幂函数系｛1,x,x2,…,xn｝正交化所得的正交多项式就是切比雪夫多项式(系)｛Tn(x)｝

可表示为

Tn(x)=cos(n

arccon

x)

x∈[-1,1]

如令x=cosθ,则Tn(x)=cosnθ切比雪夫多项式的性质:(P74)性质5递推关系T0(x)=1，T1(x)=x,Tn+1(x)=2xTn(x)-Tn-1(x)，n≥1(2.11)性质6

正交性Tk(x)它在[-1,1]上关于权函数ρ(x)=1/(1-x)2正交，即17它的前7个多项式如下表：T0(x)=1

T1(x)=xT2(x)=2x2-1T3(x)=4x3-3xT4(x)=8x4-8x2+1T5(x)=16x5-20x3+5xT6(x)=32x6-48x4+18x2-1性质7

T2k(x)只含x的偶次幂,T2k+1(x)只含x的奇次幂.

即Tn(x)随n为奇或偶函数.18性质８

Tn(x)在区间[-1,1]上有n个零点性质

Tn(x)的最高项系数为2n-1(n1).性质

|Tn(x)|1这是因为Tn(x)=cos(narccosx)的缘故.192.勒让德(Legendre)多项式系｛Pk(x)｝(P71)性质:

Tn(x)在区间[-1,1]上有n+1个不同的极值点使Tn(x)轮流取得最大值1和最小值-1.也称为Tn(x)的交错点组．当权函数区间为[-1,1]时,由幂函数系｛1,x,x2,…,xn｝正交化所得的正交多项式就是勒让德多项式(系)记为｛Pk(x)｝证:20在实际计算中，往往需要计算有：１=T0(x)

x=T1(x)x2=(T0(x)+T2(x))/2x3=(

3T1(x)+T3(x))/4x4=(3T0(x)+4T2(x)+T4(x))/8x5=(10T1(x)+5T3(x)+T5(x))/16x6=(10T0(x)+15T2(x)+6T4(x)+T6(x))/3221它也可由如下递推公式(P71性质3)P0(x)=1，P1(x)=x(2.9)Pk+1(x)=[(2k+1)/(k+1)]x

Pk(x)-[k/(k+1)]Pk-1(x)，k≥1它的前7式如下表：P0(x)=1P1(x)=xP2(x)=(3x2-1)/2P3(x)=(5x3-3x)/2P4(x)=(35x4-30x2+3)/8P5(x)=(63x5-70x3+15x)/8P6(x)=(231x6-315x4+105x2-5)/1622性质1它在［-1,1］上关于权函数ρ(x)≡1正交，即3.其他常用的正交多项式(P77)拉盖尔(Laguerre)多项式系｛Lk(x)｝(2.7)

性质2

Pn(-x)=(-1)n

Pn(x)(2.8)性质4

Pn(x)在区间[-1,1]内有n个不同的实零点.性质

Pn(x)的的最高幂次xn系数为故是最高项系数为1的勒让德多项式23正交多项式还有一个重要性质：以上各种正交多项式的零点全部是单实根，且都分布在它的正交定义区间内.这个性质在数值积分中有应用.它的前7式如下表：H0(x)=1,H1(x)=2x,H2(x)=4x2-2H3(x)=8x3-12xH4(x)=16x4-48x2+12H5(x)=32x5-160x3+120xH6(x)=64x6-480x4+720x2-120第二类切比晓夫多项式(P77)24它也可用如下递推公式写出：L0(x)=1，L1(x)=1-xLk+1(x)=(2n+1-x)Lk(x)-n2Lk-1(x)，k≥1(7.18)它在[0，+∞)上关于权函数ρ(x)=e-x正交，即它的前7式如下：L0(x)=1L1(x)=1-xL2(x)=2-4x+x2L3(x)=6-18x+9x2-x3L4(x)=24-96x+72x2-16x3+x4L5(x)=120-600x+600x2-200x3+25x4-x5L6(x)=720-4320x+5400x2-2400x3+450x4-36x5+x625埃尔米特(Hermite)多项式系｛Hk(x)｝它可由如下递推公式写出H0(x)=1,H1(x)=2xHk+1(x)=2xHk(x)-2kHk-1(x)，k≥1它在(-∞，+∞)上关于权函数ρ(x)=e-x2正交，即26§3最佳一致逼近多项式常称之为三维欧几里德空间,就是一个线性赋范空间.

基本概念及理论线性赋范空间定义

在线性空间X中,对每一个元x引进一个度量‖x‖,称为x的范数,这时线性空间X就称为线性赋范空间,若

yX,则称‖x-y‖为元素x与y的距离.例

在R3中,任一xR3定义范数27例在连续函数空间C[a,b]中.定义范数,设fC[a,b],则C[a,b]成为线性赋范空间.如果设MC[a,b],M是C[a,b]的一个子空间,为最小,寻找(x)M,使得则称(x)为M中对f(x)的最佳一致逼近函数.2828定义

设f(x)C[a,b],‖f‖

已定义,Hn为不超过n次的多项式的集合,Hn显然是C[a,b]的子空间,寻找Pn(x)Hn,使为最小,则称Pn(x)为Hn中对f(x)的n次最佳一致逼近多项式.最佳一致逼近多项式以下定理保证了最佳一致逼近多项式的存在唯一性.定理4

设f(x)C[a,b],Hn为不超过n次的多项式的集合,则存在唯一的En称为f(x)在[a,b]上的最小偏差.证明略.29最佳一致逼近多项式的特征为讨论最佳一致逼近多项式的构造方法,先讨论它的特征.先给出偏差点的概念:对连续函数f(x)和p(x),其差的绝对值也必连续,故在[a,b]上存在x0,使x0称为p(x)对f(x)的偏差点.若p(x0)-f(x0)>0,称x0为正偏差点若p(x0)-f(x0)<0,称x0为负偏差点切比晓夫给出了最佳一致逼近多项式的特征定理.30定理5

Pn(x)Hn,Pn(x)为最佳一致逼近多项式的充要条件是Pn(x)在[a,b]上至少有n+2个交错偏差点,即

a

x0<x1<…<xn<xn+1

b使得为1或-1.证明见P79.定理5说明Pn(xi)-f(xi)至少在n+2个点上交错变号,都达到最大偏差幅度‖f-Pn

‖

,因此在整个[a,b]上误差分布比较均匀.求最佳一致逼近多项式是十分困难的,以下定理可解决在某些简单情况下的求解.定理

f

(n+1)(x)在(a,b)上存在且保号（保持恒正或恒负),则

Hn中对f(x)的最佳一致逼近多项式恰有n+2个交错偏差点,且两端点a,b都是偏差点.证：用反证法,设偏差点超过n+2个或至少有一个端点不是偏差点,则(a,b)内部的偏差点至少有n+1个.这些偏差点即误差函数的极值点,即该点的导数应为零.有R'(xi)=f'(xi)-P'n(xi)=0,i=1,2,…,n+1由罗尔定理R"(x)应至少有n个互异零点在(a,b)内.R

(n+1)(x)=f(n+1)(x)-P

(n+1)

n(x)应至少有一个零点i

(a,b).注意到P

(n+1)

n(x)0,得f

(n+1)(i)=0,与假设的f(n+1)(x)在[a,b]内保号矛盾，得证.因此,在f

(n+1)(x)在(a,b)上存在且保号，只要在(a,b)内再找出n个交错偏差点,特别地,在n=1时,只要在(a,b)内找出一个偏差点,问题比较简单.最佳一次逼近多项式(P82)假设f(x)二次连续可导,且导数不变号,求最佳一致逼近多项式根据定理5知至少有3个点x0,x1,x2,使且x0=a,x2=b例求最佳一致逼近多项式解上恒负,设交错偏差点为x0,x1,x2,则有x0=1/4,x2=1，还要求一个x1就行了。可解得:见P82图3-3由偏差点定义有由(2)解出由(3)解出代入(1)得到在一般情况下,求最佳一致逼近多项式很困难.一是采取逐次逼近的方法,如雷米兹(Remes)方法,二是退而求其次,求近似最佳一致逼近多项式.近似最佳一致逼近多项式对一般函数,求最佳一致逼近多项式极为困难.常用近似最佳一致逼近多项式替代.为此,先讨论切比雪夫多项式的最小零偏差性质,然后引入两种近似方法.定理6(最小零偏差定理)在[-1,1]上,首项系数为1的一切n次多项式Pn(x)中,wn(x)=21-nTn(x)对0的偏差最小,即:证由性质知wn(x)是首项系数为1的n次多项式.若另有一首项系数为1的n次多项式Pn(x)对零的偏差比wn(x)对零的偏差小,即:由性质知是Tn(x)的交错偏差点组,轮流取(-1)k.得知wn(x)在x*k处轮流取(-1)k21-n,所以因此Pn(x*k)-wn(x*k)在n+1个点上轮流取正负号,由连续函数的性质知,Pn(x*k)-wn(x*k)在(-1,1)上至少有n个不同的零点.但由于Pn(x)-wn(x)的最高次项系数均为1,故Pn(x)-wn(x)只能是不超过n-1的多项式,不可能有n个零点.引出矛盾，得证。切比雪夫节点插值即拉格朗日插值余项的极小化设在[-1,1]上n+1个点xk,(k=0,1,…,n)上的代数插值多项式为Pn(x),其截断误差如何选取xk使为最小?由最小零偏差定理,只要选择xk使为n+1次切比雪夫多项式Tn+1(x)零点就可以了,这里此时有当插值区间不是[-1,1]而是一般[a,b]时,可作变换后得到为[a,b]上的所求节点.在此基础上作插值函数Pn(x)它可作为最佳一致逼近多项式的一种近似.这种求f(x)在[a,b]上的近似最佳一次多项式的方法称为切比雪夫节点插值.以上方法将误差项中的两个影响因素中之一控制到最小.对很多函数,这样的近似方法是相当好的.特别地,当f(x)是只比Pn(x)高一次的多项式时,Pn(x)就是最佳一致逼近多项式.

例f(x)=ex,用切比雪夫节点插值求[-1,1]上的近似最佳一致逼近多项式P1(x)=a1x+a0解取二次切比雪夫多项式节点:作一次插值多项式此处t是可选择的常数,选择t使f(x)与tT3(x)的3次项系数一样,以消去x3项.解因为f(3)(x)=24,切比雪夫节点插值多项式就是最佳一致逼近多项式.例f(x)=4x3+2x2+x+1,x[-1,1],

求作次数不超过2次的多项式P2(x)为f(x)的最佳一致逼近多项式.选择t=1,消去x3项.P2(x)=2x2+4x+1是f(x)的最佳一致逼近多项式缩减幂级数法对f(x)的泰勒级数就是f(x)的一种近似,但泰勒级数的误差分布极不均匀,在展开点附近误差很小,但x的值稍偏离展开点,误差迅速增大.而切比雪夫多项式的误差分布则比较均匀.于是可以设计出以下方法:将f(x)作m次泰勒展开,得部分和Pm(x),然后将Pm(x)中的x各次幂全部表为切比雪夫多项式之和,整理后,将Pm(x)缩减为n次多项式(n<m)Pn(x),Pn(x)可作为近似最佳一次逼近多项.例15f(x)=ex,x[-1,1],求其一次和四次近似最佳一致逼近多项式.解:将ex作泰勒展开到第7项由表7-11,可得:注意到|Tn(x)|1,T5和T6的系数又已很小,于是有误差若ex直接展开到第4次得到的泰勒级数,误差约为0.0227,比|R|大得多.同是四次近似多项式,可知P4(x)的误差相当小,也可作为近似最佳一致逼近多项式.若在(7.21)中只取前二项,得可作为近似最佳一致逼近的一次多项式.最佳一致逼近考虑的是整个区间上绝对误差的最大值,计算时非常困难.另一方面,对于那些仅有个别小区段上有较大误差的函数,反而不能很好地反映其真实情况.本节介绍最佳平方逼近,引入另一个近似标准.§4最佳平方逼近内积和内积空间对C[a,b]空间引进内积:若f,gC[a,b],则为f与g的内积.这样C[a,b]就成为一种线性赋范空间,通常称为内积空间.内积可用来定义2-范数:内积空间中,若两个元素内积为零,则称此二元素正交,如f,gC[a,b],有则称函数f和g

正交.若C[a,b]中已定义内积,则最佳平方逼近可描述为:fC[a,b],则S*(x)称Ø中对f(x)的最佳平方逼近函数.为C[a,b],的子空间,选择S*(x)Ø,使最佳平方逼近定理

C[a,b]是内积空间,Ø是其有限维子空间,fC[a,b],Ø中S*(x)是f(x)的最佳平方逼近函数的充要条件是f-S*与Ø中任一元正交.(证明)根据以上特征定理,不难得出最佳平方逼近函数的求法.设Ø的基底为{

k}k=0,1,…,n,则对任意S(x)Ø,有由上述定理,误差函数应与Ø中任意元正交,即与基底k,k=0,1,…,n中任一元正交:或改写为这是一个关于aj(j=0,1,…,n)的n+1阶线性方程组,称为正规方程组(或法方程组),简记为定理(4.3)的解存在且唯一.故由矩阵形式:求解出a0,a1,…,an即可得到最佳平方逼近函数:证任给n+1维非零向量x=(x0,x1,…,xn)

T因为

i是Ø的基底,故

i线性无关,它的线性组合在x

i不全为0时不恒为0.所以xTAx>0.这表明A是对称正定矩阵,故A非奇异.(4.3)的解存在且唯一。例10设f(x)=ex,x[0,1],求最佳二次平方逼近多项式

P2(x)=c0+c1x+c2x2解这里Ø=span{1,x,x2}则有解c0=1.013,c1=0.851,c2=0.839所以P2(x)=1.013+0.851x+0.839x2注意系数阵是以自然数的倒数顺序排成的对称矩阵,称为希尔伯特矩阵(P85).当n稍高时,它是典型的病态矩阵,求解时舍入误差很大,可能导致计算失败,所以以上方法不适用于较高次数的多项式逼近.正交多项式在逼近和拟合中的应用正交多项式系在最佳平方逼近中可使问题大大简化，由(4.3)式当选择Ø的基函数为正交多项式系时,所以以上系数阵就成了对角阵，即因为根本用不着解方程组，只要计算上式就行了.为此fC[a,b],在Ø中的最佳平方逼近函数为误差为:定理9在所有最高项系数为1的n次多项式中,勒让德多项式在[-1,1]上与零的平方误差为最小.(P89)例12设求它在［-1,1］上的三次最佳平方逼近多项式.解:取勒让德多项式系中为基函数证(充分性)设S是Ø中任意元,则S

*-S也是Ø中元素,有所以S

*是最佳平方逼近函数.(必要性)反证法设Ø中S*是f的最佳平方逼近函数,但存在S

Ø使记(S,S)=,易证

>0(因为若

=0,则S=0,则

=0).所以S*不是f的最佳平方逼近函数,引出矛盾.继续讨论用简单函数近似代替较复杂函数的问题.上章提到的插值就是近似代替的方法之一,插值的近似标准是在插值点处误差为零.但在实际应用中,有时不要求具体某些点误差为零,而要求考虑整体的误差限制,这就引出了拟合和逼近的概念.§5曲线拟合的最小二乘对离散型函数(即数表形式的函数)考虑数据较多的情况.若将每个点都当作插值节点,则插值函数是一个次数很高的多项式,比较复杂.而且由于龙格振荡现象,这个高次的插值多项式可能并不接近原函数.同时由于数表中的点一般是由观察测量所得,往往带有随机误差,要求近似函数过所有的点既不现实也不必要.

如果不是要求近似函数过所有的数据点,而是要求它反映原函数整体的变化趋势,可得到更简单更适用的近似函数,这样的方法称为数据拟合.数据拟合最常用的近似标准是最小二乘法则：设f(x)为原函数,S(x)为近似函数,(xi

,f(xi))(i=0,1,…,m)为数据点,要求选择S(x)使为最小.这里即找:S*当S(x)选择为多项式时,称为多项式拟合.最小二乘拟合,特别是多项式拟合,是最流行的数据处理方法之一.它常用于把实验数据(离散的数据)归纳总结为经验公式(连续的函数),以利于进一步的推演分析或应用.如果记:类似于平方逼近得法方程(P92):超定方程组的最小二乘解设Ax=b中A=(aij)m×n,b是m维已知向量,x是n维解向量.当m>n时,即方程组中方程的个数多于未知量个数时,称此方程组为超定方程组或矛盾方程组.一般说,超定方程组无解.但有时需要寻找一个“最近似”的解.记r=b-Ax,定义使‖r‖2为最小的解x*为Ax=b的最小二乘解.关于超定方程组的最小二乘解有如下定理定理

x*为Ax=b的最小二乘解的充要条件为ATAx*=ATb.以上定理说明求解超定方程组Ax=b的最小二乘解可转化为求解它对应的正规方程组ATAx*=ATb.ATA是对称正定的系数阵,此方程组可用平方根法或SOR方法求解.证明多项式拟合最小二乘如k(x)=xk仍假设有已知数据组(xi,yi)(i=0,1,2,…,m).现求作一个不超过n(n<m)次多项式使得记ri=yi-Sn(xi)(i=0,1,2,…,m),r=(r0,r1,…,rm)T,不难看出以上多项式最小二乘拟合问题就是求解关于ak(k=0,1,…,n)的超定方程组.把ak当作变量,上述方程组的矩阵记法为是一个超定方程组.由定理可得对应的正规方程组以上的∑记号均为从0到m求和,记;则上式可改写为通过解该正规方程组便可解出ak

,从而确定出拟合多项式Sn(x).多项式拟合的一般方法可归纳为：(1)根据具体问题,确定拟合多项式的次数n；(2)计算(3)写出正规方程组(4)解正规方程组,求出a0,a1,…,an；(5)写出拟合多项式Sn(x)

解首先作平面散点图如下：

从图中观察,这5个点大致在一条抛物线的附近,可考虑用二次多项式进行拟合。yx12345123456789100

然后计算正则方程组(m=4)设正规方程组的解为：则以此解为系数的多项式就是最小二乘拟合多项式。

例设5组数据如下表,用一多项式对其进行拟合。的系数如下表：用高斯-若当无回代消去法解此方程组,得a0=13.454,a1=-3.657,a2=0.272。正则方程组为

最小二乘拟合多项式为：非线性曲线转化为线性:有些非线性曲线可以转化为线性,从而用线性拟合进行处理,比如：例3:已知数据为x12345678y15.320.527.436.649.165.687.811