数值分析13插值方法

插值的应用背景拉格朗日插值公式牛顿插值公式插值误差余项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)内存在