第二章-數(shù)值代數(shù)(與“插值”相關(guān)共43張)

插值與擬合

插值擬合第四章數(shù)據(jù)建模

§4.1多項(xiàng)式插值§4.2Newton插值法§4.3三階樣條插值§4.4最小二乘擬合§4.1多項(xiàng)式插值Lagrange插值存在唯一性計(jì)算公式余項(xiàng)公式(截?cái)嗾`差)Hermite插值存在唯一性計(jì)算公式余項(xiàng)公式(截?cái)嗾`差)基本概念函數(shù)y=f(x)未知或很復(fù)雜已知函數(shù)y=f(x)在xi的函數(shù)值yi=f(xi)，i=0,…,n.求一“簡(jiǎn)單”的函數(shù)p(x)滿足p(xi)=yi,i=0,…,n.原函數(shù)插值函數(shù)

插值節(jié)點(diǎn)

插值條件

插值區(qū)間I=[min(x0,x2,…,xn),max]當(dāng)插值點(diǎn)xI,稱內(nèi)插(Interpolation)當(dāng)插值點(diǎn)xI,稱外推(Extrapolation)Lagrange插值:p(x)不超過n次多項(xiàng)式

存在唯一性定理

設(shè)節(jié)點(diǎn)互不相同，則存在唯一次數(shù)不超過n的多項(xiàng)式使?jié)M足證明利用Vandermonde行列式線性插值(n=1)

基函數(shù)拋物插值(n=2)一般Lagrange插值公式證明：直接驗(yàn)證Lagrange插值余項(xiàng)

定理4.2設(shè)[a,b]互不相同，f(x)在[a,b]上有連續(xù)的n+1階導(dǎo)數(shù)，則對(duì)任意x[a,b],證明：由微分學(xué)Rolle中值定理

精度提高的條件插值點(diǎn)與節(jié)點(diǎn)靠近內(nèi)插精度一般比外推高插值點(diǎn)適當(dāng)多注意：n,不收斂！P76例

y=sinxHermite插值具有節(jié)點(diǎn)的導(dǎo)函數(shù)值約束的插值已知求不超過3次多項(xiàng)式H3(x)使?jié)M足存在唯一性計(jì)算公式余項(xiàng)公式(截?cái)嗾`差)存在唯一性導(dǎo)出計(jì)算公式(基函數(shù)法)變量代換設(shè)基函數(shù)計(jì)算公式余項(xiàng)公式(截?cái)嗾`差)Hermite余項(xiàng)證明比較:Lagrange余項(xiàng)(n=3)§4.2Newton插值法(略)Lagrange插值公式缺點(diǎn)：缺少遞推關(guān)系，每次新增加節(jié)點(diǎn)，都要重新計(jì)算，高次插值無(wú)法利用低次插值結(jié)果。

Newton插值法：Lagrange插值的一種變形，可在增加節(jié)點(diǎn)時(shí)進(jìn)行遞推計(jì)算，高次插值可利用低次插值結(jié)果。

差商一階差商

二階差商

k階差商P80例差商的性質(zhì)

定理：差商與結(jié)點(diǎn)的排列次序無(wú)關(guān)

證明：數(shù)學(xué)歸納法，k=1設(shè)k-1階差商成立，記y0=x0,…,yk-2=xk-2及yk-1=xk得

Newton插值法且Nn(xi)=f(xi)，N1(x)

例題xkf(xk)f[x0,xk]f[x0,x1,xk]f[x0,x1,x2,xk]x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x0,x2]f[x0,x1,x2]x3f(x3)f[x0,x3]f[x0,x1,x3]f[x0,x1,x2,x3]P82例4.3利用低次插值結(jié)果計(jì)算高次插值遞推公式§4.3三階樣條插值Runge現(xiàn)象：高階多項(xiàng)式插值的振蕩(不收斂)

[-5，5]多項(xiàng)式插值一般不宜超過7階分段線性插值

問題已知及，為[x0,xn]上的分段線性函數(shù)且滿足計(jì)算公式余項(xiàng)公式收斂性

缺點(diǎn)：不光滑！分段3次Hermite插值已知及，為[x0,xn]上的分段3次多項(xiàng)式且滿足計(jì)算公式余項(xiàng)公式收斂性

一階光滑！三階(次)樣條插值

(具有二階光滑性)問題已知及，S(x)為[xi-1,xi]上的不超過3次多項(xiàng)式，且滿足插值條件：，

連接條件:四類邊界條件(i)一階導(dǎo)數(shù)：S'(x0)=y0',S'(xn)=yn';(ii)二階導(dǎo)數(shù)：S''(x0)=y0'',S''(xn)=yn'';自然樣條：S''(x0)=S''(xn)=0;(iii)周期樣條：S'(x0)=S'(xn)，S''(x0)=S''(xn)（其前提條件S(x0)=S(xn)）,當(dāng)被插值函數(shù)為周期函數(shù)或封閉曲線，宜用周期樣條。(iv)非扭結(jié)：第一﹑二段多項(xiàng)式三次項(xiàng)系數(shù)相同,最后一段和倒數(shù)第二段三次項(xiàng)系數(shù)相同.

三階樣條插值求解公式利用分段3次Hermite插值

