数值分析Lagrange插值与Newton插值

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数值分析,数值分析,插值与拟合的基本问题,如果可以将一个实际问题用函数来描述，那么对这个函数性质以及运算规律的研究，就是对这一实际问题的某些内在规律的理性揭示。,在工程实践和科学实验中，经常需要建立函数关系，即,y=f(x),。虽然从原则上说，它在某个区间,a,b,上是存在的，但通常只能观测到它的部分信息，即只能获取,a,b,上一系列离散点上的值，这些值构成了观测数据。这就是说，我们只知道的一张观测数据表，,1,而不知道函数在其他点,x,上的取值，这时只能用一,个经验函数,y=g(x),对真实函数,y=f(x),作近似。,x,i,x,1,x,2,x,n,f(x,i,),f(x,1,),f(x,2,),f(x,n,),2,已知数据表,下面两种办法常用来确定经验函数,y=g(x),（1）插值法 （2）拟合法,根据问题的不同，有时要用插值技术来解决，有时则应该采用拟合的方法才合理。,（1）插值法的基本思想,求一个经验函数,y=g(x),，使,g(,x,i,)=f(,x,i,), i=1,n.,x,i,x,1,x,2,x,n,f(x,i,),f(x,1,),f(x,2,),f(x,n,),3,插值的任务,就是由已知的观测点(,x,i,y,i,),为物理量(未知量),建立一个简单的、连续的解析模型,g(x),，以便能根据该模型推测该物理量在非观测点处的特性,。,o,x,y,y,0,x,1,x,2,x,n,y,1,y,2,y,n,x,0,y=f(x),g(x),4,机翼断面的下轮廓线如图所示，下表给出了下轮廓线上的部分数据。用程控铣床加工时，每一刀只能沿,x,方向和,y,方向走非常小的一步。例如，如果工艺要求铣床沿,x,方向每次只能移动0.1单位，这时就需要求出当,x,坐标每改变0.1单位时的,y,坐标。试完成加工所需的数据，画出曲线。,问题1：机床加工,x,i,0,3,5,7,9,11,12,13,14,15,y,i,0,1.2,1.7,2.0,2.1,2.0,1.8,1.2,1.0,1.6,5,（2）拟合法的基本思想,已知数据表,o,x,y,(,x,0,y,0,),x,1,x,2,x,n,(,x,1,y,1,),x,0,(,x,n,y,n,),(,x,2,y,2,),y=g(x),x,i,x,1,x,2,x,n,f(x,i,),f(x,1,),f(x,2,),f(x,n,),6,在水文数据的测量中，不同水深的流速是不同的。水文数据的测量是天天进行的，为了减少测量的工作量，希望确定水深和流速之间的关系。为此测量了一系列不同水深和流速值，下表给出了对某河流的测量数据,问题2：水深和流速的关系,水深,x,i,0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,流速,y,i,3.195,3.229,3.253,3.261,3.251,3.228,3.187,3.126,3.059,2.975,7,第五章 函数插值,第一节 函数插值的基本问题,第二节 Lagrange插值,第三节 Newton插值,第四节 带导数条件的Hermite插值,第五节 分段低次插值,第六节 分段三次样条插值,8,插值法,:,由实验或测量的方法得到所求函数,y=f,(,x,),在互异点,x,0, x,1, . , x,n,处的值,y,0, y,1, , y,n,构造一个简单函数,F,(,x,),作为函数,y=f,(,x,),的近似表达式,y= f,(,x,), F,(,x,),使,F,(,x,0,),=y,0, F,(,x,1,),=y,1, , F,(,x,n,),=y,n,(a),这类问题称为,插值问题,。,f,(,x,),称为,被插值函数,，,F,(,x,),称为,插值函数,，,x,0, x,1, . , x,n,称为,插值节点,。,(a),式称为,插值条件,。,第一节 函数插值的基本问题,9,插值函数的类型,10,当插值函数是代数多项式时，插值问题称为,代数插值,。,代数插值,定理1,设,x,0,x,1,x,n,是,n,+1个互异节点,函数,f,(,x,)在这组节点的值,y,k,=f,(,x,k,)(,k,=0,1,n,)是给定的，那么存在唯一的,次数,n,的,多项式,P,n,(,x,)满足,P,n,(,x,k,),= y,k, k,=0,1,n。,设,P,n,(,x,)=,a,0,+,a,1,x,+,a,n,x,n, .(1),n次代数插值问题为:,求次数,n的多项式,P,n,(x),使满足插值条件,P,n,(,x,i,),=y,i, i,= 0,1,2,，,n, ,(2),只要求出,P,n,(,x,)的系数,a,0,a,1,a,n,即可,11,由插值条件(2)知,P,n,(,x,),的系数满足下列,n+,1,个代数方程构成的线性方程组,a,0,+a,1,x,0,+ a,2,x,0,2,+ +a,n,x,0,n,=y,0,a,0,+a,1,x,1,+ a,2,x,1,2,+ +a,n,x,1,n,=y,1,.,a,0,+a,1,x,n,+ a,2,x,n,2,+ +a,n,x,n,n,=y,n,证明,a,i,(,i,=0,1,2,n,)的系数行列式是Vandermonde行列式,(3),12,由于,x,i,互异，所以(4)右端不为零，从而方程组(3)的解,a,0,a,1,a,n,存在且唯一。,但遗憾的是方程组(3)是病态方程组,阶数,n,越,高，病态越严重。为此我们从另一途径寻求获得,P,n,(,x,),的方法-Lagrange,插值和Newton插值。（这两种方法称为基函数法）,证毕,插值误差估计,13,第二节 Lagrange插值,线性插值(,n,=1),求次数1 的多项式,L,1,(,x,).,满足条件,L,1,(,x,0,),=y,0, L,1,(,x,1,),=y,1,y=f,(,x,),y=L,1,(,x,),x,0,x,1,x,y,14,15,令,L,2,(,x,),=l,0,(,x,),y,0,+ l,1,(,x,),y,1,+ l,2,(,x,),y,2,要求,l,0,(,x,),，l,1,(,x,),，l,2,(,x,)是二次多项式，且满足,l,0,(,x,0,),=,1, l,0,(,x,1,)=0, l,0,(,x,2,)=0,l,1,(,x,0,)=0, l,1,(,x,1,)=,1, l,1,(,x,2,)=0,l,2,(,x,0,)=0, l,2,(,x,1,)=0, l,2,(,x,2,)=,1,.,二次插值 (n=2),求次数2 的多项式,L,2,(,x,),使其满足条件,L,2,(,x,0,),=y,0, L,2,(,x,1,),=y,1, L,2,(,x,2,),=y,2,l,0,(,x,)含有,x-x,1, x-x,2,两个因子，令,l,0,(,x,),=,(,x-x,1,)(,x-x,2,),利用,l,0,(,x,0,),=,1 确定其中的系数,，得到：,16,类似的可以得到,l,1,(,x,), l,2,(,x,),l,0,(,x,), l,1,(,x,), l,2,(,x,),称为以,x,0, x,1, x,2,为节点的,插值基函数,。,17,令,L,n,(,x,),=l,0,(,x,),y,0,+ l,1,(,x,),y,1,+,+l,n,(,x,),y,n,求,n,次多项式,l,j,(,x,),(,j=,0,1,n,)使其满足条件,n 次插值多项式 :,求次数,n,的多项式,L,n,(,x,),使其满足,L,n,(,x,0,),=y,0, L,n,(,x,1,),=y,1, . , L,n,(,x,n,),=y,n,.(7),容易求得,l,j,(,x,)(,j=,0,1,n,)称为以,x,0, x,1,. , x,n,为节点的,Lagrange,插值基函数,。,18,公式（9）就是,n,次Lagrange插值多项式,.,特点：构造容易，L-型插值基函数理论上有意义，,但增加节点要重新计算，不适合编程计算。,实际应用：只用低次插值。,(9),19,定理2:,设,L,n,(,x,),是过点,x,0,，x,1,，x,2,，x,n,的,f,(,x,),的,n,次插值多项式，,f,(,x,),C,n+1,a,b,，其中,a，b,是包含点,x,0,，x,1,，x,2,，,x,n,的区间，则对任意给定的,x,a，b,，,总存在一点,（,a，b,）（依赖于,x,）使,Lagrange,插值的截断误差,(10),其中,罗尔定理,设,f,(,x,)在,a,b,内连续，在(,a,b,)内可导，且有,f,(,a,),=f,(,b,)；则在(,a,b,)内一定存在一点,，使得,f,(,),=,0.,20,证明,:,显然,R,n,(,x,i,),=f,(,x,i,),-L,n,(,x,i,)=0,i=,0,1,n,现在任意固定一点,x,a,b, xx,i,(,i=,0,1,n,),设,R,n,(,x,),=K,(,x,),n+1,(,x,),引进辅助函数,g,(,t,),=f,(,t,),-,L,n,(,t,),-K,(,x,),n+1,(,t,),(*),则,g,(,t,)在,a,b,上具有,n+,1阶连续导数，在,t= x,0, x,1,x,n,x,诸点处函数值皆等于零。,即g(t)在,a,b,中有n+2个零点。,由,罗尔定理,知,g,(,t,)在,a,b,中有,n+,1个零点。,如此反复，最后可推知,g,(n+1),(,t,)在,a,b,中有,1个零点,，即有,g,(n+1),(,),=0, a,0 是步长。记,f,i,=f,(,x,i,) (,i=0,1,n,),f,i,=f,i+1,-f,i,称为,f(x),在点,x,i,处的一阶向前差分。,n,f,i,=,n-1,f,i+1,-,n-1,f,i,称为,f,(,x,)在点,x,i,处的,n,阶向前差分。,规定,f,i,=,0,f,i,为,f,(,x,)在点,x,i,处的零阶差分。,Newton差分插值（等距节点插值公式）,47,例:,f,(,x,),=x,2, x,i,=i,(,i=,1,2,n,),求,n,f,(,x,i,), (,i=,1,n-,1),n,3,解:,f,(,x,i,),=f,(,x,i+1,),-f,(,x,i,),=,(,i+1,),2,-i,2,=2i+1,2,f,(,x,i,),=,f,(,x,i+1,)-,f,(,x,i,),=2,(,i+1,),+1-,(,2i+1,),=2,3,f,(,x,i,),=,2,f,(,x,i+1,),-,2,f,(,x,i,),=,2-2,=,0,n,f,(,x,i,),=,0,n,3,48,定义3 (向后差分),设节点,x,i,=x,0,+ih,(,i=0,1,n,),其中,h0,是步长。记,f,i,=f,(,x,i,) (,i=0,1,n,),f,i,=f,i,- f,i-1,称为,f,(,x,)在点,x,i,处的一阶向后差分。,n,f,i,=,n-1,f,i,-,n-1,f,i-1,称为,f,(,x,)在点,x,i,处的,n,阶向后差分。,规定,f,i,=,0,f,i,为,f,(,x,)在点,x,i,处的零阶差分。,解：,f,(,x,i,),= f,(,x,i,),- f,(,x,i-1,),=i,2,-,(,i-1,),2,=2i-1,例,f,(,x,),=x,2, x,i,=i,(,i=1,2,n,),求,n,f,(,x,i,),(,i=1,n-1,),n,3,2,f,(,x,i,),=,f,(,x,i,),-,f,(,x,i-1,),=2i-,1-,2,(,i-,1)-1=,2,3,f,(,x,i,),=,2,f,(,x,i,),-,2,f,(,x,i-1,)=2-2=0,n,f,(,x,i,)=0, n, 3,49,定义4 (中心差分),设节点,x,i,=x,0,+ih,(,i=0,1,n,),其中,h0,是步长。记,f,i+1/2,=f,(,x,i,+1/2,),(,i=,0,1,n,),f,i,=f,i+1/2,- f,i-1/2,称为,f(x),在点,x,i,处的一阶中心差分。,n,f,i,= ,n-1,f,i+1/2,- ,n-1,f,i-1/2,称为,f,(,x,),在点,x,i,处的,n,阶中心差分。,规定,f,i,= ,0,f,i,为,f,(,x,),在点,x,i,处的零阶差分。,50,解：,f,(,x,i,),= f,(,x,i+1/2,),- f,(,x,i-1/2,),=,（,i+1/2,）,2,-,(,i-1/2,),2,=2i,2,f,(,x,i,),=,f,(,x,i+1/2,),-,f,(,x,i-1/2,),=2,(,i+1/2,),-2,(,i-1/2,),=2,3,f,(,x,i,),=,2,f,(,x,i+1/2,),-,2,f,(,x,i-1/2,),=,2-2=0,n,f,(,x,i,),=,0, n, 3,例,f,(,x,),=x,2, x,i,=i,(,i=1,2,n,),求,n,f,(,x,i,),(,i=,1,n-1,),n,3,差分与差商的关系,51,差分与函数值的关系,52,Newton,差分插值多项式,Newton向前差分公式,设：,x,0,x,1,x,n-1,x,0 ,x,n-i,=x,n,-ih,Newton差商,插值多项式为：,且,x-x,n-i,=,(,s+i,),h, 代入上式，得,当,x,x,n-1, x,n,时，令,x=x,n,+sh ,-1,s,0,56,当插值点,x,靠近表尾(,x,n,)时，亦采用Newton向后,差分插值公式。,（5）式称为Newton向后差分公式,x=x,0,+sh,57,利用Newton差分插值，计算函数,f(x),在,x,*,处的,近似值分为以下步骤：,1）根据等距节点表，构造差分表，,2）根据,x,*,的位置，建立Newton差分插值多项式。,差分表,x,i,f,i, ,2,3,n,x,0,f,0,x,1,f,1,x,2,f,2,x,3,f,3,x,n-3,f,n-3,x,n-2,f,n-2,x,n-1,f,n-1,x,n,f,n,f,0,f,1,f,2,f,n-3,f,n-2,f,n-1,2,f,0,2,f,1,2,f,n-3,2,f,n-2,3,f,0,3,f,n-3,n,f,0,i,f,n,=,i,f,n-i,58,例,给出如下函数表：,解,造差分表,x,i,f(x,i,),0 1,1 2,2 17,3 64,1,15,47,14,32,18,构造三阶Newton差分插值多项式，计算,f,(,0.5,),、,f,(,1.5,) 与,f,(,2.5,)。,x,i,f(x,i,),0 1,1 2,2 17,3 64,1,15,47,14,32,18,x,i,f(x,i,),0 1,1 2,2 17,3 64,x,i,f(x,i,),0 1,1 2,2 17,3 64,x,i,f(x,i,),0 1,1 2,2 17,3 64,59,0.5靠近表头，构造前插公式：,P3(x)=1+s+7s(s-1)+3s(s-1)(s-2),这里,x=s ，f(0.5)P3(0.5)=2.875,2.5靠近表尾，构造后插公式：,P3(x)=64+47s+16s(s+1)+3s(s+1)(s+2)，,这里,x=3+s, 当,x=2.5,时,s=-0.5,f(2.5) P3(2.5)=35.375,60,习题,P195- 1, 2,6,61,