最佳一致逼近多项式课件.ppt

1、3.3 3.3 最佳一致逼近多项式最佳一致逼近多项式 3.3.1 3.3.1 基本概念及其理论基本概念及其理论 设,baCf 在 中求多项式,1nnxxspanH),(*xPn)()(max*xPxfPfnbxan这就是最佳一致逼近或切比雪夫逼近问题.使其误差.minnHPPfnn1 显然 ，0),(nPf记为 ，),(nPf 定义定义7 7nnPfPf),(为 与 在 上的偏差偏差.)(xf)(xPn,ba 若记集合的下确界为),(infnHPnPfEnn则称之为 在 上的最小偏差最小偏差.)(xf,ba,)(,baCxfHPnn设称其下界为0.),(nPf的全体组成一个集合，（3.1）)(

2、)(maxxPxfnbxa（3.2）,)()(maxinfxPxfnbxaHPnn2 定义定义8 8,),(*nnEPf（3.3）则称 是 在 上的最佳一致逼近多项式最佳一致逼近多项式nnHxP)(*)(xf,ba 定理定理4 4则总存在 ，nnHxP)(*.)()(*nnExPxf这个定理是最佳逼近多项式的存在性定理.,baCf 假定nnHxP)(*若存在使得简称最佳逼近多项式最佳逼近多项式.,baCf 若使或最小偏差逼近多项式最小偏差逼近多项式，3 定义定义9 9,)(nHxP若在 上有0 xx,)()(max)()(00 xfxPxfxPbxa就称 是 的偏差点偏差点.0 x)(xP 若

3、,)()(00 xfxP称 为“正正”偏差点偏差点.0 x 若,)()(00 xfxP称 为“负负”偏差点偏差点.0 x 由于函数 在 上连续，)()(xfxP,ba在一个点,0bax,)()(00 xfxP所以说 的偏差点总是存在的.)(xP,baCf 设因此，至少存使4要证明的是“负”的偏差点，,)()()1()()(xfxPxfxPkkk这样的点组称为切比雪夫交错点组切比雪夫交错点组.证明证明 假定在 上有 个点使（3.4）成立，,ba2n 定理定理5 5即有 个点 ，bxxxan 2212n在 上至少有 个轮流为“正”、)(xP,ba2n是 的最佳逼近多项式nHxP)(,baCf 的充

4、分必要条件是使是 在 上的最佳逼近多项式)(xf,ba)(xP只证充分性.（3.4）,15 用反证法，若存在 ，)()(,)(xPxQHxQn.)()()()(xPxfxQxf由于)()()()()()(xfxQxfxPxQxP在点 上的符号与221,nxxx)2,1)()(nkxfxPkk故 也在 个点上轮流取“+”、“-”号.)()(xQxP2n 由连续函数性质，它在 内有 个零点，但因,ba1n0)()(xQxP是不超过 次的多项式，n不能超过 .n使所以它的零点个数一致，6 这说明假设不对，故 就是所求最佳逼近多项式.)(xP 必要性证明略.推论推论1 1 若 ，,baCf 充分性得证

5、.则在 中存在唯一的最佳逼近nH多项式.7 证明证明)(21)(1xTxnnn)(max21)(max11111xTxnxnnx且点 是 的切比雪夫交错点组，),1,0(cosnknkxk)(xTn 定理定理6 6在区间 上所有最高次项系数为1的 次多1,1n项式中，)(21)(1xTxnnn与零的偏差最小，.211n其偏差为由于),(*1xPxnn,211n8由定理5可知，即 是与零的偏差最小的多项式.)(xn区间 上 在 中最佳逼近多项式1,1nx1nH),(*1xPn为定理得证.9.min)()(max*211xPxfx由定理6可知，)(21)()(3*2xTxPxf时，多项式 与零偏差

6、最小，)()(*2xPxf求 在 上的最佳2次逼122)(23xxxxf1,1 解解由题意，所求最佳逼近多项式 应满足)(*2xP当xx2323故例例3 3近多项式.10)(21)()(3*2xTxfxP就是 在 上的最佳2次逼近多项式.)(xf1,11272xx11 3.3.2 3.3.2 最佳一次逼近多项式最佳一次逼近多项式 定理5给出了 的特性，这里讨论具体求法.)(xP 先讨论 的情形.1n 假定,2baCf 且 在 内不变号，)(xf ),(ba求最佳一次逼近多项式 .xaaxP101)(根据定理5可知,至少有3个点,321bxxxa)()(max)1()()(11xfxPxfxPb

7、xakkk).3,2,1,1(k我们要使12,0)()()(2122xfaxfxP即 .12)(axf 由于 在 上不变号，)(xf ,ba故 单调，)(xf 1)(axf在 内只有一个零点，记为 ，),(ba2x 另外两个偏差点必是区间端点，即 且,21bxax)()()()(11bfbPafaP由此得到 于是满足).()(221xfxP13解出 代入（3.5）得).()()();()(2102101010 xaaxfafaaabfbaaafaaa（3.5）),()()(21xfabafbfa（3.6）这就得到最佳一次逼近多项式 ，其几何意义如图3-3.)(1xP.2)()(2)()(220

8、 xaabafbfxfafa（3.7）14 直线 与弦MN平行，且通过MQ的中点D，)(1xPy).2()()(21212xaxaxfafy图3-3其方程为15由（3.6）可算出 例例4 4求 在 上的最佳一次逼近多项式.21)(xxf1,0 解解,414.0121a又 ,1)(2xxxf,4551.02122x由（3.7），得,121222 xx故解得.0986.11)(222xxf16,414.0955.0)(1xxP即;10,414.0955.012xxx（3.8）误差限为.045.0)(1max1210 xPxx于是得 的最佳一次逼近多项式为 21x,955.0221121220 xa

9、xa17在（3.8）中若令,1abx.414.0955.022baba则可得一个求根式的公式183.4 3.4 最佳平方逼近最佳平方逼近19 3.4.1 3.4.1 最佳平方逼近及其计算最佳平方逼近及其计算 对 及 中的一个子集,)(baCxf,baC)(,),(),(10 xxxspann若存在 ，使)(*xS22)(22*)()(min)()(xSxfxSxfxS.)()()(min2)(baxSdxxSxfx（4.1）则称 是 在子集 中的最佳平方逼近最佳平方逼近函数函数.)(*xS)(xf,baC20 由（4.1）可知该问题等价于求多元函数 banjjjndxxfxaxaaaI2010

10、)()()(),(（4.2）的最小值.是关于 的二次函数，),(10naaaInaaa,100kaI),1,0(nk即 baknjjjkdxxxfxaxaI)()()()(20),1,0(nk利用多元函数求极值的必要条件 21于是有)(),()(),(0 xxfaxxknjjjk).,1,0(nk（4.3）这个关于 的线性方程组，称为法方程法方程.naaa,10 由于 线性无关，故)(,),(),(10 xxxn0),(det10nG于是方程组（4.3）有唯一解),1,0(*nkaakk).()()(*0*0*xaxaxSnn从而得到22即对任何,)(xS 下面证明 满足（4.1），)(*xS

11、babadxxSxfxdxxSxfx22*)()()()()()(（4.4）为此只要考虑 babadxxSxfxdxxSxfxD2*2)()()()()()(badxxSxfx2*)()()(badxxSxfxSxSx.)()()()()(2*有23 由于 的系数 是方程（4.3）的解，)(*xS*ka0)()()()(*bakdxxxSxfx),1,0(nk从而上式第二个积分为0，,0)()()(2*badxxSxSxD故（4.4）成立.这就证明了 是 在 中的最佳平方逼近函数.)(*xS)(xf故于是24若令),()()(*xSxfx)()(),()()(*22xSxfxSxfx)(),(

12、)(),(*xfxSxfxf,)(*1*0*nnxaxaaxS 若取,1,0)(,1)(,)(Cxfxxxkk中求 次最佳平方逼近多项式n（4.5）.)(),()(0*22nkkkxfxaxf则平方误差为nH则要在25此时,11)(),(10jkdxxxxjkkj 若用 表示 对应的矩阵，H),1(nnxxGG)12/(1)2/(1)1/(1)2/(13/12/1)1/(12/11nnnnnH H（4.6）称为希尔伯特希尔伯特(Hilbert)矩阵矩阵.)()(),(10kkkddxxxfxxf即26 记,),(),(1010TnTnddddaaaa,dHa（4.7）的解 即为所求.),1,0

