數(shù)值計(jì)算：函數(shù)逼近

第三章函數(shù)逼近/*ApproximationTheory*/一致逼近平方逼近

/*minimaxApproximation*/

太復(fù)雜

/*Least_SquaresApproximation*/

逼近誤差的度量常用標(biāo)準(zhǔn)有：設(shè)在區(qū)間(a,b)上非負(fù)函數(shù)，滿足條件：定義稱為函數(shù)與在[a,b]上的內(nèi)積。1）存在(n=0,1,…)，2）對(duì)非負(fù)的連續(xù)函數(shù)，若。則在(a,b)上,就稱為區(qū)間(a,b)上的權(quán)函數(shù)。設(shè)是[a,b]上的權(quán)函數(shù)，積分定義滿足內(nèi)積定義的函數(shù)空間稱為內(nèi)積空間。因此，連續(xù)函數(shù)空間上定義了內(nèi)積就形成一個(gè)內(nèi)積空間。1）2）為常數(shù)3）4），當(dāng)且僅當(dāng)時(shí)四條公理：，量稱為的歐氏范數(shù)。定義則其內(nèi)積定義是

向量的模（范數(shù)）定義為將它推廣到任何內(nèi)積空間中就有下面定義?！?內(nèi)積空間/*Innerproductspace*/平行四邊形定律可直接計(jì)算得證畢。對(duì)任何，下列結(jié)論成立定理此式稱為柯西—許瓦茲（Cauchy-Schwarz）不等式（1）（2）（三角不等式） （3）（平行四邊形定律）利用（1）考慮兩邊開方則得（2）.§1

Innerproductspace現(xiàn)取，代入上式得即兩邊開平方即得(1).證明若，則柯西—許瓦茲（Cauchy-Schwarz）不等式顯然成立，現(xiàn)考慮，對(duì)任何實(shí)數(shù)，有則稱f與g在[a,b]上帶權(quán)正交，若函數(shù)族就稱是[a,b]上帶權(quán)的正交函數(shù)族；若，就稱之為標(biāo)準(zhǔn)正交函數(shù)族。若，滿足定義滿足關(guān)系而對(duì)時(shí)就是在區(qū)間上的正交函數(shù)族，因?yàn)槔缛呛瘮?shù)族在空間中任一向量都可用它的一組線性無關(guān)的基表示，對(duì)內(nèi)積空間的任一元素也同樣可用線性無關(guān)的基表示，此時(shí)相應(yīng)地有….在n維空間中兩個(gè)向量正交的定義也可推廣到內(nèi)積空間?！?

Innerproductspace

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

對(duì)任意x[a,b]成立當(dāng)且僅當(dāng)時(shí)成立，則稱在[a,b]上是線性無關(guān)的，若函數(shù)族中的任何有限個(gè)線性無關(guān)，則稱{}為線性無關(guān)函數(shù)族。定義例如：就是[a,b]上線性無關(guān)函數(shù)族，若是中的線性無關(guān)函數(shù)，且是任意實(shí)數(shù)，則的全體是中的一個(gè)子集，記作§1

Innerproductspace在[a,b]上線性無關(guān)的充要條件是它的克萊姆（Cramer）行列式，其中定理判斷函數(shù)族{}線性無關(guān)的充要條件證（反證法）則齊次線性方程組假設(shè)有非零解§1

Innerproductspace§1

Innerproductspace因而有這與在上線性無關(guān)矛盾。若函數(shù)系線性相關(guān)，則由定義可知有不全為0的數(shù)值使得于是將此式兩邊乘以之后再積分，便得到方程組既然上面的齊次方程組有非0解故其系數(shù)這與矛盾。行列式的值一定為0;亦即設(shè)函數(shù)，用次多項(xiàng)式作最佳平方逼近，就是要求得以為系數(shù)的多項(xiàng)式使推廣到一般的情況，就是對(duì)于給定的權(quán)函數(shù)，要求得使§2函數(shù)的最佳平方逼近

/*Least_SquaresApproximation*/

