计算机数值方法第三章 插值法及最小二乘法.ppt

1、第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法延安大学数学与计算机科学学院*)()(xxxxxExEr)(*yEr*2*2*2*1*1*1rrxfyxxfyx第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法本章要点本章要点:插值问题与插值法插值问题与插值法拉格朗日插值法拉格朗日插值法牛顿插值法牛顿插值法埃尔米特插值埃尔米特插值三次样条插值法三次样条插值法最小二乘法最小二乘法第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法第第3章章 插值法插值法 1 插值问题插值问题2 拉格朗日插值拉格朗日插值3

2、分段低次插值法分段低次插值法4 牛顿均差插值多项式牛顿均差插值多项式5 埃尔米特插值埃尔米特插值6 三次样条插值三次样条插值7 数据拟合的最小二乘法数据拟合的最小二乘法第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法1 插值问题插值问题当精确函数当精确函数 y = f(x) 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函，由此构造一个简单易算的近似函数数 P(x) f(x)，满足，满足条件条件P(xi) = f(xi) (i = 0,

3、n)。这样的问题称为。这样的问题称为插值问题插值问题。第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法称为插值节点点, 2 , 1 , 0,nixi称为插值区间区间,ba其插值函数的图象如下图这里的这里的 P P( (x x) ) 称为称为f f( (x x) ) 的的插值函数插值函数。最常用的插值函数是最常用的插值函数是 ?多项式！多项式！第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法x0 x1x2x3x4xP(x) f(x)()(xPxf和插值函数对于被插函数处的函数值必然相等在节点ix)()(xfxP的值可能就会偏离但在节

4、点外必然存在着误差近似代替因此)()(xfxP第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法线性插值与二次插值线性插值与二次插值 第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法问题问题 求作一次式一次式 ，使满足条件 从几何图形上看， 表示过两点 的直线。)(1xL1111)(,)(kkkkyxLyxL)(1xLy k 1k 1(,)(,y)kkxyx与一、线性插值一、线性插值第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法过两点的直线 ，可表示为如下点斜式：)()(Lkk1kk1kk1xxxx

5、yyyx)(1xLy )()()11kk1xlyxly(xLkk也可表示为如下对称的两点式：第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法其中，k1k1)(xxxxxlkk11kkkkxxxx(x)l显然，;)(x,l)(xl;)(xl,)(xlkkkkkkkk01011111称称1kkl (x)l(x)，为为线性插值基函数线性插值基函数第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法例例1: 已知 ， ，求 代入点斜式插值多项式 得 y=10.71428 精确值为 10.723805， 故这个结果有3位有效数字。10100 1

6、1121 115y )()(0010101xxxxyyyxL第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 问题问题 求作二次式二次式 ，使满足条件 二次插值的几何解释是用通过三个点 的抛物线来近似考察曲线，故又称为拋物插值拋物插值。)(2xL) 1, 1()(2kkkjyxLjj二、二次插值二、二次插值第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法类似于线性插值，构造基函数，要求满足下式：)()()()11kk112xlyxlyxly(xLkkkk第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方

7、法称称11kkkl(x)l (x)l(x)，为为二次插值基函数二次插值基函数第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法代数多项式插值的存在唯一性代数多项式插值的存在唯一性 线性插值和二次插值都属于代数多项式插值。对于一般的代数插值问题代数插值问题,就是寻求一个不高于n次的代数多项式 Pn(x)=a0+a1x+a2x2+anxn (31) 使其在给定的n+1个互异的插值结点插值结点上满足插值条件插值条件 Pn(xi)=yi （i=0,1,n） (32)第三章第三章 插值法与最小二

8、乘法插值法与最小二乘法 计算机数值方法计算机数值方法 这样的多项式是否存在并且唯一呢? 根据插值条件,代数多项式(31)中的各个系数a0,a1,an应满足下列n+1阶线性方程组2001020002101121112012()()()nnnnnnnnnnnnnnP xaa xa xa xyP xaa xa xa xyP xaa xa xa xy(33)第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法线性方程组的系数行列式为范德蒙特行列式范德蒙特行列式200020111121(,)11nnnnnnnxxxV x xxxxxxxx由于插值结点 xi (i=0,1,n)

9、互异,故 V(x0,x1,xn)0 因此,方程组(33)有唯一的一组解a0,a1,an,于是Pn(x)存在且唯一。第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法代数多项式的余项代数多项式的余项 代数多项式Pn(x)仅为已知函数f(x)的一种近似表达式,用它来代替f(x)进行计算总会带来误差误差。 一般说来,对插值区间a,b上插值结点xi(i=0,1,2,n)以外的点 , Pn(x)f(x)。 若令 Rn(x)=f(x)-Pn(x) 则 f(x)=Pn(x)+Rn(x) 称Rn(x)为插值多项式Pn(x)的余项余项。显然有 Rn(xi)=0 , i=0,1,2,

10、n第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 则对插值区间上的任何x,都存在(a,b),使得(1)11010( ) ( )( )(1)!( )()()()()nnnnnniifRxxnxxxxxxxxx其中， 下面给出插值多项式Pn(x)余项的表达式。 定理定理 设函数f(x)在区间a,b上具有n+1阶导数， Pn(x)为次数不高于n的多项式, 且 Pn(xi)=yi （i=0,1,n） 第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 (2)若f(x)为次数不超过n的多项式,那么以n+1个点为基点的插值多项式就一定是其本身

11、,即Pn(x)f(x)。这是因为此时 Rn(x)=0。 (3)从余项Rn(x)中的(n+1)(x)知,当点x位于x0,x1,xn的中部时,|n+1(x)|比较小,精度要高一些,而位于两端时,精度要差一些;若x位于x0,x1,xn的外部,一般称为外插(或外推),此时精度一般不理想,使用时必须注意。 几点说明几点说明: (1)插值多项式本身只与插值基点及f(x)在这些基点上的函数值有关,而与函数f(x)并没有关系。但余项Rn(x)却与f(x)联系很紧。第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法n所有不超过 次的多项式构成是n+1维的线性空间1n其基底也由个多项

12、式组成，且不唯一n又任意一个 次多项式，均可由基底线性表示且在不同的基底下有不同的形式01( ),( ),( )nxxx设为一组基底线性无关显然)(,),(),(10 xxxn2 拉格朗日插值多项式拉格朗日插值多项式 第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法01( )( ),( ),( )nnP xxxx且多项式可由线性表示)()()()(1100 xaxaxaxPnnn的插值函数为某个函数如果)()(xfxPn01( ),( ),( )nxxx则称为插值基函数 ( )( )0,1,2,niiiP xyf xin且为插值节点其中nixi,2 , 1 ,

13、0,第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法012 , naxxxxba b为区间上的一组节点( ),0,1,2,jnlxjn作一组 次多项式如下)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxl0()0,1,2,()niijiijxxjnxx （）)()(10nxxxxxx)(1xn令)(1jnx则)()()(1110njjjjjjjxxxxxxxxxxn+1次多项次多项式式第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()()()()()()(11101

14、110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnj,2 , 1 ,0)(ijxljiji01nji,2 , 1 ,0,线性无关显然)(,),(),(),(210 xlxlxlxln)()(11jjnnxxxx第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法012( ), ( ), ( ), ( )nlx l x lxlx插用作值基函数则的插值多项式为而,)()(xfxPn)()()()(1100 xlaxlaxlaxPnnn为待定参数、其中naaa10)(inxPniyxfii,2 , 1 ,0)(令即njijjxla0)(niyi,

15、2 , 1 ,0可得niyaii,2 , 1 ,0第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法( )(0,1, ),( ) (0,1, )( )ijnyf xxinlxinL x在节点以为插值基函数的插值多项式为)()()()(1100 xlyxlyxlyxLnnn)(xljnjiiijixxxx0)()(其中( )( )nL xyf xLagrange称为的插值多项式( ) (0,1, )jlxinnLagrange为 次插值基函数)()(11jjnnxxxx第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法11,kkkkyy

16、xx函数值节点Lagrange线性插值基函数为)(xlk11kkkxxxx)(1xlkkkkxxxx1Lagrange线性插值多项式为)()()(111xlyxlyxLkkkk11kkkkxxxxykkkkxxxxy11第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法例例1:15)225(,13)169(,12)144()(fffxf满足已知.)175(,)(的近似值并求插值多项式的二次作fLagrangexf解解:225,169,144210 xxx设15,13,12210yyy第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)

17、(0 xl插值基函数为的二次则Lagrangexf)()()(201021xxxxxxxx2025)225)(169(xx)(1xl)()(210120 xxxxxxxx1400)225)(144(xx)(2xl)()(120210 xxxxxxxx4536)169)(144(xx第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法插值多项式为的二次因此Lagrangexf)()()()()(2211002xlyxlyxlyxL且)175(f)175(2L)175(15)175(13)175(12210lll73158230.13第三章第三章 插值法与最小二乘法插值

18、法与最小二乘法 计算机数值方法计算机数值方法例例2.).175(1fLagrange中的线性插值多项式求例用之间与在由于插值点22516917521xxx解解:为插值节点与因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函数为第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法Lagrange线性插值多项式为)()()(22111xlyxlyxL5622513x5616915x)175(f5622517513561691751571285214.13所以第三章第三章 插值法与最小二乘法插值法与最

19、小二乘法 计算机数值方法计算机数值方法拉格朗日插值多项式的缺点：拉格朗日插值多项式的缺点：（1）插值基函数计算复杂（2）高次插值的精度不一定高（3）插值基函数的计算没有继承性拉格朗日插值多项式的优点：拉格朗日插值多项式的优点：（1）插值基函数形式对称（2）低次插值的计算简单（4）高次插值的稳定性不好第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 3 分段低次插值法分段低次插值法一、分段线性Lagrange插值,ix设插值节点为niyi, 1 , 0,函数值为,11kkkkxxxx形成一个插值区间任取两个相邻的节点构造Lagrange线性插值1,2 , 1 ,0

20、,1nixxhiiiiihhmax1. 分段线性插值的构造第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()()(11)(1xlyxlyxLkkkkk11kkkkxxxxykkkkxxxxy111, 1 , 0nk)(1xLnnnxxxxLxxxxLxxxxL1)1(121)1(110)0(1)()()(显然)(1ixLniyi, 1 , 0,-(1)-(2)我们称由(1)(2)式构成的插值多项式 为分段线性Lagrange插值多项式)(1xL第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法为插值点设*xx 1*kkxxx若*

21、)(*1xLy 则*)()(1xLk11*kkkkxxxxykkkkxxxxy11*0*xx 若*)(*1xLy 取*)()0(1xL1010*xxxxy0101*xxxxynxx *若*)(*1xLy 取*)()1(1xLnnnnnxxxxy11*11*nnnnxxxxy第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法的图象分段线性插值)(1xLy 的一条折线实际上是连接点niyxkk, 1 , 0,),(也称折线插值,如下图，曲线的光滑性较差， 在节点处有尖点 但如果增加节点，减小步长,会改善插值效果)(lim10 xLh)(xf上连续在若,)(baxf因此

22、则第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计

23、算机数值方法)()!1()(1)1(xnfnnn次Lagrange插值多项式的余项为)()()(xPxfxRnn1( )L x因此分段线性插值的余项为)()()(11xLxfxR)()()(1xLxfk)(2)(1 kkxxxxf有关与且xxxxkk,1|)(|1xR|)(|max|)(|max211 kkkbxabxaxxxxxf224121hM 2281hM2. 分段线性插值的误差估计第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法二、分段二次Lagrange插值,ix设插值节点为niyi, 1 , 0,函数值为为插值区间以任取三个相邻节点,1111kkkk

24、kxxxxx构造Lagrange二次插值)()()()(1111)(2xlyxlyxlyxLkkkkkkk1,2 , 1nk1,2 , 1 ,0,1nixxhiiiiihhmax1. 分段二次插值的构造第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()(11111kkkkkkkxxxxxxxxy1,2 , 1nk)()(2xLk)()(1111kkkkkkkxxxxxxxxy)()(11111kkkkkkkxxxxxxxxy上式称为分段二次Lagrange插值,*,*1kkxxxx且为插值点若显然,插值区间,211kkkkxxxx和*x都包含*)(*)(2x

25、Lyk那么*)(*)1(2xLyk还是第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法一般则更接近且若,*,*1kkkxxxxx*)(*)(2xLyk则更接近且若,*,*11kkkxxxxx*)(*)1(2xLyk1,2 , 1nk则含若),*(*01xxxx1,2 , 1nk*)(*)1(2xLy 则含若),*(*1nnxxxx*)(*)1(2xLyn时使用的方法是外插和nxxxx*0第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法*x*x*x*x*x*x0 x1x2kx1kxkx1kx1nxnx*x*)()1(2xL)1(2k

26、L)(2kL)1(2kL*)()1(2xLn第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()!1()(1)1(xnfnn)()()(xPxfxRnn的余项为那么分段二次插值)(2xL)()()(22xLxfxR)()()(2xLxfk)()(6)(11 kkkxxxxxxf有关与且xxxxkk,11|)(|2xR| )()( |max| )(|max611111 kkkkxxxbxaxxxxxxxfkk3393261hM 33273hM2. 分段二次插值的误差估计由于第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法分段低次L

27、agrange插值的特点计算较容易可以解决Runge现象但插值多项式分段插值曲线在节点处会出现尖点插值多项式在节点处不可导第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法因为任何一个n次多项式都可以表示成, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,共n+1个多项式的线性组合是否可以将这n+1个多项式作为插值基函数呢？4 牛顿均差插值多项式牛顿均差插值多项式 由于拉格朗日插值多项式li(x)依赖于全部结点,所以不具有继承性。为了克服这个缺点, 引进牛顿均差插值多项式。第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机

28、数值方法, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,线性无关， 因此，可以作为插值基函数,ix设插值节点为nifi, 1 , 0,函数值为1,2 , 1 ,0,1nixxhiiiiihhmaxnifxPii, 1 , 0,)(插值条件为第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法nifxPxPii, 1 , 0,)()(应满足插值条件000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()()()(110102010nnxxxxxxaxxxxaxxaaxP具有如下形式设插值多项式)(xP第三章第

29、三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法再继续下去待定系数的形式将更复杂为此引入差商和差分的概念)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法定义定义1.( )(0,1, )iif xxf in在互异节点的函数值为称)(,jixxffxxfjijiji)(,)(均差一阶差商关于节点为jixxxf)(,kjixxxxfxxfxxxfjkjikikji的二阶差商关于为kjixxxxf,)(一、差商一、差商(均差均差)第三章第三章 插

30、值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法,110kkiiiixxxxf阶差商的关于节点为kxxxxxfkkiiii,)(110,110kkxxxxf显然kkkkkiiiiiiiiixxxxxxfxxxf1210110,kkkkkxxxxxxfxxxf1210110,依此类推第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法差商的主要性质：差商的主要性质：01101( ),(1,(),(),(),)kkkf xkf xxxxf xf xf x的 阶差商可由函数值的线性组合表示 且,110kkxxxxfkikiiiiiiixxxxxxxxxf0

31、110)()()()(第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法(2) 对称性,即任意调换节点的次序,差商的值不变,210 xxxf,120 xxxf,012xxxf如)01( )(3,),kkfxxxx（当在包含节点的区间存在时使得之间必存在一点在,10kxxx,10kxxxf!)()(kfk)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四阶差商三阶差商二阶差商一阶差商差商表差商表,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xx

32、xxf,410 xxxf规定函数值规定函数值为零阶差商为零阶差商第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()()()()(110102010nnnxxxxxxaxxxxaxxaaxNnkkjjkxxxxxff110100)(,称( )inNewtoxnf x次均差为关于节点的插值多项式定义定义3.nkkkxxxxff1100)(,二、二、Newton均差插值多项式均差插值多项式10)(kjjxx为k次多项式)(xk第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()()(xNxfxRnn)()!1()(1)1(xnfn

33、n由插值多项式的唯一性,Newton基本插值公式的余项为因此可得( )( )( )nnf xNxR x)(,110 xxxxxfnn)(xRk)(,1110 xxxxfkknk 一般误差估计式误差估计式第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法即是等距节点如果节点,10nxxxnabhnkkhxxk, 1 ,0,0)(xNnnkkkxxxxff1100)(,则Newton均差插值公式可以得到简化，为此引入差分的概念三、三、Newton前差和后差插值多项式前差和后差插值多项式第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法定义

34、定义2.0( )(0,1, ) ,kkf xxxkhfkn 设在等距节点处的函数值为称kkkfff1处的一阶向前差分在为kxxf)(1, 1 , 0nk1kkkfff处的一阶向后差分在为kxxf)(nk,2 , 1一、差分一、差分第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法kkkfff12处的二阶向前差分在为kxxf)(12kkkfff处的二阶向后差分在为kxxf)(kmkmkmfff111阶向前差分处的在为mxxfk)(阶向后差分处的在为mxxfk)(依此类推111kmkmkmfff第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数

35、值方法可以证明mkmkmff1kkff222kkff333kkff如kkkfff1kkkfff11kkkfff121222kkkfff4433221100fxfxfxfxfxfxkk四阶差分三阶差分二阶差分一阶差分0f1f2f3f02f12f22f03f13f04f差分表差分表4f3f2f1f42f32f22f43f33f44f第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法在等距节点的前提下,差商与差分有如下关系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hffii2222hfiiiiixxff112211,iiiii

36、ixxxxfxxf第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法,321iiiixxxxf312223hffii33! 3 hfi332121,iiiiiiiixxxxxfxxxf3322223hffii333! 3 hfi第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法,1miiixxxf依此类推mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法即是等距节点如果节点,10nxxxnabhnkkhxxk, 1 ,0,0,10k

37、xxxfkkhkf!0由差商与向前差分的关系设thxx0二、二、Newton向前差分插值多项式向前差分插值多项式10)(kjjxx)(xk1000)(kjjhxthx10)(kjhjt第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法kkhkf!0nkf10)(10kjhjt!0kfknkf10 )(10kjjt)(xNnnkkkxxxxff1100)(,)(0thxNn则均差插值公式化为)(0thxNn称为Newton向前插值公式向前插值公式第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)(0thxRn)!1()()1(nfnn

38、jnjth01)(插值余项插值余项为)(xRn)()!1()(1)1(xnfnn其余项)(0thxRn)!1()()1(nfnnjnjth01)(化为第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法!kfnknknf1 )(10kjjt)(thxNnn)(thxRnn)!1()()1(nfnnjnjth01)(插值余项插值余项为根据向前差分和向后差分的关系mkmkmff如果假设thxxn)0( t可得Newton向后插值公式向后插值公式三、三、Newton向后差分插值多项式向后差分插值多项式第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机

39、数值方法例例 已知数据表x 1 2 3 5 6F(x) 0 2 6 20 90 试求牛顿均差插值多项式。解：解：作均差表如下：第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 例例2 分别作出 f(x)=x2+x+1 在区间1，4的前差、后差表，其中h=1。 解：解：前差表、后差表如下： 30624211)5)(3)(2)(1()3)(2)(1( 0)2)(1()1( 20)(2344xxxxxxxxxxxxxxxP前前 差差 表表后后 差差 表表第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 例例3 给出正弦函数sinx由x=

40、0.4到0.7的值(h=0.1),试分别 用牛顿前差和后差公式计算sin0.57891的近似值。 解解 作差分表：-第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 利用牛顿前差公式54711.0)00083.0(!3)27891.1)(17891.1(7891.1)00480.0(!2)17891.1(7891.109001.07891.138942.057891.0sin7891.11.04.057891.00hxxt第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 利用牛顿后差公式 0.578910.71.21090.1si

41、n0.578910.64422( 1.2109)0.07958( 1.2109)( 1.21091)( 0.00563)2!( 1.2109)( 1.21091)( 1.21092)3!( 0.00083)0.54711nxxth 第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法 5 Hermite插值法插值法,)(1010nnyyybxxxaxf处的函数值为在节点设值函数上的具有一阶导数的插,在区间)(为)(设baxfxP处必须满足在节点显然nxxxxP,)(10iiiyxfxP)()(iiiyxfxP)()()(,)()1(一阶光滑度上具有一阶导数在若要求b

42、axPni, 1 ,0ni, 1 ,0-(1)第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法处必须满足在节点显然nxxxxP,)(10iiiyxfxP)()(iiiyxfxP)()()(,)(,)2(阶光滑度阶导数上具有在若要求同样mmbaxP个待定的系数可以解出22 n次的多项式可以是最高次数为因此12)(nxP次多项式作为插值函数两个节点就可以用3112iiiyxfxP )()()()()()()(miimimyxfxPni, 1 ,0-(2)个方程共22 n第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法定义1. 称满足(

43、1)或(2)式的插值问题为Hermite插值，称满足(1)或(2)式的插值多项式P(x)为Hermite插值多项式，记为Hk(x) , k为多项式次数；,( )(),kHermiteHxkRungek一般插值多项式的次数 如果太高，会影响收敛性和稳定性现象 因此 不宜太大 常用分段插值第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法一、两点三次Hermite插值先考虑只有两个节点的插值问题1010,)(yyxxxf处的函数值为在节点设1010,yyxx处的的一阶导数值为在节点作为插值函数多项式次两个节点最高可以用)(33xHHermite第三章第三章 插值法与最

44、小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法应满足插值条件)(3xH003)(yxH113)(yxH003)(yxH113)(yxH3( )Hx如前，可以用四个插值基函数表示3 ,2 , 1 ,0),()(3ixhxHi的插值基函数为设)()()()()(332211003xhaxhaxhaxhaxH希望插值系数与Lagrange插值一样简单重新假设)()()()()(110011003xyxyxyxyxH第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法其中1)(00 x0)(00 x1)(00 x)()()()()(110011003xyxyxyx

45、yxH0)(10 x0)(01x1)(11x0)(10 x0)(01x0)(11x0)(00 x0)(10 x0)(01 x0)(11 x0)(10 x0)(01 x1)(11 x可知即可假设的二重零点是,)(01xx)()()(210baxxxx1)(00 x0)(00 x由第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法可得310)(2xxa3100210)(2)(1xxxxxb)()()(210baxxxx21)(xx 310)(2xxx3100210)(2)(1xxxxx21021)()(xxxx102xxx10021xxx01021xxxx2101xx

46、xx)()(21(201xlxlLagrange插值基函数第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)(1x)()(21(210 xlxl类似可得)(0 x)()(200 xlxx)(1x)()(211xlxx10121xxxx2010 xxxx0 xx 2101xxxx2010 xxxx1xx )(0 x01021xxxx2101xxxx)()(21(201xlxl即将以上结果代入第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()()()()(110011003xyxyxyxyxH得两个节点的三次Hermite插值公式

47、)()()()()(110011003xyxyxyxyxH)()(21(2101xlxly)()(2000 xlxxy)()(2111xlxxy)()(21(2010 xlxly101121xxxxy2010 xxxx00 xxy2101xxxx2010 xxxx11xxy010021xxxxy2101xxxx第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法二、两点三次Hermite插值的余项两点三次Hermite插值的误差为)()()(33xHxfxR0)()()(33iiixHxfxR0)()()(33iiixHxfxR1 , 0i因此可设的二重零点均为,)

48、(,310 xRxx21203)()()(xxxxxKxR待定其中)(xK第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法21203)()()()()(xtxtxKtHtft构造辅助函数0)()()()()(21203xxxxxKxHxfxiiiii1 , 0i0)()()()()(21203xxxxxKxHxfx均是二重根个零点至少有因此5)(t使用4次Rolle定理，可得：,10 xx至少存在一点使得0)()4(第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法0)(! 4)()()4()4(xKf即! 4)()()4(fxK所

49、以,两点三次Hermite插值的余项为2120)4(3)()(! 4)()(xxxxfxR10 xx上述余项公式成立上存在且连续时在当,)(10)4(xxxf第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法例例1.1)2(,0)1(21)(3)2(,2)1(21)(ffxfffxf处的导数值为，在节点处的函数值为，在节点已知( )1.5,1.7.f xx 求的两点三次插值多项式及在处的近似值解解:2, 110 xx3,210yy1,010yy)()()()()(110011003xyxyxyxyxH101121xxxxy2010 xxxx00 xxy2101xx

50、xx2010 xxxx11xxy010021xxxxy2101xxxx第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)2(213x21x21x2 x)1(212x22x)(3xH91713323xxx)5 . 1(f)5 . 1(3H625. 2)7 . 1(f)7 . 1(3H931. 2 作为多项式插值，三次已是较高的次数，次数再作为多项式插值，三次已是较高的次数，次数再高就有可能不稳定，因此，对有高就有可能不稳定，因此，对有n+1个节点个节点的插值问题，的插值问题，我们可以使用分段两点三次我们可以使用分段两点三次Hermite插值插值第三章第三章 插值法

51、与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法三、分段两点三次Hermite插值niyxbaxfii, 1 , 0,)(上的函数值为上的节点在设函数niyxii, 1 ,0,上的导数值为在节点1, 1 ,0,1nkxxkk对任意两个相邻的节点可构造两点三次Hermite插值多项式)()()()()()(11)(0)(11)(0)(3xyxyxyxyxHkkkkkkkkk,1kkxxx1, 1 ,0nk插值基函数为Hermitexxxxkkkk)(),(),(),()(1)(0)(1)(0第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)()(0 x

52、k)()(1xk)()(0 xk)()(1xk1121kkkxxxx21kkkxxxxkxx 211kkkxxxx21kkkxxxx1kxxkkkxxxx121211kkkxxxx其中第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法我们称1, 1 ,0,)()()(33nkxHxHk为分段三次Hermite插值多项式，其余项为)()(! 4)(max)(max)(212)4(10)(3103kknkknkxxxxfxRxR212104)()(max! 4kknkxxxxM212104)()(max! 4kknkxxxxM)(3xR即第三章第三章 插值法与最小二乘

53、法插值法与最小二乘法 计算机数值方法计算机数值方法 6 三次样条插值三次样条插值样条:是 指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具样条本质上是一段一段的三次多项式拼合而成的曲线在拼接处, 函数连续,且一阶和二阶导数也是连续的将样条引入数学,即所谓的样条函数第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法一、三次样条插值函数定义1. 的一个分割为区间,10babxxxan:,)(上满足条件在区间如果函数baxS,)(,)(),(),()1(2baCxSbaxSxSxS 即上连续都在区间上都是三次多项式在每个小区间,)()2(1kkxxxS

54、上的三次样条函数为区间则称,)(baxS第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法处的函数值为在节点如果函数nxxxxf,)()3(10njyxfjj, 1 , 0,)(满足而三次样条函数)(xSnjyxSjj, 1 , 0,)(上的三次样条插值函数在为则称,)()(baxfxS-(1)第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法二、三次样条插值多项式处的函数值为在节点如果函数nxxxxf,)(10njyxfjj, 1 , 0,)(的一个分割为区间,10babxxxan则其必满足的三次样条插值函数是如果,)()(xfxS

55、-(2)(),0,.,jjS xyj n 1, 1,)()(limnjmxSxSjjxxj1, 1),()(lim njxSxSjxxj1, 1,)()(limnjyxSxSjjxxj第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法条件个共要满足上述四组)24()(nxS( ) , ,S xa b在上必然是分段函数 即,)(,)(,)(11211100nnnxxxxSxxxxSxxxxS)(xS-(3)第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法满足三次样条插值多项式两点上的是,)(,)(1kkkxxxS1,2,1nk个条件共

56、24nnj,1 ,0jjkyxS)()(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk -(4)第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法个待定的系数应有式上的三次样条插值多项是4,)(1kkkxxxS个待定的系数必须确定即要确定nxS4)(少两个条件并且我们不能只对插值函数在中间节点的状态进行限制也要对插值多项式在两端点的状态加以要求第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法也就是所谓的边界条件:第一类(一阶)边界条件:00)(f

57、xSnnfxS)(第二类(二阶)边界条件00)(fxS 第三类(周期)边界条件)(lim)(lim)(1)(00 xSxSpnxxpxxn2 ,1p-(5)-(6)-(7)加上任何一类边界条件(至少两个)后一般使用第一、二类边界条件, 常用第二类边界条件nnfxS )(第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法个好也是个待定的系数的条件正必须确定确定nnxS44)(即1,2 , 1nknj, 1 , 01,2 , 1nk1,2 , 1nk-(8)kmjjkyxS)()(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk

58、)(lim)(lim1xSxSkxxkxxkk 00)(fxSnnfxS)(00)(fxS 或nn)(fxS njmxSjj, 1 ,0,)(设)(,)(1xSxxxfkkk上的三次插值多项式在小区间逐个求插值多项式上的两点三次表示为将HermitexxxSkkk,)(1)(xSk)()()()()()(11)(0)(11)(0)(3xmxmxyxyxHkkkkkkkkk11121kkkkxxxxy21kkkxxxxkkxxm211kkkxxxx21kkkxxxx11kkxxmkkkkxxxxy121211kkkxxxx-(9)第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法

59、计算机数值方法kkkkkkyxxhxxhxS213)()(2)(1231)()(2kkkkkyxxhxxhkkkkmxxhxx212)()(1221)()(kkkkmxxhxx加以整理后可得并整理后得求二阶导数对,)(xSk)()2(6)(131kkkkkkyyhxxxxS kkkkmhxxx21426121246kkkkmhxxx-(10)-(11)1, 1 ,01nkxxhkkk，令第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nk由条件)(limxSkxxk )(612kkkyyhkkmh41

60、2kkmh)(lim1xSkxxk )(6121kkkyyh112kkmhkkmh14由于以上两式相等,得11111)11(21kkkkkkkmhmhhmh)(321121kkkkkkhyyhyy1, 1nk个未知量1,个方程1共nn第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算机数值方法计算机数值方法得并加以整理除上式的两边用,111kkhh112kkkkkmmmkg1kkkkhhh11kkkkhhh)(3111kkkkkkkkkhyyhyyg1, 1nk-(12)1, 1nk个未知量1,个方程1共nn(12)式称为基本方程组第三章第三章 插值法与最小二乘法插值法与最小二乘法 计算