数值分析(插值方法)总结.ppt

《数值分析(插值方法)总结.ppt》由会员分享，可在线阅读，更多相关《数值分析(插值方法)总结.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/50*插值的应用背景插值的应用背景拉格朗日插值公式拉格朗日插值公式牛顿插值公式牛顿插值公式插值误差余项插值误差余项Runge反例反例数值分析122/50*3/50*4/50*趣例趣例1:图像放大图像放大5/50*趣例趣例2:工业设计工业设计http:/ x0 x1f(x)y0y1例例求求的近似值的近似值(函数值函数值:10.7238)真实值真实值:10.723812线性插值函数线性插值函数x0 x1(x0，y0)(x1，y1)L1(x)可见可见是过是过 和和两点的直线。两点的直线。13抛物插值函数抛物插值函数x0 x1x2因过三点的二次曲线为抛物线因过三点的二次曲线为抛物线,故称为抛物插值

2、。故称为抛物插值。14/50*选择多项式函数的理由选择多项式函数的理由:理论方面理论方面多项式函数简单明了的数学性质。多项式函数简单明了的数学性质。有一个简单的原理可以说明什么时候存在给定有一个简单的原理可以说明什么时候存在给定次数的插值多项式。次数的插值多项式。更重要的是更重要的是计算方面计算方面多项式函数是计算机多项式函数是计算机最基本的函数最基本的函数,计算多项式函数的值只需用加计算多项式函数的值只需用加和乘运算和乘运算,且积分和微分均非常方便。且积分和微分均非常方便。插值函数的选择插值函数的选择:15/50*则则称称P(x)为为插插值值多多项项式式,称称x0,x1,xn为为插插值节点。

3、值节点。如果如果P(x)=a0+a1x+anxn满足满足P(xk)=yk(k=0,1,n)考虑区间考虑区间a,b上上(n+1)个点个点a x0 x1xnb。代数插值问题代数插值问题插值条件插值条件16/50*点点,则满足插值条件则满足插值条件L(xk)=yk(k=0,1,n)的的次次数小于等于数小于等于n次次的插值多项式的插值多项式L(x)=a0+a1x+anxn存在而且唯一存在而且唯一。证明证明:由插值条件由插值条件L(x0)=y0L(x1)=y1L(xn)=yn定理定理5.1若插值结点若插值结点x0,x1,xn是是(n+1)个互异个互异17/50*回顾回顾1:非齐次方程组有唯一解的充分必要

4、条件是系数矩非齐次方程组有唯一解的充分必要条件是系数矩阵可逆阵可逆(矩阵可逆的充分必要条件是行列式不等于零矩阵可逆的充分必要条件是行列式不等于零)。系数矩阵行列式不等于零系数矩阵行列式不等于零,则方程组有唯一解。因此则方程组有唯一解。因此插值多项式插值多项式L(x)存在且唯一。存在且唯一。回顾回顾2:范德蒙范德蒙(Vandermonde)矩阵矩阵18/50*注释注释:插值多项式的存在唯一性说明满足插值插值多项式的存在唯一性说明满足插值条件的多项式存在而且与条件的多项式存在而且与构造方法无关构造方法无关。只要插值节点互异只要插值节点互异,则则Vandermonde矩阵矩阵总是非奇异。然而范得蒙矩

5、阵条件数通常很总是非奇异。然而范得蒙矩阵条件数通常很大大,故直接求解方程组是危险的故直接求解方程组是危险的。Hilbert和和Vandermonde条件数条件数:fori=1:10c(i)=cond(hilb(i),2);%vander(1:i)endplot(1:10,c)19/50*过两点直线方程过两点直线方程已知函数表求满足已知函数表求满足:L(x0)=y0和和L(x1)=y1的线性函数的线性函数L(x)。x x0 x1f(x)y0y120/50*记记xx0 x1l0(x)10l1(x)01对称形式对称形式21/50*二次插值问题二次插值问题 x x0 x1x2 f(x)y0y1y2已知

6、函数表已知函数表求函数求函数L(x)=a0+a1x+a2x2满足满足:L(x0)=y0,L(x1)=y1,L(x2)=y2L(x)=l0(x)y0+l1(x)y1+l2(x)y2l0(x)100l1(x)010l2(x)001L(x)y0y1y2 xx0 x1x222/50*二次插值函数二次插值函数:L(x)=l0(x)y0+l1(x)y1+l2(x)y2，l0(x)100l1(x)010l2(x)001L(x)y0y1y2 xx0 x1x223/50*二次插值基函数图形二次插值基函数图形取取 x0=0,x1=0.5,x2=1l0(x)=2(x0.5)(x1);l1(x)=4x(x 1);l2

