3.1函數(shù)逼近的基本概念3.2正交多項(xiàng)式3.3最佳平方逼近3.4曲線擬合的最小二乘法3.6最佳平方三角逼近與快速傅里葉變換第三章函數(shù)逼近與曲線擬合3.1函數(shù)逼近的基本概念第三章函數(shù)逼近與曲線擬合1§3.１函數(shù)逼近的基本概念一、函數(shù)逼近與函數(shù)空間1、函數(shù)逼近

在數(shù)值計(jì)算中經(jīng)常遇到求函數(shù)值的問題，手算時(shí)常常通過函數(shù)表求得．用計(jì)算機(jī)計(jì)算時(shí)若把函數(shù)表存入內(nèi)存進(jìn)行查表，則占用單元太多，不如直接用公式計(jì)算方便．因此，我們希望求出便于計(jì)算且計(jì)算量省的公式近似已知函數(shù)f(x)．例如，泰勒展開式的部分和§3.１函數(shù)逼近的基本概念一、函數(shù)逼近與函數(shù)空間1、函2就是的一種近似公式．用它求x0附近的函數(shù)值誤差較小，當(dāng)|x-x0|

較大時(shí)誤差就很大．例如在[-1，1]上用近似，其誤差，于是它在整個(gè)區(qū)間上誤差較大．若在計(jì)算機(jī)上用這種方法計(jì)算，如精度要求較高，則需取很多項(xiàng)，這樣既費(fèi)時(shí)又多占存儲(chǔ)單元，因此，我們要求在給定精度下求計(jì)算次數(shù)最少的近似公式，這就是函數(shù)逼近與計(jì)算要解決的問題.就是的一種近似公式．用它求x0附近的函數(shù)值誤差較小，當(dāng)|3這問題可敘述為：“對(duì)函數(shù)類A中給定的函數(shù)f(x),要求在另一類較簡(jiǎn)單的便于計(jì)算的函數(shù)類B中，求函數(shù),使P(x)與f(x)之差在某種度量意義下最小”.函數(shù)類A通常是區(qū)間[a，b]上的連續(xù)函數(shù)，記作C[a，b]；函數(shù)類B通常是代數(shù)多項(xiàng)式，分式有理函數(shù)或三角多項(xiàng)式．這問題可敘述為：“對(duì)函數(shù)類A中給定的函數(shù)f42、函數(shù)空間數(shù)學(xué)上常把在各種集合中引入某些不同的確定關(guān)系稱為賦予集合以某種空間結(jié)構(gòu)，并將這樣的集合稱為空間.2、函數(shù)空間數(shù)學(xué)上常把在各種集合中引入某些不5定義1設(shè)集合S是數(shù)域P上的線性空間，元素，如果存在不全為零的數(shù)，使得，則稱線性相關(guān).否則，則稱線性無關(guān).若線性空間S是由n個(gè)線性無關(guān)元素生成的，即對(duì)定義1設(shè)集合S是數(shù)域P上的線性空間，元素6下面考察次數(shù)不超過n次的多項(xiàng)式集合Hn,其元素p(x)Hn,表示為它由n+1個(gè)系數(shù)唯一確定,線性無關(guān),它是Hn的一組基.故Hn=span且是p(x)的坐標(biāo)向量,Hn是n+1維的.下面考察次數(shù)不超過n次的多項(xiàng)式集合Hn,其元素p(x)Hn,7更一般地,可用一組在C[a,b]上線性無關(guān)的函數(shù)集合來逼近元素表示為逼近問題就是對(duì)任何在子空間中找一個(gè)元素使在某種意義下最小.更一般地,可用一組在C[a,b]上線性無關(guān)的函數(shù)集合來逼近元8 設(shè)S為線性空間,x∈S,若存在唯一實(shí)數(shù) 滿足條件： (1)‖x‖≥0;當(dāng)且僅當(dāng)x＝0時(shí),‖x‖＝0; (正定性) (2)‖αx‖＝|α|‖x‖,α∈R; (齊次性) (3)‖x＋y‖≤‖x‖＋‖y‖,x,y∈S. (三角不等式) 則稱為線性空間S上的范數(shù),S與一起稱為賦范線性空間,記為X.3、范數(shù)的定義 設(shè)S為線性空間,x∈S,若存在唯一實(shí)數(shù) 滿足9在Rn上的向量x＝(x1,x2,…,xn)T∈Rn,三種常用范數(shù)為稱為： 幾種常用范數(shù)在Rn上的向量x＝(x1,x2,…,xn)T∈Rn10類似的對(duì)連續(xù)函數(shù)空間C[a,b],若f∈C[a,b]可定義以下三種常用函數(shù)的范數(shù)類似的對(duì)連續(xù)函數(shù)空間C[a,b],若f∈C[a,b]11設(shè)X為一個(gè)內(nèi)積空間,對(duì)u,v∈X有稱為柯西－施瓦次不等式.柯西－施瓦次不等式魏爾斯特拉斯定理

設(shè)f(x)∈C[a,b],則對(duì)任何ε＞0,總存在一個(gè)代數(shù)多項(xiàng)式p(x),使在[a,b]上一致成立。設(shè)X為一個(gè)內(nèi)積空間,對(duì)u,v∈X有稱為柯12定理：設(shè)X為一個(gè)內(nèi)積空間,u1,u2,…,un∈X,矩陣稱為格拉姆矩陣,則G非奇異的充分必要條件是u1,u2,…,un線性無關(guān)

