插值的應(yīng)用背景拉格朗日插值公式牛頓插值公式插值誤差余項Runge反例《數(shù)值分析》12趣例1:圖像放大Non-damagedDamaged趣例2:圖像修復(fù)數(shù)據(jù)和插值函數(shù)

如果一個函數(shù)P(x)滿足P(xi)=yi

(i=0,…,n),那么函數(shù)P(x)

插值了一系列數(shù)據(jù)點(x0,y0),···(xn,yn)，其中P(x)稱為插值函數(shù),點x0,···,xn稱為插值節(jié)點。x0x1x2x3x4xP(x)函數(shù)是描述自然界客觀規(guī)律的重要工具。壓縮的概念:觀測的離散數(shù)據(jù)可以想象成現(xiàn)實中無窮多信息的代表。通過給定數(shù)據(jù)求出插值函數(shù)意味著用簡單的規(guī)則代替無窮多信息。盡管期待這種簡單規(guī)則精確地反映實際情況是不現(xiàn)實的,但是它可以充分接近實際。選擇多項式函數(shù)的理由:計算方面多項式函數(shù)是計算機(jī)最基本的函數(shù),計算多項式函數(shù)的值只需用加和乘運算,且積分和微分均非常方便。理論方面多項式函數(shù)簡單明了的數(shù)學(xué)性質(zhì)。有一個簡單的原理可以說明什么時候存在給定次數(shù)的插值多項式。

插值函數(shù)類的選擇:插值問題研究包括如下三個方面:插值函數(shù)的構(gòu)造插值函數(shù)的唯一性插值誤差估計的問題過兩點直線方程已知函數(shù)表求滿足:

P(x0)=y0和P(x1)=y1的線性函數(shù)

P(x)x

x0x1

y

y0

y1引例求的近似值真實值:10.723811線性插值函數(shù)x0x1(x0，y0)(x1，y1)P(x)可見

是過和兩點的直線。12拋物插值函數(shù)x0x1x2因過三點的二次曲線為拋物線,故稱為拋物插值。

則稱

P(x)為

插值多項式,稱

x0,x1,···,xn為

插值節(jié)點。

如果

P(x)=a0+a1x+···+anxn滿足

P(xk)=yk(k=0,1,…,n)考慮區(qū)間[a,b]上(n+1)個點a≤x0＜x1＜···＜xn≤b。插值條件

由插值條件P(x0)=y0P(x1)=y1············P(xn)=yn范德蒙(Vandermonde)矩陣

Vandermonde矩陣條件數(shù)很大,直接求解方程組是危險的。則滿足插值條件

P(xk)=yk(k=0,1,…,n)的次數(shù)小于等于n次的插值多項式

P(x)=a0+a1x+…+anxn存在而且唯一。證明:由插值條件P(x0)=y0P(x1)=y1············P(xn)=yn定理

若插值結(jié)點x0,x1,···,xn

是(n+1)個互異點,回顧1:非齊次方程組有唯一解的充分必要條件是系數(shù)矩陣行列式不等于零。系數(shù)矩陣行列式不等于零,則方程組有唯一解。因此插值多項式P(x)存在且唯一。回顧2:范德蒙(Vandermonde)矩陣過兩點直線方程已知函數(shù)表求滿足:

P(x0)=y0

和P(x1)=y1的線性函數(shù)

P(x)。x

x0x1

y

y0

y1記x

x0

x1l0(x)10l1(x)01I=imread('yao.png');J=imread('li.png');foralpha=1:-0.01:0K=alpha*I+(1-alpha)*J;pause(0.3),imshow(K,[])endHybridimages

hybridimagesaregeneratedbysuperimposingtwoimagesattwodifferentspatialscales:thelow-spatialscaleisobtainedbyfilteringoneimagewithalow-passfilter,andthehighspatialscaleisobtainedbyfilteringasecondimagewithahigh-passfilter.Thefinalhybridimageiscomposedbyaddingthesetwofilteredimages.去霧SingleImageHazeRemovalUsingDarkChannel去雨ANovelTensor-basedVideoRainStreaksRemovalApproachviaUtilizingDiscriminativelyIntrinsicPriors去水印OntheEffectivenessofVisibleWatermarks二次插值問題x

x0x1x2y

y0

y1

y2已知函數(shù)表求函數(shù)

P(x)=a0+a1x+a2

x2滿足:P(x0)=y0,P(x1)=y1,P(x2)=y2P(x)=l0(x)y0+l1(x)y1+l2(x)y2l0(x)1 0 0l1(x)0 1 0l2(x) 00 1

