南大數(shù)值分析課件第六章-曲線擬合與函數(shù)逼近

第六章曲線擬合與函數(shù)逼近/*ApproximationTheory*/仍然是已知x1…xm

;y1…ym,求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)

f(x)。但是①

m很大；②

yi本身是測(cè)量值，不準(zhǔn)確，即yi

f(xi)這時(shí)沒(méi)必要取P(xi)=yi,而要使P(xi)yi總體上盡可能小。常見(jiàn)做法：

使最小/*minimaxproblem*/

太復(fù)雜使最小不可導(dǎo)，求解困難使最小/*Least-Squaresmethod*/第六章曲線擬合與函數(shù)逼近仍然是已知x1…xm;1§1最小二乘擬合多項(xiàng)式

/*L-Sapproximatingpolynomials*/確定多項(xiàng)式，對(duì)于一組數(shù)據(jù)(xi,yi)(i=1,2,…,n)使得達(dá)到極小，這里n

<<

m。naaa10實(shí)際上是a0,a1,…,an的多元函數(shù)，即[]=-+++=miinininyxaxaaaaa121010...),...,,(j在的極值點(diǎn)應(yīng)有kiminjijijxyxa==-=10][2-====+njmikiimikjijxyxa0112記====mikiikmikikxycxb11,法方程組(或正規(guī)方程組)/*normalequations*/回歸系數(shù)/*regressioncoefficients*/§1最小二乘擬合多項(xiàng)式/*L-Sapproxim2§1L-SApproximatingPolynomials定理L-S擬合多項(xiàng)式存在唯一

(n<m)。證明：記法方程組為Ba=c.則有其中對(duì)任意，必有。若不然，則存在一個(gè)使得…即是n

階多項(xiàng)式的根則B為正定陣，則非奇異，所以法方程組存在唯一解。Waitasecond!Youonlygavemeacriticalpoint,butit’snotnecessarilyaminimumpoint!§1L-SApproximatingPolynomi3§1L-SApproximatingPolynomials定理

Ba=c的解確是的極小點(diǎn)。即：設(shè)a

為解，則任意b=(b0

b1…bn)T

對(duì)應(yīng)的多項(xiàng)式必有==njjjxbxF0)(===--=mimiiiiibyxFyxPa1122)(])([])([)(jj證明：==---=-miiimiiiyxPyxFab1212])([])([)()(jj==---+-=miiimiiiiiyxPyxPxPxF1212])([])()()([==--+-=miiiiimiiiyxPxPxFxPxF112])()][()([2)]()([0注：L-Smethod首先要求設(shè)定P(x)的形式。若設(shè)n=m1，則可取P(x)為過(guò)m個(gè)點(diǎn)的m1階插值多項(xiàng)式，這時(shí)=0。P(x)不一定是多項(xiàng)式，通常根據(jù)經(jīng)驗(yàn)確定?！?L-SApproximatingPolynomi4例用來(lái)擬合。例用5§1L-SApproximatingPolynomials例：xy(xi,yi),i=1,2,…,m方案一：設(shè)baxxxPy+=)(求a和b使得最小。=-+=miiiiybaxxba12)(),(jButhey,thesystemofequationsforaandbisnonlinear!Takeiteasy!Wejusthavetolinearizeit…線性化

/*linearization*/：令，則bXaY+就是個(gè)線性問(wèn)題將化為后易解a和b。),(iiYX),(iiyx§1L-SApproximatingPolynomi6例用來(lái)擬合。例用7§1L-SApproximatingPolynomials方案二：設(shè)xbeaxPy/)(-=(a>0,b>0)線性化：由可做變換xbay-lnlnbBaAxXyY-====,ln,1,lnBXAY+就是個(gè)線性問(wèn)題將化為后易解A和B),(iiYX),(iiyxHW:p.233#7，#9,#10,#11§1L-SApproximatingPolynomi8例用來(lái)擬合。例用9§2正交多項(xiàng)式與最小二乘擬合

/*OrthogonalPolynomials&Least-SquaresApproximation*/已知x1…xm

;y1…ym,求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)

f(x)使得最小。已知[a,b]上定義的f(x)，求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)使得最小。定義