。定理：設(shè)X為一個(gè)內(nèi)積空間,u1,u2,…,un∈X,矩陣稱為13記區(qū)間[a,b]上所有連續(xù)函數(shù)的全體為C[a,b],可以證明C[a,b]是一個(gè)線性空間,把所有次數(shù)不超過n的多項(xiàng)式全體記為Pn,則Pn是C[a,b]的子空間.若(x),g(x)C[a,b],

則稱

為(x)與g(x)的內(nèi)積,記為(,g),

4、函數(shù)的內(nèi)積滿足(1)(,g)=(g,);記區(qū)間[a,b]上所有連續(xù)函數(shù)的全體為C[a,b],14若(,g)=0,稱(x)與g(x)正交,記為g.(2)(c,g)=c(,g);(3)(1+2,g)=(1,g)+(2,g);利用內(nèi)積可以定義函數(shù)的平方模若(,g)=0,稱(x)與g(x)正交,記為g.15(1)20,而且2=0(x)=0;(2)c2=|c|2;(3)+g22+g2(4)(,g)2g2函數(shù)的平方模滿足(1)20,而且2=0(x)=016考慮到(x)在區(qū)間[a,b]上各點(diǎn)的函數(shù)值比重不同,常引進(jìn)加權(quán)形式的定義這里函數(shù)(x)是非負(fù)連續(xù)函數(shù),稱為[a,b]上的權(quán)函數(shù).它的物理意義可以解釋為密度函數(shù).

權(quán)函數(shù)返回主頁考慮到(x)在區(qū)間[a,b]上各點(diǎn)的函數(shù)值比重不同17一、正交函數(shù)族與正交多項(xiàng)式

正交多項(xiàng)式是函數(shù)逼近的重要工具，在數(shù)值積分中也有重要作用.§3.２正交多項(xiàng)式

定義5若為[a,b]上的權(quán)函數(shù)且滿足f(x),g(x)C[a,b],(x)(f(x),g(x))=baρ(x)

f(x)g(x)dx=0

則稱f(x)與g(x)在[a,b]上帶權(quán)(x)正交.若函數(shù)族0(x),1(x),…,n(x),…滿足關(guān)系則稱{k(x)}是[a,b]上帶權(quán)(x)的正交函數(shù)族;若Ak=1,則稱之為標(biāo)準(zhǔn)正交函數(shù)族.(j,

k

)=baρ(x)

j(x)k(x)dx={0,jkAk>0,j=k(2.2)(2.1)一、正交函數(shù)族與正交多項(xiàng)式正交多項(xiàng)式是函數(shù)逼近的重要工18例如,三角函數(shù)族就是區(qū)間上的正交函數(shù)族.因?yàn)閷?duì)有而對(duì)例如,三角函數(shù)族就是區(qū)間上的正交函數(shù)族.因?yàn)閷?duì)有而對(duì)192)如何構(gòu)造正交多項(xiàng)式

只要給定區(qū)間[a,b]及權(quán)函數(shù),均可由一組線性無關(guān)的冪函數(shù){1,x,…,xn,…},利用逐個(gè)正交化手續(xù)構(gòu)造出正交多項(xiàng)式序列

如此得到的正交多項(xiàng)式有如下性質(zhì)：(1) 是具有最高次項(xiàng)系數(shù)為1的n次2)如何構(gòu)造正交多項(xiàng)式只要給定區(qū)間[a,b]及權(quán)函數(shù),均20(2)任何n次多項(xiàng)式Pn(x)∈Hn均可表示為 的線性組合.(3)當(dāng)k≠j時(shí), 與任一次數(shù)小于k的多項(xiàng)式正交.(4)成立遞推關(guān)系

(2)任何n次多項(xiàng)式Pn(x)∈Hn均可表示為 21(5)設(shè) 是在[a,b]上帶權(quán)ρ(x)的正交多項(xiàng)式序列,則(n≥1)的n個(gè)根都是在區(qū)間(a,b)內(nèi)的單重實(shí)根.(5)設(shè) 是在[a,b]上帶權(quán)ρ(x)22例題：利用Gram-schmidt方法構(gòu)造[0,1]上帶權(quán)

的前3個(gè)正交多項(xiàng)式

解：利用正交化公式來求

例題：利用Gram-schmidt方法構(gòu)造[0,1]23于是于是于是于是243）幾種常用的正交多項(xiàng)式勒讓德多項(xiàng)式 當(dāng)區(qū)間[-1,1],權(quán)函數(shù)ρ(x)≡1時(shí),由{1,x,…,xn,…}正交化得到的多項(xiàng)式就稱為勒讓德多項(xiàng)式,并用P0(x),P1(x),…,Pn(x),…表示.其簡(jiǎn)單的表達(dá)式為最高項(xiàng)系數(shù)為1的勒讓德多項(xiàng)式為

