计算方法-2-插值法

1、2022-3-31第二章 插值法2022-3-32第二章 插值法 2.1 引言引言 2.2 拉格朗日插值拉格朗日插值 2.3 均差与牛顿插值公式均差与牛顿插值公式 2.4 差分与等距节点插值差分与等距节点插值 2.5 埃尔米特插值埃尔米特插值 2.6 分段低次插值分段低次插值 2.7 三次样条插值三次样条插值2022-3-33本章要点用简单的函数(如多项式函数)作为一个复杂函数的近似,最简单实用的方法就是插值.本章主要介绍有关插值法的一些基本概念，及多项式插值的基础理论和几个常用的插值方法：拉格朗日插值、分段线性插值、牛顿插值、埃尔米特插值和三次样条插值.2022-3-34 2.1 引言引言且

2、不利于在计算机上其函数形式可能很复杂对函数,),(xf个不同的点上的一组在区间可以获得量假如可以通过实验或测运算1,)(,nbaxfbxxxxan210nixfyii,2 , 1 , 0),(上的函数值能否存在一个性能优良、便于计算的函数满足比如多项式函数),(xP一、插值问题2022-3-35niyxPii,2 , 1 ,0)()()(xfxP近似代替并且用这就是插值问题，上式为插值条件的插值函数为函数称函数)()(xfxP则称之为插值多项式为多项式函数如果,)(xP称为插值节点点, 2 , 1 , 0,nixi称为插值区间区间,ba个等分点上若给定如函数5,0,sinxy 其插值函数的图象

3、如下图2022-3-3600.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的 插 值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的值可能就会偏离但在节点外必然存在着误差近似代

4、替因此)()(xfxP2022-3-37二、插值法的类型上的代数插值多项式为在区间设函数,)(baxfy nnnxaxaxaaxP2210)(且满足niyxPiin,2 , 1 ,0)(其中 为实数，就称P(x)为插值多项式，相应的插值法称为多项式插值；若P(x)为分段的多项式，就称为分段插值；若P(x)为三角多项式，就称为三角插值。ia本章只讨论多项式插值与分段插值2022-3-38 2.2 拉格朗日插值拉格朗日插值 此插值问题可表述为如下： 问题问题 求作次数 多项式 ，使满足条件 这就是所谓的拉格朗日（拉格朗日（Lagrange）插值）插值。n ), 1 , 0( ,niyxLiin)(

5、xLn 拉格朗日（Lagrange）插值公式(以下统称为Lagrange插值公式)的基本思想是，把pn(x)的构造问题转化为n+1个插值基函数li(x)(i=0,1,n)的构造。2022-3-392022-3-310问题问题 已知函数y=f(x)在点x0,x1上的值为y0,y1，求 作一次一次式 ，使满足条件 其几何意义，就是通过两点 的一条直线。 2.2.1 线性插值与抛物插值线性插值与抛物插值111001)(,)(yxLyxL),(),(1100yxByxA一、线性插值一、线性插值点斜式点斜式)(1xL2022-3-311L12022-3-312由直线两点式可知，通过A，B的直线方程为 称

6、为线性插值(n=1的情况)，分为内插与外推。)()(1001010 xLxxxxyyyy适用情况：适用情况：|01xx 很小时2022-3-313)()()11001xlyxly(xL也可表示为如下对称形式：其中，0101)(xxxxxl1010 xxxx(x)l显然，;)(xl,)(xl;)(xl,)(xl010101111000为线性插值基函数及函数1 0(x)l(x)l2022-3-314 线性插值的局限性线性插值的局限性2022-3-315线性插值举例线性插值举例例1: 已知 ， ，求代入点斜式插值多项式得 y=10.71428精确值为 10.723805，故这个结果有3位有效数字。1

7、0100 11121 115y)()(0010101xxxxyyyxL2022-3-316 问题问题 求作二次二次式 ，使满足条件二次插值的几何解释是用通过三个点 的抛物线来近似考察曲线，故称为拋物插值。类似于线性插值，构造基函数，要求满足下式：)(2xL二、抛物插值二、抛物插值) 1, 1()(2kkkjyxLjj)()()()11kk112xlyxlyxly(xLkkkk2022-3-3172022-3-318x0=100, x1=121, x2=144f(x0)=10, f(x1)=11, f(x2)=12 (121100)(121144)L2(115) =(100121)(100144

8、)(115121)(115144)* 10+(115100)(115144)* 11+(144100)(144121)(115100)(115121)* 12= 10.7228抛物插值抛物插值举例2(x0 x1)(x0 x2)(xx1)(xx2)f(x0) +(x1x0)(x1x2)(xx0)(xx2)f(x1)+(x2x0)(x2x1)(xx0)(xx1)f(x2)L L2 2(x)=(x)=和用线性插值相比，有效数字增加一位2022-3-319为了构造 ，我们先定义n次插值基函数。)(xLn2.2.2 拉格朗日n次插值多项式定义：若n次多项式),1 , 0()(nixli在n+1个节点nx

9、xx10上满足条件。次插 值插值基上的为节点)(,),(),(次多 项多个1就称 这1010n,x,xxxlxlxlnnnn2022-3-320)()()()()()()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxlnkiiikixxxx0)()(), 2 , 1 , 0(nk)()(10nxxxxxx(x)n 1令)(xkn 1则)()()(1110nkkkkkkkxxxxxxxxxxn+1次多项式对n=1及n=2时的情况前面已经讨论，用类似的推导方法，可得到n次插值基函数为：2022-3-321)()()()()()()(11101110nkkkkk

10、kknkkkxxxxxxxxxxxxxxxxxxxxxl), 2 , 1 , 0(nk且)(xLnnkknknkxxxxy011)()()()()()(11knknxxxx从而2022-3-322为记为项式为插值基函数的插值多以上在节点于是)(), 1 , 0()(,), 1 , 0()(,xLnixlnixxfyniiininijjjijnnnyxxxxxlyxlyxlyxL001100)()()()()()(总总结结称)(xLn为y=f(x)的拉格朗日插值多项式称), 1 , 0)(nixli为n次拉格朗日插值基函数2022-3-323例3：求过点(2，0) (4，3) (6，5) (8，

11、4) (10，1)的 拉格朗日插值多项式。2022-3-3242022-3-3252022-3-3262022-3-327拉格朗日插值多项式的缺点：（1）插值基函数计算复杂（2）高次插值的精度不一定高2022-3-328 2.2.3 插值余项与误差估计插值余项与误差估计一、插值余项插值的从上节可知Lagrangexfy)(,niiinxlyxL0)()(满足nixfxLiin, 1 , 0)()(,bax但)()(xfxLn不会完全成立因此，插值多项式存在着截断误差,那么我们怎样估计这个截断误差呢？2022-3-329)(xLn)(xRn)()!1()(1)1(xnfnn,)()(01niin

12、xxx其中.,),(xba且依赖于2022-3-330)()()(xLxfxRnn令上显然在插值节点为), 1 , 0(nixi)()()(iniinxLxfxRni, 1 , 0,0个零点上至少有在因此1,)(nbaxRn)()()(1xxKxRnn设)()()(101nnxxxxxxx为待定函数)(xK其中)()()()()(1xxKxLxfxRnnn证明：证明：假设在区间a,b上f(x)的插值多项式为)(xLn2022-3-331)()()()(1xxKxLxfnn0)(x则有0的区分与注意xt)(ix且)()()(1ininxxKxR0即个零点上至少有在区间若令因此,2,)(,nbat

13、xxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)()()()()(1xxKxLxfnn)()()()(1ininixxKxLxf)()()()()(1txKtLtftnn若引入辅助函数2022-3-332根据罗尔定理,个零点上有至少在区间1),()(nbat再由罗尔定理,个零点上有至少在区间nbat),()( 依此类推阶导数为零的使得内至少有一个点在区间1)(,),(ntba0)()1(n)()1(tn)()()()()1(1)1()1(txKtLtfnnnnn由于2022-3-333)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xn