連續(xù)函數(shù).組合構(gòu)成的一類函數(shù)。進(jìn)一步推廣可將改為一般的線性無關(guān)的成的子空間，即。次多項(xiàng)式,以為基函數(shù)所作的線性以為線性組合的全體構(gòu)稱為在子集中的最佳平方逼近函數(shù)，為了求得，這個(gè)問題等價(jià)于關(guān)于的多元函數(shù)的最小值問題。為了確定參數(shù)，由多元函數(shù)極值存在的必要條件，有最佳平方逼近的提法可敘述為：求使§2Least_SquaresApproximation即有下證是所求解，即對(duì)任何，有這是關(guān)于未知數(shù)的線性代數(shù)方程組，稱為法方程組，由于線性無關(guān)，故系數(shù)行列式，于是方程組有唯一解，從而得到§2Least_SquaresApproximation為此只要考慮這就證明了是在中的最佳平方逼近函數(shù)。這時(shí)若取，要在中求次最佳平方逼近多項(xiàng)式等于0大于0如果令，由法方程組知?jiǎng)t平方誤差為：§2Least_SquaresApproximation這里實(shí)際上要求的是(0,1)上的一次最佳平方逼近多項(xiàng)式于是法方程組的系數(shù)矩陣為

Hilbert陣！記,則的解即為所求.例定義內(nèi)積，試在中尋求對(duì)于的最佳平方逼近元素。解§2Least_SquaresApproximation解得，所求的最佳平方逼近元素為平方誤差對(duì)于一般的基底，當(dāng)稍大時(shí)，計(jì)算法方程組中的以及求解法方程組的計(jì)算量都是很大的，若采用作基底，當(dāng)時(shí)，雖然容易計(jì)算，但由此形成的法方程組系數(shù)矩陣當(dāng)時(shí)是病態(tài)矩陣，用單字長在計(jì)算機(jī)上求解法方程組，其結(jié)果往往不太可靠，如何解決？。注意看法方程組若要法方程非對(duì)角線上元素為零，應(yīng)怎么??？為此，我們先介紹正交多項(xiàng)式可采用正交基底.得法方程組為§2Least_SquaresApproximation若首項(xiàng)系數(shù)的次多項(xiàng)式，滿足定義次數(shù)不超過的多項(xiàng)式，都有，在[a,b]上帶權(quán)的正交。即與任何次數(shù)不超過的多項(xiàng)式設(shè)是次多項(xiàng)式，則多項(xiàng)式系是[a,b]上帶權(quán)的正交多項(xiàng)式的充分必要條件是對(duì)任何定理在[a,b]上帶權(quán)正交，并稱是[a,b]上帶權(quán)的次正交多項(xiàng)式。就稱多項(xiàng)式序列§3

正交多項(xiàng)式/*OrthogonalPolynomials*/設(shè)為[a,b]上的正交多項(xiàng)式序列，其中為次正交多項(xiàng)式，則具有下列基本性質(zhì)。其中都是與無關(guān)的常數(shù)，且正交多項(xiàng)式的性質(zhì)性質(zhì)1是線性無關(guān)的。性質(zhì)2的k個(gè)零點(diǎn)都是實(shí)的、相異的（即單重的），且全部在區(qū)間（a,b）內(nèi)部。性質(zhì)3最高項(xiàng)系數(shù)為1的正交多項(xiàng)式{}中任何相鄰三個(gè)多項(xiàng)式存在如下的三項(xiàng)遞推關(guān)系：§3OrthogonalPolynomials提示：歸納法證明。注：首1的正交多項(xiàng)式唯一當(dāng)區(qū)間為,權(quán)函數(shù)時(shí)，由正交化得到的多項(xiàng)式就稱為Legendre多項(xiàng)式，并用表示， 由于是次多項(xiàng)式，求階導(dǎo)數(shù)后得最高項(xiàng)系數(shù)為1的勒讓德多項(xiàng)式勒讓德\*Legendre*\多項(xiàng)式一般說來，當(dāng)權(quán)及區(qū)間[a,b]給定后，從序列就可構(gòu)造出正交多項(xiàng)式，下面我們介紹幾類。這是勒讓德于1785年引進(jìn)的，1814年羅德利克（Rodrigul）給出了簡單的表達(dá)式§3OrthogonalPolynomials性質(zhì)1正交性性質(zhì)2奇偶性勒讓德多項(xiàng)式有下述幾個(gè)重要性質(zhì)：性質(zhì)4在區(qū)間內(nèi)有n

