機器學(xué)習(xí)計算方法函數(shù)插值與曲線擬合

計算方法1第5章函數(shù)插值與曲線擬合5.1引入——圖像縮放5.2拉格朗日插值法5.3牛頓插值法5.4三次埃爾米特插值5.5差分與等距節(jié)點地插值公式5.6曲線擬合與最小二乘法2第5章函數(shù)插值與曲線擬合5.1引入——圖像縮放5.2拉格朗日插值法5.3牛頓插值法5.4三次埃爾米特插值5.5差分與等距節(jié)點地插值公式5.6曲線擬合與最小二乘法35.1引入——圖像縮放我們所說地圖像都是指點陣圖,也就是用一個像素矩陣來描述圖像對于另一種圖像:用函數(shù)來描述圖像地矢量圖,不在本文討論之列。4當(dāng)點陣圖類型地圖像放大時,像素也會相應(yīng)地增加,那么這些增加地像素從何而來呢？這時插值方法就派上用場了。插值可以在不生成光學(xué)像素地情況下增加圖像像素大小其方法是在缺失像素周圍像素值地基礎(chǔ)上使用數(shù)學(xué)公式計算該缺失像素值。所以在放大圖像時,圖像看上去會比較平滑,干凈。但需要注意地是插值并不能增加圖像地光學(xué)信息。5常見地圖像處理方法最近鄰插值算法雙線性插值算法雙三次插值算法6最近鄰插值算法7當(dāng)圖片放大時,"照搬"旁邊地像素也就是缺失地像素值通過直接使用與之最接近地原有像素值生成假設(shè)有一個3×3地256級灰度圖地像素矩陣A:放大成一個4×4大小地256級灰度圖地像素矩陣為B最近鄰插值算法8用A矩陣地元素值填充B矩陣地元素值。設(shè)矩陣地行坐標(biāo)與列坐標(biāo)為從0開始地整數(shù)Bx為欲填充地矩陣B某個位置地橫坐標(biāo)By為欲填充地矩陣B某個位置地縱坐標(biāo)Ax為B映射回矩陣A之后該位置地橫坐標(biāo)Ay為B映射回矩陣A之后該位置地縱坐標(biāo)則有對應(yīng)關(guān)系如下:Ax=Bx×(A地列數(shù)/B地列數(shù))(5.1.1)Ay=By×(A地行數(shù)/B地行數(shù))(5.1.2)最近鄰插值算法9Ax或Ay出現(xiàn)小數(shù)時,采用四舍五入地方法把非整數(shù)坐標(biāo)轉(zhuǎn)換成整數(shù)。也可以采用直接舍掉小數(shù)位地方法B(1,0)對應(yīng)地A地坐標(biāo)(1,0),計算方法為:(1×(3/4),0×(3/4))=>(0.75,0)=>(1,0)由此可得B(1,0)=A(1,0)=88放大后地像素矩陣B為:10插值像素數(shù)碼變焦公元六世紀(jì),我國劉焯將等距二次插值應(yīng)用于天文計算;十七世紀(jì),牛頓,格雷哥里建立了等距節(jié)點上地一般插值公式;十八世紀(jì),拉格朗日給出了非等距節(jié)點上地插值公式。插值方法在數(shù)值分析地許多分支(例如,數(shù)值積分,數(shù)值微分,微分方程數(shù)值解,曲線曲面擬合,函數(shù)值近似計算,等等)均有應(yīng)用。11第5章函數(shù)插值與曲線擬合5.1引入——圖像縮放5.2拉格朗日插值法5.3牛頓插值法5.4三次埃爾米特插值5.5差分與等距節(jié)點地插值公式5.6曲線擬合與最小二乘法125.2拉格朗日插值法基本原理函數(shù)是通過實驗與觀測得到地,不知道具體地解析表達式有明確地解析表達式,但由于形式復(fù)雜,不便于進行分析與計算13數(shù)學(xué)描述設(shè)函數(shù)y=f(x)在[a,b]上是有定義地,已知x0,x1,···,xn∈[a,b]與f(x)在xi(i=0,1,...,n)點地值yi=f(xi)或直至r階導(dǎo)數(shù)值f(k)(xi)k=1,...,r.若存在一個簡單函數(shù),使14(5.2.1)(5.2.2)或還有成立則稱(x)插值函數(shù)f(x)被插值函數(shù)xi(i=0,1,...,n)插值節(jié)點[a,b]插值區(qū)間(5.2.1)（5.2.2）式插值條件求插值函數(shù)(x)地方法稱為插值法15數(shù)學(xué)描述設(shè)為次數(shù)不超過n地代數(shù)多項式,其中a0,a1,···,an為系數(shù)。當(dāng)取插值函數(shù)(x)=Pn(x)時,稱此插值法為代數(shù)多項式插值Pn(x)稱為代數(shù)插值多項式。16數(shù)學(xué)描述175.2.1Lagrange插值設(shè)函數(shù)y=f(x)在[a,b]上有定義,x0,x1,···,xn為[a,b]上n+1個互異地點。已知f(x)于點xi地值yi,求一個不高于n次地代數(shù)多項式

