上海交大数值分析课件数值分析插值法.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章插 值 法,数,值,分,析,1,引,言,一、实际背景,二、问题的分类,三、插值问题的定义,一、实际背景,基本过程：,飞机、汽车的外形设计制造,测点,插值曲线,插值曲面,三角函数表、对数表等,不在表上的函数值如何求？,插值问题：,求一条曲线严格通过数据点,曲线拟合问题：,求一条曲线在一定意义下靠近数据点,注：插值问题和曲线拟合问题统称函数逼近问题！,二、问题的分类,三、插值问题的定义,1.插值问题的有关概念,设给出关于函数,y,=,f,(,x,)的一组函数值，,已知条件,x,x,0,x,1,x,2,x,n,y,y,0,y,1,y,2,y,n,其中,x,0,x,1,x,2,x,n,是区间a,b上的互异点,(,因为函数是这样的映射：一个x唯一的对应一个y,)，,求,一个简单函数,(,x,)作为,f,(,x,)的近似表达式，以满足,我们称这样的问题为,插值问题,，并称,(,x,)为,f,(,x,)的,插值函数,，,f,(,x,)为,被插函数，,x,0,x,1,x,2,x,n,是,插值节(基)点,是,插值原则.,条件,思考题,当数据点(,x,i,y,i,)给定后，满足插值条件的插值函数,(,x,)有多少种类型？,答,有许多种。例如给出平面上两个点，则过这两个点的曲线有无穷多种，可以是代数多项式、三角多项式、有理函数等等，但最简单而最常用的是代数多项式，它有许多良好的性质，故本章仅考虑代数,多项式插值问题,2.代数多项式插值问题,设给出关于函数,y,=,f,(,x,)的一组函数值，,x,x,0,x,1,x,2,x,n,y,y,0,y,1,y,2,y,n,其中,x,0,x,1,x,2,x,n,是区间,a,b,上的互异点(,因为函数是这样的映射：一个x唯一的对应一个y,)(,一共n+1个节点,),已知条件,求,一个次数不超过n的多项式,称,P,n,(,x,)为,f,(,x,)的,n,次插值多项式,使满足插值原则(条件),问题：,这样的插值多项式是否存在唯一呢？,定理,在,n,+1个互异节点处满足插值原则且次数不超过,n,的多项式,P,n,(,x,)存在并且唯一。,证明,设P,n,(x)为所求多项式，则,这是未知量,a,0,a,1,a,n,的线性方程组，其系数行列式是范德蒙行列式,因为,x,0,x,1,x,n,的互不相同，故系数行列式不等于0，因此方程组有唯一解，即P,n,(x)存在并唯一。,注意,从定理的证明可以看出，只要通过求解一个线性方程组得出,a,0,a,1,a,n,的值，便可以确定,P,n,(,x,)了。,然而,这样构造多项式不但计算量大，而且难以得到,P,n,(,x,)的简单公式，因此本章下面几节将介绍几种直接构造,P,n,(,x,)的方法。,注：若不将多项式次数限制为,n,，则插值多项式不唯一。,也是一个插值多项式，其中 可以是任意多项式。,例如,The mathematician S.had to move to a new place.His wife didnt trust him very much,so when they stood down on the street with all their things,she asked him to watch their ten trunks,while she got a taxi.Some minutes later she returned.Said the husband:I thought you said there were ten trunks,but Ive only counted to,nine,!,The wife said:No,theyre,TEN,!,But I have counted them:0,1,2,.,A mathematician,a physicist,and an engineer were traveling through Scotland when they saw a black sheep through the window of the train.,Aha,says the engineer,I see that Scottish sheep are black.,Hmm,says the physicist,You mean that some Scottish sheep are black.,No,says the mathematician,All we know is that there is at least one sheep in Scotland,and that at least one side of that one sheep is black!,2,拉格朗日插值,一、线性插值,三、,n,次多项式,四、插值余项,二、二次插值,一、线性插值,1.线性插值的定义,当,n,=1时的n次代数多项式插值称为,线性插值,，即：已知在互异点,x,0,x,1,处的函数值,f,(,x,0,)=,y,0,f,(,x,1,)=,y,1,，要构造线性函数,L,1,(,x,)=,a,0,+,a,1,x,，满足,L,1,(,x,i,)=,y,i,，,i,=0,1,2.线性插值的几何意义,用通过两点(,x,0,y,0,)、(,x,1,y,1,)的直线,y,=,L,1,(,x,)近似代替曲线,y,=,f,(,x,)，如下图所示。,y,=,L,1,(,x,),y,=,f,(,x,),x,1,x,0,y,0,y,1,x,y,o,3.线性插值公式的推导,根据直线的点斜式，有,把上式改写成,称按如上方法确定的,L,1,(,x,)为,拉格朗日线性插值多项式,，其特点为：是两个函数,l,0,(,x,),l,1,(,x,)的线性组合，并且,l,0,(,x,),l,1,(,x,),具有性质,(1)都是一次多项式；,(2),l,0,(,x,0,)=1,l,1,(,x,0,)=0,l,0,(,x,1,)=0,l,1,(,x,1,)=1,线性插值基函数,二、二次插值,1.二次插值的定义,设给出关于函数,y,=,f,(,x,)在三个互异点处的函数值，,x,x,0,x,1,x,2,y,y,0,y,1,y,2,求,一个次数不超过二次的多项式.,求 一个次数不超过二次的多项式.,will have to be re-calculated.,定义 函数f(x)用n次插值多项式Ln(x)近似代替时，截断误差记为,（1）来看n+1(x)对Rn(x)的影响,（2）若被插函数f(x)是k次多项式，,如果用三次插值，就选,The mathematician S.,也是一个插值多项式，其中 可以是任意多项式。,y0 y1 y2 yn,在本题中二次插值时：包含11.,思考1 设f(x)=x2，求f(x)的次数不超过1、2、3、的插值多项式各是什么？在哪些点处会有误差？,点，故 在a,b内至少有n+1个零点。,（2）若被插函数f(x)是k次多项式，,将 K(x)代入余项表达式即可得到结论。,称Pn(x)为 f(x)的n次插值多项式,Rn=0,因为：为0.,His wife didnt trust him very much,so when they stood down on the street with all their things,she asked him to watch their ten trunks,while she got a taxi.,(1)根此定理可计算插值多项式的余项(误差)。,这就是,二次插值问题,满足,2.二次插值的几何意义,用经过三点(,x,0,y,0,),(,x,1,y,1,),(,x,2,y,2,)的抛物线,y,=,L,2,(,x,)近似代替曲线,y,=,f,(,x,)，如下图所示。,x,y,o,y=f(x),y=L,1,(x),x,2,x,0,y,0,y,2,y,1,x,1,3.二次插值公式的推导,仿照线性插值多项式的构造特点，先对每个基点,x,i,构造一个二次函数,l,i,(,x,),(,i,=0,1,2),使满足,先构造,l,0,(,x,)。,l,0,(,x,)满足,则,l,0,(,x,)可设为如下形式,又因为,，即,解得,即,同理可得,称这三个函数为,二次插值基函数,再令,显然它是次数不超过2次的多项式，且满足,即为所求的二次插值多项式,三、n次插值,1.n次插值的定义,设给出关于函数,y,=,f,(,x,)在,n,+1个互异点处的函数值,x,x,0,x,1,x,2,x,n,y,y,0,y,1,y,2,y,n,求,一个次数不超过,n,次的多项式,L,n,(,x,)插值这,n,+1个点。,2.n次插值的一般形式,其中,是,n,次插值基函数,思考1,设,f,(,x,)=,x,2,，求,f,(,x,)的次数不超过1、2、3、的插值多项式各是什么？在哪些点处会有误差？,思考2,设,f,(,x,)=sin,x,，求,f,(,x,)的次数不超过1、2、3、的插值多项式各是什么？在哪些点处会有误差？,思考1答案：,当,f,(,x,)是次数不超过n的多项式时，其n次的插值多项式就是,f,(,x,)本身。此时误差为0！,f,(,x,)的次数不超过1时存在误差：只在插值点处没有误差。,思考2答案：,当,f,(,x,)是非多项式时，其任何的插值多项式除插值点外均有误差！Sinx的幂展开为无限多次项。,四、插值余项,定义,函数,f,(,x,)用n次插值多项式,L,n,(,x,)近似代替时，截断误差记为,称,R,n,(,x,)为n次插值多项式,L,n,(,x,)的,余项,L,n,(x)中的n指的是Ln(x)为n次多项式，而R,n,(x)中的想指的是它是与L,n,(x)相对应的余项，R,n,(x)不一定是x的n次多项式。,当,f,(,x,)足够光滑时，有如下估计定理：,定理,设函数,f,(,x,)在包含节点,x,0,x,1,x,n,的区间,a,b,上连续，在(,a,b,)上具有,n,+1阶导数，,L,n,(,x,)为满足插值条件的,n,次插值多项式，则对任一点,x,a,b,，总存在相应的点(,a,b,)，使,其中,注意,(1),根此定理可计算插值多项式的余项(误差)。,(2),定理中的下标意义不同,L,n,(,x,)和,n+1,(,x,)的下标表示次数，而,R,n,(,x,)的下标则不表示次数。,(3),复习罗尔定理,罗尔定理如果函数满足：,（1）如果在闭区间a,b上连续；,（2）在开区间（a,b）上可导；,（3）在区间断点处函数值相等，即：f(a)=f(b),那么在(a,b)上至少存在,一点(a6-4.8),例2,给定函数,y,=ln,x,在两点的值如表,x,10,11,y,2.303,2.398,试用线性插值求ln10.5的近似值，并估计截断误差。,解,记,f,(,x,)=ln,x,，取,x,0,=10，,x,1,=11，,x,=10.5，有,因为,故,插值余项为,所以,例3,设,求证,（其中：表示f(x)在(a,b)上,直到二阶导数连续。）,证：,以 为节点进行线性插值，得,因,，故,根据插值余项定理，有,故,例4,已知函数,y,=ln,x,的函数表如下：,x,10 11 12,y,2.3062 2.3979 2.4849,x,13 14,y,2.5649 2.6391,分别用拉格朗日线性插值和二次插值求ln11.5的近似值，并估计余项。,解,线性插值。,取两个基点,插值基函数为,故线性拉格朗日插值函数为,其插值余项为,因为,而 在11与12之间，故,于是,二次插值。,取三个基点,插值多项式为,所以,估计误差为,高次插值通常优于低次插值,但绝对不是次数越高就越好，嘿嘿,注意：,在本题中二次插值时：包含11.5的个区间10，11，12和11，12，13的长度相等，即11.5-10=13-11.5，此时区间的选择原则是：,（1）取函数值变化小的区间，误差小。本题中：,f(12)-f(10)f(13)-f(11),（2）若两个区间的函数变化值相差不大，则分别计算两个区间上的，再取均值。,When you start writing the program,you will find how easy it is to calculate,the Lagrange polynomial.,Oh yeah?What if I find the current interpolation not accurate enough?,Then you might want to take,more interpolating points into account.,Right.Then all,the Lagrange basis,l,i,(,x,),will have to be re-calculated.,Excellent point!,We will come to discuss this problem,next time.,作业：,习题 1，2，3，4，5,