第2章--插值法.ppt

第二章插值法,2020/5/4,1,现代数值分析（三大模块）,数值逼近：插值法、函数逼近、数值积分与数值微分数值代数：线性方程组、非线性方程的数值解法微分方程数值解：常微分方程数值解、偏微分方程数值解,2020/5/4,第2章插值法,2,第2章插值法/*Chapter2Interpolation*/,2.1引言,2.2Lagrange插值,2.3差商与Newton插值,2.4带导数条件的Hermite插值,2.5*分段低次插值,2.6*三次样条插值,2020/5/4,第2章插值法,3,在工程实践和科学实验中，经常需要建立函数关系，即y=f(x)。虽然从原则上说，它在某个区间a,b上是存在的，但通常只能观测到它的部分信息，即只能获取a,b上一系列离散点上的值，这些值构成了观测数据。这就是说，我们只知道一张观测数据表，,解决方法,用一个经验函数y=g(x)对真实函数y=f(x)作近似。,确定经验函数y=g(x)的方法,（1）插值法（2）拟合法,2020/5/4,第2章插值法,4,已知数据表,（1）插值法的基本思想,求一个经验函数y=g(x)，使g(xi)=f(xi),i=1,n.,（2）拟合法的基本思想,求一个经验函数y=g(x)，使,通过已知样点,不要求近似函数通过已知样点,2020/5/4,第2章插值法,5,2.1引言,2.1.1插值法的提出背景,插值法就是一种最简单的重要方法,实际问题中经常要涉及到函数值的计算问题：（1）如果函数表达式本身比较复杂，且需要多次重复计算时，计算量会很大；（2）有的函数甚至没有表达式，只是一种表格函数，而我们需要的函数值不在该表格中。对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数来近似代替，这就是数值逼近问题。,2020/5/4,第2章插值法,6,设函数f(x)在区间a,b上有定义，且已知在点ax0x1xnb处的函数值y0=f(x0),y1=f(x1),yn=f(xn)，若存在一简单的函数P(x)，满足条件P(xi)=f(xi)(i=0,1,n)，就称P(x)称为f(x)的插值函数。,插值法定义,点x0,x1,xn称为插值节点，区间a,b称为插值区间，求插值函数P(x)的方法称为插值法。,几何意义：,P(x)f(x),2020/5/4,第2章插值法,7,常用,插值函数的类型,代数插值：多项式插值,有理插值：有理分式函数,三角插值：三角多项式,2.1.2多项式插值/*PolynomialInterpolation*/,（1.3）,设在区间上给定个点,上的函数值,求次数不超过的多项式，使,多项式插值问题,2020/5/4,第2章插值法,8,由插值条件得关于系数的元线性方程组,（1.4）,问题：P(x)是否存在？若存在，是否唯一？如何求？,系数矩阵为,（1.5）,2020/5/4,第2章插值法,9,称为范德蒙德（Vandermonde）矩阵,由互异，故,因此线性方程组（1.4）的解存在且唯一.,结论,定理1设x0,x1,xn是n+1个互异节点,函数f(x)在这组节点的值yk=f(xk)(k=0,1,n)是给定的，那么存在唯一的次数n的多项式P(x)满足P(xk)=yk,k=0,1,n。,P(x),但遗憾的是方程组(1.4)阶数n越高，计算量越大。能不能不通过解方程组直接得到插值多项式呢？,2020/5/4,第2章插值法,10,Interpolationpolynomial,ps.神威-太湖之光(10亿亿)、天河二号(5亿亿),2020/5/4,第2章插值法,11,2.2拉格朗日多项式,n=1,P1(x)是过(x0,y0)和(x1,y1)两点的直线。,2.1.1线性插值与抛物插值,两点式,点斜式,线性插值,2020/5/4,第2章插值法,12,二次插值,n=2,方程组求解麻烦,抛物插值,思路：对于线性插值的两种形式解进行适当的分析,从中寻求规律得到拉格朗日插值(公式)和牛顿插值(公式).,我们先来看看如何得到二次拉格朗日插值公式.,两点式,点斜式,2020/5/4,第2章插值法,13,首先,线性插值的两点式可看作是两个特殊的一次式的一种线性组合.,对称式,的一次插值多项式,称l0(x)和l1(x)为以x0,x1为节点的基本插值多项式，也称为线性插值的插值基函数。,基函数的线性组合,基函数法,满足li(xj)=ij,显然有l0(x)+l1(x)1.,其中，l0(x)和l1(x)满足：,l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1,L1(x),L1(xj),=yj,2020/5/4,第2章插值法,14,启发:,其中，l0(x),l1(x),l2(x)都是二次多项式，且应满足,满足(2.1)的li(x)是否存在?若存在，具有什么形式呢?,（2.1）,二次Lagrange插值多项式为L(x)=y0l0(x)+y1l1(x)+y2l2(x),二次插值是否能由一些二次插值基函数来线性组合？,先考虑l0(x)。,l0(x)0(xx1)(xx2),其中0是待定系数。,2020/5/4,第2章插值法,15,同理,l1(x)1(xx0)(xx2),l2(x)2(xx0)(xx1),此即二次拉格朗日插值公式,其中,l0(x),l1(x),l2(x)是满足(2.1)的特殊(基本)二次插值多项式;称为二次插值基函数.,l0(x)0(xx1)(xx2),由l0(x0)=1，所以0(x0x1)(x0x2)1，则,L2(xj),=yj,2020/5/4,第2章插值法,16,n1,LagrangePolynomial,与有关，而与无关,节点,f,2.2.2拉格朗日插值多项式,展开,n次插值多项式:求次数n的多项式Ln(x),使其满足Ln(x0)=y0,Ln(x1)=y1,.,Ln(xn)=yn,令Ln(x)=l0(x)y0+l1(x)y1+ln(x)yn,2020/5/4,第2章插值法,17,其中,满足条件,（2.9）,易求得,（2.10）,记,（2.11）,2020/5/4,第2章插值法,18,例1已知，求的近似值.,解：,这是一个线性插值问题,插值多项式为,L1(x)=l0(x)y0+l1(x)y1,基函数分别为,注2：若不将多项式次数限制为n，则插值多项式不唯一。,2020/5/4,第2章插值法,19,注1:次插值多项式通常是次数为的多项式，特殊情况下次数可能小于.,例如也是一个插值多项式，其中可以是任意多项式。,练习求经过A(0,1)，B(1,2)，C(2,3)三个点的二次Lagrange插值多项式.,解：,插值条件,注2：若不将多项式次数限制为n，则插值多项式不唯一。,注1:次插值多项式通常是次数为的多项式，特殊情况下次数可能小于.,例如也是一个插值多项式，其中可以是任意多项式。,2020/5/4,第2章插值法,20,2.2.3插值余项(Remainder),罗尔定理设f(x)在a,b内连续，在(a,b)内可导，且有f(a)=f(b)；则在(a,b)内一定存在一点，使得。,显然Rn(xi)=f(xi)-Ln(xi)=0,i=0,1,n,设Rn(x)=K(x)n+1(x),现在任意固定一点xa,b,xxi(i=0,1,n),引进辅助函数g(t)=f(t)-Ln(t)-K(x)n+1(t),则g(t)在(a,b)上具有n+1阶导数，在t=x0,x1,xn,x诸点处函数值皆等于零。,即g(t)在a,b中有n+2个零点。,由罗尔定理知g(t)在a,b中有n+1个零点。,2020/5/4,第2章插值法,21,如此反复，最后可推知g(n+1)(t)在a,b中有1个零点，即有g(n+1)()=0,a三次多项式),多项式的曲线通过,故,可由条件确定,通过计算,余项,可设,其中为待定函数.,2020/5/4,第2章插值法,43,构造,a,b上有四个零点x，x0，x1，x2；其中x1为二重零点.利用Rolly定理，知g(t)在x0，x1，x2，x组成的三个小区间内至少各有一个零点，记为1,2,3，加上x1，在a,b上至少有4个零点.,反复应用罗尔定理，得在内至少有一个零点，,故有,(4.5),余项表达式为,2020/5/4,第2章插值法,44,例8给定求在上的三次埃尔米特插值多项式，使它满足并写出余项表达式.,求出函数值,构造均差表,解,待定系数，令,2020/5/4,第2章插值法,45,可得,故,余项,由条件，可得,2020/5/4,第2章插值法,46,Newton形式的Hermite插值,2020/5/4,第2章插值法,47,(4.7),基函数法,插值节点取为及，插值多项式为，插值条件为,其中是关于节点及的三次埃尔米特插值基函数，分别满足,(4.6),完全导数,两点三次埃尔米特插值,插值多项式,2020/5/4,第2章插值法,48,令,显然,再利用,及,解得,于是求得,同理可得,(4.8),(4.9),该是什么样的呢？,2020/5/4,第2章插值法,49,为求，由给定条件可令,直接由，得到,(4.10),(4.11),同理,2020/5/4,第2章插值法,50,最后代入，得,(4.12),(4.13),余项，,2020/5