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

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

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

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

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

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

P(x)x

x0x1

y

y0

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

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

則稱

P(x)為

插值多項式,稱

x0,x1,···,xn為

插值節點。

如果

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

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

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

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

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

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

若插值結點x0,x1,···,xn

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

P(x0)=y0

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

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已知函數表求函數

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二次插值函數: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

個插值基函數

或例1求插值于點(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次數小于等于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,求二次函數

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

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

滿足插值條件的關于a0,

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

若已知函數

f(x)在點

x0,x1,···,xn

處的值

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

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

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

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

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

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

若插值結點x0,x1,···,xn

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

y

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

y8-7.5-18

x

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

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