使之滿足(5.2.3)1818Ln(x)地存在性與唯一性由插值條件(5.2.3)式可知,Ln(x)地系數(shù)a0,a1,···,an滿足(5.2.4)1919要證明Ln(x)是存在地且唯一地,只需求證明a0,a1,…,an地存在且唯一即可。而(5.2.4)是一個以a0,a1,…,an作為未知數(shù)地n+1階線性方程組,此方程組解存在且唯一地充分必要條件是此方程組系數(shù)行列式不為零。由于此系數(shù)行列式2020是Vandermonde行列式,利用節(jié)點互異,知Vn(x0,x1,…,xn)≠0此方程組有唯一解,從而插值多項式Pn(x)是存在地且唯一地.通常我們并不使用解線性方程組地方法去求插值多項式,而是采用不同地方法去構(gòu)造插值多項式。21215.2.2插值余項函數(shù)f(x)地插值多項式Ln(x)只是在x0,x1,…xn處有若x≠xi(i=0,1,…,n),則一般地令Rn(x)=f(x)-Ln(x),則Rn(x)表示用Ln(x)代替f(x)時,在點x處產(chǎn)生地誤差,稱為插值余項或截斷誤差項。222223定理5.1設(shè),在內(nèi)存在,節(jié)點,,則對任何有(5.2.7)23若f(x)在[a,b]區(qū)間上有直到n+1階導(dǎo)數(shù),xi(i=0,1,…,n)為[a,b]上地插值節(jié)點,xi互異,Ln(x)為f(x)滿足(5.2.3)式地n次插值多項式,對[a,b]上任何取定地x≠xi,記從而有函數(shù)24在t=x,x0,x1,…xn這n+2個點處取零值,反復(fù)應(yīng)用Rolle定理n+1次,則至少存在一個點ξ∈(a,b),使得從而有25(5.2.5)(5.2.6)25將F地表達式代入(5.2.6)式,得插值余項公式26其中ξ∈(a,b).

265.2.3插值公式27已知函數(shù)表要構(gòu)造一個次數(shù)不超過1次地多項式L1(x),使得它滿足插值條件xx0x1yy0y11線性插值28線性插值290xyx1x0y0y1y=f(x)y=L1(x)點斜式對稱式301線性插值31l1(x)l0(x)(5.2.11)322拋物線插值已知函數(shù)表要構(gòu)造一個次數(shù)不超過2次地多項式L2(x),使得它滿足插值條件:xx0x1x2yy0y1y22拋物線插值330xyy=f(x)x0x1y0y1y2x2y=L2(x)342拋物線插值(5.2.12)其中3一般插值公式35已知要構(gòu)造一個次數(shù)不超過n地多項式Ln(x),使得它滿足(n+1)個插值條件:xx0x1x2··········xnyy0y1y2··········yn3一般插值公式構(gòu)造n次多項式li(x)使其滿足如下條件36(5.2.8)由于li(x)=0有n個根x0,x1,···,xi-1,xi+1,···,xn,故設(shè)由li(xi)=1,可求出稱li(x)為以x0,x1,…xn為節(jié)點地插值基函數(shù)n次拉格朗日插值多項式為(5.2.9)(5.2.10)3738帶余項地Lagrange插值公式余項為例5.1已知,求解1:選擇x0=121,x1=144為插值節(jié)點,則

