1、1iiijjijiilxlbx11nnnnnnaaaaaaaaaA212222111211bAx 第三章第三章 插值法和最小二乘法插值法和最小二乘法 3.1 插值法插值法 3.2 插值多项式中的误差插值多项式中的误差 3.3 分段插值法分段插值法 3.4 Newton插值插值 3.5 Hermite插值插值 3.6 三次样条三次样条 插值插值 3.7 数据拟合数据拟合2本章要点要点用简单的函数(如多项式函数)作为一个复杂函数的近似,最简单实用的方法就是插值,而数据拟合则是另外一类的函数近似问题.本章主要介绍有关插值法的一些基本概念,及多项式插值的基础理论和几个常用的插值方法:Lagrange插
2、值、分段线性插值、Newton插值、Hermite插值和三次样条插值在本章的最后介绍了拟合的最小二乘法P122.2.5.10.11.16.19,20,25.27.本章作业3 为了计算函数值或分析函数的性态为了计算函数值或分析函数的性态,必须首先产必须首先产生函数可计算的近似式生函数可计算的近似式.函数的插值与数据拟合的函数的插值与数据拟合的最小二乘法就是研究如何用简单函数为各种离散数最小二乘法就是研究如何用简单函数为各种离散数据建立连续模型据建立连续模型,为各种非有理函数提供好的逼近为各种非有理函数提供好的逼近,使它们既能达到精度要求使它们既能达到精度要求,又使计算量尽可能小又使计算量尽可能小
3、.插插值与数据拟合是数值计算的最基本的内容值与数据拟合是数值计算的最基本的内容,这方面这方面的研究无论是对实际应用还是对数值计算领域本身的研究无论是对实际应用还是对数值计算领域本身都是极为重要的都是极为重要的.请看下面的问题请看下面的问题:4给出概率积分202xxyedx的一个函数表格:012340.450.460.470.480.490.4755 0.4847 0.4937 0.5027 0.5117iixiy有什么简便的方法,可求出当x=0.463的概率积分值的近似值?5 3.1 插值法插值法bxxxxan210nixfyii,2,1,0),(上的函数值一、插值问题一、插值问题对于函数()
4、yf x,其函数形式很复杂或根本没有解析的表达式,假定可以通过实验或测量,获得()yf x在区间,a b上1n个不同点 能否找到一个性能优良、便于计算的函数()P x满足:6niyxPii,2,1,0)()().P xf x并且用近似代替-(1)这就是插值问题,(1)式为插值条件,的插值函数为函数称函数)()(xfxP称为插值节点点,2,1,0,nixi称为插值区间区间,ba个等分点上若给定如函数5,0,sinxy 其插值函数的图象如图700.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.2
5、0.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy)()(xPxf和插值函数对于被插函数处的函数值必然相等在节点ix)()(xfxP的值可能就会偏离但在节点外必然存在着误差近似代替因此)()(xfxP8二、插值多项式的存在唯一性二、插值多项式的存在唯一性插值函数类插值函数类:多项式,分段多项式,有理函数,样条函数,三角多项式.求插值多项式的方法称为多项式插值
6、多项式插值.上的代数插值多项式为在区间设函数,)(baxfy nnnxaxaxaaxP2210)(且满足niyxPiin,2,1,0)(-(2)-(3)则称之为插值多项式为多项式函数如果,)(xP9满足线性方程组的系数即多项式nnaaaaxP,)(21000202010yxaxaxaann11212110yxaxaxaannnnnnnnyxaxaxaa2210-(4)上述方程组的系数行列式为n+1阶Vandermond行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx 010定理1.由Cramer法则,线性方程组(4)有唯一解nnnxaxaxaa
7、xP2210)(niyxPiin,2,1,0)(-(2)-(3),(jixxji若插值节点则满足插值条件的插值多项式存在且唯一.虽然线性方程组(4)推出的插值多项式存在且唯一但通过解线性方程组(4)求插值多项式却不是好方法11三、Lagrange插值多项式)()()()(1100 xlyxlyxlyxPnnn设:,2,1,0),(满足只要nixlj;,2,1,0),()1(的多项式是次数不超过nnixlj.,2,1,0,0,1)()2(njijijixlij-(5)12)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnjiiiji
8、xxxx0)()(nj,2,1,0-(6)()(10nxxxxxx)(1xn令)(1jnx则)()()(1110njjjjjjjxxxxxxxxxxn+1次多项式由待定系数法可求得:)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnj,2,1,0-(6).)(,),(),(),(210线性无关显然xlxlxlxln(请同学们思考)()(11jjnnxxxx从而14为记为次插值多项式的上在节点于是)(),1,0()(,xLnnixxfyni)()()()(1100 xlyxlyxlyxLnnn)(xljnjiiijixxxx0)()
9、(其中-(6)-(7)插值多项式的为式称LagrangexfyxLn)()()7(插值基函数次为称Lagrangennixlj),1,0()()()(11jjnnxxxx15例例1:15)225(,13)169(,12)144()(fffxf满足已知.)175(,)(的近似值并求插值多项式的二次作fLagrangexf解解:225,169,144210 xxx设)(0 xl插值基函数为的二次则Lagrangexf)()()(201021xxxxxxxx2025)225)(169(xx)(1xl)()(210120 xxxxxxxx1400)225)(144(xx)(2xl)()(120210
10、xxxxxxxx4536)169)(144(xx15,13,12210yyy16插值多项式为的二次因此Lagrangexf)()()()()(2211002xlyxlyxlyxL且)175(f)175(2L)175(15)175(13)175(12210lll73158230.13在例1中,如果只给出两个节点169和225,也可以作插值多项式,即1次Lagrange插值多项式,有两个插值基函数,这种插值方法称为Lagrange线性插值,也可以在n+1个节点中取相邻的两个节点作线性插值1711,kkkkyyxx函数值节点Lagrange线性插值基函数为)(xlk11kkkxxxx)(1xlkkk
11、kxxxx1Lagrange线性插值多项式为)()()(111xlyxlyxLkkkk11kkkkxxxxykkkkxxxxy1118例例2.).175(1fLagrange中的线性插值多项式求例用之间与在由于插值点22516917521xxx解解:为插值节点与因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函数为插值基函数为Lagrange线性插值多项式为线性插值多项式为)()()(22111xlyxlyxL5622513x5616915x19)175(f5622517513561691751571285214.13所以
12、20Lagrange 插插值值算算法法:1.输入数据),.,2,1(,niyxii、及插值点 u 2.yy=0 3.for i=1,2,3,n do 3.1 t:=1 3.2 for j=1,2,3,n 3.3 如果ji 则*jijuxttxx 3.4:*iyyyyty 4.输出 yy u21 3.2 插值多项式中的误差插值多项式中的误差一、插值余项插值的从上节可知Lagrangexfy)(,njjjnxlyxL0)()(满足nixfxLiin,1,0)()(,bax但)()(xfxLn不会完全成立因此,插值多项式存在着截断误差,那么我们怎样估计这个截断误差呢？22)()(,xPxfban的插
13、值多项式为上假设在区间)()()(xPxfxRnn令上显然在插值节点为),1,0(nixi)()()(iniinxPxfxRni,1,0,0个零点上至少有在因此1,)(nbaxRn)()()(1xxKxRnn设)()()(101nnxxxxxxx为待定函数)(xK其中)()()()()(1xxKxPxfxRnnn23)()()()(1xxKxPxfnn0)()()()()(1txKtPtftnn若引入辅助函数)(x则有0的区分与注意xt)(ix且)()()(1ininxxKxR0即个零点上至少有在区间若令因此,2,)(,nbatxxi,0)(xni,1,0nixi,2,1,0,0)(也可微则可
14、微因此若为多项式和由于)(,)(,)()(1txfxxPnn)()()()()(11xtRtxRtnn也可令)()()()(1xxKxPxfnn)()()()(1ininixxKxPxf24根据Rolle定理,个零点上有至少在区间1),()(nbat再由Rolle定理,个零点上有至少在区间nbat),()(依此类推阶导数为零的使得内至少有一个点在区间1)(,),(ntba0)()1(n)()1(tn)()()()()(1txKtPtftnn)()()()()1(1)1()1(txKtPtfnnnnn由于)()()()()()1(1)1()1()1(nnnnnnxKPf因此)!1()()()1(
15、nxKfn025)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfnn所以)()()(截断误差的余项为插值多项式称xPxRnn定理1.有则插值节点为次插值多项式上的在为阶可微上在区间设,)()(,1,)(0baxbaxnbaxfxPnbaxfniin)(xRn)()!1()(1)1(xnfnn,)()(01niinxxx其中.,),(xba且依赖于Lagrange型余项26|)(|max)1(1xfMnbxan|)(|)(|011niinnxxxN设|)(|xRn则)()!1()(1)1(xnfnn11)!1(1nnNMn27例1:225,169,144
16、,)(,.1三个节点为若中在上节例xxf线性插值的余项为设LagrangexR)(1插值的余项为二次LagrangexR)(2解:.)175(截断误差近似值的线性和二次插值做试估计用fLagrangexxf21)(2341)(xxf2583)(xxf|)(|max2251692xfMx|)169(|f 41014.1|)(|max2251443xfMx|)144(|f 61051.128|)175(|)175(22N|)225175)(169175(|300|)175(|)175(33N|)225175)(169175)(144175(|9300|)175(|1R22!21NM3001014.
17、121421.71 10|)175(|2R33!31NM93001051.161632.34 10误差更小二次插值比线性插值的用时在求从以上分析可知Lagrange175,29Lagrange插值多项式的缺点：插值基函数计算复杂高次插值的精度不一定高如果增一个节点,所有基函数必须重新计算30例2.5,5,11)(2xxxf设函数ninhihxnni,1,0,10,515,5个节点等份取将插值多项式次的作试就Lagrangenxfn)(10,8,6,4,2并作图比较.解:211)(iiixxfy插值多项式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10,8,6
18、,4,2n31-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次数的Lagrange插值多项式的比较图Runge现象32结果表明,并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象.3.63|5Runge,()|3.6,lim max|()()|.nnnxnL xxf xL x 还进一步证明了,在节点等距的条件下,当时只在内收敛 除此范围外以,有
