插值法小结

第二章插值法（总结）/*Chapter2Interpolation*/主要内容•本章引入了那些问题•所引入问题的原因•解决问题的方法•各种方法的优缺点•插值法讲的是构造函数使已知点最大程度的满足函数关系，即已知点与点之间内在规律的数量关系，从而推测未知点的性质。•现实中我们只可能得到有限的数据，而这些数据不可能恰好满足某些我们已知的函数，插值法就是构造函数从而揭开已知数据之间的内在规律。•在生产和科学实验中，函数有时仅能获得它的若干点的函数值或微商值，即只给出的一张数据表。如果根据这张数据表，构造一个简单函数，使之满足数据表中的数据。这样的函数就是的逼近函数。这种逼近问题就称为插值问题。•常见的插值法：拉格朗日插值、均差与牛顿插值多项式、埃米尔特插值、分段低次插值、三次样条插值。•而每种插值方法均有自己的优缺点，以下是对各种插值方法的介绍。设表示所有次数不超过n的多项式的集合。设是一组互异的点，所谓n次多项式插值，就是求多项式，使之满足(1.1)其中称为插值节点，是插值多项式，是被插（值）函数，(1.1)是插值条件。nP()nnpxP()(0,1,2,,)niipxyin01,,,nxxx()npx()fx01,,,nxxx()(0,1,2,,)iiyfxin•n次多项式•(1.4)•满足插值条件(1.1)，其中•(1.5)•称(1.4)式为Lagrange插值多项式或Lagrange插值公式；(1.5)式为Lagrange插值基函数。0()()nnkkkpxylx0(),0,1,,njkjkjjkxxlxknxxLagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过，这就大大地增大了计算量。优点：结构紧凑、思想清晰、显式表示、公式对称，与插值节点的编号无关，适合理论分析。缺点：没有承袭性。牛顿插值],[)()()(000xxfxxxfxf],,[)(],[],[101100xxxfxxxxfxxf],...,,[)(],...,[],...,,[0010nnnnxxxfxxxxfxxxf))...((...))(()()(10102010nnnxxxxaxxxxaxxaaxN12…………n11+(xx0)2+……+(xx0)…(xxn1)n1...))(](,,[)](,[)()(102100100xxxxxxxfxxxxfxfxf))...(](,...,[100nnxxxxxxf))()...(](,...,,[100nnnxxxxxxxxxfNn(x)--牛顿插值多项式Rn(x)ai=f[x0,…,xi]注：由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即)(!)1()()(],...,,[1)1(10xnfxxxxfkxnkn),(,!)(],...,[maxmin)(0xxkfxxfkk实际计算过程为f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]差分形式—等距节点公式向前差分iiifff1ikikikikffff1111)(向后差分111ikikikfffi1iifff中心差分212111ikikikfff其中)(221hiixff当节点等距分布时:),...,0(0nihixxi牛顿公式))...(](,...,[...)](,[)()(1000100nnnxxxxxxfxxxxfxfxN牛顿前插公式牛顿后插公式将节点顺序倒置：))...(](,...,[...)](,[)()(101xxxxxxfxxxxfxfxNnnnnnnn设htxx0，则)()()(000xfkthtxNxNknknn),(,))...(1()!1()()(01)1(nnnnxxhntttnfxR设htxxn，则)()1()()(0nknkknnnxfkthtxNxN注：一般当x靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。•Newton插值公式仅是Lagrange插值公式的一种变形。•Newton插值公式既具有Lagrange插值公式便于理论上分析的优点，又具有Aitken算法的承袭性，从而在需要增加节点时，可大大减少计算量。埃尔米特插值不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数(x)满足(xi)=f(xi),’(xi)=f’(xi),…,(mi)(xi)=f(mi)(xi).注：N个条件可以确定次多项式。N1要求在1个节点x0处直到m0阶导数都重合的插值多项式即为Taylor多项式00)(!)(...))(()()(000)(000mmxxmxfxxxfxfx其余项为)1(00)1(00)()!1()()()()(mmxxmfxxfxR一般只考虑f与f’的值。一般地，已知x0,…,xn处有y0,…,yn和y0’,…,yn’，求H2n+1(x)满足H2n+1(xi)=yi，H’2n+1(xi)=yi’。解：设ni)()()(0iixhxhyixH2n+1n0iyi’其中hi(xj)=ij,hi’(xj)=0,(xj)=0,’(xj)=ijhihihi(x)有根x0,…,xi,…,xn且都是2重根)()()(2xlBxAxhiiiiijjijixxxxxl)()()(由余下条件hi(xi)=1和hi’(xi)=0可解Ai和Bi)()])((21[)(2xlxxxlxhiiiii(x)hi有根x0,…,xn,除了xi外都是2重根hi)()(iili2(x)xxCxhi又:’(xi)=1Ci=1hi)(x)(ili2(x)xx设],[,...210baCfbxxxann则20)22()()!22()()(niixnnxxnfxR埃尔米特插值构造基函数的方法•优点：1)显式算法，算法简单，收敛性、稳定性好。只要结点间距充分小，分段插值总能获得所要求的精度，而不会出现Rung现象。•2)局部性。如果要修改某个数据，插值曲线仅仅在某个局部范围内受到影响；而代数插值却会影响到整个插值区间。•缺点：光滑度不高。若要提高光滑度，必须提供较多的信息才能达到。分段线性插值在每个区间上，用1次多项式(直线)逼近f(x):],[1iixx11111)()(iiiiiiiiyxxxxyxxxxxPxf],[for1iixxx记，易证：当时，||max1iixxh0h)()(1xfxPh一致失去了原函数的光滑性。分段三次Hermite插值给定nnnyyyyxx,...,;,...,;,...,000在上利用两点的y及y’构造3次Hermite函数],[1iixx导数一般不易得到。•分段三次埃尔米特插值比分段线性插值效果明显改善。但分段三次埃尔米特插值要求给出节点上的导数值，所要提供的信息太多，其光滑度也不高，只有一阶导数连续。三次样条插值定义设。三次样条函数,且在每个上为三次多项式/*cubicpolynomial*/。若它同时还满足，则称为f的三次样条插值函数.bxxxan...10],[)(2baCxS],[1iixx),...,0(),()(nixfxSii注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f在所有插值点的导数值。f(x)H(x)S(x)构造三次样条插值函数的三弯矩法在上，记],[1jjxx,1jjjxxh],[for)()(1][jjjxxxxSxS则S[j]”(x)为次多项式，需个点的值确定之。12设S[j]”(xj1)=Mj1，S[j]”(xj)=Mj对于x[xj1,xj]可得到S[j]”(x)=jjjjjjhxxMhxxM11积分2次，可得S[j]’(x)和S[j](x)：jjjjjjjAhxxMhxxM2)(2)(21121S[j]’(x)=jjjjjjjjBxAhxxMhxxM6)(6)(3131S[j](x)=利用已知S[j](xj1)=yj1S[j](xj)=yj可解jjjjjjjhMMhyyA611jjjjjjjjjjjjhxxhMyhxxhMyBxA12211)6()6(下面解决Mj：利用S’在xj的连续性[xj1,xj]:S[j]’(x)=jjjjjjjjjjjhMMxxfhxxMhxxM6],[2)(2)(1121211111211216],[2)(2)(jjjjjjjjjjjhMMxxfhxxMhxxM[xj,xj+1]:S[j+1]’(x)=利用S[j]’(xj)=S[j+1]’(xj)，合并关于Mj1、Mj、Mj+1的同类项，并记,,,整理后得到：11jjjjhhhl1jjlm]),[],[(6111jjjjjjjxxfxxfhhg211gMMMjjjjjjlmj1n1即：有个未知数，个方程。n1n+1110111122nnnnggMMlmlm还需2个边界条件第1类边条件：S’(a)=y0’，S’(b)=yn’[a,x1]:S[1]’(x)=0011002102106],[2)(2)(hMMxxfhaxMhxxM010010)],[(62gy0’xxfhMMnnnn-1nngxxfyn’hMM]),[(6211类似地利用[xn1,b]上的S[n]’(x)第2类边条件：S”(a)=y0”=M0，S”(b)=yn”=Mn这时：nnnygyg2,0;2,0000ml特别地，M0=Mn=0称为自由边界，对应的样条函数称为自然样条。第3类边条件：当f为周期函数时，yn=y0，S’(a+)=S’(b)M0=MnnnnnnnggMM111122112222mllmlmml注：另有三转角法得到样条函数，即设S[j]’(xj)=mj，则易知[xj1,xj]上的S[j](x)就是Hermite函数。再利用S”的连续性，可导出关于mj的方程组，加上边界条件即可解。CubicSpline由边界条件boundaryconditions唯一确定。收敛性：若，且，则],[baCfChhiiminmax一致S(x)f(x)0maxihas即:提高精度只须增加节点,而无须提高样条阶数。稳定性：只要边条件保证|m0|,|l0|,|mn|,|ln|2，则方程组系数阵为SDD阵，保证数值稳定。•三次样条插值具有良好的收敛性与稳定性，又有二阶光滑性，理论上和实际应用上都有重要意义，在计算机图形学中有重要应用。插值法小结(1)拉格朗日插值拉格朗日插值多项式在理论分析中非常方便，因为它的结构紧凑，利用基函数很容易推导和形象的描述算法，但是也有一些缺点，当插值节点增加、减少或其