線性無(wú)關(guān)/*linearlyindependent*/函數(shù)族{0(x),1(x),…,n(x),…}滿足條件：其中任意函數(shù)的線性組合

a00(x)+a11(x)+…+ann(x)=0對(duì)任意x[a,b]成立當(dāng)且僅當(dāng)a0=a1=…=an=0?！?正交多項(xiàng)式與最小二乘擬合已知x1…xm;y10§2OrthogonalPolynomials&L-SApproximation定義考慮一般的線性無(wú)關(guān)函數(shù)族={0(x),1(x),…,n(x),…}，其有限項(xiàng)的線性組合稱為廣義多項(xiàng)式

/*generalizedpolynomial*/.常見(jiàn)多項(xiàng)式：

{j(x)=xj}對(duì)應(yīng)代數(shù)多項(xiàng)式/*algebraicpolynomial*/

{j(x)=cosjx}、{j(x)=sinjx}{j(x),j(x)

}對(duì)應(yīng)三角多項(xiàng)式/*trigonometricpolynomial*/

{j(x)=ekjx,ki

kj

}對(duì)應(yīng)指數(shù)多項(xiàng)式/*exponentialpolynomial*/§2OrthogonalPolynomials&L11§2OrthogonalPolynomials&L-SApproximation定義權(quán)函數(shù)：①

離散型/*discretetype*/根據(jù)一系列離散點(diǎn)擬合時(shí)，在每一誤差前乘一正數(shù)wi

，即誤差函數(shù)

，這個(gè)wi