3）幾種常用的正交多項(xiàng)式勒讓德多項(xiàng)式最高項(xiàng)系數(shù)為1的勒讓德多25數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件26P0(x)P1(x)P2(x)P3(x)P0(x)P1(x)P2(x)P3(x)27時(shí),由序列{1,x,…,xn,…}正交化得到的多項(xiàng)式就是切比雪夫多項(xiàng)式,它可表示為 Tn(x)=cos(narccosx), |x|≤1若令x＝cosθ，則Tn(x)=cosnθ，0≤θ≤π.切比雪夫多項(xiàng)式區(qū)間為[-1,1]當(dāng)權(quán)函數(shù)時(shí),由序列{1,x,…,xn,…}正交化得到的多項(xiàng)式就是切比28(1)遞推關(guān)系切比雪夫多項(xiàng)式的性質(zhì)T0(x)T1(x)T2(x)T3(x)(1)遞推關(guān)系切比雪夫多項(xiàng)式的性質(zhì)T0(x)T1(x)T2(29(2)切比雪夫多項(xiàng)式{Tk(x)}在區(qū)間[-1,1]上帶權(quán) 正交且(3)T2k(x)只含x的偶次冪,T2k+1(x)只含x的奇次冪.

(4)Tn(x)在區(qū)間[-1,1]上有n個(gè)零點(diǎn)(2)切比雪夫多項(xiàng)式{Tk(x)}在區(qū)間[-1,1]上帶權(quán) 30若將xn用T0(x),T1(x),…,Tn(x)的線性組合表示,則其公式為若將xn用T0(x),T1(x),…,Tn(x)的線性組合31返回主頁返回主頁32

最佳平方逼近：在意義下，使得最小。最佳一致逼近/*uniformapproximation*/在意義下，使得最小。也稱為minimaxproblem。偏差/*deviation*/§3.3最佳平方逼近最佳平方逼近：在33一、最佳平方逼近及其計(jì)算對(duì)f(x)C[a,b]及C[a,b]中的一個(gè)子集=span{0(x),1(x),…,n(x)},若存在S*(x),使則稱S*(x)是f(x)在子集

C[a,b]中的最佳平方逼近函數(shù).的最小值.||f(x)-S*(x)||

22=||f(x)-S(x)||

22=(x)[f(x)-S(x)]2dx,

baI(a0,a1,…,an)=

(x)[ajj(x)-f(x)]2dxbaj=0n?ak?I(k=0,1,…,n)=2

(x)[ajj(x)-f(x)]k(x)dx=0baj=0n求S*(x)：等價(jià)于求多元函數(shù)

I(a0,a1,…,an)是關(guān)于a0,a1,…,an的二次函數(shù),取極值必要:(3.1)(3.2)一、最佳平方逼近及其計(jì)算對(duì)f(x)C[a,34于是有這是關(guān)于a0,a1,…,an的線性方程組,稱為法方程.

0(x),1(x),…,n(x)線性無關(guān),則系數(shù)detG(0,1,…,n)0,于是上述方程組有唯一解ak=ak*(k=0,1,…,n),可得S*(x)=a0*0(x)+a1*1(x)+…+an*n(x).j=0n(j(x),k(x))aj=(f(x),k(x))(k=0,1,…,n),下面證明S*滿足（3.１）(3.3)即對(duì)任何有(3.4)即考慮:于是有這是關(guān)于a0,a1,…,an的線性方程組,稱為法方35若令(x)=f(x)-S*(x),則平方誤差為

||(x)||=(f(x)-S*(x),f(x)-S*(x))=(f(x),f(x))-(S*(x),f(x))22=||f(x)||-

ak*(k(x),f(x)).k=0n22由于的系數(shù)是方程(3.3)的解,故有從而上式第二個(gè)積分為0,于是故(3.4)成立,這就證明了是f(x)在中的最佳平方逼近函數(shù)(3.5)若令(x)=f(x)-S*(x),則平方誤差為||36若取

k(x)=xk,(x)≡1,f(x)C[0,1],在Hn中求n次最佳平方逼近多項(xiàng)式:S*(x)=a0*+a1*x+a2*x2

+…+an*

xn.(j(x),k(x))

=(f(x),k(x))=此時(shí)xk+jdx=10k+j+11f(x)xkdx≡dk10若用H表示Gn=G(1,x,x2,…xn)對(duì)應(yīng)的矩陣，即稱為希爾伯特(Hilbert)矩陣.記a=(a0,a1,…,an)T

,d=(d0,d1,…,dn)T,則Ha

=d的解ak=ak*(k=0,1,…,n)即為所求.H=11/21/(n+1)1/21/31/(n+2)1/(n+1)1/(n+2)1/(2n+1)………………(3.6)(3.7)若取k(x)=xk,(x)≡1,37數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件38二、用正交函數(shù)族作最佳平方逼近二、用正交函數(shù)族作最佳平方逼近39(3.10)(3.11)(3.12)(3.10)(3.11)(3.12)40(3.13)(3.14)(3.15)(3.13)(3.14)(3.15)41數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件42數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件43數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件44數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件45返回主頁返回主頁46仍然是已知x1…xm

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

f(x)。但是①

m很大；②

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

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

使最小太復(fù)雜使最小不可導(dǎo)，求解困難使最小§3.5曲線擬合的最小二乘法仍然是已知x1…xm;y1…y47一、最小二乘擬合多項(xiàng)式

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

<<

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

(n<m)。證明：記法方程組為Ba=c.則有其中對(duì)任意，必有。則B為正定陣，則非奇異，所以法方程組存在唯一解。

定理最小二乘擬合多項(xiàng)式存在唯一(n<m)。證明：記法方49定理

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注：最小二乘法首先要求設(shè)定P(x)的形式。若設(shè)n=m1，則可取P(x)為過m個(gè)點(diǎn)的m1階插值多項(xiàng)式，這時(shí)=0。P(x)不一定是多項(xiàng)式，通常根據(jù)經(jīng)驗(yàn)確定。==--+-=mkiikkmiiiyxPabxPxF112])()[(2)]()([=mi1ixk定理Ba=c的解確是50例：xy(xi,yi),i=1,2,…,m方案一：設(shè)baxxxPy+=)(求a和b使得最小。=-+=miiiiybaxxba12)(),(j線性化：令，則bXaY+就是個(gè)線性問題將化為后易解a和b。),(iiYX),(iiyx例：xy(xi,yi),i=1,2,…,51方案二：設(shè)xbeaxPy/)(-=(a>0,b>0)線性化：由可做變換xbay-lnlnbBaAxXyY-====,ln,1,lnBXAY+就是個(gè)線性問題將化為后易解A和B),(iiYX),(iiyx方案二：設(shè)xbeaxPy/)(-=(a>0,b52二、一般的最小二乘法=-miiiyxS*02])([===-miiiyxS02])([(4.1)其中(4.2)為了更具一般性,通常考慮為加權(quán)平方和是[a,b]上的權(quán)函數(shù),它表示不同點(diǎn)(xi,f(xi))的數(shù)據(jù)比重不同.(4.3)用最小二乘法求擬合曲線的問題,就是在形如(4.2)的S(x)中求一函數(shù)y=S*(x),使(4.3)取得最小.它轉(zhuǎn)化求多元函數(shù)(4.4)的極小值問題.二、一般的最小二乘法=-miiiyxS*02])([==53=2(xi)[ajj(xi)-f(xi)]k(xi)=0j=0ni=0m?ak?I(k=0,1,…,n)(j,k)=(xi)j(xi)k(xi),i=0m(f,k)=(xi)f(xi)k(xi)≡dki=0m(k=0,1,…,n)j=0n(j,k)aj=dk(k=0,1,…,n)Ga

=d這方程稱為法方程，可寫成矩陣形式:上式可改寫為若記(4.5)(4.6)由求多元函數(shù)的極值的必要條件，有其中a=

T,d=(d0,d1,…,dn)T,

G=(0,0)…(0,n)(0,1)(1,0)…(1,n)(1,1)(n,0)…(n,n)(n,1)………(4.7)=2(xi)[ajj(xi)-f(xi)54要使法方程(4.6)有唯一解a0,a1,…,an,就要求矩陣G非奇異.必須指出,0(x),1(x),…,n(x)在[a,b]上線性無關(guān)不能推出矩陣G非奇異.例如,令0(x)=sinx,1(x)=sin2x,x[0,2],顯然{0(x),1(x)}在[0,2]上線性無關(guān),但若取點(diǎn)xk=k,k=0,1,2(n=1,m=2),那么有0(xk)=1(xk)=0,k=0,1,2,由此得出G==0(0,0)(0,1)(1,0)(1,1)為保證(4.6)的系數(shù)矩陣G非奇異，必須加上另外的條件.定義7設(shè)0(x),1(x),…n(x)C[a,b]的任意線性組合在點(diǎn)集{xi,i=0,l,...,m}(mn)上至多只有n個(gè)不同的零點(diǎn),則稱0(x),1(x),…,n(x)在點(diǎn)集{xi,i=0,l,...,m}上滿足哈爾(Haar)條件.

可以證明,如果0(x),1(x),…n(x)C[a,b]在{xi}0m上滿足哈爾(Haar)條件,則法方程(4.6)的系數(shù)矩陣G非奇異.要使法方程(4.6)有唯一解a0,a1,55于是方程(4.6)存在唯一的解從而得到函數(shù)f(x)的最小二乘解為:可以證明這樣得到的對(duì)任何形如(4.2)的S(x),都有的確是所求最小二乘解.故于是方程(4.6)存在唯一的解從而得到函數(shù)f(x)的最小二乘56給定f(x)的離散數(shù)據(jù)要確定是困難的.一般可取但這樣做當(dāng)n大于等于3時(shí),G為病態(tài)問題.通常對(duì)n=1的簡(jiǎn)單情形可以通過求法方程(４.6)得到有時(shí)根據(jù)給定數(shù)據(jù)圖形,其擬合函數(shù)表面上不是(４.2)的形式但通過變化可化為線性模型,例如,若兩邊取對(duì)數(shù)得給定f(x)的離散數(shù)據(jù)要確定是困難的.一般可取但這樣做當(dāng)n大57例９已知一組實(shí)驗(yàn)數(shù)據(jù)如下,求它的擬合曲線xi12345yi44.5688.5wi21311解:選擇線性函數(shù)做擬合曲線,令functionf=polifitw(x,y,w,n)%帶權(quán)最小二乘擬合m=length(x);A=zeros(n+1,n+1);b=zeros(n+1,1);fori=1:n+1forj=1:n+1fort=1:mA(i,j)=A(i,j)+w(t)*x(t)^(i+j-2)endendendfori=1:n+1fort=1:mb(i)=b(i)+w(t)*y(t)*x(t)^(i-1);endendf=A\b;x=[12345];y=[44.5688.5];w=[21311];P=polifitw(x,y,w,1)例９已知一組實(shí)驗(yàn)數(shù)據(jù)如下,求它的擬合曲線xi12345yi458例10設(shè)數(shù)據(jù)由表給出，表中第4行為可以看出數(shù)學(xué)模型為用最小二乘法確定a及b.i012341.005.101.255.791.506.531.757.452.008.461.6291.7561.8762.0082.135解:兩邊取對(duì)數(shù)得:若令先將例10設(shè)數(shù)據(jù)由表給出，表中第4行為可以看出數(shù)學(xué)模型為用最小59用最小二乘法得到的法方程組(4.6)，其系數(shù)矩陣G是病態(tài)的,但如果0(x),1(x),…n(x)是關(guān)于點(diǎn)集{xi}(i=0,l,...,m)帶權(quán)(xi)(i=0,l,...,m)

正交的函數(shù)族，即則方程（4.6）的解為(j,k)=(xi)j(xi)k(xi)=i=0m0,j≠k,Akj=

k.=ak*=(k,k)(f,k)(xi)f(xi)k(xi)i=0m(xi)k2(xi)i=0m

(k=0,l,...,n)3.5.2用正交多項(xiàng)式做最小二乘擬合(5.8)且平方誤差為用最小二乘法得到的法方程組(4.6)，其系60從而:離散點(diǎn)集上正交多項(xiàng)式的構(gòu)造方法:給定點(diǎn)集和權(quán)數(shù)并且點(diǎn)集中至少有n+1個(gè)互異,則由下列三項(xiàng)遞推公式給出的多項(xiàng)式序列是正交多項(xiàng)式序列,其中從而:離散點(diǎn)集上正交多項(xiàng)式的構(gòu)造方法:給定點(diǎn)集和權(quán)數(shù)并且點(diǎn)集61例:已知點(diǎn)集和權(quán)數(shù)試用三項(xiàng)遞推公式求關(guān)于該點(diǎn)集的正交多項(xiàng)式解:例:已知點(diǎn)集和權(quán)數(shù)試用三項(xiàng)遞推公式求關(guān)于該點(diǎn)集的正交多項(xiàng)式解62例:已知點(diǎn)集和權(quán)數(shù)用正交多項(xiàng)式做最小二乘擬合解:做一般的二乘擬合.返回主頁例:已知點(diǎn)集和權(quán)數(shù)用正交多項(xiàng)式做最小二乘擬合解:做一般的二乘633.6.1最佳平方三角逼近與三角插值§3.6最佳平方三角逼近與快速傅里葉變換當(dāng)f(x)是周期函數(shù)時(shí),顯然用三角多項(xiàng)式逼近f(x)比用代數(shù)多項(xiàng)式更合適,本節(jié)主要討論用三角多項(xiàng)式做最小平方逼近及快速傅里葉變換(FastFourierTransform)簡(jiǎn)稱FFT算法.設(shè)f(x)是以2π為周期的平方可積函數(shù),用三角多項(xiàng)式做最佳平方逼近函數(shù).由于三角函數(shù)族在[0,2π]上是正交函數(shù)族,于是f(x)在[0,2π]

上的最小平方三角逼近多項(xiàng)式Sn(x)的系數(shù)是:3.6.1最佳平方三角逼近與三角插值§3.6最佳64ak,bk

稱為傅里葉系數(shù),函數(shù)f(x)按傅里葉系數(shù)展開得到的級(jí)數(shù)就稱為傅里葉級(jí)數(shù),只要f′(x)

在[

0,2π]

上分段連續(xù),則級(jí)數(shù)(6.3)一致收斂到f(x).頻譜分析ak,bk稱為傅里葉系數(shù),函數(shù)f(x)按傅里葉652.離散型當(dāng)只是在給定的離散點(diǎn)集上已知時(shí)，則可以類似地得到離散點(diǎn)集正交性與相應(yīng)的Fourier級(jí)數(shù)，一下只給出奇數(shù)個(gè)點(diǎn)的情形。令若令則的最小二乘三角逼近為：2.離散型當(dāng)只是在給定的離散點(diǎn)集上已知時(shí)，則可以類似地得到離66數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件673.1函數(shù)逼近的基本概念3.2正交多項(xiàng)式3.3最佳平方逼近3.4曲線擬合的最小二乘法3.6最佳平方三角逼近與快速傅里葉變換第三章函數(shù)逼近與曲線擬合3.1函數(shù)逼近的基本概念第三章函數(shù)逼近與曲線擬合68§3.１函數(shù)逼近的基本概念一、函數(shù)逼近與函數(shù)空間1、函數(shù)逼近

在數(shù)值計(jì)算中經(jīng)常遇到求函數(shù)值的問題，手算時(shí)常常通過函數(shù)表求得．用計(jì)算機(jī)計(jì)算時(shí)若把函數(shù)表存入內(nèi)存進(jìn)行查表，則占用單元太多，不如直接用公式計(jì)算方便．因此，我們希望求出便于計(jì)算且計(jì)算量省的公式近似已知函數(shù)f(x)．例如，泰勒展開式的部分和§3.１函數(shù)逼近的基本概念一、函數(shù)逼近與函數(shù)空間1、函69就是的一種近似公式．用它求x0附近的函數(shù)值誤差較小，當(dāng)|x-x0|

較大時(shí)誤差就很大．例如在[-1，1]上用近似，其誤差，于是它在整個(gè)區(qū)間上誤差較大．若在計(jì)算機(jī)上用這種方法計(jì)算，如精度要求較高，則需取很多項(xiàng)，這樣既費(fèi)時(shí)又多占存儲(chǔ)單元，因此，我們要求在給定精度下求計(jì)算次數(shù)最少的近似公式，這就是函數(shù)逼近與計(jì)算要解決的問題.就是的一種近似公式．用它求x0附近的函數(shù)值誤差較小，當(dāng)|70這問題可敘述為：“對(duì)函數(shù)類A中給定的函數(shù)f(x),要求在另一類較簡(jiǎn)單的便于計(jì)算的函數(shù)類B中，求函數(shù),使P(x)與f(x)之差在某種度量意義下最小”.函數(shù)類A通常是區(qū)間[a，b]上的連續(xù)函數(shù)，記作C[a，b]；函數(shù)類B通常是代數(shù)多項(xiàng)式，分式有理函數(shù)或三角多項(xiàng)式．這問題可敘述為：“對(duì)函數(shù)類A中給定的函數(shù)f712、函數(shù)空間數(shù)學(xué)上常把在各種集合中引入某些不同的確定關(guān)系稱為賦予集合以某種空間結(jié)構(gòu)，并將這樣的集合稱為空間.2、函數(shù)空間數(shù)學(xué)上常把在各種集合中引入某些不72定義1設(shè)集合S是數(shù)域P上的線性空間，元素，如果存在不全為零的數(shù)，使得，則稱線性相關(guān).否則，則稱線性無關(guān).若線性空間S是由n個(gè)線性無關(guān)元素生成的，即對(duì)定義1設(shè)集合S是數(shù)域P上的線性空間，元素73下面考察次數(shù)不超過n次的多項(xiàng)式集合Hn,其元素p(x)Hn,表示為它由n+1個(gè)系數(shù)唯一確定,線性無關(guān),它是Hn的一組基.故Hn=span且是p(x)的坐標(biāo)向量,Hn是n+1維的.下面考察次數(shù)不超過n次的多項(xiàng)式集合Hn,其元素p(x)Hn,74更一般地,可用一組在C[a,b]上線性無關(guān)的函數(shù)集合來逼近元素表示為逼近問題就是對(duì)任何在子空間中找一個(gè)元素使在某種意義下最小.更一般地,可用一組在C[a,b]上線性無關(guān)的函數(shù)集合來逼近元75 設(shè)S為線性空間,x∈S,若存在唯一實(shí)數(shù) 滿足條件： (1)‖x‖≥0;當(dāng)且僅當(dāng)x＝0時(shí),‖x‖＝0; (正定性) (2)‖αx‖＝|α|‖x‖,α∈R; (齊次性) (3)‖x＋y‖≤‖x‖＋‖y‖,x,y∈S. (三角不等式) 則稱為線性空間S上的范數(shù),S與一起稱為賦范線性空間,記為X.3、范數(shù)的定義 設(shè)S為線性空間,x∈S,若存在唯一實(shí)數(shù) 滿足76在Rn上的向量x＝(x1,x2,…,xn)T∈Rn,三種常用范數(shù)為稱為： 幾種常用范數(shù)在Rn上的向量x＝(x1,x2,…,xn)T∈Rn77類似的對(duì)連續(xù)函數(shù)空間C[a,b],若f∈C[a,b]可定義以下三種常用函數(shù)的范數(shù)類似的對(duì)連續(xù)函數(shù)空間C[a,b],若f∈C[a,b]78設(shè)X為一個(gè)內(nèi)積空間,對(duì)u,v∈X有稱為柯西－施瓦次不等式.柯西－施瓦次不等式魏爾斯特拉斯定理

設(shè)f(x)∈C[a,b],則對(duì)任何ε＞0,總存在一個(gè)代數(shù)多項(xiàng)式p(x),使在[a,b]上一致成立。設(shè)X為一個(gè)內(nèi)積空間,對(duì)u,v∈X有稱為柯79定理：設(shè)X為一個(gè)內(nèi)積空間,u1,u2,…,un∈X,矩陣稱為格拉姆矩陣,則G非奇異的充分必要條件是u1,u2,…,un線性無關(guān)

。定理：設(shè)X為一個(gè)內(nèi)積空間,u1,u2,…,un∈X,矩陣稱為80記區(qū)間[a,b]上所有連續(xù)函數(shù)的全體為C[a,b],可以證明C[a,b]是一個(gè)線性空間,把所有次數(shù)不超過n的多項(xiàng)式全體記為Pn,則Pn是C[a,b]的子空間.若(x),g(x)C[a,b],

則稱

為(x)與g(x)的內(nèi)積,記為(,g),

4、函數(shù)的內(nèi)積滿足(1)(,g)=(g,);記區(qū)間[a,b]上所有連續(xù)函數(shù)的全體為C[a,b],81若(,g)=0,稱(x)與g(x)正交,記為g.(2)(c,g)=c(,g);(3)(1+2,g)=(1,g)+(2,g);利用內(nèi)積可以定義函數(shù)的平方模若(,g)=0,稱(x)與g(x)正交,記為g.82(1)20,而且2=0(x)=0;(2)c2=|c|2;(3)+g22+g2(4)(,g)2g2函數(shù)的平方模滿足(1)20,而且2=0(x)=083考慮到(x)在區(qū)間[a,b]上各點(diǎn)的函數(shù)值比重不同,常引進(jìn)加權(quán)形式的定義這里函數(shù)(x)是非負(fù)連續(xù)函數(shù),稱為[a,b]上的權(quán)函數(shù).它的物理意義可以解釋為密度函數(shù).

權(quán)函數(shù)返回主頁考慮到(x)在區(qū)間[a,b]上各點(diǎn)的函數(shù)值比重不同84一、正交函數(shù)族與正交多項(xiàng)式

正交多項(xiàng)式是函數(shù)逼近的重要工具，在數(shù)值積分中也有重要作用.§3.２正交多項(xiàng)式

定義5若為[a,b]上的權(quán)函數(shù)且滿足f(x),g(x)C[a,b],(x)(f(x),g(x))=baρ(x)

f(x)g(x)dx=0

則稱f(x)與g(x)在[a,b]上帶權(quán)(x)正交.若函數(shù)族0(x),1(x),…,n(x),…滿足關(guān)系則稱{k(x)}是[a,b]上帶權(quán)(x)的正交函數(shù)族;若Ak=1,則稱之為標(biāo)準(zhǔn)正交函數(shù)族.(j,

k

)=baρ(x)

j(x)k(x)dx={0,jkAk>0,j=k(2.2)(2.1)一、正交函數(shù)族與正交多項(xiàng)式正交多項(xiàng)式是函數(shù)逼近的重要工85例如,三角函數(shù)族就是區(qū)間上的正交函數(shù)族.因?yàn)閷?duì)有而對(duì)例如,三角函數(shù)族就是區(qū)間上的正交函數(shù)族.因?yàn)閷?duì)有而對(duì)862)如何構(gòu)造正交多項(xiàng)式

