数值分析课件 第二章 插值

第二章插值方法/*Interpolation*/,Interpolation_introduction,1问题提出函数逼近/*problemformulation-functionapproximation*/,用,Interpolation_introduction,函数逼近的方法有很多，例如Taylor级数，Fourier级数，有限元方法、边界元方法，小波分析等，大学科叫逼近论。本书讨论连续函数的逼近，主要介绍插值法(chapter2)和最佳一直逼近、最小平方逼近离散数据拟合(chapter3),Interpolation_introduction,插值节点,插值条件,-插值问题,多项式插值是数值分析的基本工具，常用来计算被插函数的近似函数值，零、极点，导数、积分（第四章数值积分和数值微分），解微分方程（第五章）、积分方程,插值,多项式插值-polynomialinterpolation,ProblemI.给定y=f(x)的函数表,xia,b,Interpolationinterval,Interpolationcondition,Interpolationpolynomial,Interpolationpoints,Interpolationpolynomial,(2.1),(2.2),Pn(x)f(x),多项式插值的几何意义,Interpolationpolynomial,求,插值多项式的唯一性,提问：ProblemI中的Pn(x)是否存在？若存在，是否唯一？如何求？,Interpolationpolynomial,Interpolationpolynomial,Interpolationpolynomial,2拉格朗日多项式/*LagrangePolynomial*/,n=1,可见P1(x)是过(x0,y0)和(x1,y1)两点的直线。,称为拉氏基函数/*LagrangeBasis*/，满足条件li(xj)=ij/*KroneckerDelta*/,2LagrangePolynomial,n1,LagrangePolynomial,与节点有关，而与f无关,基函数法（n=1情形的推广）,2LagrangePolynomial,证明：(前面已利用Vandermonde行列式论证),反证：若不唯一，则除了Ln(x)外还有另一n阶多项式Pn(x)满足Pn(xi)=yi。,考察则Qn的阶数,n,而Qn有个不同的根,注：若不将多项式次数限制为n，则插值多项式不唯一。,例如也是一个插值多项式，其中可以是任意多项式。,2LagrangePolynomial,插值余项/*Remainder*/,RollesTheorem:若充分光滑，则存在使得。,推广：若,使得,Rn(x)至少有个根,n+1,任意固定xxi(i=0,n),考察,(x)有n+2个不同的根x0xnx,注意这里是对t求导,2LagrangePolynomial,1LagrangePolynomial,注：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。,当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。,Quiz:给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？,1LagrangePolynomial,解：,n=1,分别利用x0,x1以及x1,x2计算,利用,这里,而,sin50=0.7660444,外推/*extrapolation*/的实际误差0.01001,利用,内插/*interpolation*/的实际误差0.00596,内插通常优于外推。选择要计算的x所在的区间的端点，插值效果较好。,1LagrangePolynomial,n=2,sin50=0.7660444,2次插值的实际误差0.00061,高次插值通常优于低次插值,但绝对不是次数越高就越好，嘿嘿,Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.,Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?,Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.,Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.,Excellentpoint!Wewillcometodiscussthisproblemnexttime.,3逐次线性插值/*LagrangePolynomial*/,实际上，,是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次插值的方法称为逐次线性插值。,Aitken法(按下表计算),线性插值基函数,增加,如果精度不构，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。,k1,k0,k2,k3,k4,Neville法(按下表计算),如果精度不构，增加节点x4,同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。,k1,k0,k1,k1,k1,HW:用类似于前面的方法构造Neville计算公式,注：Atkin方法和Neville方法与Lagrange公式相比，当需要增加节点时，很容易由低次插值构造高次插值，而Lagrange插值公式中，每个基函数都需要作适当变化。,误差估计：由插值多项式的存在唯一性知，仍有,但这里可采用一种更简便的方法。当f(n+1)(x)在插值区间变化不大时，设f(n+1)(x)L，则有,可认为满足精度要求。,根据前面的计算结果估计当前的误差：事后误差估计（实用），前面给出的误差估计（事先误差估计）不实用,HW:p.58-59#1-8,4牛顿插值/*NewtonsInterpolation*/,差商(亦称均差)/*divideddifference*/,1阶差商/*the1stdivideddifferenceoffw.r.t.xiandxj*/,2阶差商,f(x0),1阶差商的几何意义：弦截线的斜率,4NewtonsInterpolation,4NewtonsInterpolation,(k+1)阶差商：,Warning:myheadisexplodingWhatisthepointofthisformula?,差商的值与xi的顺序无关！,1.线性：,2.差商可以表示为函数值的线性组合：,3.对称性：由2知，差商的值与节点的顺序无关！,4.差商的另一种定义：由2，3及均差定义可得,4NewtonsInterpolation,5.差商与导数的关系：f(x)Cka,b,则a,b,s.t.,HW:证明差商的性质2，4,4NewtonsInterpolation,4NewtonsInterpolation,牛顿插值/*NewtonsInterpolation*/,Nn(x)n次多项式，满足：Nn(xi)=f(xi),Rn(x)插值余项，满足Rn(xi)=0，i=0,n,ai=,fx0,xi,(1),(2),(n),(n)(n-1)(2)(1),4NewtonsInterpolation,注：由唯一性可知Nn(x)Ln(x)，只是算法不同，表达形式不同，故其余项也相同，即,实际计算过程为,f(x0)f(x1)f(x2)f(xn1)f(xn),fx0,x1fx1,x2fxn1,xn,fx0,x1,x2fxn2,xn1,xn,fx0,xn,f(xn+1)fxn,xn+1fxn1,xn,xn+1fx1,xn+1fx0,xn+1,如果精度不构，增加节点xn+1,同时表中增加一行，三角形斜边上即为所要求的各次项系数。,4NewtonsInterpolation,等距节点公式/*FormulaewithEqualSpacing*/,向前差分/*forwarddifference*/,向后差分/*backwarddifference*/,中心差分/*centereddifference*/,其中,当节点等距分布时:,fi=f(xi),差分的重要性质：,线性：例如,各阶差分可用函数值表示：,4NewtonsInterpolation,函数值可用各阶差分表示：,差商与差分的关系：,若f(x)是n次多项式，则是次多项式，而,差分与导数的关系(由差分与差商、差商与导数的关系得）：,4NewtonsInterpolation,等距节点牛顿公式,牛顿前差公式/*Newtonsforward-differenceformula*/,注：一般当x靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。,牛顿后差公式/*Newtonsforward-differenceformula*/,HW:p.59#9-16,5厄米插值/*HermiteInterpolation*/,不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数(x)满足(xi)=f(xi),(xi)=f(xi),(mi)(xi)=f(mi)(xi).,注：N个条件可以确定阶多项式。,N1,一般只考虑f与f的值。,厄米插值,3HermiteInterpolation,例：设x0x1x2,已知f(x0)、f(x1)、f(x2)和f(x1),求多项式P(x)满足P(xi)=f(xi)，i=0,1,2，且P(x1)=f(x1),并估计误差。,模仿Lagrange多项式的思想，设,解：首先，P的阶数=,3,h0(x),有根,x1,x2，且h0(x1)=0x1是重根。,又:h0(x0)=1C0,h2(x),h1(x),有根x0,x2,由余下条件h1(x1)=1和h1(x1)=0可解。,与h0(x)完全类似。,有根x0,x1,x2,与Lagrange分析完全类似,3HermiteInterpolation,一般地，已知x0,xn处有y0,yn和y0,yn，求H2n+1(x)满足H2n+1(xi)=yi，H2n+1(xi)=yi。,解：设,其中i(xj)=ij,i(xj)=0,(xj)=0,(xj)=ij,i,i(x),由余下条件i(xi)=1和i(xi)=0可解Ai和Bi,有根x0,xn,除了xi外都是2重根,又i(xi)=1Ci=1,i,),(,x,=,这样的Hermite插值唯一,i,Th.设f(x)C2n+2a,b,则a,b,s.t.满足下面插值条件,3HermiteInterpolation,斜率=1,求Hermite多项式的基本步骤：,根据多项式的总阶数和根的个数写出表达式；,根据尚未利用的条件解出表达式中的待定系数；,最后完整写出H2n+1(x)。,HW:p.59#17-19,注：待定系数法仍适用，但插值节点多时比较麻烦。,4分段低次插值/*piecewisepolynomialapproximation*/,RememberwhatIhavesaid?IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult,sincehigh-degreepolynomialsareoscillating.,例：在5,5上考察的Ln(x)。取,n越大，端点附近抖动越大，称为Runge现象,4PiecewisePolynomialApproximation,分段线性插值/*piecewiselinearinterpolation*/,在每个区间上，用1阶多项式(直线)逼近f(x):,分段Hermite插值/*Hermitepiecewisepolynomials*/,Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf?Headache,5三次样条/*CubicSpline*/,注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f在所有插值点的导数值。,f(x),H(x),S(x),5CubicSpline,构造三次样条插值函数的三弯矩法/*methodofbendingmoment*/,对每个j,此为3次多项式,则Sj”(x)为次多项式，需个点的值确定之。,1,2,设Sj”(xj1)=Mj1，Sj”(xj)=Mj,对应力学中的梁弯矩，故名,对于xxj1,xj可得到,Sj”(x)=,积分2次，可得Sj(x)和Sj(x)：,5CubicSpline,下面解决Mj：,利用S在xj的连续性,xj1,xj:Sj(x)=,xj,xj+1:Sj+1(x)=,j,1,n1,即：有个未知数，个方程。,n1,n+1,还需2个边界条件/*boundaryconditions*/,5CubicSpline,第1类边条件/*clampedboundary*/：S(a)=y0，S(b)=yn,类似地利用xn1,b上的Sn(x),第2类边条件：S”(a)=y0”=M0，S”(b)=yn”=Mn,这时：,特别地，M0=Mn=0称为自由边界/*freeboundary*/，对应的样条函数称为自然样条/*NaturalSpline*/。,第3类边条件/*periodicboundary*/：当f为周期函数时，yn=y0，S(a+)=S(b)M0=Mn,5CubicSpline,注：另有三转角法(p.49-53)得到样条函数，即设Sj(xj)=mj，则易知xj1,xj上的Sj(x)就是Hermite函数。再利用S”的连续性，可导出关于mj的方程组，加上边界条件即可解。,CubicSpline由boundaryconditions唯一确定。,即:提高精度只须增加节点,而无须提高样条阶数。,稳定性：只要边条件保证|0|,|0|,|n|,|n|2，则方程组系数阵为SDD阵，保证数值稳定。,HW:p.59-60,#19-25,5CubicSp