14、fnn所以)()()(截断误差的余项为插值多项式称xLxRnn)()()()()()1(1)1()1()1(nnnnnnxKLf因此)!1()()()1(nxKfn02022-3-334|)(|xRn则)()!1()(1)1(xnfnn)()!1(11xnMnn注意（1）余项表达式只有在f(x)的高阶导数存在时 才能应用。（2）在ba,内的具体位置通常不可能给出，所以，设)() 1(1maxxfMnbxan2022-3-335例1:225,169,144,)(,. 1三个节点为若中在上节例xxf线性插值的余项为设LagrangexR)(1插值的余项为二次LagrangexR)(2解:.)175

15、(截断误差近似值的线性和二次插值做试估计用fLagrangexxf21)(2341)( xxf2583)( xxf|)(|max2251692xfMx |)169(| f 41014. 1|)(|max2251443xfMx |)144(| f 61051. 12022-3-336| )175(|2|)225175)(169175(|300| )175(|3|)225175)(169175)(144175(|9300| )175(|1R)175(! 2122M3001014. 121421071. 1| )175(|2R)175(! 3133M93001051. 161631035. 2202

16、2-3-337例2.5 , 5,11)(2xxxf设函数ninhihxnni, 1 ,0,10,515 , 5个节点等份取将插值多项式次的作试就Lagrangenxfn)(10, 8 , 6 , 4 ,2并作图比较.解:211)(iiixxfy插值多项式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10, 8 , 6 , 4 ,2n2022-3-338-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-

17、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)不同次数的拉格朗日插值多项式的比较图Runge现象2022-3-339结果表明,并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象. P44 1、2本章作业1、给定正弦函数表如下，试用拉格朗日二次插值，求sin0.57891的近似值并估计误差。0.5

18、0.60.70.479340.564640.644222、已知函数表x1.131.151.171.20y=f(x)1.1911.3951.5931.790应用拉格朗日插值公式计算f(1.16)2022-3-341 2.3 均差与牛顿插值公式均差与牛顿插值公式2022-3-342 2.3.1 均差及其性质均差及其性质)(xljnjiiijixxxx0)()(nj,2 , 1 ,0我们知道,拉格朗日插值多项式的插值基函数为形式上太复杂,计算量很大,并且重复计算也很多由线性代数的知识可知,任何一个n次多项式都可以表示成, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,共n+1个多

19、项式的线性组合2022-3-343)()()()()(110102010nnnxxxxxxaxxxxaxxaaxP具有如下形式设插值多项式)(xP2022-3-344000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa2022-3-345一、差商(均差)定义2.nifxxfii, 1 ,0,)(处的函数值为在互异的节点设称)0()()(,000kxxxfxfxxfkkk)(,)(0差商一阶均差关于节点为kxxxf2022-3-346二、均差具有如下性质：2022

20、-3-347,110kkxxxxfkjkjjjjjjjxxxxxxxxxf0110)()()()(2022-3-3482022-3-349)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四阶均差三阶均差二阶均差一阶均差三、均差的计算方法(表格法):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf规定函数值为零阶均差均差表2022-3-3502.3.2 牛顿插值公式2022-3-3512022-3-352)(xRn)()!1()()()(1)1(x

21、nfxNxfnnn)(,110 xxxxxfnn我们称 为牛顿(Newton)均差插值多项式。)(xNn称)(xRn 为牛顿均差插值多项式的截断误差。2022-3-3532022-3-3542022-3-355显然：2022-3-356例1：2022-3-357解：2022-3-3582022-3-359四、拉格朗日插值与牛顿插值的比较2022-3-360P59 13、14本章作业2022-3-361 2.4 差分与等距节点插值差分与等距节点插值2022-3-362一、差分定义3.称处的函数值为在等距节点设, 1 , 0,)(0nkfkhxxxfkkkkkfff1处的一阶向前差分在为kxxf)