就稱作權(quán)/*weight*/，反映該點(diǎn)的重要程度。=-=niiiiyxPw12])([②

連續(xù)型

/*continuoustype*/在[a,b]上用廣義多項(xiàng)式P(x)擬合連續(xù)函數(shù)f(x)時(shí)，定義權(quán)函數(shù)(x)C[a,b]，即誤差函數(shù)=。權(quán)函數(shù)必須(x)滿足：非負(fù)、可積，且在[a,b]的任何子區(qū)間上(x)0?！?OrthogonalPolynomials&L12§2OrthogonalPolynomials&L-SApproximation定義廣義L-S擬合：①

離散型/*discretetype*/在點(diǎn)集{x1…xm}

上測(cè)得{y1…ym}，在一組權(quán)系數(shù){w1…wm}下求廣義多項(xiàng)式P(x)使得誤差函數(shù)最小。

=-=niiiiyxPw12])([②

連續(xù)型

/*continuoustype*/已知y(x)

C[a,b]以及權(quán)函數(shù)(x)，求廣義多項(xiàng)式P(x)使得誤差函數(shù)=最小。dxxyxPxba2)]()([)(-r內(nèi)積與范數(shù)離散型連續(xù)型則易證(f,g)是內(nèi)積，而是范數(shù)。(f,g)=0表示f與g

帶權(quán)正交。廣義L-S問(wèn)題可敘述為：求廣義多項(xiàng)式P(x)使得最小?！?OrthogonalPolynomials&L13§2OrthogonalPolynomials&L-SApproximationnkyaknjjjk,...,0,),(),(0===jjj設(shè)則完全類似地有：)(...)()()(1100xaxaxaxPnnjjj+++=法方程組

/*normalequations*/定理

Ba=c存在唯一解

0(x),1(x),…,n(x)線性無(wú)關(guān)。即：),(),(),(00yyaabnnjiijjjjj===c證明：若存在一組系數(shù){i

}使得0...1100=+++nnjajaja則等式兩邊分別與0,1,…,n作內(nèi)積，得到：即：B=0……§2OrthogonalPolynomials&L14§2OrthogonalPolynomials&L-SApproximation例：用來(lái)擬合，w1解：0(x)=1，1(x)=x，2(x)=x2Itissoooosimple!Whatcanpossiblygowrong?7623)(463||||484,||||1==-=BcondBB§2OrthogonalPolynomials&L15§2OrthogonalPolynomials&L-SApproximation例：連續(xù)型擬合中，取則Hilbert陣！改進(jìn)：若能取函數(shù)族={0(x),1(x),…,n(x),…}，使得任意一對(duì)i(x)和j(x)兩兩（帶權(quán)）正交，則B就化為對(duì)角陣！這時(shí)直接可算出ak=Well,nofreelunchanyway…

正交多項(xiàng)式的構(gòu)造：將正交函數(shù)族中的k取為k階多項(xiàng)式，為簡(jiǎn)單起見(jiàn)，可取k的首項(xiàng)系數(shù)為1。有遞推關(guān)系式：其中證明略§2OrthogonalPolynomials&L16§2OrthogonalPolynomials&L-SApproximation例：用來(lái)擬合，w1解：通過(guò)正交多項(xiàng)式0(x),1(x),2(x)求解設(shè))()()(221100xaxaxayjjj++=1)(0=xj229),(),(0000==jjjya25),(),(00001==jjjjax25)()()(011-=-=xxxxjaj537),(),(1111==jjjya25),(),(11112==jjjjax45),(),(00111==jjjjb55)(45)()25()(2012+-=--=xxxxxxjjj21),(),(2222==jjjya與前例結(jié)果一致。注：手算時(shí)也可用待定系數(shù)法確定函數(shù)族。§2OrthogonalPolynomials&L17§2OrthogonalPolynomials&L-SApproximation

Algorithm:OrthogonalPolynomialsApproximation

Toapproximateagivenfunctionbyapolynomialwitherrorboundedbyagiventolerance.Input:numberofdatam;x[m];y[m];weightw[m];toleranceTOL;maximumdegreeofpolynomialMax_n.Output:coefficientsoftheapproximatingpolynomial.Step1Set0(x)

1;a0=(0,y)/(0,0);P(x)=a00(x);err=(y,y)a0(0,y);Step2Set1=

(x0,0)/(0,0);1(x)

=(x1)0(x);

a1=(1,y)/(1,1);P(x)+=a11(x);err

=a1(1,y);Step3Setk=1;Step4While((k<Max_n)&&(|err|TOL))dosteps5-7

Step5k++;

Step6k=

(x1,1)/(1,1);k1=(1,1)/(0,0);

2(x)

=(xk)1(x)k10(x);ak

=(2,y)/(2,2);

P(x)+=ak

2(x);err

=ak

(2,y);

Step7Set0(x)=1(x);1(x)=2(x);Step8Output();STOP.注：§2OrthogonalPolynomials&L18AnothervonNeumannquote:Youngman,inmathematicsyoudon'tunderstandthings,youjustgetusedtothem.HW:p.152#1§2OrthogonalPolynomials&L-SApproximationLab12.OrthogonalPolynomialsApproximationGivenafunctionfandasetof200

m>0distinctpoints.YouaresupposedtowriteafunctionvoidOPA(double(*f)(),doublex[],doublew[],intm,doubletol,FILE*outfile)toapproximatethefunctionfbyanorthogonalpolynomialusingtheexactfunctionvaluesatthegivenmpointsx[].Thearrayw[m]containsthevaluesofaweightfunctionatthegivenpointsx[].Thetotalerrormustbenolargerthantol.AnothervonNeumannqu19§2OrthogonalPolynomials&L-SApproximationInputThereisnoinputfile.Instead,youmusthandinyourfunctionina*.hfile.Theruleofnamingthe*.hfileisthesameasthatofnamingthe*.cor*.cppfiles.Output(representsaspace)Foreachtestcase,youaresupposedtooutputthefollowinginformation:

The1stlinecontainstheinteger6

n>0whichisthedegreeofthepolynomialintheformat:

fprintf(outfile,"%d\n",n);

The2ndlinecontainsthen+1coefficientsoftheapproximationpolynomialwhere.EachofthecoefficientistobeprintedasinCprintf:fprintf(outfile,"%8.4e",coefficient);

The3rdlinecontainsthetotalerrorintheformat:fprintf(outfile,"error=%12.8e\n",err);Note:Ifthetotalerrorisstillnotsmallenoughwhenn=6,simplyoutputtheresultobtainedwhenn=6.Theoutputsoftwotestcasesmustbeseperatedbyablankline.§2OrthogonalPolynomials&L20§2OrthogonalPolynomials&L-SApproximationSampleJudgeProgram#include<stdio.h>#include<math.h>#defineMAX_m200#defineMAX_n6#include"98115001_12.h"

doublef1(doublex){returnsin(x);}

doublef2(doublex){returnexp(x);}

voidmain(){FILE*outfile=fopen("out.txt","w");

intm,i;doublex[MAX_m],w[MAX_m],tol;m=90;for(i=0;i<m;i++){x[i]=3.1415926535897932;x[i]=x[i]*(double)(i+1)/180.0;w[i]=1.0;}tol=0.001;OPA(f1,x,w,m,tol,outfile);m=200;for(i=0;i<m;i++){x[i]=0.01*(double)i;w[i]=1.0;}tol=0.001;OPA(f2,x,w,m,tol,outfile);

fclose(outfile);}§2OrthogonalPolynomials&L21§2OrthogonalPolynomials&L-SApproximationSampleOutput(representsaspace)32.5301e0031.0287e+0007.2279e0021.1287e001error=6.33097847e005

41.0025e+0009.6180e0016.2900e0017.0907e0031.1792e001error=1.61711536e004

§2OrthogonalPolynomials&L22§2函數(shù)的最佳逼近/*OptimalApproximation*/

最佳平方逼近：即連續(xù)型L-S逼近，在意義下，使得最小。最佳一致逼近/*uniformapproximation*/在意義下，使得最小。也稱為minimaxproblem。偏差/*deviation*/若，則稱x0為偏差點(diǎn)。Didn’tyousayit’saverydifficultproblem?Takeiteasy.It’snotsodifficultifweconsiderpolynomialsonly.§2函數(shù)的最佳逼近/*OptimalApprox23§3OptimalApproximationv1.0最佳一致逼近多項(xiàng)式

/*optimaluniformapproximatingpolynomial*/的構(gòu)造：求n

階多項(xiàng)式Pn(x)使得||Pn

y

||最小。直接構(gòu)造OUAP

的確比較困難，不妨換個(gè)角度，先考察它應(yīng)該具備的性質(zhì)。有如下結(jié)論：

OUAP存在，且必同時(shí)有偏差點(diǎn)。證明：存在性證明略。后者用反證法，設(shè)只有正偏差點(diǎn)。設(shè)而對(duì)于所有的x[a,b]都有是n階多項(xiàng)式是誤差更小的多項(xiàng)式§3OptimalApproximationv1.024§3OptimalApproximation（Chebyshev定理）Pn是y的OUAP

Pn關(guān)于y在定義域上至少有n+2個(gè)交錯(cuò)的偏差點(diǎn)。即存在點(diǎn)集at1<…<tn+2b使得{tk}稱為切比雪夫交錯(cuò)組

/*Chebyshevalternatingsequence*/若且y不是n

次多項(xiàng)式，則n次OUAP

唯一。證明：反證，設(shè)有2個(gè)OUAP’s，分別是Pn

和Qn。則它們的平均函數(shù)也是一個(gè)OUAP。2)()()(xQxPxRnnn+=對(duì)于Rn

有Chebyshev交錯(cuò)組{t1,…,tn+2}使得nkknkknkknnEtytQtytPtytRE-+--=|)()(|21|)()(|21|)()(|nkknkknEtytQtytP=-=-|)()(||)()(|則至少在一個(gè)點(diǎn)上必須有)()()()(knkkkntQtytytP-=-0)()(=-kkntytR0=nE§3OptimalApproximation（Ch25§3OptimalApproximation由Chebyshev定理可推出：Pn(x)

y(x)在定義域上至少變號(hào)

次，故至少有個(gè)根。xy0yyx=()yyxEn=+()yyxEn=-()yPxn=()n+1n+1可見(jiàn)Pn(x)是y(x)的某一個(gè)插值多項(xiàng)式

如何確定插值節(jié)點(diǎn){x0,…,xn

}的位置，使得Pn(x)剛好是

y

的OUAP？即，使插值余項(xiàng)v2.0達(dá)到極??？§3OptimalApproximation由Ch26§3OptimalApproximationv2.1

在[1,1]上求{x1,…,xn}使得的||wn||最小。=-=niinxxxw1)()(注意到，要使||wn||最小就意味著)()(1xPxxwnnn--=v3.0

在[1,1]上求函數(shù)xn的n1階

OUAP。由Chebyshev定理可推出：Pn1(x)關(guān)于xn有n+1個(gè)偏差點(diǎn)，即wn(x)在n+1個(gè)點(diǎn)上交錯(cuò)取極大、極小值。v3.1

在[1,1]上求切比雪夫交錯(cuò)組{t1,…,tn+1

}?！?OptimalApproximationv2.127切比雪夫多項(xiàng)式/*Chebyshevpolynomials*/§3OptimalApproximation考慮三角函數(shù)cos(n)在[0,]上的個(gè)極值點(diǎn)。n+1當(dāng)時(shí)，cos(n)交錯(cuò)達(dá)到極大值1和極小值1，且存在系數(shù)a0,…,an使得

令x=cos()，則x[1,1

]。)cos

arccos()cos()(xn·nxTn==q稱為Chebyshev多項(xiàng)式Tn的重要性質(zhì)：當(dāng)時(shí)，交錯(cuò)取到極大值1和極小值1，即1當(dāng)時(shí)，即{x1,…,xn}為Tn(x)的n個(gè)零點(diǎn)。切比雪夫多項(xiàng)式/*Chebyshevpolynom28§3OptimalApproximationTn(x)滿足遞推關(guān)系：T0(x)=1，T1(x)=x，Tn(x)為n

次多項(xiàng)式，首項(xiàng)系數(shù)為。且T2n(x)只含x

的次冪，T2n+1(x)只含x

的次冪。2n1偶奇{T0(x),T1(x),…}是[1,1

]上關(guān)于權(quán)正交的函數(shù)族。即在內(nèi)積的意義下有

OKOK,Ithinkit’senoughforus…What’sourtargetagain?v3.1

在[1,1]上求切比雪夫交錯(cuò)組{t1,…,tn+1

}。v3.0

在[1,1]上求函數(shù)xn的n1階

OUAP?！?OptimalApproximationTn(29Tn(x)的n個(gè)零點(diǎn)?！?OptimalApproximation可見(jiàn)：若取，則wn在[1,1

]上有n+1

個(gè)極值點(diǎn){tk}，也即Pn1(x)=xn

wn(x)關(guān)于xn在[1,1

]上有n+1個(gè)交錯(cuò)偏差點(diǎn){tk}

。v3.0OKv2.1

在[1,1]上求{x1,…,xn}使得的||wn||最小。=-=niinxxxw1)()(取最小值n={首項(xiàng)系數(shù)為1的n

階多項(xiàng)式/*monicpolynomialsofdegreen*/}{x1,…,xn}即為

如何確定插值節(jié)點(diǎn){x0,…,xn

}的位置，使得Pn(x)剛好是

y

的OUAP？即，使插值余項(xiàng)達(dá)到極??？v2.0取{x0,…,xn}為Tn+1(x)的n+1個(gè)零點(diǎn)，做y

的插值多項(xiàng)式Pn(x)，則插值余項(xiàng)的上界可達(dá)極小。Tn(x)的n個(gè)零點(diǎn)?！?OptimalApproxi30§3OptimalApproximation注：上界最小不表示|Rn(x)|最小，故Pn(x)嚴(yán)格意義上只是y(x)的近似最佳逼近多項(xiàng)式；對(duì)于一般區(qū)間x[a,b]，可作變量替換，則t[1,1

]，這時(shí)即以為插值節(jié)點(diǎn)(k=0,…,n)，得Pn(x)，余項(xiàng)有最小上界?！?OptimalApproximation注：對(duì)31§3OptimalApproximation例：求f(x)=ex在[0,1]上的近似最佳逼近多項(xiàng)式，使其誤差不超過(guò)0.5104。解：根據(jù)誤差上界確定n:n=4計(jì)算T5(t)的根：以x0,…,x4為節(jié)點(diǎn)作L4(x)§3OptimalApproximation例：求f32§3OptimalApproximationChebyshev多項(xiàng)式的其它應(yīng)用——多項(xiàng)式降次

/*reducethedegreeofpolynomialwithaminimallossofaccuracy*/設(shè)f(x)Pn(x)。在降低Pn(x)次數(shù)的同時(shí),使因此增加的誤差盡可能小,也叫economiza-tionofpowerseries。從Pn中去掉一個(gè)含有其最高次項(xiàng)的,結(jié)果降次為,則：Pn~Pn1|)(|max|)()(|max|)()(|max]1,1[]1,1[1]1,1[xPxPxfxPxfnnn----+--~因降次而增的誤差設(shè)Pn的首項(xiàng)系數(shù)為an，則取可使精度盡可能少損失。12)()(-=nnnnxTaxP§3OptimalApproximationCh33§3OptimalApproximation例：

f(x)=ex在[1,1]上的4階Taylor展開(kāi)為，此時(shí)誤差請(qǐng)將其降為2階多項(xiàng)式。解：?。ú楸碇┤。ú楸碇┤艉?jiǎn)單取，則誤差另類解法可查p.163表7-2，將x3和x4中的T3和T4刪除。注：對(duì)一般區(qū)間[a,b]，先將x換為

