用正交多项式做最小二乘拟合精品文档

13.5.2用正交多项式做最小二乘拟合如果是关于点集)(,),(),(10xxxn带权),,1,0(}{mixi),,1,0()(mixi,0,0)()()(),(0kmiikijikjAxxx,kj,kj（5.8）用最小二乘法得到的法方程组（5.6），其系数矩阵是病态的.G函数族，即2miikimiikiikkkkxxxxfxfa020*)()()()()(),(),().,,1,0(nk（5.9）则方程（5.6）的解为且平方误差为.)(02*2222nkkkaAf3接下来根据给定节点及权函数mxxx,,,10,0)(x构造带权正交的多项式.)(x)}({xPn注意，用递推公式表示，即mn)(xPk)()()()(),()()(,1)(1110110xPxPxxPxPxxPxPkkkkk).1,,2,1(nk（5.10）根据的)(xPk这里是首项系数为1的次多项式，)(xPkk正交性，得4miikimiikiikxPxxPxx02021)()()()(),(),(11kkkkPPPP（5.11）).1,,2,1(nk下面用归纳法证明这样给出的是正交的.)}({xPk))(),(())(),((xPxPxPxxPkkkk),(),(kkkkPPPxPmiikimiikikxPxxPx02102)()()()(5),(),(),(0010010PPxPPPP假定对及)(0),(slPPsl1,,1,0ls;,,1,0kl要证对均成立.0),(1skPPks,,1,0由（5.10）有),(),)((),(111skkskkskPPPPxPP由（5.10）第二式及（5.11）中的表达式，有1),(),(),(),(00000000PPPPPxPxPP.0nk均成立，（5.12）).,(),(),(11skkskkskPPPPPxP6而，11ks,0),(),(skskxPPPxP于是由（5.12），当时，2ks.0),(1skPP另外，是首项系数为1的次多项式，它可由)(xxPs1s由归纳法假定，当时20ks,0),(slPP.0),(1skPP110,,,sPPP的线性组合表示.由归纳法假定又有7由假定有),(),(11kkkkxPPPxP再考虑（5.13）),,(),(),(),(1111111kkkkkkkkkkPPPPPxPPP),(10kjjjkkPcPP).,(kkPP利用（5.11）中表达式及以上结果，得k),(),(),(11111kkkkkkkPPPxPPP.0),(),(kkkkPPPP8),(),(),(),(111kkkkkkkkkkPPPPPxPPP至此已证明了由（5.10）及（5.11）确定的多项式)}({xPk组成一个关于点集的正交系.}{ix用正交多项式的线性组合作最小二乘曲线拟合，)}({xPk只要根据公式（5.10）及（5.11）逐步求的同时，)(xPk相应计算出系数*ka.0),(),(),(),(kkkkkkkkPPPPPxPPxP最后，由和的表达式（5.11）有kk9),(),(*kkkkPPPfa),,,1,0(nk并逐步把累加到中去，最后就可得到所求的)(*xPakk)(xS).()()()(*1*10*0xPaxPaxPaxSynn用这种方法编程序不用解方程组，只用递推公式，并且当逼近次数增加一次时，只要把程序中循环数加1，其余不用改变.这里可事先给定或在计算过程中根据误差确定.n)()()()()(200ikmiimiikiixPxxPxfx拟合曲线103.6最佳平方三角逼近与快速傅里叶变换当是周期函数时，显然用三角多项式逼近比用代数多项式更合适，本节主要讨论用三角多项式做最小平方逼近及快速傅里叶变换，简称FFT算法.)(xf)(xf113.6.1最佳平方三角逼近与三角插值设是以)(xfπ2nxbnxaxbxaaxSnnnsincossincos21)(110（6.1）做最佳平方逼近函数.由于三角函数族kx,kx,,x,x,,sincossincos1在上是正交函数族，于是在上的最小平方三角逼近多项式]π2,0[]π2,0[)(xf)(xSn12称为傅里叶系数.kkba,函数按傅里叶系数展开得到的级数)(xf10)sincos(21kkkkxbkxaa（6.3）就称为傅里叶级数.20cos)(π1kxdxxfak),,,1,0(nk（6.2）),,,1,0(nk20sin)(π1kxdxxfbk13只要在上分段连续，则级数（6.3）一致收敛到.)(xf]π2,0[)(xf对于最佳平方逼近多项式（6.1）有.)()()()(222222xSxfxSxfnn由此可以得到相应于（4.11）的贝塞尔不等式.)]([1)(2120212220dxxfbaankkk因为右边不依赖于，左边单调有界，所以级数n14当只在给定的离散点集)(xf1,,1,0,π2NjjNxj上已知时，则可类似得到离散点集正交性与相应的离散傅里叶系数.下面只给出奇数个点的情形.12220)(21kkkbaa收敛，并有.0limlimkkkkba1512π2mjxj),2,,1,0(mj可以证明对任何成立mlk,0令.,0,0sincos;0,12;0212;,0coscos;0,212;0,,0sinsin202020mjkkxlxklmklmklkxlxklmklklkxlxmjjjmjjjmjjj16这表明函数族在点集}sincossincos1{mxmx,,x,x,,}12π2{mjxj上正交.若令),2,,1,0()(mjxffjj则的最小二)(xf,),sincos(21)(10mnkxbkxaaxSnkkkn其中乘三角逼近为),,,1,0(12π2cos12220mkmjkfmamjjk17当时mn,)2,,1,0()(mjfxSjjm于是（6.4）).,,1(12π2sin12220nkmjkfmbmjjkmkkkmkxbkxaaxS10)sincos(21)(就是三角插值多项式，系数仍由（6.4）表示.18由于),1i,1,,1,0()sin(i)cos(eiNjjxjxjx所以函数族在区间上是正交的.}e,,e,1{)1(iixNx]π2,0[一般情形，假定是以为周期的复函数，给定)(xfπ2在个等分点上的值)1,,1,0(π2NjjNxj,π2jNffjN函数在等距点集上的值jxie)1,,1,0(π2NkkNxk.)e,,e,1()1(π2iπ2ijTNNjNjkjxie组成的向量记作19102πi2πilee),(NkkNskNls当时，个复向量具有如下正交性：1,,1,0Nj110,,,NN102π)i(eNkkNsl（6.5）.,;,0slNsl20事实上，令,eπ2)(iNslr,0)1(,10sNNl于是,1)1(NslN即;1111NNNslNN若,0sl;1eπ2)(islNr,1,0Nsl若则有,1r则从而21于是10l),(NkksrrrN11.0若,sl10s),(Nkksr这就证明了（6.5）成立.即是正交的.110,,,N,1r则于是.N因此，在个点上的最小二乘傅里叶逼近为)(xf)}1,,1,0(π2{NjjNxjN22,,e)(10iNncxSnkkxk（6.6）其中).1,,1,0(,e110π2i-nkfNcNjNkjjk（6.7）在（6.6）中，若，Nn则为在点)(xS)(xf)1,,1,0(Njxj上的插值函数，于是由（6.6）得),()(jjxfxS即).1,,1,0(,e10π2iNjcfNkjNkkj（6.8）23（6.7）是由求的过程，}{jf}{kc称为的离散)(xf而（6.8）是由求的过程，称为反变换.}{kc}{jf傅里叶变换.简称DFT，243.6.2快速傅氏变换（FFT）不论是按（6.7）式由求，}{jf}{kc由求，}{kc}{jf),1,,1,0(,10NjwxcNkkjkj（6.9）其中(正变换))/π2iexp(Nw或(反变换)，)/π2iexp(Nw,,kkba还是由（6.4）计算傅里叶逼近系数都可归结为计算)1,,1,0}({Nkxk是已知复数序列.或是按（6.8）25当较大且处理数据很多时，就是用高速的电子计算机，很多实际问题仍然无法计算，N如直接用（6.9）计算，需要次复数乘法和次jcNN复数加法，称为个操作，计算全部共要个操作.Njc2N直到20世纪60年代中期产生了FFT算法，大大提高了运算速度，从而使傅氏变换得以广泛应用.FFT算法的基本思想就是尽量减少乘法次数.26用（6.9）计算全部，jc表面看要做个乘法，2N实际上所有中，1,,1,0,),/π2iexp(NkjNkj只有个不N,,,,110N同的值特别当时，只有个不同的值.pN22/N因此可把同一个对应的相加后再乘，这就能大量减少乘法次数.rwkxrw27设正整数除以后得商及余数，Nmqr则，rqNm称为的同余数，以表示.rmNrmN由于,1),/π2iexp(π2iewNwN因此计算时可用的同余数代替，从而推出FFT算法.mwwNrm以为例.说明FFT的计算方法.32N由于则（6.9）的和是,121,03Njk).7,,1,0(,70jwxckkjkj（6.10）.)(rrqNm故有28将用二进制表示为jk,),(222012001122kkkkkkk其中只能取0或1，)2,1,0(,rjkrr例如).110(20226022根据表示法，有jk,).(),(012012kkkxxjjjcckj公式（6.10）可表示为);(222012001122jjjjjjj29101010)222)((012012012001122012)()(kkkjjjkkkwkkkxjjjc（6.11）)00(10)0(1010)(012020011120120)(kjkkkjkkkkkj若引入记号),()(0120120kkkxkkkA.)()(10)00(01020123002kkjwjjkAjjjA（6.12）,)()(10)(0120001120120kkkkjwkkkAjkkA,)()(10)0(001101021011kkkjwjkkAjjkA30则（6.11）变成).()(0123012jjjAjjjc它说明利用同余数可把计算分为步，用公式（6.12）计算.Njcp每计算一个只用2次复数乘法，计算一个用qAjcp2次复数乘法，计算全部共用次复数乘法.jcpN2若注意公式（6.12）还可进一步简化为,)1(2/2010jNj