3939例5.1已知,求解2:選取x0=100,x1=121,x2=144,則40

故有40結(jié)果比較線性插值(n=1)11.17391拋物線插值(n=2)11.18107拉格朗日插值(n=3)11.18047準(zhǔn)確值11.1803441是否插值多項式地次數(shù)越高,結(jié)果越準(zhǔn)確呢？一般情況下,如何估計拉格朗日插值結(jié)果地精度呢？42?Runge現(xiàn)象藍:f(x)綠:L5(x)黑:L6(x)紅:L10(x)43例5.2已知函數(shù)分別用線性插值與拋物線插值計算sin0.3367地值,并估計誤差。44x0.320.340.36sinx0.3145670.3334870.352274解:1用線性插值計算由定理5.1知誤差為45解:1用線性插值計算

46

2用拋物線插值計算472用拋物線插值計算

48第5章函數(shù)插值與曲線擬合5.1引入——圖像縮放5.2拉格朗日插值法5.3牛頓插值法5.4三次埃爾米特插值5.5差分與等距節(jié)點地插值公式5.6曲線擬合與最小二乘法4949拉格朗日插值已知要構(gòu)造一個次數(shù)不超過n地多項式Ln(x),使得它滿足插值條件xx0x1x2··········xnyy0y1y2··········yn5050定義5.1稱函數(shù)f(x)于點xi,xj(xi≠xj)上地平均變化率為f(x)在xi,xj處地一階差商,記作f[xi,xj],即一階差商地差商為f(x)在點xi,xj,xk處地二階差商,記作f[xi,xj,xk],即51(5.3.1)(5.3.2)51一般地,在求出f(x)地m-1階差商之后,就可以構(gòu)造f(x)地m階差商,稱

為f(x)在點xi0,xi1,…,xim處地m階差商特別地,規(guī)定零階差商f[xi]=f(xi)52(5.3.3)52差商地性質(zhì)零階差商f[xi]=f(xi)k階差商5353差商地性質(zhì)54k階差商可表示為函數(shù)值f(x0),…,f(xk)地線性組合,即各階差商均具有對稱性,即改變節(jié)點地位置,差商值不變.f[x0,…,xk]=f[x1,x0,x2,…,xk]=f[x1,x2,…,xk,x0](5.3.4)(5.3.5)54差商地性質(zhì)差商與導(dǎo)數(shù)地關(guān)系若f(x)是n次多項式,則一階差商是n-1次多項式計算各階差商,可按差商表進行55(5.3.6)55差商表構(gòu)造按照給定順序x0,x1,…,xn,計算差商表56節(jié)點零階差商一階差商二階差商三階差商四階差商x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]x4f(x4)f[x3,x4]f[x2,x3,x4]f[x1,x2,x3,x4]f[x0,x1,x2,x3,x4]5657Newton插值多項式575858595960606161n次Newton插值多項式62(5.3.8)62由插值多項式地唯一性可知,當(dāng)f(n+1)(x)存在時,n次Newton插值多項式地余項與n次Lagrange插值多項式地余項相同,即介于x,x0,x1,…,xn之間6363在實際計算中,特別當(dāng)函數(shù)f(x)地高階導(dǎo)數(shù)比較復(fù)雜或f(x)地表達式?jīng)]有給出時,常用差商來表示插值余項公式。由差商與導(dǎo)數(shù)地關(guān)系(5.3.6)式,有64(5.3.10)64Newton插值法1）各階差商可以由差商表給出,Newton插值法使用地是差商表中斜線部分（帶橫線差商）2）每當(dāng)增加一個插值節(jié)點,只需求增加一項就行了,即有3）Newton余項與Lagrange方法相同65654）牛頓插值法求解過程根據(jù)給定節(jié)點構(gòu)造差商表;根據(jù)差商表寫出Nn(x);將x代入66665）插值節(jié)點地選擇極小值原則避免出現(xiàn)高次插值,不穩(wěn)定6767紅色曲線是龍格函數(shù)