x x0x1 x2二次插值函數(shù):P(x)=l0(x)y0+l1(x)y1+l2(x)y2l0(x)1 0 0l1(x)0 1 0l2(x) 00 1

x x0x1 x2拉格朗日方法插值條件:P(xk)=yk(k=0,1,…,n)其中第k

個插值基函數(shù)

或例1求插值于點(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次數(shù)小于等于4的拉格朗日插值多項式。程序片段1:MatlabCode:拉格朗日插值多項式functionv=polyinterp(x,y,u)%POLYINTERPPolynomialinterpolation.%v=POLYINTERP(x,y,u)computesv(j)=P(u(j))wherePisthe%polynomialofdegreed=length(x)-1withP(x(i))=y(i).%UseLagrangianrepresentation.%Evaluateatallelementsofusimultaneously.n=length(x);v=zeros(size(u));fork=1:nw=ones(size(u));forj=[1:k-1k+1:n]

w=(u-x(j))./(x(k)-x(j)).*w;endv=v+w*y(k);endDemox=0:3;y=[-5-6-116];u=-.25:.01:3.25;v=polyinterp(x,y,u);plot(x,y,'o',u,v,'-')symx=sym('x'),L=polyinterp(x,y,symx);L=simplify(L);給定x0,x1和

x2,求二次函數(shù)

P(x)=a0+a1(x–x0)+a2(x–x0)(x–x1)滿足條件

P(x0)=y0,P(x1)=y1,P(x2)=y2

滿足插值條件的關(guān)于a0,

a1和a2方程牛頓差商方法解下三角方程組過程中引入符號牛頓插值多項式:定義

若已知函數(shù)

f(x)在點

x0,x1,···,xn

處的值

y0,y1,···,yn。如果

i≠j,則各階差商(divideddifference)定義如下(j=1,…,n)一階差商n階差商二階差商三階差商(j=2,…,n)(j=3,…,n)更加一般地考慮牛頓插值多項式求解該方程組可得待定系數(shù)如下:例2求插值于點(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次數(shù)小于等于4的牛頓插值多項式。例3求插值于點(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次數(shù)小于等于4的拉格朗日插值多項式。例3求插值于點(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4),(2,-4)的次數(shù)小于等于5的牛頓插值多項式。

加入一個新的點到拉格朗日插值多項式所需要額外工作與牛頓插值多項式進(jìn)行比較是很有趣的。牛頓差商方法具有拉格朗日方法所缺少的”實時更新”性質(zhì)。例4

證明:例5求插值于點(0,2),(1,1),(3,-1)的次數(shù)小于等于2的插值多項式(拉格朗日方法和牛頓方法)。問題2：是否有多個經(jīng)過這三個數(shù)據(jù)點的次數(shù)小于等于2次的多項式？問題1：拉格朗日方法和牛頓方法的多項式是否相同？則滿足插值條件

P(xk)=yk(k=0,1,…,n)的次數(shù)小于等于n次的插值多項式

P(x)=a0+a1x+…+anxn存在而且唯一。定理

若插值結(jié)點x0,x1,···,xn

是(n+1)個互異點,問題3：是否有多個經(jīng)過這三個數(shù)據(jù)點的次數(shù)大于2次的多項式？加入第四個點(2,0),得到的多項式是加入第四個點(2,3),得到的多項式是例.給定插值條件f(x0)=y0,f(x1)=y1,f′(x1)=m1,f(x2)=y2,試求滿足條件的插值多項式。解:例.已知y=f(x)的函數(shù)表x012

y

8-7.5-18求函數(shù)f(x)在[0,2]之間的零點。

y8-7.5-18

x

01217:46壓縮的概念:觀測的離散數(shù)據(jù)可以想象成現(xiàn)實中無窮多信息的代表。通過給定數(shù)據(jù)求出插值函數(shù)意味著用簡單的規(guī)則代替無窮多信息。盡管期待這種簡單規(guī)則精確地反映實際情況是不現(xiàn)實的,但是它可以充分接近實際。這一類壓縮是有損的壓縮,即它會產(chǎn)生誤差。用簡單規(guī)則代替無窮多信息時會產(chǎn)生多大的誤差,這是我們下面研究的內(nèi)容。兩點線性插值插值誤差余項:

R(x)=f(x)–P(x)R(x)=???Rolle引理P(x)是滿足P(xk)=f(xk)的n次插值多項式,則對任何x∈[a,b],在(a,b)內(nèi)存在