13、(*nkaakk则27 例例5 5设,1)(2xxf求 上的一次最佳平方1,0 解解10201dxxd10211dxxxd得方程组,609.0147.13/12/12/1110aa逼近多项式.利用（4.7），得,147.122)21ln(213122,609.0102/32)1(31x28解之,426.0,934.010aa故.426.0934.0)(*1xxS平方误差)(),()(),()(*122xfxSxfxfx01102934.0426.0)1(dddxx最大误差.066.0)(1max)(*1210 xSxxx.0026.029 3.4.2 3.4.2 用正交函数族作最佳平方逼近用正

14、交函数族作最佳平方逼近 设,)(baCxf),(,),(),(10 xxxspann若 是满足条件(2.2)的正交函数族，)(,),(),(10 xxxnjixxji,0)(),(而 0)(),(xxjj故法方程（4.3）的系数矩阵)(,),(),(10 xxxGGnn则30为非奇异对角阵，)(),(/()(),(*xkxxfakkkk).,1,0(nk（4.8）于是 在 中的最佳平方逼近函数为,)(baCxfnkkkkxxxxfxS022*).()()(),()(（4.9）且方程（4.3）的解为31由（4.5）可得均方误差为 2*2)()()(xSxfxnn.)()(),()(2102222

15、nkkkxxxfxf（4.10）由此可得贝塞尔贝塞尔(Bessel)不等式不等式.)()(22122*xfxankkk（4.11）32 若 ，,)(baCxf按正交函数族 展开，)(xk0*)(kkkxa（4.12）称这个级数为 的广义傅里叶广义傅里叶(Foureir)级数级数，)(xf 讨论特殊情况，设 是正交多项式，可由 正交化得到，则有下面的收敛定理.)(,),(),(10 xxxn),(,),(),(10 xxxspann),1,0)(nkxknxx,1得级数系数),1,0(*kak按（4.8）计算，*ka系数称为广义傅里叶系数广义傅里叶系数.它是傅里叶级数的直接推广.33 定理定理7

16、 7设,)(baCxf.0)()(lim2*xSxfnn 考虑函数,1,1)(Cxf),()()()(*1*10*0*xPaxPaxPaxSnnn（4.13）)(xf的最佳平方逼近多项式，)(*xS是由（4.9）给出的,1,0),(nkxk其中是正交多项式族，则有)(,),(),(10 xPxPxPn展开，由(4.8)，(4.9)可得按勒让德多项式 34根据均方误差公式(4.10)，平方误差为.122)()(02*11222nkkkakdxxfx（4.15）由定理7可得.0)()(lim2*xSxfnn其中)(),()(),()(*xPxPxPxfxakkkk（4.14）11.)()(212d

17、xxPxfkk35 如果 满足光滑性条件,还有 一致收敛于 的结论.)(xf*nS)(xf.)()(*nxSxfn 公式(2.6)给出了首项系数为1的勒让德多项式 ，nP 定理定理8 8则对任意 和1,1x,0当 充分大时有n,1,1)(2 Cxf设)(*xSn由(4.13)给出，它具有以下性质.3610),()()(nkkknnxPaxPxQ 证明证明设 是任意一个最高次项系数为1的 次)(xQnn 定理定理9 9勒让德多项式 在 上与零的平方误差最小.)(xPn1,1在所有最高次项系数为1的 次多项式中，n多项式，它可表示为37于是)(),()(22xQxQxQnnn102)(),()()