個(gè)不同的實(shí)零點(diǎn)。（反證法）性質(zhì)3在所有最高項(xiàng)系數(shù)為1的次多項(xiàng)式中，勒讓德多項(xiàng)式在上與零的平方誤差最小?！?OrthogonalPolynomials提示：令則P2(x)Oyx－11性質(zhì)5遞推性當(dāng)時(shí)，有由，利用遞推關(guān)系就可推出在上的圖形如下：P1(x)P0(x)P3(x)§3OrthogonalPolynomialsPn(1)=1結(jié)論：Pn(-1)=(-1)n當(dāng)區(qū)間為，權(quán)函數(shù)時(shí),由序列若令，則正交化得到的正交多項(xiàng)式就是Chebyshev多項(xiàng)式，它可表為性質(zhì)1Chebyshev多項(xiàng)式在區(qū)間上帶權(quán)正交，且切比雪夫\*Chebyshev*\多項(xiàng)式Chebyshev多項(xiàng)式有以下重要性質(zhì)：§3OrthogonalPolynomials性質(zhì)2遞推關(guān)系由遞推關(guān)系可得性質(zhì)4在區(qū)間上有個(gè)零點(diǎn)性質(zhì)3只含的偶次方，只含的奇次方，這性質(zhì)由遞推關(guān)系可直接得到?！?OrthogonalPolynomials即可以得出一個(gè)級(jí)數(shù)若是帶權(quán)正交的函數(shù)系，即

那么，由法方程組 的各個(gè)方程可以獨(dú)立地解得基函數(shù)系，只要按公式逐個(gè)計(jì)算出這個(gè)級(jí)數(shù)稱為對(duì)應(yīng)于基函數(shù)系的廣義Fourier級(jí)數(shù)，從而得出最佳平方逼近函數(shù)這里的每個(gè)與是無關(guān)的，因此對(duì)于函數(shù)與正交§4用正交函數(shù)系作最佳平方逼近/*OrthogonalPolynomailsandL-S

Appoximaition*/

系數(shù)稱為廣義Fourier系數(shù)，對(duì)任意固定的，其部分和多項(xiàng)式。稱為廣義多項(xiàng)式，就是所求的最佳平方逼近當(dāng)時(shí),可以用勒讓德多項(xiàng)式作基函數(shù)，有其中這時(shí)的平方誤差為則是使最小的最佳平方逼近多項(xiàng)式?！?

OrthogonalPolynomailsandL-SAppoximaition例求在上的三次最佳平方逼近多項(xiàng)式，要求用作基函數(shù)。解先計(jì)算平方誤差于是得§3

OrthogonalPolynomailsandL-SAppoximaition例求在區(qū)間[0,1]上的一次最佳平方逼近多項(xiàng)式解令，則將代入，就得在區(qū)間[0,1]上的一次最佳平方逼近多項(xiàng)式先求在區(qū)間上的一次最佳平方逼近多項(xiàng)式，由可知 將它轉(zhuǎn)化為區(qū)間上的情形來處理。注如果所給的區(qū)間不是，而是一般的有限區(qū)間[a,b]，那么，可以通過變量置換HW:p.85#2,#3,#4,#6§3

OrthogonalPolynomailsandL-SAppoximaition仍然是已知x1…xN

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

f(x)。但是①

N

很大；②

yi

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

f(xi)這時(shí)沒必要取P(xi)=yi,而要使P(xi)yi

總體上盡可能小。常見做法：

使最小/*minimaxproblem*/

太復(fù)雜使最小不可導(dǎo)，求解困難使最小/*Least-Squaresmethod*/§5最小二乘擬合/*DiscreteL-Sapproximating*/引入內(nèi)積