t，考慮f(t)在[1,1]上的逼近Pn(t)，再將t換回x，最后得到Pn(x)。HW:p.164#3§3OptimalApproximation例：f34第六章曲線擬合與函數(shù)逼近/*ApproximationTheory*/仍然是已知x1…xm

;y1…ym,求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)

f(x)。但是①

m很大；②

yi本身是測(cè)量值，不準(zhǔn)確，即yi

f(xi)這時(shí)沒(méi)必要取P(xi)=yi,而要使P(xi)yi總體上盡可能小。常見(jiàn)做法：

使最小/*minimaxproblem*/

太復(fù)雜使最小不可導(dǎo)，求解困難使最小/*Least-Squaresmethod*/第六章曲線擬合與函數(shù)逼近仍然是已知x1…xm;35§1最小二乘擬合多項(xiàng)式

/*L-Sapproximatingpolynomials*/確定多項(xiàng)式，對(duì)于一組數(shù)據(jù)(xi,yi)(i=1,2,…,n)使得達(dá)到極小，這里n

<<

m。naaa10實(shí)際上是a0,a1,…,an的多元函數(shù)，即[]=-+++=miinininyxaxaaaaa121010...),...,,(j在的極值點(diǎn)應(yīng)有kiminjijijxyxa==-=10][2-====+njmikiimikjijxyxa0112記====mikiikmikikxycxb11,法方程組(或正規(guī)方程組)/*normalequations*/回歸系數(shù)/*regressioncoefficients*/§1最小二乘擬合多項(xiàng)式/*L-Sapproxim36§1L-SApproximatingPolynomials定理L-S擬合多項(xiàng)式存在唯一

(n<m)。證明：記法方程組為Ba=c.則有其中對(duì)任意，必有。若不然，則存在一個(gè)使得…即是n

階多項(xiàng)式的根則B為正定陣，則非奇異，所以法方程組存在唯一解。Waitasecond!Youonlygavemeacriticalpoint,butit’snotnecessarilyaminimumpoint!§1L-SApproximatingPolynomi37§1L-SApproximatingPolynomials定理

Ba=c的解確是的極小點(diǎn)。即：設(shè)a

為解，則任意b=(b0

b1…bn)T

對(duì)應(yīng)的多項(xiàng)式必有==njjjxbxF0)(===--=mimiiiiibyxFyxPa1122)(])([])([)(jj證明：==---=-miiimiiiyxPyxFab1212])([])([)()(jj==---+-=miiimiiiiiyxPyxPxPxF1212])([])()()([==--+-=miiiiimiiiyxPxPxFxPxF112])()][()([2)]()([0注：L-Smethod首先要求設(shè)定P(x)的形式。若設(shè)n=m1，則可取P(x)為過(guò)m個(gè)點(diǎn)的m1階插值多項(xiàng)式，這時(shí)=0。P(x)不一定是多項(xiàng)式，通常根據(jù)經(jīng)驗(yàn)確定?！?L-SApproximatingPolynomi38例用來(lái)擬合。例用39§1L-SApproximatingPolynomials例：xy(xi,yi),i=1,2,…,m方案一：設(shè)baxxxPy+=)(求a和b使得最小。=-+=miiiiybaxxba12)(),(jButhey,thesystemofequationsforaandbisnonlinear!Takeiteasy!Wejusthavetolinearizeit…線性化

/*linearization*/：令，則bXaY+就是個(gè)線性問(wèn)題將化為后易解a和b。),(iiYX),(iiyx§1L-SApproximatingPolynomi40例用來(lái)擬合。例用41§1L-SApproximatingPolynomials方案二：設(shè)xbeaxPy/)(-=(a>0,b>0)線性化：由可做變換xbay-lnlnbBaAxXyY-====,ln,1,lnBXAY+就是個(gè)線性問(wèn)題將化為后易解A和B),(iiYX),(iiyxHW:p.233#7，#9,#10,#11§1L-SApproximatingPolynomi42例用來(lái)擬合。例用43§2正交多項(xiàng)式與最小二乘擬合

/*OrthogonalPolynomials&Least-SquaresApproximation*/已知x1…xm

;y1…ym,求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)

