数值分析Lagrange插值与Newton插值

《数值分析Lagrange插值与Newton插值》由会员分享，可在线阅读，更多相关《数值分析Lagrange插值与Newton插值（61页珍藏版）》请在装配图网上搜索。

1、,*,,,,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,数值分析,,,,,,,,,,数值分析,,插值与拟合的基本问题,,,,如果可以将一个实际问题用函数来描述，那么对这个函数性质以及运算规律的研究，就是对这一实际问题的某些内在规律的理性揭示。,,在工程实践和科学实验中，经常需要建立函数关系，即,y=f(x),。虽然从原则上说，它在某个区间[,a,b,]上是存在的，但通常只能观测到它的部分信息，即只能获取[,a,b,]上一系列离散点上的值，这些值构成了观测数据。这就是说，我们只知道的一张观测数据表，,,,1,,而不知道函数在其他点

2、,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

3、,),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,

4、坐标每改变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,)

5、,,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插值,,第四节

6、 带导数条件的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,

7、(,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,

8、)=,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,+

9、…+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插值。（这两种方法称为基函数法）,证毕,

10、插值误差估计,,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,

11、, 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

12、,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,(

13、,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,

14、),的,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,

15、i,)=0,,,i=,0,1,,…,n,,,现在任意固定一点,x,∈,,[,a,b,],, x≠x,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+,

16、1个零点。,如此反复，最后可推知,g,(n+1),(,t,)在[,a,b,]中有,1个零点,,，即有,g,(n+1),(,,),=0,, a<,,

17、阶导数,就有上式成立,其余项为,,令,x,1,-x,0,=b-a=h, x= x,0,+t h , 0,,t,,1 则,特别，当,n,=1时，取,x,0,=a, x,1,=b,，则有,易证，当0,,t,,1时,,|t,(1,-t,),|,的最大值为1/4,，,,23,,,,应当指出，余项表达式只有在,f,(,x,) 的高阶导数存在时才能应用。,,在 （,a，b,）内的具体位置通常不可能给出，如果我们可以求出,,,,那么插值多项式,L,n,(,x,)逼近,f,(,x,),的截断误差是,,,…(11),,,,,,24,,,例:,,已给sin0.32=0.314567, s

18、in0.34=0.333487, sin0.36=0.352274, 用线性插值及抛物插值计算 sin0.3367 的值并估计截断误差。,解：,,由题意取,x,0,=,0.32,, y,0,=,0.31456,7 , x,1,=,0.34,,,,y,1,=,0.333487,, x,2,=,0.36,, y,2,=,0.352274,, x=,0.3367,。,,用线性插值计算，取,x,0,=,0.32,,及,,x,1,=,0.34,,,又由公式得,,,25,,其截断误差得,,其中 ，因,,f(x)=sinx，f,”,(x)= -sinx，,,可取 ，于是,,,

19、,R,1,(0.3367),,=,sin 0.3367 –L,1,(0.3367),,1/2(0.3335)(0.0167)(0.0033)0.9210,–5,，,若取,x,1,=,0.34,，x,2,=,0.36,为节点，则线性插值为,,26,,其截断误差为,,,其中,,,于是,,,,R,1,,27,,用抛物插值计算,sin0.3367时，可得,这个结果与六位有效数字的正弦函数表完全一样，,,这说明查表时用二次插值精度已相当高了。,,28,,其截断误差得,,,其中,,于是,,29,,事后误差估计,,30,,,31,,例:,已知,f,(,x,),=e,x,,的数据点如下：,,,,

20、（1）用,x,1,,x,2,,x,3,构造二次Lagrange插值多项式,L,2,(,x,)，,,并计算,e,1.5,的近似值,L,2,(,1.5,) 。,,（2）用事后误差估计方法估计,L,2,(,1.5,)的误差。,,,,,,x,i,0,1,,2,3,e,xi,,1,2.7183,7.3891,20.0855,L,2,(1.5),=,4.0505,,32,,第三节 Newton插值,本节介绍Newton插值多项式，该公式是另一种具有承袭性的插值多项式，且在后续章节有重要应用。为了使Newton插值多项式具有承袭性，令,,33,,差商及其性质,,定义1,,给定一个函数表,式中,c,0,,

