《计算方法》插值方法.ppt

计 算 方 法,华中科技大学数学与统计学院,第四章 插值方法,计算方法课程组,4 插值方法,4.1多项式插值问题的一般提法,4.2 拉格朗日(Lagrange)插值,4.3 差商与差分及其性质,4.4 牛顿插值公式,4.5 分段插值法,4.6曲线拟合的最小二乘法,4.0 引言,插值法是广泛应用于理论研究和生产实践的重 要数值方法, 它是用简单函数(特别是多项式或分 段多项式)为各种离散数组建立连续模型；为各种 非有理函数提供好的逼近方法。众所周知，反映 自然规律的数量关系的函数有三种表示方法：,解析表达式,图象法,表格法,4.0 引言,许多数据都是用表格法给出的(如观测和实验而得到的函数数据表格)，可是，从一个只提供离散的函数值去进行理论分析和进行设计，是极不方便的, 甚至是不可能的。因此需要设法去寻找与已知函数值相符，并且形式简单的插值函数(或近似函数)。,另外一种情况是，函数表达式完全给定，但其形式不适宜计算机使用，因为计算机只能执行算术和逻辑操作，因此涉及连续变量问题的计算都需要经过离散化以后才能进行。如数值积分方法、数值微分方法、差分方程以及有限元法等，都必须直接或间接地应用到插值理论和方法。,4.1 多项式插值问题的一般提法,当精确函数 y = f (x) 非常复杂或未知时，在一系列节点 x0 xn 处测得函数值 y0 = f (x0) , , yn = f (xn)， 由此构造一个简单易算的近似函数 p(x) f(x)，满足条件: p(xi) = f(xi) (i = 0, n)。 这里的 p(x) 称为f(x) 的插值函数。,最常用的插值函数是 ? 代数多项式、三角多项式、有理分式,插值函数 p (x) 作为 f (x) 的近似，可以选自不同类型的 函数, 如 p (x) 为代数多项式、三角多项式、有理分式； 其函数性态可以是光滑的、亦可以是分段光滑的。其 中，代数多项式类的插值函数占有重要地位：,(a) 结构简单、计算机容易处理、任何多项式的导数和积分也易确定，并且仍是多项式。,(b) 著名的Weierstrass逼近定理(定义在闭区间上的 任何连续函数 f(x) , 存在代数多项式p(x)一致逼近f(x), 并达到所要求的精度)。,因此，我们主要考虑代数多项式的插值问题。,x0 , x1, , xn 插值节点,函数 P(x) 称为函数 y=f(x) 的插值函数， 区间 a, b 称为插值区间。,例题:,已知函数 f(x) 有如下数据:,求 f(x) 的插值多项式 p(x)， 并求 f(x) 在 x=0.5 处的近似值。,插值的几何意义,从几何上看，插值就是求一条曲线 使其通过给定的 个点 ， 并且与已知曲线 有一定的近似度。,从几何上看,曲线 P ( x) 近似 f ( x),插值方法的研究问题,曲线 P ( x) 近似 f ( x),求 n 次多项式 使得:,条件：无重合节点，即,4.2 拉格朗日多项式 /* Lagrange Polynomial */,Vandermonde行列式,注意到插值节点,两两相异，而,故方程组(1)有惟一解,于是满足插值条件的多项式存在且惟一。,(唯一性),Return,n = 1,已知 x0 , x1 ; y0 , y1 ，求,使得,1,1,1,0,0,1,),(,),(,y1,x1,L,y0,x0,L,=,=,可见 L1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。,4.2 拉格朗日多项式 /* Lagrange Polynomial */,线性插值基函数,1. 构造线性插值基函数的方法:,线性插值与其基函数示意图,显然, 是过 、 、 三点的一条抛物线。,已知 , 求 ，,n = 2,使得,显然, 是过 、 、 三点的一条抛物线。,已知 , 求 ，,n = 2,使得,抛物线插值基函数,于是,抛物线基函数,希望找到 li (x)，i = 0, , n 使得 li (xj) = ij ；然后令,，则显然有 Pn(xi) = yi 。,每个 li 有 n 个根 x0 , xi , xn,， k = 0, 1 , n .,k = 0, 1 , n .,由 得:,设 函数表 则满足插值条件的多项式,（Lagrange）插值多项式,其中, .,以下的问题：如何分析插值的余项？,(1) 先求插值基函数. (2) 构造插值多项式.,构造插值多项式的方法：,已知连续函数 f (x) 的函数表如下：,求方程 f (x)=0 在(-1,2)内的近似根。,例题,解：利用Lagrange插值法有,取初值x=0.5，利用牛顿法求解可得 f (x) 在(-1,2)内的近似根 为0.67433。,解方程,已知连续函数f (x)的函数表如下：,求方程 f (x)=0 在(-1,2)内的近似根。,例题,，且 f 满足条件 , Lagrange插值法插值余项,设节点,在a , b内存在, 考察截断误差:, Lagrange插值法的插值余项, Lagrange插值法的插值余项,证明：由已知条件得到：,于是有：,其中 是与 x 有关的待定函数。,故,处均为零，,在,上有n+2个个零点，根据 Roll 定理,在 的每两个零点间至少有一个零点，故 在 内至少有 一 个零点，对 再用Roll 定理，可知 在 内至少有 n 个零点，依此类推， 在 内至少有一个零点，记为,使得:,由于 是不能确定，因此我们并不能确定误差的大小 但如能求出 ，那么用 逼近 的截断误差限是： 当 时， 当 时,当 f (x) 为任一个次数 n 的多项式时， , 可知， 即插值多项式对于次数 n 的多项式是精确的。,注意,给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是 l2(x) 的图像？,问题,算例1,Lagrange插值法,已知 ， ， 用线性插值及抛物线插值计算 的值并估计截断误差。,算例1,Lagrange插值法,已知 ， ， 用线性插值及抛物线插值计算 的值并估计截断误差。,线性插值时取,解:,其截断误差为： 其中, 因为 可取 于是：,用抛物线插值时，取所有节点，得到,余项讨论： 其中：,算例2,Lagrange插值法,利用 100，121 的开方计算 .,由于:,解:,利用Lagrange插值法有,于是,的精确值为 10.72380529, 因此, 近似值 10.71428 有3 位有效数字.,Return,4.3 差商与差分,Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 li (x) 都需重新算过。,由线性代数的知识可知：任何一个n次多项式都可以表示成,共 n+1 个线性无关的多项式的线性组合。,那么，是否可以将这 n+1 个多项式作为插值基函数呢？,设插值多项式P(x)具有如下形式：,再继续下去,待定系数的形式将更复杂,为此引入 差商和差分的概念.,P(x)应满足插值条件：,有：,4.3.1 差商的概念,从零阶差商出发，归纳地定义各阶差商:,称 为函数 关于点 的一阶差商.,一般地， 关于 的 k 阶差商:,记函数 在 的值 ， 称 为 关于 的零阶差商。,一般地， 关于 的 n 阶差商:,n 阶差商的概念,差商的基本性质,性质1：差商可表示为函数值的线性组合，即： 性质2：差商关于所含节点是对称的，即：,可用归纳法证明,差商的基本性质,性质3： 性质4：设 在 存在 n 阶导数，且 则 ，使得:,差商的计算-差商表,已知,计算三阶差商,解：列表计算,算例,4.3.2 差分,在前面的讨论中，节点是任意分布的，但实际上经常遇 到等距节点的情况，这时插值公式可以得到简化，为此，我 们先介绍差分的概念。 设函数 在等距节点 上的值 为已知，这里 为常数，称为步长。,下面来讨论差分的定义。,差分的定义,记号 分别称为 在 处以 为步长的 向前差分、向后差分、中心差分 符号 、 、 分别称为向前差分算子、向后差分算子、 中心差分算子.,高阶差分,用一阶差分可以定义二阶差分 一般地可定义 m 阶差分为： 中心差分定义为: 以此类推。,不变算子 I、移位算子 E,定义 从而可得： 于是得到： 同理，由于： 得到： 由于： 得到： 由差分的定义及不变算子和移位算子有如下性质:,差分的性质,性质1：各阶差分均可用函数值表示，如： 性质2：某点的函数可用各阶差分来表示：,性质3：差商与差分有如下关系： 性质4：差分与导数有如下关系：,差分的计算,Return,4.4 牛顿插值公式,根据差商的定义，把 看成 上的一点， 可得：,4.4 牛顿插值公式,根据差商的定义，把 看成 上的一点， 可得：,把后一式代入前一式,其中 显然 满足插值条件，且次数不超过 ,它就 是插值多项式，其系数为： 我们称 为牛顿插值多项式.,从表中可以看到4 阶差商几乎为0，故取4次插值多项式即可， 于是：,解：列表计算,已知 的函数表，求4 次牛顿插值多项式, 并求,算例,解：列表计算,已知 的函数表，求4 次牛顿插值多项式, 并求,算例,截断误差为：,和 均是 n 次多项式,且均满足插值条件: 由多项式的唯一性, ,因而,两个公式 的余项是相等的,即 当插值多项式从 n-1 次增加到 n 次时, 拉格朗日型插值必须重新计算所有的基本插值多项式; 而对于牛顿型插值,只需用表格再计算一个 n 阶差商, 然后加上一项即可。,牛顿插值公式和Lagrange插值公式比较,Return,4.5 分段插值公式,在区间 a, b 上用插值多项式 P 逼近函数 f 时，f 和P 在每个节点上的差异(理论上)应该为零。自然，我们期望 在一切中间点上也能很好地逼近 f ，并且当插值点增加时 这种逼近效果应该越来越好。 但上述的期望不可能实现的。当认识到这一点时，在数 学界曾引起强烈的震动。,20 世纪初，Runge就给出了一个等距节点插值多项式 不收敛到 的例子。,设函数 ， 在该区间 上取 个等距节点, 构造 的 次 拉格朗日插值多项式为,其matlab的lagrange.m文件及相关图形如下.,Runge 现象,% lagrange.m function y=lagrange (x0,y0,x) n=length(x0);m=length(x); for i=1:m z=x(i);s=0; for k=1:n L=1; for j=1:n if j=k L=L*(z-x0(j)/(x0(k)-x0(j); end end s=s+L*y0(k); end y(i)=s; end y;,Lagrange插值多项式 求插值的Matlab程序.,%Compare_Runge.m x=-5:0.1:5;z=0*x;y=1./(1+x.2); plot(x,z,k,x,y,r) axis(-5 5 -1.5 2);pause,hold on for n=2:2:20 x0=linspace(-5,5,n+1); y0=1./(1+x0.2); x=-5:0.1:5; y1=lagrange(x0,y0,x); plot(x,y1), pause end y2=1./(1+x0.2);y=interp1(x0,y2,x); plot (x,y,k),hold off gtext(n=2),gtext(n=4),gtext(n=6) gtext(n=8),gtext(n=10) gtext(f(x)=1/(1+x2),比较不同的插值多项式次数对插值的影响,不同次数的Lagrange插值多项式的比较图,Runge现象,令 ，则 ， 下表列出了 和 的值。,结果表明,随着 的增加， 的绝对值几乎成倍地增加，这说明当 时 在 上不收敛。 Runge证明了，存在一个常数 , 使得当 时， ; 而当 时 发散。 说明: 并不是插值多项式的次数越高, 插值效果越好, 精度也不一定是随次数的提高而升高, 这种现象在上个世纪初由Runge发现, 故称为Runge现象.,分段线性插值特别简单，从几何上看，就是用折线逼近 曲线。 分段线性插值的数学定义 设 是区间 上的函数，在节点 上的函数值为 ， 求一分段折线函数 满足： （1） （2） 在 上， 是一次多项式。 （3） 则称 为 的分段线性插值函数。,4.5.1 分段线性插值,易知, P(x) 是个折线函数，在每个区间,上,有,在 a,b 上是连续的，但其一阶导数是不连续的.,当 时,当 时,4.5.1 分段线性插值的基函数,当 时,显然 是 的线性组合： 在区间 上的值为：,，,算例,解: 在每个分段区间,于是，,实际值:,当n=7 时， P(4.5)=0.04762270321996 ; 当n=10时，P(4.5)=0.04705882352941 由此可见，对于光滑性要求不高的插值问题，分段线性插值的 效果非常好！计算也简单!,4.5.2 埃尔米特 (Hermite) 插值,拉格朗日和牛顿均只保证函数插值； 实际问题有时需要导数也插值； 满足这种需要的插值称为埃尔米特插值.,埃尔米特插值的一般提法为： 设函数在节点 的函数值与导数值为： 其中 是正整数，寻求一个次数尽可能低的多 项式 ，满足：,埃尔米特插值的一般提法,以如下数据构建埃尔米特插值,埃尔米特插值,算例,以如下数据构建埃尔米特插值,埃尔米特插值,算例,共有 个条件，可唯一确定一个次数不超过 的多项式 ，其形式为： 目标：求出所有的 , 方法：基函数法.,这样 可表示为：,显然有：,现在求 及 ， 令 其中 从而有： 由此得： ， 故： ，,由 的表达式可得： 于是得到： 同理可得,解：,n = 1,分别利用x0, x1 以及 x1, x2 计算,利用,这里,而,sin 50 = 0.7660444,外推 /* extrapolation */ 的实际误差 0.01001,利用,内插 /* interpolation */ 的实际误差 0.00596,内插通常优于外推。选择要计算的 x 所在的区间的端点，插值效果较好。,n = 2,sin 50 = 0.7660444,2次插值的实际误差 0.00061,高次插值通常优于低次插值,Return,巴尔末(J.J.Balmer，1825-1898),特殊爱好: 数字游戏,职 业: 数学教师，瑞士某女子中学，,兼巴塞尔大学无薪讲师,“我能用公式把任意4个数字有规律地联系起来”,4 Why?,信息量?,道家: 1生2，2生3，3生万物,4 万物？全部信息量?!,4 条谱线的波长数据,实验: 氢光谱谱线的波长数据,巴尔末公式:,艰苦努力+天才,引子,1884年,4.6 曲线拟合的最小二乘法,物理实验,实验数据,经验公式,天才,数学: 一般方法？,引子(续）,问题,已知:,求 :,特点,实验数据,n 1,实验值 yi 有误差，个别点可能误差还比较大。,方法:,多项式插值,点点通过,高次插值效果不好,?,启发,手工!,实例,某种纤维的强度 y 与 其拉伸倍数 x 的关系,实验数据: 24个纤维样品,实例,x,y,坐标纸 后勤集团印制,1981,1. 描点,手工方法:,2. 画直线,3. 求出 a0 , a1,直线应该与所有点靠得比较近,或者说: 所有点应该尽量靠近直线,实例(续1),注意:,xi,数学方法:,所有点应该尽量靠近直线,xi 点误差：,( a0 + a1 xi ) - yi ,=,实例(续2),i = 1, 2, , n,尽量小,误差向量,向量大小:,残差,范数,min,min,min,实例(续3),F(a0, a1),=,min,即: 求 a0 , a1, 使误差平方和取最小值!,二元函数求极值问题,解出 a0, a1,最小二乘解,实例(续4),实例求解:,y = 0.1505 + 0.8587 x,即为最小二乘解,平方误差为,一般地:,一般,已知:,求 :,y = a0 + a1 x + a2 x2 + + am xm =,m次多项式,多项式拟合的最小二乘法,使,F(a0 , a1 , , am ),=,min,取极小。,即,类似地 m +1 元函数求极值,一般(续),k = 0, 1, , m,得,即,解出 a0 , a1 , , am,得:,y = a0 + a1 x + a2 x2 + + am xm,法方程组,例1,例1,用最小二乘法求一个形如y=a+bx2的经验公式， 使与下列数据相拟合:,a = 0.972577,b = 0.050035,y=0.972577+0.050035x2,拟合曲线为非线性模型,Return,