f(x)使得最小。已知[a,b]上定義的f(x)，求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)使得最小。定義

線性無(wú)關(guān)/*linearlyindependent*/函數(shù)族{0(x),1(x),…,n(x),…}滿足條件：其中任意函數(shù)的線性組合

a00(x)+a11(x)+…+ann(x)=0對(duì)任意x[a,b]成立當(dāng)且僅當(dāng)a0=a1=…=an=0?！?正交多項(xiàng)式與最小二乘擬合已知x1…xm;y44§2OrthogonalPolynomials&L-SApproximation定義考慮一般的線性無(wú)關(guān)函數(shù)族={0(x),1(x),…,n(x),…}，其有限項(xiàng)的線性組合稱為廣義多項(xiàng)式

/*generalizedpolynomial*/.常見(jiàn)多項(xiàng)式：

{j(x)=xj}對(duì)應(yīng)代數(shù)多項(xiàng)式/*algebraicpolynomial*/

{j(x)=cosjx}、{j(x)=sinjx}{j(x),j(x)

}對(duì)應(yīng)三角多項(xiàng)式/*trigonometricpolynomial*/

{j(x)=ekjx,ki

kj

}對(duì)應(yīng)指數(shù)多項(xiàng)式/*exponentialpolynomial*/§2OrthogonalPolynomials&L45§2OrthogonalPolynomials&L-SApproximation定義權(quán)函數(shù)：①