藍色曲線是5階多項式

綠色曲線是9階多項式

隨著階次地增加,誤差逐漸變大68龍格現(xiàn)象68例5.3已知函數(shù)地函數(shù)表,69xkf(xk)0.400.410750.550.578150.650.696750.800.888110.901.026521.051.25386作插值多項式計算f(0.596)=sh0.596地值69解:差商表地計算結(jié)果見表。由表中可以看出其四階差商相同,則五階差商為0,因此可取四次插值多項式。根據(jù)極小化原理選擇0.40~0.90地5個節(jié)點作為插值節(jié)點,由(5.3.8)式,有于是,f(0.596)=sh(0.596)≈N4(0.596)=0.63192.70f(0.596)地差商表計算結(jié)果節(jié)點零階差商一階差商二階差商三階差商四階差商0.400.410751.11600.550.578150.28001.18600.1970.650.696750.35880.0341.27570.2140.800.888110.43360.0341.38410.2370.901.026520.52601.51561.051.2538671第5章函數(shù)插值與曲線擬合5.1引入——圖像縮放5.2拉格朗日插值法5.3牛頓插值法5.4三次埃爾米特插值5.5差分與等距節(jié)點地插值公式5.6曲線擬合與最小二乘法7272許多應(yīng)用問題不但要求構(gòu)造插值函數(shù)在節(jié)點上地值與被插函數(shù)值相等地條件外,還要求它地導(dǎo)數(shù)值也要與被插函數(shù)地導(dǎo)數(shù)值相等,如一階導(dǎo)數(shù)值,高階導(dǎo)數(shù)等這種插值稱為Hermite(埃爾米特)插值。7373整齊地Hermite插值,節(jié)點處地函數(shù)值與導(dǎo)數(shù)值成對出現(xiàn)。非整齊地Hermite插值,節(jié)點處地函數(shù)值與導(dǎo)數(shù)值不成對出現(xiàn)。7474問題一整齊地已知下面地函數(shù)表,構(gòu)造Hermite插值多項式H3(x),使得xx0x1yy0y1y’m0m17575解1基于插值基函數(shù)構(gòu)造插值多項式(5.4.2)令

容易驗證H3(x)滿足Hermite插值條件7677插值基函數(shù)應(yīng)有下面形式其中:a,b,c,d,e,f為待定系數(shù)。7778由基函數(shù)固有性質(zhì)帶回到式(5.4.2)中,即可得到滿足插值條件地多項式H3(x)78插值余項(5.4.7)79已知x0,x1處函數(shù)值與導(dǎo)數(shù)值,在構(gòu)造差商表時,引入重點x0,x1,（已知導(dǎo)數(shù)值地點為重合節(jié)點）。對于差商表中地一階差商f[z0,z1],根據(jù)導(dǎo)數(shù)定義8080解2（利用差商地方法）寫出差商表z0=x0f(z0)z1=x0f(z1)f’(x0)z2=x1f(z2)f[z1,z2]f[z0,z1,z2]z3=x1f(z3)f’(x1)f[z1,z2,z3]f[z0,z1,z2,z3]8181問題二非整齊地已知下面地函數(shù)表,構(gòu)造Hermite插值多項式H2(x),使得82xx0x1x1yy0y1m1y’m182解1基于插值基函數(shù)構(gòu)造插值多項式(5.4.11)

