四章 多项式插值与数值逼近.pptx

实际问题中经常要涉及到函数值的计算问题：（1）如果函数表达式本身比较复杂，且需要多次重复计算时，计算量会很大；（2）有的函数甚至没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数来近似代替，这就是数值逼近问题。问题背景问题背景第1页/共31页1 1 插值问题 /*Interpolation Problem*/（插值的定义）已知定义于区间 上的实值函数 在 个互异节点 处的函数值 ，若函数集合 中的函数 满足则称 为 在函数集合 中关于节点 的一个插值函数，并称 为被插值函数,a,b,a,b为插值区间，为插值节点，（*）式为插值条件。设外插法：内插法：用 计算被插值函数 在点 处的近似值 用 计算被插值函数 在点 处的近似值 第2页/共31页插值类型代数插值：集合 为多项式函数集x0 x1x2x3x4xg(x)f(x)几何意义：有理插值：集合 为有理分式函数集三角插值：集合 为三角函数集第3页/共31页代数插值的存在唯一性设即代入插值条件：第4页/共31页方程组的系数矩阵是Vandermonde矩阵 方程组存在唯一解，因此满足插值条件(*)(*)的不超过n次的插值多项式是唯一存在的.第5页/共31页截断误差插值余项设 在区间 a,ba,b上连续，在区间 a,ba,b上存在,是满足插值条件（*）的不超过n次的插值多项式，则对 存在 ，满足其中 。且当 在区间 a,ba,b有上界 时，有代数插值的插值余项/*Remainder*/第6页/共31页2 2 代数插值多项式的构造方法一、一、拉格朗日多项式 /*Lagrange Polynomial*/niyxPiin,.,0,)(=求 n 次多项式 使得条件：无重合节点，即n=1已知 x0,x1;y0,y1，求使得111001)(,)(yxPyxP=可见 P1(x)是过(x0,y0)和(x1,y1)两点的直线。)()(0010101xxxxyyyxP +=101xxxx 010 xxxx =y0+y1l0(x)l1(x)=10)(iiiyxl称为拉氏基函数 /*Lagrange Basis*/，满足条件 li(xj)=ij第7页/共31页与 有关，而与 无关n 1希望找到li(x)，i=0,n 使得 li(xj)=ij；然后令=niiinyxlxP0)()(，则显然有Pn(xi)=yi。li(x)每个 li(x)有 n 个根 x0 xi-1、xi+1 xn =j i jiiiixxCxl)(11)(Lagrange Polynomial节点f第8页/共31页例如例如 也是一个插值多项式，也是一个插值多项式，其中其中 可以是可以是任意任意多项式。多项式。（2）Lagrange插值多项式结构对称，形式简单.（3）误差估计注：（1）若不将多项式次数限制为 n，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，n较大时，计算量非常大,故常用于理论分析。第9页/共31页二二、牛顿插值 /*Newtons Interpolation*/Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x)都需重新算过。将 Ln(x)改写成的形式，希望每加一个节点，只附加一项上去即可。?差商(亦称均差)/*divided difference*/1阶差商/*the 1st divided difference of f w.r.t.xi and xj*/2阶差商第10页/共31页11101010111010,.,.,.,.,.,+=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商：事实上其中差商的值与 xi 的顺序无关！第11页/共31页12 n+11+(x x0)2+(x x0)(x xn 1)n+1Nn(x)Rn(x)ai=f x0,xi 3第12页/共31页注：由唯一性可知 Nn(x)Ln(x)，只是算法不同，故其余项也相同，即 实际计算过程为（建立差商表）f x0,x1f x1,x2 f xn 1,xnf x0,x1,x2 f xn 2,xn 1,xnf x0,xn xn+1 f(xn+1)f xn,xn+1 f xn 1,xn,xn+1 f x1,xn+1 f x0,xn+1f(x0)f(x1)f(x2)f(xn 1)f(xn)x0 x1x2xn 1xn第13页/共31页例3：已知函数 的函数表：xi 1 2 3 4 5yi=f(xi)1 4 7 8 6写出4次Newton插值多项式解：构造差商表第14页/共31页4 分段插值 /*piecewise Interpolation*/一、高次插值评述1 1、从插值余项角度分析 为了提高插值精度，一般来说应该增加插值节点的个数，这从插值余项的表达式也可以看出，但不能简单地这样认为，原因有三个：插值余项与节点的分布有关；余项公式成立的前提条件是 有足够阶连续导数（即函数足够光滑），但随着节点个数的增加，这个条件一般很难成立；随着节点个数的增加，可能会增大。随着节点个数增加到某个值，误差反而会增加。第15页/共31页注意下面图中曲线的变化情况！例3：在 5,5上考察 的Ln(x)。取-5-4-3-2-1 0 1 2 3 4 5-0.5 0 0.5 1 1.5 2 2.5 n 越大，端点附近误差越大，称为Runge 现象Ln(x)f(x)第16页/共31页5 三次样条插值/*Cubic Spline Interpolation*/许多实际工程技术中一般对精度要求非常高，（1）要求近似曲线在节点连续；（2）要求近似曲线在节点处导数连续，即充分光滑。分段插值不能保证节点的光滑性，而Hermite插值需要知道节点处的导数值，实际中无法确定。问题背景问题背景第17页/共31页一、三次样条函数的力学背景 在工程技术和数学应用中经常遇到这样一类数据处理问题：在平面上给定了一组有序的离散点列，要求用一条光滑曲线把这些点按次序连接起来。.压铁弹性木条.数据点形象地称之为样条曲线第18页/共31页 在力学上，通常均匀细木条可以看作弹性细梁，压铁看作是作用在梁上的集中载荷，“样条曲线”就模拟为弹性细梁在外加集中载荷作用下的弯曲变形曲线。设细梁刚度系数为 ，弯矩为 ，样条曲线的曲率为 由力学知识：当 时（即“小挠度”的情况）上述微分方程简化为：是线性函数因此，“样条曲线”可近似认为是三次多项式第19页/共31页二、三次样条函数定义及求法 设在区间 上给定一个分割，定义在 上的函数 如果满足下列条件：(1)(1)在每个小区间 内是三次多项式(2)(2)在整个 区间上，为二阶连续可导函数，即在每个节点 处则称 为三次样条函数第20页/共31页假设现在已知函数 在节点处的函数值：如果三次样条函数 满足则称 为插值于 的三次样条函数，简称三次样条插值函数。如何求 的三次样条插值函数:4n个未知数3n-1个条件第21页/共31页线性插值函数1 1、M连续方程与 的表达式记因为 在每一个子区间 上都是线性函数 两边积分两边再积分一次？第22页/共31页由其中代入插值条件：第23页/共31页写成方程组的形式：上述方程组称为 的M连续方程 n-1个方程n+1个未知数三弯矩方程第24页/共31页M、m连续方程的求解：需要补充附加条件3 3、边界条件/*boundary conditions*/已知端点的斜率：已知端点的二阶导数：设 是以 为周期的周期函数，对 附加周期性条件：即要求三次样条插值函数在端点处函数值、一阶导数值和二阶导数值相同。第25页/共31页M连续方程在各类边界条件下的求解方法 对于第一类边界条件由得第26页/共31页从而得到方程组（三对角）：可用追赶法求解第27页/共31页注：三次样条与分段 Hermite 插值的根本区别在于S(x)自身光滑，不需要知道 f 的导数值（除了在2个端点处的函数值）；而Hermite插值依赖于f 在许多插值节点的导数值。f(x)H(x)S(x)第28页/共31页第29页/共31页性质3 3（误差估计）设函数 ，是区间 的一个分割，是关于 的带有型(斜率边界)或型(二阶导数边界)边界条件的插值函数，则有误差估计其中 是分割比，并且系数 与 是最优估计。性质说明：三次样条插值函数本身连同它的一、二、三阶导数分别收敛到 及其相应导数，具有强收敛性。第30页/共31页感谢您的观看。第31页/共31页