计算方法 Newton插值ppt课件

.,第2次Newton插值,计算方法(NumericalAnalysis),.,牛顿插值多项式的概念差商及其性质牛顿插值多项式的系数与误差余项的导出利用牛顿插值多项式近似求解的例子,.,牛顿插值多项式的概念,.,3均差与牛顿插值多项式拉格朗日插值多项式的优点与缺点优点：结构对称，使用方便。缺点：由于是用基函数构成的插值，要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。,.,例如：3个节点，抛物插值的情况：,若要新增加一个节点，而进行3次插值的时候，则需要重新计算,.,试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服这个缺点，即，每增加一个新节点时，只需在P(x)原来的表达式中增加相应的一项即可，而不改变P(x)的原来已经存在的表达式部分。这就是牛顿插值多项式的特点。,.,可以证明,可将满足插值条件p(x0)=y0,p(x1)=y1，p(xn)=yn的n次插值多项式,写成如下形式:,基函数：(x-x0),(x-x0)(x-x1),，(x-x0)(x-x1)(x-xn-1),.,定义：给定n+1个插值节点x0,x1,xn,如下形式的插值多项式称为Newton插值多项式：,（3.12）,其中ak(k=0,1,2,n)为待定系数。,无xn,将出现在系数中,.,牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式,与Lagrange多项式相比它克服了“增加一个节点时整个计算工作重新开始”的缺点,节省乘除法运算次数,在Newton插值多项式中用到的差商等概念，又与数值计算的其他方面有密切的关系.,要确定牛顿插值多项式Nn(x)系数，需要利用下一节差商的计算。,Home,.,差商及其性质,.,3.1差商及其性质,定义：函数y=f(x)在区间xi,xi+1上的平均变化率,称为f(x)关于xi,xi+1的1阶差商。,定义2阶差商,.,2阶差商fxi,xj,xk是指,一般地,可定义xi,xi+1,xi+n上的n阶差商：,.,为了方便地计算差商，需要建立差商表。表中的箭头指向表示更高阶差商所需要的低阶差商的参与。,.,例2.11求f(x)=x3在节点x=0,2,3,5,6上的各阶差商值。,解:计算得如下表,.,性质1函数f(x)的n阶差商fx0,x1,xn可由f(x0),f(x1),f(xn)的线性组合表示：,差商的性质,验证,同学自己验证,真漂亮,.,这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。,应理解：右端分母中，xk-xk项永远不出现。,或者表示成,以上公式可以利用如下的表达式直接验证,.,性质2差商具有对称性,即在k阶差商中任意交换两个节点和的次序,其值不变。,即：,学生自己验证以上两个公式,.,性质3若fx,x0,x1,xk是x的m次多项式,则fx,x0,x1,xk,xk+1是x的m-1次多项式。,注意：右端分子为m次多项式,且由差商的对称性可知，当x=xk+1时,分子为0,故分子含有因子xk+1x，与分母相消后，右端为m-1次多项式。,证：由差商定义,常数,.,性质4若f(x)是n次多项式,则fx,x0,x1,xn恒为0。,证：f(x)是n次多项式，则fx,x0是n-1次多项式,fx,x0,x1是n-2次多项式。,fx,x0,x1,xn0,依次递推，fx,x0,x1,xn-1是n-n次（零次）多项式，即常数c.,所以,.,性质5若f(x)存在k阶导数，则f(x)的k阶差商与其k阶导数之间有下列关系：,证明：这个性质可直接用罗尔(Rolle)定理证明。,Home,.,牛顿插值多项式的系数与误差余项的导出,.,牛顿插值多项式的系数与误差余项的导出,的系数ak(k=0,n)可根据以下插值条件推出。,.,一般，用数学归纳法可证明,从上述各个公式中可以解出：,将a1=fx0,x1代入下一个等式，得,.,n次牛顿(Newton)插值公式的表达式：,这里没有假设f(x)可导,.,牛顿插值多项式余项公式的推导：,设x为区间a,b上的一点，可得：,从前往后，将后式逐渐带入到前式,即得：,根据1阶差商的定义,根据2阶差商的定义,.,推导完毕(下一页PPT有3个节点情况的详细推导)。,.,设x为区间a,b上的一点，可得：,将(2)式代入(1)式，得：,牛顿插值多项式余项公式的仔细推导（以仅有3个插值节点的2次插值为例）：,(1),(2),(3),(4),将(3)式代入(4)式，得：,整理，得,整理，得：,N2(x),R2(x),.,解释：由插值多项式的存在唯一性定理知，满足同一组插值条件的拉格朗日插值多项式P(x)与牛顿插值多项式Nn(x)实际上是同一个多项式,的形式以后，所得的表达式是相同的。,即将P(x)和Nn(x)所得的多项式表达式，化为,.,若f(n+1)(x)不存在，则只有使用(*)式来表达误差。,Newton插值多项式的误差(不要求f(x)光滑),(*),.,评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有规律。,Home,若f(n+1)(x)存在,.,利用牛顿插值多项式近似求解的例子,.,.,N2(x)=1+1/3(x-1)-1/60(x-1)(x-4)=-1/60 x2+5/12x+3/5,N2(7)=2.7,例2.12已知x=1,4,9的平方根值，求,解1：考虑f(x)=x，利用差商表求差商,.,解2：利用公式求差商,用这种方法解得得系数与方法1的相同。,.,解3：利用拉格朗日方法求插值对多项式,求2次插值对多项式,=-1/60 x2+5/12x+3/5,.,4.4.1差商及其性质,例2.13已知x=0,2,3,5对应的函数值为y=1,3,2,5,作三次Newton插值多项式。,.,例2.14求的值，并估计其误差,解：令,，取x0=4,x1=9,x2=6.25,差商表,.,在区间4,9上，,由,计算器计算结果：,N2(7)=2.7，差一些,例2.12中，计算结果为：,代入x=7,例2.14中，计算结果为：,N2(7)=2.64848，好一些,.,4.4.1差商及其性质,例2.15已知f(x)=x7+x4+3x+1求f20,21,27及f20,21,27,28,分析：本题f(x)是一个多项式,故应利用差商的性质,解:由差商与导数之间的关系,.,例2.16给出f(x)的函数表如下，求4次Newton插值多项式，并且由此计算f(0.596)的值,并且估计误差R4(0.596).,.,解：首先计算出差商表如下：,.,经计算得N4(0.596)=0.63192,现在试图进行误差估计：R4(x)=|fx,x0,x1,x2,x3,x45(x)|,因为x=0.596，所以要进行以上的差商运算，需要知道f(0.596)的值，但是我们现在不知道f(0.596)的值。,怎么办？,可以利用f(0.596)N4(0.596)=0.63192来计算差商，见下页。