問題一般的提法是：對(duì)于給定的數(shù)據(jù)，達(dá)到極小，顯然上式是個(gè)變量的二次函數(shù)選取線性無關(guān)的函數(shù)族及權(quán)函數(shù)，要求在函數(shù)類中尋找一個(gè)函數(shù)，使由多元函數(shù)極值的必要條件，有 /*discretetype*/離散型連續(xù)型§5

DiscreteL-Sapproximating構(gòu)成的矩陣A，即這個(gè)方程組稱為法方程或正規(guī)方程組，若用方程組可以表示為即有 回歸系數(shù)/*regressioncoefficients*/法方程組(或正規(guī)方程組)/*normalequations*/§5

DiscreteL-Sapproximatingúúúú?ùêêêê?é=)()()()()()()()()(A102212011110NmNNmmxxxxxxxxxjjjjjjjjjLMLMMLM又引入向量，權(quán)w=I由于線性無關(guān)，可知法方程存在唯一解類似連續(xù)型的證明，可知使I取最小值。從而得到函數(shù)最小平方誤差為則法方程組可寫成以下矩陣形式：

§5

DiscreteL-Sapproximating最小二乘擬合多項(xiàng)式

/*L-Sapproximatingpolynomials*/求出法方程組的解，就可得到擬合多項(xiàng)式若取，即取為基函數(shù)的代數(shù)多項(xiàng)式擬合時(shí)，相應(yīng)的法方程組就是§5

DiscreteL-Sapproximatingúúúúúúúú?ùêêêêêêêê?é=úúúú?ùêêêê?éúúúúúúúú?ùêêêêêêêê?é????????????=====+==+=====NiimiiNiiiiNiiimNimiiNimiiNimiiNimiiNiiiNiiiNimiiNiiiNiiyxyxyaaaxxxxxxxx111101211111121111wwwwwwwwwwwwMMLMMMMLL253171296102538114732531000021640010040410965616252438127398409612512864162872401256494971761296643636616562581502510254256276416164438114591553211101101011xiyiyixii（8）（7）（6）（5）（4）（3）（2）（1）例:設(shè)有一組數(shù)據(jù)為表中第（2），（3）兩列所示，求一代數(shù)多項(xiàng)式擬合這組數(shù)據(jù)§5

DiscreteL-Sapproximating81210642246810O（1）繪草圖（3）建立包含未知數(shù)的正規(guī)方程組，為此列表算出以下各數(shù)值由表的最后一行的數(shù)值可得正規(guī)方程組(xi,yi),i=1,2,…,m解通?？砂聪铝胁襟E求解：（2）造型從草圖可設(shè)擬合曲線為故所求的二次擬合多項(xiàng)式為由已知數(shù)據(jù)描出粗略的圖形從圖看出近似為一條拋物線（4）求解正規(guī)方程組得§5

DiscreteL-Sapproximating解：0(x)=1，1(x)=x，2(x)=x2Itissoooosimple!Whatcanpossiblygowrong?例：用來擬合，§5

DiscreteL-Sapproximating7623)(463||||484,||||1==-=BcondBB例試分別用二次和三次多項(xiàng)式以最小二乘擬合表中的數(shù)據(jù)，并比較優(yōu)劣。利用法方程解：設(shè)二次擬合函數(shù)為0.1-0.1210-1-2其中§5

DiscreteL-Sapproximating同樣可以求得三次多項(xiàng)式為誤差平方和為顯然三次多項(xiàng)式的精度要好些。誤差平方和故所求得二次多項(xiàng)式為§5

DiscreteL-Sapproximating

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-6

Step5k++;

Step6k=

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

k(x)

=(xk)k-1(x)k1k-2(x);ak

=(k,y)/(k,k);

P(x)+=ak

k(x);err

=ak

(k,y);Step8Output();STOP.注：§5

DiscreteL-Sapproximating解：通過正交多項(xiàng)式0(x),1(x),2(x)求解設(shè))()()(221100xaxaxayjjj++=1)(0=xj229),(),(0000==jjjya25),(),(00001==jjjjax25)()()(011-=-=xxxxjaj537),(),(1111==jj