22、(1, 1 ,0nk1kkkfff处的一阶向后差分在为kxxf)(nk,2 , 1 2.4.1 差分及其性质差分及其性质2022-3-363kmkmkmfff111阶向前差分处的在为mxxfk)(阶向后差分处的在为mxxfk)(依此类推111kmkmkmfff可以证明mkmkmff1kkff222kkff333kkff如kkkfff12处的二阶向前差分在为kxxf)(12kkkfff处的二阶向后差分在为kxxf)(2022-3-3644433221100fxfxfxfxfxfxkk四阶差分三阶差分二阶差分一阶差分0f1f2f3f02f12f22f03f13f04f差分表4f3f2f1f42f3

23、2f22f43f33f44f2022-3-365二、在等距节点的前提下,差商与差分有如下关系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hffii2222hfi,321iiiixxxxf312223hffii33! 3 hfiiiiixxff112211,iiiiiixxxxfxxf332121,iiiiiiiixxxxxfxxxf2022-3-3663322223hffii333! 3 hfi,1miiixxxf依此类推mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!2022-3-367 2.4.2 等距节点插值公式等距节点

24、插值公式一、牛顿前插公式2022-3-3682022-3-369二、牛顿向后(差分)插值公式2022-3-3702022-3-371 牛顿插值法的优点是计算较简单,尤其是增加节点时,计算只要增加一项,这是拉格朗日插值无法比的. 但是牛顿插值仍然没有改变拉格朗日插值的插值曲线在节点处有尖点，不光滑，插值多项式在节点处不可导等缺点.三、牛顿插值公式与拉格朗日插值相比2022-3-372 2.5 埃尔米特插值法埃尔米特插值法2022-3-373 2.5 埃尔米特插值法埃尔米特插值法2022-3-3742022-3-3752022-3-3762022-3-3772022-3-3782022-3-379

25、2022-3-3802022-3-3812022-3-3822022-3-3832022-3-3842022-3-3852022-3-3862022-3-387解：解：1 )2022-3-3882022-3-3892022-3-3902022-3-3912022-3-3922022-3-3932022-3-3942022-3-3952022-3-3962022-3-397P60 15、16本章作业2022-3-398 2.6 分段插值法分段插值法2022-3-399例2.5 , 5,11)(2xxxf设函数ninhihxnni, 1 ,0,10,515 , 5个节点等份取将插值多项式次的作试就

26、Lagrangenxfn)(10, 8 , 6 , 4 ,2解:211)(iiixxfy插值多项式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10, 8 , 6 , 4 ,2n 2.6.1 高次插值的病态性质高次插值的病态性质2022-3-3100-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

27、.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)不同次数的拉格朗日插值多项式的比较图Runge现象2022-3-3101结果表明,并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象. 2022-3-3102 2.6.2 分段线性插值分段线性插值一、 分段线性插值的构造202

