计算方法课件第二章3节.ppt
1/47,2.3 Newton插值多项式,本节内容一.差分二.差商三.差商与差分关系四.Newton基本插值公式五.Newton插值计算步骤返回章节目录,2/47,2.3 Newton插值多项式,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x)都需重新算过。将Ln(x)改写成 的形式，希望每加一个节点时，只附加一项上去即可。下面首先讨论在实际问题中常遇到的等距节点(差分)情况，此时，牛顿插值公式被进一步简化。然后学习不等距节点(差商)的牛顿插值多项式。,3/47,2.3 Newton插值多项式,一.差分,4/47,2.3 Newton插值多项式,5/47,2.3 Newton插值多项式,6/47,2.3 Newton插值多项式,二差商（亦称均差）/*divided difference*/差商是数值方法中的一个重要概念，它可以反映出列表函数的性质，并能对 Lagrange 插值公式给出新的表达形式，这就是 Newton 插值/*Newtons Interpolation*/。,7/47,2.3 Newton插值多项式,对已知的列表函数 称为 f 关于 xi 的零阶差商，记为：由零阶差商出发，可归纳地定义各阶差商。,插值节点,对应的函数值,8/47,2.3 Newton插值多项式,1.定义,一阶差商的差商,9/47,2.3 Newton插值多项式,P47,10/47,2.4 Newton插值多项式,3.差商表（实用）,规定函数值为零阶差商,P47,11/47,2.3 Newton插值多项式,三.在等距节点的前提下,差商与差分有如下关系,12/47,2.3 Newton插值多项式,13/47,2.3 Newton插值多项式,依此类推,P41,14/47,2.3 Newton插值多项式,4.例：对函数的列表部分，列出差商表（见表）f(x)=lg x 差商计算表,15/47,2.3 Newton插值多项式,四.Newton 基本插值公式,牛顿公式,16/47,2.3 Newton插值多项式,牛顿公式,P48,17/47,2.3 Newton插值多项式,牛顿前差公式/*Newtons forward-difference formula*/牛顿后差公式/*Newtons backward-difference formula*/,P42,P45,18/47,2.3 Newton插值多项式,注：一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为表初公式和表末公式。,19/47,2.3 Newton插值多项式,五.Newton插值计算步骤1.计算差商2.计算插值根据以上步骤,自己写出Newton插值算法流程图,并能参照流程图编程上机。,20/47,2.3 Newton插值多项式,计算Newton插值步骤：首先根据节点和节点值计算差商表;然后利用Newton插值多项式估算 f(x)。例：,21/47,2.3 Newton插值多项式,解：先造差商表,22/47,2.3 Newton插值多项式,由Newton公式得四次插值多项式为：例：教材 P42 例4，P45 例5，P48 例6,教材自学，此处不详解,23/47,2.补 Hermite插值,本节内容一.问题提出二.数学描述三.求解思想返回章节目录,24/47,前述插值问题:要求被插函数与插值多项式在节点取相同值Lagrange型插值条件然而,不少实际问题 不但要求在节点上 函数值相等,而且还 要求它的导数值也 相等(即要求在节点 上具有一阶光滑度),甚至要求高阶导数也相等,满足这种要求的插值多项式称埃尔米特(Hermite)插值多项式。,2.补 Hermite插值,25/47,2.补 Hermite插值,现代的仿生学就是一个典型的例子。在设计交通工具的外形，就是参照海豚的标本上已知点及已知点的导数，做插值在计算机上模拟海豚的外形制成飞机、汽车等外形。下面只讨论函数值与导数值个数相等的情况。,26/47,2.补 Hermite插值,27/47,2.补 Hermite插值,有关Hermite（埃尔米特）插值的详细方法等，此处略。具体请参阅教材或相关资料。,28/47,2.补 Hermite插值,29/47,2.4 分段插值,分段插值(piecewise polynomial approximation)本节内容一.Runge 现象二.分段线性插值三.分段 Hermite 插值返回章节目录,30/47,2.4 分段插值,一.计算中的Runge现象由插值问题的提出,通常我们会觉得当节点越来越密时,插值函数越来越接近于原函数。但是结果并非如此,因为多项式是上下震荡的,震荡的幅度不尽相同,不同区段的震荡密度也不一样,由此导致,利用较高阶的插值多项式所计算的结果,与原来的函数值相差甚远。这说明高次插值未必可行。结果表明,并不是插值多项式的次数越高,插值效果越好,精度也不一定是随次数的提高而升高,这种现象在上个世纪初由Runge发现,故称为Runge现象。,P50,31/47,2.4 分段插值,不同次数的Lagrange插值多项式的比较图,Runge现象,32/47,2.4 分段插值,例：,n 越大，端点附近抖动越大，称为Runge 现象,33/47,2.4 分段插值,二.分段线性插值/*piecewise linear interpolation*/,34/47,2.4 分段插值,三.分段Hermite插值/*Hermite piecewise polynomials*/,35/47,2.4 分段插值,分段线性插值（图）,36/47,2.4 分段插值,分段三次Hermite插值（图）,37/47,2.5 三次样条插值,本节内容一.分段插值法二.三次样条插值 三.三次样条插值函数四.边界条件五.三次样条插值函数的表达式六.例返回章节目录,38/47,2.5 三次样条插值,一.分段插值法：问题：结点增多,多项式次数增高,逼近精度越好?未必!多结点高次插值往往在局部误差更大Runge（龙格）现象。实用：采用分段低次插值。有分段线性,分段二次插值等,其几何意义缺点：分段插值函数只能保证连续性,不能保证光滑性。,折线代替曲线,39/47,2.5 三次样条插值,二.三次样条插值/*Cubic Spline*/分段插值可以得到整体连续函数，但在连接点处一般不光滑，而 Hermite 插值虽然在连接点处一阶光滑，但整体插值由于结点多次数高而有可能发生龙格现象。希望：既想分段插值，又想在结点处保持光滑，甚至二阶光滑 三次样条。,P53,40/47,2.5 三次样条插值,什么是样条：是指飞机或轮船等的制造过程中为描绘出光滑的外形曲线（放样）所用的工具；样条本质上是一段一段的三次多项式拼合而成的曲线；在拼接处，不仅函数是连续的，且一阶和二阶导数也是连续的；1946年，Schoenberg将样条引入数学，即所谓的样条函数。,41/47,2.5 三次样条插值,三.三次样条插值函数,P54,42/47,2.5 三次样条插值,四.边界条件S(x)在区间 xi-1,xi 上是三次多项式,S(x)=aix3+bix2+cix+di,有4个待定系数,要确定S(x)共要4n个待定系数。由S(xi)=yi，i=0,1,n,有2n个条件。再由S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件 及S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件 共有4n-2个条件。尚缺少两个条件。为得到唯一的三次样条函数,通常可在区间a,b的端点x0=a,xn=b上各加一个条件,称为边界条件。,P54,43/47,2.5 三次样条插值,注：4n-2个条件 S(xi)=yi，i=0,1,n,有n+1个条件。S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件 S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件 S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件,44/47,2.5 三次样条插值,常用的边界条件有1.S(x0)=y0,S(xn)=yn;(夹持条件)2.S(x0)=y0,S(xn)=yn;(自然边界条件)3.假设(x)是以b-a为周期的周期函数,这时要求S(x0+0)=S(xn-0)S(x0+0)=S(xn-0)S(x0+0)=S(xn-0)这样确定的S(x)为周期样条函数。(周期性条件),P55,45/47,2.5 三次样条插值,有关三次样条插值多项式的存在性和唯一性证明，此处略。通过具体求解待定系数来证明，具体请参考相关资料。,46/47,2.5 三次样条插值,五.三次样条插值函数的表达式若假设S(xi)=mi,i=0,1,n,利用分段Hermite插值多项式,当xxi-1,xi时,有其中hi=xi-xi-1。为确定S(x),只需确定mi,i=0,1,n。可利用S(xi-0)=S(xi+0)来求出mi。,P55,47/47,2.5 三次样条插值,48/47,2.5 三次样条插值,所以,49/47,2.5 三次样条插值,于是有由连续性条件S(xi-0)=S(xi+0)可得,50/47,2.5 三次样条插值,3(ixi-1,xi+ixi,xi+1)=gi,则有 imi-1+2mi+imi+1=gi,i=1,2,n-1.(*式)再结合不同的边界条件,可得关于mi的方程。,51/47,2.5 三次样条插值,若边界条件为:m0=y0,mn=yn,带入(*式)可得,52/47,2.5 三次样条插值,若边界条件为:S(x0)=y0,S(xn)=yn,则有 连同(*式)一起,可得,53/47,2.5 三次样条插值,若边界条件为周期性边界条件，由S(x0+0)=S(xn-0),和S(x0+0)=S(xn-0),有m0=mn和 nmn-1+2mn+nm1=gn，其中 于是有,54/47,2.5 三次样条插值,对应不同的边界条件,只要求出相应的线性方程组的解,便得到三次样条函数在各区间xi-1,xi上的表达式由于三个方程组的系数矩阵都是严格对角占优矩阵,所以都有唯一解,前两个方程组均可用追赶法求解,第三个方程组可用LU分解法或Gauss消元法求解.,55/47,2.5 三次样条插值,例：,先看教材 P60例7,56/47,2.5 三次样条插值,故有,57/47,2.5 三次样条插值,例：,58/47,2.5 三次样条插值,故有,59/47,小结,2.1 引言2.2 Lagrange 插值多项式2.3 Newton插值多项式2.补 Hermite插值2.4 分段低次插值2.5 三次样条插值 2.6 数值微分（*）,60/47,作业与实验,作业（上作业本）：习题二（P68）：1、3、5实验实验名称：实验一 拉格朗日插值法实验目的：验证拉格朗日插值多项式，进一步加深对拉格朗日插值法的理解。实验日期：09计11：2011年5月6日（周五）7、8节09计61：2011年5月3日（周二）1、2节具体要求见另外文档,