只要給定區(qū)間[a,b]及權(quán)函數(shù),均可由一組線性無關(guān)的冪函數(shù){1,x,…,xn,…},利用逐個(gè)正交化手續(xù)構(gòu)造出正交多項(xiàng)式序列

如此得到的正交多項(xiàng)式有如下性質(zhì)：(1) 是具有最高次項(xiàng)系數(shù)為1的n次2)如何構(gòu)造正交多項(xiàng)式只要給定區(qū)間[a,b]及權(quán)函數(shù),均87(2)任何n次多項(xiàng)式Pn(x)∈Hn均可表示為 的線性組合.(3)當(dāng)k≠j時(shí), 與任一次數(shù)小于k的多項(xiàng)式正交.(4)成立遞推關(guān)系

(2)任何n次多項(xiàng)式Pn(x)∈Hn均可表示為 88(5)設(shè) 是在[a,b]上帶權(quán)ρ(x)的正交多項(xiàng)式序列,則(n≥1)的n個(gè)根都是在區(qū)間(a,b)內(nèi)的單重實(shí)根.(5)設(shè) 是在[a,b]上帶權(quán)ρ(x)89例題：利用Gram-schmidt方法構(gòu)造[0,1]上帶權(quán)

的前3個(gè)正交多項(xiàng)式