設(shè)，利用分段3次Hermite插值公式(含未知mi)，已使插值條件和連接條件的連續(xù)性和一階光滑性滿足；由n-1個(gè)二階光滑性約束條件和邊界條件來(lái)求個(gè)待定參數(shù)，轉(zhuǎn)化為解三對(duì)角方程組(一階導(dǎo)數(shù)邊界條件

)三階樣條插值求解步驟數(shù)值求解步驟由邊界條件和插值條件列三對(duì)角方程組用追趕法解方程組求得判斷插值點(diǎn)x在第i個(gè)小區(qū)間用第i個(gè)小區(qū)間的3階Hermite公式求插值例4.6求三階樣條插值函數(shù)解法二（待定系數(shù)法）解法三（用計(jì)算公式）解法一（分析推導(dǎo),稱為承襲法）關(guān)于承襲法的注釋關(guān)于承襲法的注釋關(guān)于承襲法的注釋關(guān)于承襲法的注釋§4.4最小二乘擬合

數(shù)據(jù)建模

插值:過點(diǎn);(適合精確數(shù)據(jù))擬合:不過點(diǎn),整體近似;(適合有經(jīng)驗(yàn)公式或有誤差的數(shù)據(jù))最小二乘法

最小二乘法:最小化誤差平方和(等價(jià)最小化向量2-范數(shù))最小二乘擬合:在一類曲線中求一曲線使與被擬合曲線f(x)在節(jié)點(diǎn)x1,…,xn的誤差平方和最小。P91例4.7(線性擬合)P92例4.8(線性化擬合)P92例4.9(超定方程組)內(nèi)積和范數(shù)關(guān)于節(jié)點(diǎn)

的內(nèi)積和2-范數(shù):當(dāng)(f,g)=0,稱f與g正交。對(duì)任意函數(shù)f,g,h和數(shù)，有(i)(f,g+h)=(f,g)+(f,h);(ii)(f,g)=(f,g);(iii)(f,g)=(g,f);(iv)||f||0且||f||=0f(xi)=0,i=1,…,n.注意:內(nèi)積和范數(shù)依賴于節(jié)點(diǎn)選取,本質(zhì)上就是函數(shù)在節(jié)點(diǎn)取值得到的向量的內(nèi)積和范數(shù).避免病態(tài):選取函數(shù)類的正交基函數(shù)0,1,,m,法方程組就成為簡(jiǎn)單的對(duì)角方程組,其解問題等價(jià)于:求a*0,a*1,,a*mR，使避免病態(tài):選取函數(shù)類的正交基函數(shù)0,1,,m,法方程組就成為簡(jiǎn)單的對(duì)角方程組,其解0(x)=1,1(x)=x,,m(x)=xm2Newton插值法證明：數(shù)學(xué)歸納法，k=1Newton插值法：Lagrange插值的一種變形，可在增加節(jié)點(diǎn)時(shí)進(jìn)行遞推計(jì)算，高次插值可利用低次插值結(jié)果。注意:擬合依賴于節(jié)點(diǎn)選取.問題已知及，為[x0,xn]上的分段線性函數(shù)且滿足當(dāng)插值點(diǎn)xI,稱內(nèi)插(Interpolation)插值:過點(diǎn);(適合精確數(shù)據(jù))3利用低次插值結(jié)果計(jì)算高次插值f[x0,x1,x2,xk]ex12,ex13,ex14當(dāng)插值點(diǎn)xI,稱外推(Extrapolation)定理設(shè)節(jié)點(diǎn)互不相同，則存在唯一次數(shù)不超過n的多項(xiàng)式使?jié)M足使與被擬合曲線f(x)在節(jié)點(diǎn)x1,…,xn的誤差平方和最小。復(fù)習(xí)：線性代數(shù)稱向量組0,1,,m線性無(wú)關(guān)，如果只有當(dāng)k0,k1,,km全為零時(shí)k00+k11++kmm=0。線性無(wú)關(guān)向量組0,1,,m的線性組合全體稱為由0,1,,m張成的向量空間，記為=span{0,1,,m}={=a00+a11++amm|a0,a1,

,amR}而0,1,,m稱為的基向量?；瘮?shù)稱函數(shù)0(x),1(x),,m(x)關(guān)于節(jié)點(diǎn)x1,…,xn線性無(wú)關(guān)，如果它們的取值向量線性無(wú)關(guān)，即只有當(dāng)k0,k1,,km全為零時(shí)k00(xi)+k11(xi)++kmm(xi)=0,i=1,2,,n

才全部成立。線性無(wú)關(guān)函數(shù)0,1,,m的線性組合全體稱為由0,1,,m張成的函數(shù)空間，記為=span{0,1,,m}={(x)=a00(x)+a11(x)++amm(x)|a0,a1,

,amR}而0,1,,m稱為的基函數(shù)。最小二乘擬合最小二乘擬合：已知數(shù)據(jù)xi,yi=f(xi)（i=1,…,n）和函數(shù)空間=span{0,1,,m},求函數(shù)*，使||f*||=min||f||

問題等價(jià)于:求a*0,a*1,

,a*mR，使S(a*0,a*1,

,a*m)=

minS(a0,a1,

,am)

其中

S(a0,a1,,am)=||f||2=

(x)=(二次函數(shù)最小化)函數(shù)極值的必要條件

對(duì)a0,a1,

,am求偏導(dǎo)，法方程組微分法求極值，法方程組(正規(guī)方程組)定理4.3如果函數(shù)0(x),1(x),,m(x)關(guān)于節(jié)點(diǎn)x1,…,xn線性無(wú)關(guān)，則法方程組的解存在唯一;法方程組的解是最小二乘擬合的唯一最優(yōu)解。證明：

(1)(2)例題P95例4.10注意:擬合依賴于節(jié)點(diǎn)選取.高階多項(xiàng)式擬合的病態(tài)

0(x)=1,1(x)=x,,m(x)=xm