28、2-3-3103-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的图象分段线性插值)(1xLy 的一条折线10,实际上是连接点,n, ,i),y(xii也称折线插值,如右图曲线的光滑性较差，在节点处

29、有尖点。但如果增加节点的数量。减小步长,会改善插值效果)()(lim10 xfxLh上连续在若,)(baxf因此则2022-3-31042022-3-31052022-3-3106)()(max1xIxfhxxxkk| )( |max2121kkxxxxxxxMkk228)()(maxhMxIxfhbxa分段线性插值的误差估计可利用插值余项得到或二、 分段线性插值的误差估计其中)(max2xfMbxa 2022-3-3107 2.6.3 分段三次埃尔米特插值分段三次埃尔米特插值2022-3-31082022-3-31092022-3-31102022-3-31112022-3-31122022

30、-3-31132022-3-31142022-3-3115)(1xI2022-3-3116P59 18、19本章作业2022-3-3117 2.7 三次样条插值三次样条插值2022-3-3118 2.7 三次样条插值三次样条插值什么是样条:是指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具.样条本质上是一段一段的三次多项式拼合而成的曲线在拼接处,不仅函数是连续的,且一阶和二阶导数也是连续的1946年,Schoenberg将样条引入数学,即所谓的样条函数2022-3-3119 2.7.1 三次样条插值三次样条插值2022-3-31202022-3-31212022-3-3122

31、2022-3-3123 2.7.2 样条插值函数的建立样条插值函数的建立三对角方程组三对角方程组2022-3-3124jjjjjjhxxMhxxMxs 11)(), 1 , 0()(njMxSjj 表达表达)(xS，由于，由于1,jjxx)(xS 在区间在区间上是线性函数，可表示为上是线性函数，可表示为)(xs 1)(jjyxs对积分两次并利用可定出积分常数，于是得三次样条表达式2022-3-3125) 1, 1 , 0()6()6(6)(6)()(211123131njhxxhMyhxxhMyhxxMhxxMxSjjjjjjjjjjjjjjjjjjjjjjjjjjjjhMMhyyhxxMhxxMx