18、,(nkkkknnxPxPaxPxP当且仅当 时等号才成立，0110naaa)(),(xPxPnn22)(xPn即当)()(xPxQnn时平方误差最小.112)(dxxQn38 例例6 6 求 在 上的三次最佳平方逼近多项式.xexf)(1,1 解解110)(),(dxexPxfx111)(),(dxxexPxfx1122)2123()(),(dxexxPxfx)(),(xPxfk).3,2,1,0(k先计算;3504.21ee;7358.021e;1431.07ee1133)2325()(),(dxexxxPxfx.02013.05137ee39由傅里叶系数计算公式(4.14)得,1752.

19、12/)(),(0*0 xPxfa,1036.12/)(),(31*1xPxfa,3578.02/)(),(52*2xPxfa.07046.02/)(),(73*3xPxfa代入(4.13)得三次最佳平方逼近多项式.1761.05367.09979.09963.0)(32*3xxxxS40最大误差.0112.0)()(*3xSexxn 如果 求 上的最佳平方逼近多项式，,)(baCxf,ba22abtabx),11(t均方误差 2*32)()(xSexxn.0084.011302*2122kkxakdxe做变换41于是),22()(abtabftF在 上可用勒让德多项式做最佳平方逼近多项式 1

20、,1),(*tSn从而得到区间 上的最佳平方逼近多项式,ba).2(1(*baxabSn42nnxaxaaxS10*)(直接通过解法方程得到 中的最佳平方逼近多项式是一致的.nH 由于勒让德多项式 是在区间 上由 )(xPk1,1 只是当 较大时法方程出现病态，计算误差较大，不能使用，而用勒让德展开不用解线性方程组，不存在病态问题，因此通常都用这种方法求最佳平方逼近多项式.n,1kxx 正交化得到的，因此利用函数的勒让德展开部分和得到最佳平方逼近多项式与由433.5 3.5 曲线拟合的最小二乘法曲线拟合的最小二乘法 3.5.1 3.5.1 最小二乘法及其计算最小二乘法及其计算 在函数的最佳平方

21、逼近中 如果 只在一组离散点集 上给定，这就是科学实验中经常见到的实验数据 的曲线拟合.,)(baCxf)(xf,1,0,mixi,1,0),(miyxii44 记误差,1,0,)(*miyxSiii则 的各分量分别为 个数据点上的误差.Tm),(10m 问题为利用 求出一个函数,1,0),(mixfyii)(*xSy 与所给数据 拟合.,1,0),(miyxii45 设 是 上线性无关函数族，)(,),(),(10 xxxn,baC在 中找一函数 ，)(,),(),(10 xxxspann)(*xS使误差平方和miiimiiyxS02*0222)(miiixSyxS02)()(min（5.1

22、）这里)()()()(1100 xaxaxaxSnn)(mn（5.2）46 这个问题称为最小二乘逼近，几何上称为曲线拟合的最小二乘法.用最小二乘求拟合曲线时,首先要确定 的形式.)(xS 确定 的形式问题不仅是数学问题,还与问题的实际背景有关.)(xS 通常要用问题的运动规律及给定的数据进行数据描图,确定 的形式,然后通过实际计算选出较好的结果.)(xS47 为了使问题的提法更有一般性，通常在最小二乘法中考虑加权平方和.)()(0222miiiiyxSx（5.3）这里 是 上的权函数，它表示不同点 处的数据比重不同.0)(x,ba)(,(iixfx就是 次多项式.)(xSn 若 是 次多项式，

23、)(xkk 的一般表达式为（5.2）表示的线性形式.)(xS48 这样，最小二乘问题就转化为求多元函数),(10naaaIminjiijjixfxax002)()()(（5.4）的极小点 问题.),(*1*0naaa 用最小二乘法求拟合曲线的问题，就是在形如(5.2)的 中求一函数 ，)(xS)(*xSy 由求多元函数极值的必要条件，有 minjikiijjikxxfxaxaI000)()()()(2).,1,0(nk使（5.3）取得最小.49若记,)()()(),(0miikijikjxxx（5.5）kmiikiikdxxfxf0)()()(),().,1,0(nk上式可改写为 knjjjk

24、da0),().,1,0(nk（5.6）这方程称为法方程法方程，可写成矩阵形式50其中,),(,),(1010TnTnddddaaaa.),(),(),(),(),(),(),(),(),(101110101000nnnnnnG（5.7）而 在 上线性无关不能推出)(,),(),(10 xxxn,ba.dGa 要使法方程(5.6)有唯一解，就要求矩阵 非奇异，G矩阵 非奇异，必须加上另外的条件.G51哈尔条件，则法方程(5.6)的系数矩阵(5.7)非奇异，显然 在任意 个点上满足哈尔条件.nxx,1)(nmm 如果 在 上满足,)(,),(),(10baxxxnmix0函数 的最小二乘解为)(

25、xf 定义定义1010设 的任意线,)(,),(),(10baxxxn则称 在点集 )(,),(),(10 xxxn性组合在点集 上至多只有 个)(,1,0,nmmixin不同的零点，,1,0,mixi上满足哈尔哈尔(Haar)条件条件.,1,0,*nkaakk方程(5.6)存在唯一的解从而得到于是52,)()()()()()(0202*miiiimiiiixfxSxxfxSx这样得到的 ，)(*xS对任何形如(5.2)的 ，)(xS).()()()(*1*10*0*xaxaxaxSnn都有故 确是所求最小二乘解.)(*xS53一般可取 ，但这样做当 时，,1nxxspan3n通常对 的简单情

26、形都可通过求法方程（5.6）得到 1n).(*xS 给定 的离散数据 ，,1,0),(miyxii)(xf 有时根据给定数据图形，其拟合函数 表面上)(xfy 例如，bxaexS)(,ln)(lnbxaxS求解法方程（5.6）将出现系数矩阵 为病态的问题，G不是（5.2）的形式，但通过变换仍可化为线性模型.若两边取对数得54 例例7 7113125.8865.4454321iiifx这样就变成了形如（5.2）的线性模型.此时，若令 则,ln),(ln)(bBaAxSxS,)(BxAxS已知一组实验数据如下，求它的拟合曲线.55 解解 从图中看到各点在一条直线附近，故可选择线性函数作拟合曲线，将

27、所给数据在坐标纸上标出，见图3-4.图3-456 令,)(101xaaxS,8),(4000ii,22),(),(400110iiix,74),(40211iiix,47),(400iiiff.5.145),(401iiiifxf,1)(,1,40 xnm这里故,)(1xx57.5.1457422472281010aaaa解得.13.1,77.210aa.13.177.2)(*1xxS由（5.6）得方程组 于是所求拟合曲线为58 关于多项式拟合，Matlab中有现成的程序 ),(myxpolyfita 其中输入参数 为要拟合的数据，为拟合多项式的次数，yx,m输出参数 为拟合多项式的系数.a

28、利用下面的程序，可在Matlab中完成上例的多项式拟合.59x=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)）60结果如下：61 例例8 8设数据 由表3-1给出，)4,3,2,1,0)(,(iyxii,bxaey 用最小二乘法确定 及 .ab135.2008.2876.1756.1629.146.845.753.679.510.500.275.150.125.100.143210iiiyyxi1表3

29、 解解,lniiyy表中第4行为通过描点可以看出数学模型为它不是线性形式.,bxaey 用给定数据描图可确定拟合曲线方程为两边取对数得62 若令,ln,lnaAyy先将 转化为),(iiyx),(iiyx为确定 ，bA,根据最小二乘法，取,1)(,)(,1)(10 xxxx,lnlnbxay.,1,xbxAy则得数据表见表3-1.得,5),(00,5.7),(4010iix,875.11),(40211iix63.422.14),(401iiiyxy,404.9),(400iiyy故有法方程.422.14875.1150.7404.950.75bAbA解得.071.3,505.0,122.1AeabA.071.3505.0 xey 于是得最小二乘拟合曲线为 64 利用下面的程序，可在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);65结果如下：66