離散型/*discretetype*/根據(jù)一系列離散點(diǎn)擬合時(shí)，在每一誤差前乘一正數(shù)wi

，即誤差函數(shù)

，這個(gè)wi

就稱作權(quán)/*weight*/，反映該點(diǎn)的重要程度。=-=niiiiyxPw12])([②

連續(xù)型

/*continuoustype*/在[a,b]上用廣義多項(xiàng)式P(x)擬合連續(xù)函數(shù)f(x)時(shí)，定義權(quán)函數(shù)(x)C[a,b]，即誤差函數(shù)=。權(quán)函數(shù)必須(x)滿足：非負(fù)、可積，且在[a,b]的任何子區(qū)間上(x)0。§2OrthogonalPolynomials&L46§2OrthogonalPolynomials&L-SApproximation定義廣義L-S擬合：①

離散型/*discretetype*/在點(diǎn)集{x1…xm}

上測(cè)得{y1…ym}，在一組權(quán)系數(shù){w1…wm}下求廣義多項(xiàng)式P(x)使得誤差函數(shù)最小。

=-=niiiiyxPw12])([②

連續(xù)型

/*continuoustype*/已知y(x)

C[a,b]以及權(quán)函數(shù)(x)，求廣義多項(xiàng)式P(x)使得誤差函數(shù)=最小。dxxyxPxba2)]()([)(-r內(nèi)積與范數(shù)離散型連續(xù)型則易證(f,g)是內(nèi)積，而是范數(shù)。(f,g)=0表示f與g

帶權(quán)正交。廣義L-S問(wèn)題可敘述為：求廣義多項(xiàng)式P(x)使得最小?！?OrthogonalPolynomials&L47§2OrthogonalPolynomials&L-SApproximationnkyaknjjjk,...,0,),(),(0===jjj設(shè)則完全類似地有：)(...)()()(1100xaxaxaxPnnjjj+++=法方程組

/*normalequations*/定理

Ba=c存在唯一解

0(x),1(x),…,n(x)線性無(wú)關(guān)。即：),(),(),(00yyaabnnjiijjjjj===c證明：若存在一組系數(shù){i

}使得0...1100=+++nnjajaja則等式兩邊分別與0,1,…,n作內(nèi)積，得到：即：B=0……§2OrthogonalPolynomials&L48§2OrthogonalPolynomials&L-SApproximation例：用來(lái)擬合，w1解：0(x)=1，1(x)=x，2(x)=x2Itissoooosimple!Whatcanpossiblygowrong?7623)(463||||484,||||1==-=BcondBB§2OrthogonalPolynomials&L49§2OrthogonalPolynomials&L-SApproximation例：連續(xù)型擬合中，取則Hilbert陣！改進(jìn)：若能取函數(shù)族={0(x),1(x),…,n(x),…}，使得任意一對(duì)i(x)和j(x)兩兩（帶權(quán)）正交，則B就化為對(duì)角陣！這時(shí)直接可算出ak=Well,nofreelunchanyway…

正交多項(xiàng)式的構(gòu)造：將正交函數(shù)族中的k取為k階多項(xiàng)式，為簡(jiǎn)單起見(jiàn)，可取k的首項(xiàng)系數(shù)為1。有遞推關(guān)系式：其中證明略§2OrthogonalPolynomials&L50§2OrthogonalPolynomials&L-SApproximation例：用來(lái)擬合，w1解：通過(guò)正交多項(xiàng)式0(x),1(x),2(x)求解設(shè))()()(221100xaxaxayjjj++=1)(0=xj229),(),(0000==jjjya25),(),(00001==jjjjax25)()()(011-=-=xxxxjaj537),(),(1111==jjjya25),(),(11112==jjjjax45),(),(00111==jjjjb55)(45)()25()(2012+-=--=xxxxxxjjj21),(),(2222==jjjya與前例結(jié)果一致。注：手算時(shí)也可用待定系數(shù)法確定函數(shù)族。§2OrthogonalPolynomials&L51§2OrthogonalPolynomials&L-SApproximation

Algorithm:OrthogonalPolynomialsApproximation

Toapproximateagivenfunctionbyapolynomialwitherrorboundedbyagiventolerance.Input:numberofdatam;x[m];y[m];weightw[m];toleranceTOL;maximumdegreeofpolynomialMax_n.Output:coefficientsoftheapproximatingpolynomial.Step1Set0(x)

1;a0=(0,y)/(0,0);P(x)=a00(x);err=(y,y)a0(0,y);Step2Set1=

(x0,0)/(0,0);1(x)

=(x1)0(x);

a1=(1,y)/(1,1);P(x)+=a11(x);err

=a1(1,y);Step3Setk=1;Step4While((k<Max_n)&&(|err|TOL))dosteps5-7

Step5k++;

Step6k=

(x1,1)/(1,1);k1=(1,1)/(0,0);

2(x)

=(xk)1(x)k10(x);ak

=(2,y)/(2,2);

P(x)+=ak

2(x);err

=ak

(2,y);

Step7Set0(x)=1(x);1(x)=2(x);Step8Output();STOP.注：§2OrthogonalPolynomials&L52AnothervonNeumannquote:Youngman,inmathematicsyoudon'tunderstandthings,youjustgetusedtothem.HW:p.152#1§2OrthogonalPolynomials&L-SApproximationLab12.OrthogonalPolynomialsApproximationGivenafunctionfandasetof200

m>0distinctpoints.YouaresupposedtowriteafunctionvoidOPA(double(*f)(),doublex[],doublew[],intm,doubletol,FILE*outfile)toapproximatethefunctionfbyanorthogonalpolynomialusingtheexactfunctionvaluesatthegivenmpointsx[].Thearrayw[m]containstheva