容易驗證H3(x)滿足Hermite插值條件(5.4.10)83解1基于插值基函數(shù)構(gòu)造插值多項式根據(jù)多項式零點性質(zhì),易知四個基函數(shù)應(yīng)具有如下形式:其中A,B,C,D,E為待定系數(shù),可根據(jù)(5.4.10)中地非零點條件確定。這樣,最后可以得到四個基函數(shù)為84解1基于插值基函數(shù)構(gòu)造插值多項式其中A,B,C,D,E為待定系數(shù),可根據(jù)(5.4.10)中地非零點條件確定。這樣,最后可以得到四個基函數(shù)為

這樣,Hermite插值多項式H3(x)可由(5.4.11)-(5.4.15)式確定,插值余項為:其中85解2（利用差商地方法）寫出差商表z0=x0f(z0)z1=x1f(z1)f[z0,z1]z2=x1f(z2)f’(x1)f[z0,z1,z2]z3=x2f(z3)f[z1,z2]f[z1,z2,z3]f[z0,z1,z2,z3]8686三次Hermite插值非整齊地插值余項

i地取值取決于給定地插值條件整齊地插值余項8787第5章函數(shù)插值與曲線擬合5.1引入——圖像縮放5.2拉格朗日插值法5.3牛頓插值法5.4三次埃爾米特插值5.5差分與等距節(jié)點地插值公式5.6曲線擬合與最小二乘法88885.5差分與等距節(jié)點地插值公式在計算過程中,常常遇到插值節(jié)點均勻分布地情況,即節(jié)點等距表示為xi=x0+ih(i=0,1,…,n)其中h是正常數(shù),稱為步長.這時差商與Newton插值公式可借助于差分地概念進行簡化89設(shè)函數(shù)f(x)在等距節(jié)點xi=x0+ih上地值為yi=f(xi)(i=0,1,…,n)定義4.2稱yi＋1－yi為函數(shù)f(x)在xi節(jié)點處地以h為步長地一階向前差分,簡稱為一階差分,記為△yi,即(5.5.1)90類似地,稱節(jié)點xi與xi＋1處地一階差分地差分△yi＋1－△yi為f(x)在點xi處地二階差分,記為一般稱m-1階差分地差分

為f(x)在點xi處地m階差分(5.5.2)91定義4.3稱

為函數(shù)f(x)在xi節(jié)點處地以h為步長地一階向后差分,稱

為f(x)在xi處以h為步長地m階向后差分(5.5.3)(5.5.4)92差分地性質(zhì)各階差分均可表示為函數(shù)值地線性組合93(5.5.5)(5.5.6)差商與向前差分地關(guān)系差商與向后差分地關(guān)系(5.5.7)(5.5.8)94各種差分之間可以轉(zhuǎn)化向前差分與導(dǎo)數(shù)地關(guān)系仿照差商表地構(gòu)造,各種差分計算也可以排列成表(5.5.10)95(5.5.9)向前差分表96xiyiΔyiΔ2yiΔ3yiΔ4yix0y0

x1y1Δy0

x2y2Δy1Δ2y0

x3y3Δy2Δ2y1Δ3y0

x4y4Δy3Δ2y2Δ3y1Δ4y0向后差分表97xiyi?yi?2yi?3yi?4yix4y4

x3y3?y4

x2y2?y3?2y4

x1y1?y2?2y3?3y4

X0y0?y1?2y2?3y3?4y4Newton向前插值公式用來計算函數(shù)表靠近前面x0附近(x∈[x0,x1],此時0<t<1)地函數(shù)值98前插公式地余項為99Newton向后插值公式用來計算函數(shù)表靠近前面xn附近(x∈[xn-1,xn],此時(-1<t<0)地函數(shù)值,因此也稱為表末插值公式100后插公式地余項為101例5.6已知f(x)=sinx地函數(shù)表,分別用二次前插,后插公式計算sin0.57891地值與誤差。x0.40.50.60.7sinx0.389420.479430.594640.64422102例5.6已知f(