解：利用正交化公式來求

例題：利用Gram-schmidt方法構(gòu)造[0,1]90于是于是于是于是913）幾種常用的正交多項(xiàng)式勒讓德多項(xiàng)式 當(dāng)區(qū)間[-1,1],權(quán)函數(shù)ρ(x)≡1時(shí),由{1,x,…,xn,…}正交化得到的多項(xiàng)式就稱為勒讓德多項(xiàng)式,并用P0(x),P1(x),…,Pn(x),…表示.其簡(jiǎn)單的表達(dá)式為最高項(xiàng)系數(shù)為1的勒讓德多項(xiàng)式為

3）幾種常用的正交多項(xiàng)式勒讓德多項(xiàng)式最高項(xiàng)系數(shù)為1的勒讓德多92數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件93P0(x)P1(x)P2(x)P3(x)P0(x)P1(x)P2(x)P3(x)94時(shí),由序列{1,x,…,xn,…}正交化得到的多項(xiàng)式就是切比雪夫多項(xiàng)式,它可表示為 Tn(x)=cos(narccosx), |x|≤1若令x＝cosθ，則Tn(x)=cosnθ，0≤θ≤π.切比雪夫多項(xiàng)式區(qū)間為[-1,1]當(dāng)權(quán)函數(shù)時(shí),由序列{1,x,…,xn,…}正交化得到的多項(xiàng)式就是切比95(1)遞推關(guān)系切比雪夫多項(xiàng)式的性質(zhì)T0(x)T1(x)T2(x)T3(x)(1)遞推關(guān)系切比雪夫多項(xiàng)式的性質(zhì)T0(x)T1(x)T2(96(2)切比雪夫多項(xiàng)式{Tk(x)}在區(qū)間[-1,1]上帶權(quán) 正交且(3)T2k(x)只含x的偶次冪,T2k+1(x)只含x的奇次冪.

(4)Tn(x)在區(qū)間[-1,1]上有n個(gè)零點(diǎn)(2)切比雪夫多項(xiàng)式{Tk(x)}在區(qū)間[-1,1]上帶權(quán) 97若將xn用T0(x),T1(x),…,Tn(x)的線性組合表示,則其公式為若將xn用T0(x),T1(x),…,Tn(x)的線性組合98返回主頁返回主頁99

最佳平方逼近：在意義下，使得最小。最佳一致逼近/*uniformapproximation*/在意義下，使得最小。也稱為minimaxproblem。偏差/*deviation*/§3.3最佳平方逼近最佳平方逼近：在100一、最佳平方逼近及其計(jì)算對(duì)f(x)C[a,b]及C[a,b]中的一個(gè)子集=span{0(x),1(x),…,n(x)},若存在S*(x),使則稱S*(x)是f(x)在子集

C[a,b]中的最佳平方逼近函數(shù).的最小值.||f(x)-S*(x)||

22=||f(x)-S(x)||

22=(x)[f(x)-S(x)]2dx,

baI(a0,a1,…,an)=

(x)[ajj(x)-f(x)]2dxbaj=0n?ak?I(k=0,1,…,n)=2

(x)[ajj(x)-f(x)]k(x)dx=0baj=0n求S*(x)：等價(jià)于求多元函數(shù)

I(a0,a1,…,an)是關(guān)于a0,a1,…,an的二次函數(shù),取極值必要:(3.1)(3.2)一、最佳平方逼近及其計(jì)算對(duì)f(x)C[a,101于是有這是關(guān)于a0,a1,…,an的線性方程組,稱為法方程.

0(x),1(x),…,n(x)線性無關(guān),則系數(shù)detG(0,1,…,n)0,于是上述方程組有唯一解ak=ak*(k=0,1,…,n),可得S*(x)=a0*0(x)+a1*1(x)+…+an*n(x).j=0n(j(x),k(x))aj=(f(x),k(x))(k=0,1,…,n),下面證明S*滿足（3.１）(3.3)即對(duì)任何有(3.4)即考慮:于是有這是關(guān)于a0,a1,…,an的線性方程組,稱為法方102若令(x)=f(x)-S*(x),則平方誤差為

||(x)||=(f(x)-S*(x),f(x)-S*(x))=(f(x),f(x))-(S*(x),f(x))22=||f(x)||-

ak*(k(x),f(x)).k=0n22由于的系數(shù)是方程(3.3)的解,故有從而上式第二個(gè)積分為0,于是故(3.4)成立,這就證明了是f(x)在中的最佳平方逼近函數(shù)(3.5)若令(x)=f(x)-S*(x),則平方誤差為||103若取

k(x)=xk,(x)≡1,f(x)C[0,1],在Hn中求n次最佳平方逼近多項(xiàng)式:S*(x)=a0*+a1*x+a2*x2

+…+an*

xn.(j(x),k(x))

=(f(x),k(x))=此時(shí)xk+jdx=10k+j+11f(x)xkdx≡dk10若用H表示Gn=G(1,x,x2,…xn)對(duì)應(yīng)的矩陣，即稱為希爾伯特(Hilbert)矩陣.記a=(a0,a1,…,an)T

,d=(d0,d1,…,dn)T,則Ha

=d的解ak=ak*(k=0,1,…,n)即為所求.H=11/21/(n+1)1/21/31/(n+2)1/(n+1)1/(n+2)1/(2n+1)………………(3.6)(3.7)若取k(x)=xk,(x)≡1,104數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件105二、用正交函數(shù)族作最佳平方逼近二、用正交函數(shù)族作最佳平方逼近106(3.10)(3.11)(3.12)(3.10)(3.11)(3.12)107(3.13)(3.14)(3.15)(3.13)(3.14)(3.15)108數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件109數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件110數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件111數(shù)值分析-第3章-函數(shù)逼近與曲線擬合)課件112返回主頁返回主頁113仍然是已知x1…xm

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

f(x)。但是①

m很大；②

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

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

使最小太復(fù)雜使最小不可導(dǎo)，求解困難使最小§3.5曲線擬合的最小二乘法仍然是已知x1…xm;y1…y114一、最小二乘擬合多項(xiàng)式

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

<<

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

(n<m)。證明：記法方程組為Ba=c.則有其中對(duì)任意，必有。則B為正定陣，則非奇異，所以法方程組存在唯一解。

定理最小二乘擬合多項(xiàng)式存在唯一(n<m)。證明：記法方116定理

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注：最小二乘法首先要求設(shè)定P(x)的形式。若設(shè)n=m1，則可取P(x)為過m個(gè)點(diǎn)的m1階插值多項(xiàng)式，這時(shí)=0。P(x)不一定是多項(xiàng)式，通常根據(jù)經(jīng)驗(yàn)確定。==--+-=mkiikkmiiiyxPabxPxF112])()[(2)]()([=mi1ixk定理Ba=c的解確是117例：xy(xi,yi),i=1,2,…,m方案一：設(shè)baxxxPy+=)(求a和b使得最小。=-+=miiiiybaxxba12)(),(j線性化：令，則bXaY+就是個(gè)線性問題將化為后易解a和b。),(iiYX),(iiyx例：xy(xi,yi),i=1,2,…,118方案二：設(shè)xbeaxPy/)(-=(a>0,b>0)線性化：由可做變換xbay-lnlnbBaAxXyY-====,ln,1,lnBXAY+就是個(gè)線性問題將化為后易解A和B),(iiYX),(iiyx方案二：設(shè)xbeaxPy/)(-=(a>0,b119二、一般的最小二乘法=-miiiyxS*02])([===-miiiyxS02])([(4.1)其中(4.2)為了更具一般性,通?？紤]為加權(quán)平方和是[a,b]上的權(quán)函數(shù),它表示不同點(diǎn)(xi,f(xi))的數(shù)據(jù)比重不同.(4.3)用最小二乘法求擬合曲線的問題,就是在形如(4.2)的S(x)中求一函數(shù)y=S*(x),使(4.3)取得最小.它轉(zhuǎn)化求多元函數(shù)(4.4)的極小值問題.二、一般的最小二乘法=-miiiyxS*02])([==120=2(xi)[ajj(xi)-f(xi)]k(xi)=0j=0ni=0m?ak?I(k=0,1,…,n)(j,k)=(xi)j(xi)k(xi),i=0m(f,k)=(xi)f(xi)k(xi)≡dki=0m(k=0,1,…,n)j=0n(j,k)aj=dk(k=0,1,…,n)Ga

=d這方程稱為法方程，可寫成矩陣形式:上式可改寫為若記(4.5)(4.6)由求多元函數(shù)的極值的必要條件，有其中a=

T,d=(d0,d1,…,dn)T,

G=(0,0)…(0,n)(0,1)(1,0)…(1,n)(1,1)(n,0)…(n,n)(n,1)………(4.7)=2(xi)[ajj(xi)-f(xi)121要使法方程(4.6)有唯一解a0,a1,…,an,就要求矩陣G非奇異.必須指出,0(x),1(x),…,n(x)在[a,b]上線性無關(guān)不能推出矩陣G非奇異.例如,令0(x)=sinx,1(x)=sin2x,x[0,2],顯然{0(x),1(x)}在[0,2]上線性無關(guān),但若取點(diǎn)xk=k,k=0,1,2(n=1,m=2),那么有0(xk)=1(xk)=0,k=0,1,2,由此得出G=