7、(x)=2(x 0.5)x24/50*拉格朗日插值公式拉格朗日插值公式插值条件插值条件:L(xk)=yk(k=0,1,n)其中第其中第k个个插值基函数插值基函数(k=0,1,，n)。或或25/50*例例1求插值于点求插值于点(0,2),(1,1),(2,0),(3,-1)的的次数次数小于等于小于等于3的插值多项式的拉格朗日形式。的插值多项式的拉格朗日形式。26/50*例例2求插值于点求插值于点(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次数小于等于的次数小于等于4的插值多项式拉格朗的插值多项式拉格朗日形式。日形式。27/50*程序片段程序片段1:MatlabCo

8、de:多项式插值多项式插值(拉格朗日形式拉格朗日形式)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(s

9、ize(u);forj=1:k-1k+1:nw=(u-x(j)./(x(k)-x(j).*w;endv=v+w*y(k);end28/50*Demo2x=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);29/50*拉格朗日形式结构紧凑拉格朗日形式结构紧凑且且形式对称。然形式对称。然而很少用它来计算而很少用它来计算,这是因为等价的牛顿形这是因为等价的牛顿形式更具操作性而且计算复杂度更低。式更具操作性而且计算复杂度

10、更低。牛顿形式相对简单牛顿形式相对简单,但是某些记号首先需但是某些记号首先需要掌握。把数据点看作由某个函数给出要掌握。把数据点看作由某个函数给出,并并把数据点列成下表把数据点列成下表:插值多项式的牛顿形式插值多项式的牛顿形式30/50*给定给定x0,x1和和x2,求二次函数求二次函数P(x)=a0+a1(x x0)+a2(x x0)(x x1)满足条件满足条件P(x0)=f(x0),P(x1)=f(x1),P(x2)=f(x2)满足插值条件的关于满足插值条件的关于a0,a1和和a2方程方程插值多项式牛顿形式插值多项式牛顿形式31/50*解下三角方程组过程中引入符号解下三角方程组过程中引入符号a

11、0=f(x0),a1=fx0,x1,a2=fx0,x1,x2P(x)=f(x0)+fx1,x2(x x0)+fx0,x1,x2(x x0)(x x1)牛顿插值公式牛顿插值公式:32/50*定义定义5.3若已知函数若已知函数f(x)在点在点x0,x1,xn处的处的值值f(x0),f(x1),f(xn)。如果如果 i j,则则(j=0,1,n-1)一阶差商一阶差商n阶差商阶差商二阶差商二阶差商三阶差商三阶差商差商差商(divideddifference)33/50*更加一般地考虑更加一般地考虑牛顿插值形式牛顿插值形式求解该方程组可得待定系数如下求解该方程组可得待定系数如下:a0=f(x0),a1=

12、fx0,x1,a2=fx0,x1,x2,an=fx0,x1,xn。34/50*例例3已知数据如下表已知数据如下表,试计算数据的差商。试计算数据的差商。35/50*例例2求插值于点求插值于点(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次数小于等于的次数小于等于4的插值多项式拉格朗的插值多项式拉格朗日形式。日形式。36/50*例例4已知数据如下表已知数据如下表,试计算数据的插值多项式。试计算数据的插值多项式。37/50*例例5已知数据如下表已知数据如下表,试计算数据的插值多项式。试计算数据的插值多项式。加入一个新的点到加入一个新的点到Lagrange形式所需要额外工

13、作形式所需要额外工作与牛顿形式进行比较是很有趣的。牛顿形式具有与牛顿形式进行比较是很有趣的。牛顿形式具有Lagrange形式所缺少的形式所缺少的”实时更新实时更新”性质。性质。38/50*差商的性质差商的性质差商的值不依赖于差商的值不依赖于x0,x1,xn的次序。的次序。39/50*压缩的概念压缩的概念:观测的离散数据可以想象成现实中无穷多观测的离散数据可以想象成现实中无穷多信息的代表。通过给定数据求出插值函数意味信息的代表。通过给定数据求出插值函数意味着用简单的规则代替无穷多信息。尽管期待这着用简单的规则代替无穷多信息。尽管期待这种简单规则精确地反映实际情况是不现实的种简单规则精确地反映实际

14、情况是不现实的,但是它但是它可以充分接近实际可以充分接近实际。这一类压缩是这一类压缩是有损的压缩有损的压缩,即它会产生误差。即它会产生误差。用简单规则代替无穷多信息时会产生多大的误用简单规则代替无穷多信息时会产生多大的误差差,这是我们下面研究的内容。这是我们下面研究的内容。40/50*两点线性插值两点线性插值插值误差余项插值误差余项:R(x)=f(x)L1(x)由插值条件知由插值条件知R(x)=C(x)(x x0)(x x1)即即f(x)L(x)=C(x)(x x0)(x x1)C(x)=?41/50*Rolle过山车过山车:42/50*回顾回顾:拉格朗日中值定理拉格朗日中值定理43/50*L

15、n(x)是是满满足足Ln(xk)=f(xk)的的n次次插插值值多多项项式式,则则对任何对任何xa,b,在在(a,b)内存在一点内存在一点使得使得其中其中定理定理5.2设设f(x)在在a,b连续且在连续且在(a,b)具有具有n+1阶导数阶导数,x0,x1,xn是是a,b内互不相同的节点内互不相同的节点。44/50*证明证明:记记 n+1(x)=(x x0)(x xn)45/50*46/50*注释注释:47/50*例例1 给出如下数据给出如下数据x0.320.340.36sin(x)0.3145670.3334870.352274用线性插值及抛物插值计算用线性插值及抛物插值计算sin0.3367的

16、值并估计误差。的值并估计误差。48/50*例例2设设y=f(x)在区间在区间a,b上连续上连续,且且 f(x)在在(a,b)内具有内具有2阶导数阶导数,已知已知f(x)在区间端点处的值。在区间端点处的值。如果当如果当x(a,b)时有时有|f(x)|M。证明证明证明证明由由Lagrange插值误差公式插值误差公式令令h(x)=|(x a)(x b)|49/50*Runge反例反例(rungeinterp)f(x)=1/(x2+1),(-5=x=5)x=-5:5;y=1./(x.2+1);u=-5:.01:5;v=polyinterp(x,y,u);plot(x,y,o,u,v,-)一般认为一般认为Ln(x)的次数的次数n越高逼近越高逼近f(x)的精度越好？的精度越好？50/50*Interploation(内插内插)Extrapolation（外推）（外推）51/50*插值方法具有预测性吗？插值方法具有预测性吗？美国美国Wired杂志杂志MathematicianPredictsWhoWillLiveandDieinGame of ThronesWhenExtrapolationFailsUs:IncorrectMathematicalConjectures