《数值分析(插值方法)总结.ppt》由会员分享，可在线阅读，更多相关《数值分析(插值方法)总结.ppt（51页珍藏版）》请在三一办公上搜索。
1、插值的应用背景拉格朗日插值公式牛顿插值公式插值误差余项Runge反例,数值分析 12,趣例1:图像放大,趣例2:工业设计,http:/,先是雷诺和雪铁龙工作的Paul de Casteljau 和Pierre Bzier,随后美国通用汽车的其它人一起推动了现在称为三次样条和Bzier样条的建立。样条是通过很少的控制点就能够生成复杂平滑曲线的方法。,趣例3:数据可视化,趣例4:游戏与电影,Demo1:figure(position,get(0,screensize)axes(position,0 0 1 1)x,y=ginput;n=length(x);s=(1:n);t=(1:.05:n);u
2、=splinetx(s,x,t);v=splinetx(s,y,t);clf resetplot(x,y,.,u,v,-);,数据和插值函数,如果一个函数P(x)满足yi=P(xi)(i=0,n),那么函数P(x)插值了一系列数据点(x0,y0),(xn,yn)，其中P(x)称为插值函数,点x0,xn称为插值节点。,P(x),函数是描述自然界客观规律的重要工具。,插值问题研究包括如下三个方面:,插值函数的选择和构造,插值函数的存在唯一性,插值误差估计的问题,过两点直线方程,已知函数表求满足:L(x0)=y0,L(x1)=y1的线性函数 L(x),例 求 的近似值(函数值:10.7238),真实
3、值:10.7238,12,线性插值函数,x0,x1,(x0，y0),(x1，y1),L1(x),可见 是过 和 两点的直线。,13,抛物插值函数,x0,x1,x2,因过三点的二次曲线为抛物线,故称为抛物插值。,选择多项式函数的理由:理论方面多项式函数简单明了的数学性质。有一个简单的原理可以说明什么时候存在给定次数的插值多项式。更重要的是计算方面多项式函数是计算机最基本的函数,计算多项式函数的值只需用加和乘运算,且积分和微分均非常方便。,插值函数的选择:,则称 P(x)为 插值多项式,称 x0,x1,xn为 插值节点。,如果 P(x)=a0+a1x+anxn满足 P(xk)=yk(k=0,1,n
4、),考虑区间a,b上(n+1)个点a x0 x1xnb。,代数插值问题,插值条件,点,则满足插值条件 L(xk)=yk(k=0,1,n)的 次数小于等于n次的插值多项式 L(x)=a0+a1x+anxn存在而且唯一。,定理5.1 若插值结点x0,x1,xn 是(n+1)个互异,回顾1:非齐次方程组有唯一解的充分必要条件是系数矩阵可逆(矩阵可逆的充分必要条件是行列式不等于零)。,系数矩阵行列式不等于零,则方程组有唯一解。因此插值多项式 L(x)存在且唯一。,回顾2:范德蒙(Vandermonde)矩阵,注释:,插值多项式的存在唯一性说明满足插值条件的多项式存在而且与构造方法无关。,只要插值节点互
5、异,则Vandermonde矩阵总是非奇异。然而范得蒙矩阵条件数通常很大,故直接求解方程组是危险的。,Hilbert和Vandermonde条件数:for i=1:10c(i)=cond(hilb(i),2);%vander(1:i)endplot(1:10,c),过两点直线方程,已知函数表求满足:L(x0)=y0 和 L(x1)=y1的线性函数 L(x)。,记,对称形式,二次插值问题,已知函数表,求函数 L(x)=a0+a1x+a2 x2 满足:L(x0)=y0,L(x1)=y1,L(x2)=y2,L(x)=l0(x)y0+l1(x)y1+l2(x)y2,二次插值函数:L(x)=l0(x)y
6、0+l1(x)y1+l2(x)y2，,二次插值基函数图形,取 x0=0,x1=0.5,x2=1,l0(x)=2(x 0.5)(x 1);l1(x)=4 x(x 1);l2(x)=2(x 0.5)x,拉格朗日插值公式,插值条件:L(xk)=yk(k=0,1,n),其中第k 个插值基函数(k=0,1,，n)。,或,例1求插值于点(0,2),(1,1),(2,0),(3,-1)的次数小于等于3的插值多项式的拉格朗日形式。,例2求插值于点(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次数小于等于4的插值多项式拉格朗日形式。,程序片段1:,Matlab Code:多项式插值
7、(拉格朗日形式)function v=polyinterp(x,y,u)%POLYINTERP Polynomial interpolation.%v=POLYINTERP(x,y,u)computes v(j)=P(u(j)where P is the%polynomial of degree d=length(x)-1 with P(x(i)=y(i).%Use Lagrangian representation.%Evaluate at all elements of u simultaneously.n=length(x);v=zeros(size(u);for k=1:n w=one
8、s(size(u);for j=1:k-1 k+1:n w=(u-x(j)./(x(k)-x(j).*w;end v=v+w*y(k);end,Demo2x=0:3;y=-5-6-1 16;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);,拉格朗日形式结构紧凑且形式对称。然而很少用它来计算,这是因为等价的牛顿形式更具操作性而且计算复杂度更低。,牛顿形式相对简单,但是某些记号首先需要掌握。把数据点看作由某个函数给出,并把数据点列成下表:,插值
9、多项式的牛顿形式,给定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方程,插值多项式牛顿形式,解下三角方程组过程中引入符号,a0=f(x0),a1=fx0,x1,a2=fx0,x1,x2,P(x)=f(x0)+fx1,x2(x x0)+fx0,x1,x2(x x0)(x x1),牛顿插值公式:,定义5.3 若已知函数 f(x)在点 x0,x1,xn 处的值 f(x0),f(x1),f(xn)。如果 i j,则,(j=0,1,n-1)
10、,一阶差商,n阶差商,二阶差商,三阶差商,差商(divided difference),更加一般地考虑,牛顿插值形式,求解该方程组可得待定系数如下:,a0=f(x0),a1=fx0,x1,a2=fx0,x1,x2,an=fx0,x1,xn。,例3 已知数据如下表,试计算数据的差商。,例2求插值于点(-2,-56),(-1,-16),(0,-2),(1,-2),(3,4)的次数小于等于4的插值多项式拉格朗日形式。,例4 已知数据如下表,试计算数据的插值多项式。,例5 已知数据如下表,试计算数据的插值多项式。,加入一个新的点到Lagrange形式所需要额外工作与牛顿形式进行比较是很有趣的。牛顿形式
11、具有Lagrange形式所缺少的”实时更新”性质。,差商的性质,差商的值不依赖于x0,x1,xn的次序。,压缩的概念:,观测的离散数据可以想象成现实中无穷多信息的代表。通过给定数据求出插值函数意味着用简单的规则代替无穷多信息。尽管期待这种简单规则精确地反映实际情况是不现实的,但是它可以充分接近实际。,这一类压缩是有损的压缩,即它会产生误差。用简单规则代替无穷多信息时会产生多大的误差,这是我们下面研究的内容。,两点线性插值,插值误差余项: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)=?,R
12、olle过山车:,回顾:拉格朗日中值定理,Ln(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内互不相同的节点。,证明:记 n+1(x)=(x x0)(x xn),注释:,例1 给出如下数据,用线性插值及抛物插值计算sin0.3367的值并估计误差。,例2 设 y=f(x)在区间 a,b上连续,且 f(x)在(a,b)内具有2阶导数,已知f(x)在区间端点处的值。如果当x(a,b)时有|f(x)|M。证明,证明 由Lagrange插值误差公式,
13、令h(x)=|(x a)(x b)|,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)的精度越好？,Interploation(内插),Extrapolation（外推）,插值方法具有预测性吗？,美国Wired杂志Mathematician Predicts Who Will Live and Die in Game of ThronesWhen Extrapolation Fails Us:Incorrect Mathematical Conjectures,