21、c,1,,,…,,c,n,为插值多项式系数。,,为便于表示,N,n,(,x,), 引出差商概念.,,34,,,,,,,,,,,,,,,,,,,,,,,,,,一般的,,f(x),关于,x,i,,x,i+1,,…,x,i+k,的,k,阶差商记做,,,f,[,x,i,,x,i+1,,…,x,i+k,],,,35,,例,：,,36,,,,,,,,,,,,,定理1:,差商具有如下性质,,,,(1)差商与函数值的关系为,,,37,,,,,,,,,,,,,,,,,,(2)差商与结点排列顺序无关,,38,,,由插值条件,N,n,(,x,i,),=f,(,x,i,),i=,0,1,,…,n,,导出,N,n,(,

22、x,0,),=c,0,=f,(,x,0,),,Newton,插值公式,,39,,,依次类推，得：,c,n,=f,[,x,0,,x,1,,…,x,n,],,40,,,因此，每增加一个结点，,Newton,插值多项式只增加一项，克服了 Lagrange插值的缺点。,,,41,,,,,,差商表,,42,,定理2：,Newton,插值多项式的余项为,,,R,n,(,x,),= f,(,x,),-N,n,(,x,),=f,[,x,x,0,,x,1,,…,x,n,],,n,+1,(,x,),,,其中,,n+1,,(,x,）,=,(,x-x,0,)(,x-x,1,)(,x-x,2,)…(,x-x,n,)

23、,证明：,过,n+,1,个点,x,0,,x,1,,…, x,n,,作,f,(,x,),的,n,次Newton插值多项式,N,n,(,t,),，设,x,与,x,0,,x,1,,…, x,n,,互异, 再取,n+2,个节点,x ,x,0,,x,1,,… x,n,,,构造,f,(,x,),的,n+,1,次Newton插值多项式,,,N,n+1,(,t,),=N,n,(,t,),+f,[,x,0,,x,1,,… ,x,n,,x,],w,n+1,(,t,),,(,a,),满足,N,n+1,(,x,i,),=f,(,x,i,),,(,b,),,N,n+1,(,x,),=f,(,x,),,(,c,),,4

24、3,,利用,Newton,插值余项，可证明差商的性质3）,事实上，由,Newton,插值余项与,Lagrange,插值,,余项的等价性，有,消掉 ，即得性质(3）。,,由,(,a,), (,c,)有,,,f,(,x,),=N,n,(,x)+ f,[,x,0,x,1,… x,n,,x,],w,n+1,(,x,),,R,n,(,x,),=f,(,x,),-N,n,(,x,),= f,[,x,0,x,1,…x,n,,x,],w,n+1,(,x,),证毕,,44,,例:,给定,f(x)=,ln,x,的数据表,,,x,i,,2.20 2.40 2.6

25、0 2.80 3.00,,f(x,i,),0.78846 0.87547 0.95551 1.02962 1.09861,,1.构造差商表,,2. 写出四次Newton插值多项式,N,4,(x),,解:1.,差商表,,45,,P,4,(,x,)= 0.78846,,+0.43505(,x,-2.20）,,- 0.087375(,x,-2.20)(,x,-2.40),,+0.0225(,x,-2.20)(,x,-2.40)(,x,-2.60),,-0.00755(,x,-2.20)(,x,-2.40)(,x,-2.60)(,x,-2.80),2.,,46

26、,,,下面讨论等距节点的Newton插值多项式，当节点等距时，利用差分的概念，可使Newton插值多项式得到简化。,定义2（向前差分）,设有等距节点,x,i,=x,0,+ih (i=0,1,…,n),,,,其中,h,>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,处的零阶差分。,Ne

27、wton差分插值（等距节点插值公式）,,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,

28、=,0,,⊿,n,f,(,x,i,),=,0,n,≥3,,48,,定义3 (向后差分),设节点,x,i,=x,0,+ih,(,i=0,1,…,n,),,,,其中,h>0,是步长。记,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,

29、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,+

30、ih,(,i=0,1,…,n,),,,,其中,h>0,是步长。记,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+

31、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,,差分与函

32、数值的关系,,52,,Newton,差分插值多项式,Newton向前差分公式,,设：,x,0,

33、Newton向后差分公式,将节点按由大到小的顺序排列，即,,,x,n,>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）根据等距节点

34、表，构造差分表，,,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

35、,,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,),,,

36、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,,