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

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

/*minimaxApproximation*/

太復雜

/*Least_SquaresApproximation*/

逼近誤差的度量常用標準有：設(shè)在區(qū)間(a,b)上非負函數(shù)，滿足條件：定義稱為函數(shù)與在[a,b]上的內(nèi)積。1）存在(n=0,1,…)，2）對非負的連續(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)積就形成一個內(nèi)積空間。1）2）為常數(shù)3）4），當且僅當時四條公理：，量稱為的歐氏范數(shù)。定義則其內(nèi)積定義是

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

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

Innerproductspace

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

對任意x[a,b]成立當且僅當時成立，則稱在[a,b]上是線性無關(guān)的，若函數(shù)族中的任何有限個線性無關(guān)，則稱{}為線性無關(guān)函數(shù)族。定義例如：就是[a,b]上線性無關(guān)函數(shù)族，若是中的線性無關(guān)函數(shù)，且是任意實數(shù)，則的全體是中的一個子集，記作§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ù)，用次多項式作最佳平方逼近，就是要求得以為系數(shù)的多項式使推廣到一般的情況，就是對于給定的權(quán)函數(shù)，要求得使§2函數(shù)的最佳平方逼近

/*Least_SquaresApproximation*/

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

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

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

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

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

Appoximaition*/

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

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

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

OrthogonalPolynomailsandL-SAppoximaition仍然是已知x1…xN

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

f(x)。但是①

N

很大；②

yi

本身是測量值，不準確，即yi

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

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

使最小/*minimaxproblem*/

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

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

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

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

§5

DiscreteL-Sapproximating最小二乘擬合多項式

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

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

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

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

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

DiscreteL-Sapproximating同樣可以求得三次多項式為誤差平方和為顯然三次多項式的精度要好些。誤差平方和故所求得二次多項式為§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解：通過正交多項式0(x),1(x),2(x)求解設(shè))()()(221100xaxaxayjjj++=1)(0=xj229),(),(0000==jjjya25),(),(00001==jjjjax25)()()(011-=-=xxxxjaj537),(),(1111==jj