计算方法 Newton插值【优选资料】

1、第2次 Newton 插值,计算方法 (Numerical Analysis),1,知识研究,牛顿插值多项式的概念 差商及其性质 牛顿插值多项式的系数与误差余项的导出 利用牛顿插值多项式近似求解的例子,2,知识研究,牛顿插值多项式的概念,3,知识研究,3 均差与牛顿插值多项式 拉格朗日插值多项式的优点与缺点 优点：结构对称，使用方便。 缺点：由于是用基函数构成的插值，要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。,4,知识研究,例如：3个节点，抛物插值的情况：,若要新增加一个节点，而进行3次插值的时候，则需要重新计算,5,知识研究,试图改进：我们要构造一种具

2、有承袭性的插值多项式P(x)来克服这个缺点， 即，每增加一个新节点时，只需在P(x)原来的表达式中增加相应的一项即可，而不改变P(x)的原来已经存在的表达式部分。 这就是牛顿插值多项式的特点。,6,知识研究,可以证明, 可将满足插值条件 p(x0) = y0 , p(x1) = y1 ， p(xn) = yn 的n次插值多项式, 写成如下形式:,基函数： (x-x0 ), (x-x0 )(x-x1 ), ，(x-x0 )(x-x1 )(x-xn-1),7,知识研究,定义：给定n+1个插值节点x0 , x1 , xn, 如下形式的插值多项式称为Newton插值多项式：,（3.12）,其中ak (

3、k=0,1,2,n)为待定系数。,无x n ,将出现在系数中,8,知识研究,牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式, 与Lagrange多项式相比 它克服了“增加一个节点时整个计算工作重新开始”的缺点, 节省乘除法运算次数, 在Newton插值多项式中用到的差商等概念，又与数值计算的其他方面有密切的关系.,要确定牛顿插值多项式Nn(x)系数，需要利用下一节差商的计算。,Home,9,知识研究,差商及其性质,10,知识研究,3.1 差商及其性质,定义：函数y= f(x)在区间xi ,xi+1上的平均变化率,称为f(x)关于xi , xi+1 的1阶差商。,定义2阶差商,11

4、,知识研究,2阶差商 fxi, xj, xk是指,一般地,可定义xi, xi+1 , xi+n上的n阶差商：,12,知识研究,为了方便地计算差商，需要建立差商表。表中的箭头 指向表示更高阶差商所需要的低阶差商的参与。,13,知识研究,例2.11 求 f(x)= x3在节点 x=0, 2, 3, 5, 6上 的各阶差商值。,解: 计算得如下表,14,知识研究,性质1 函数 f(x) 的 n 阶差商 f x0, x1 , , xn 可由 f (x0), f (x1 ), , f (xn ) 的线性组合表示：,差商的性质,验证,同学自己验证,真漂亮,15,知识研究,这种求解差商的方法的优点是直接使用

5、公式，缺点是计算量较大。,应理解：右端分母中，xk-xk 项永远不出现。,或者表示成,以上公式可以利用如下的表达式直接验证,16,知识研究,性质2 差商具有对称性,即在k阶差商 中任意交换两个节点 和 的次序,其值不变。,即：,学生自己验证以上两个公式,17,知识研究,性质3 若fx, x0, x1 , , xk 是 x 的 m 次多项式, 则 fx, x0, x1 , xk , xk+1是 x 的 m-1 次多项式。,注意：右端分子为 m 次多项式, 且由差商的对称性可知，当 x = xk+1 时, 分子为0 ,故分子含有因子 xk+1 x，与分母相消后，右端为m-1 次多项式。,证：由差商

6、定义,常数,18,知识研究,性质4 若 f(x)是n次多项式, 则fx, x0, x1 , , xn 恒为0。,证： f(x)是n次多项式，则fx, x0 是 n-1次多项式, f x, x0, x1 是 n-2 次多项式。,fx, x0, x1 , xn 0,依次递推 ， f x, x0, x1 , , xn-1 是n-n次（零次）多项式，即常数c.,所以,19,知识研究,性质5 若f(x)存在k阶导数，则f(x)的k阶差商 与其k阶导数之间有下列关系：,证明：这个性质可直接用罗尔(Rolle)定理证明。,Home,20,知识研究,牛顿插值多项式的系数 与误差余项的导出,21,知识研究,牛顿

7、插值多项式的系数与误差余项的导出,的系数ak (k=0,n)可根据以下插值条件推出。,22,知识研究,一般，用数学归纳法可证明,从上述各个公式中可以解出：,将a1 =fx0 , x1 代入下一个等式，得,23,知识研究,n次牛顿(Newton)插值公式的表达式：,这里没有假设f(x)可导,24,知识研究,牛顿插值多项式余项公式的推导：,设x为区间a, b上的一点，可得：,从前往后，将后式逐渐带入到前式,即得：,根据1阶差 商的定义,根据2阶差 商的定义,25,知识研究,推导完毕(下一页PPT有3个节点情况的详细推导)。,26,知识研究,设x为区间a, b上的一点，可得：,将(2)式代入(1)式

8、，得：,牛顿插值多项式余项公式的仔细推导（以仅有3个插值节点 的2次插值为例）：,(1),(2),(3),(4),将(3)式代入(4)式，得：,整理，得,整理，得：,N2 (x),R2 (x),27,知识研究,解释： 由插值多项式的存在唯一性定理知，满足同一组插值条件的拉格朗日插值多项式P(x)与牛顿插值多项式Nn(x)实际上是同一个多项式,的形式以后，所得的表达式是相同的。,即将P(x)和Nn(x)所得的多项式表达式，化为,28,知识研究,若f(n+1)(x)不存在，则只有使用(*)式来表达误差。,Newton插值多项式的误差(不要求f(x)光滑),(*),29,知识研究,评论：牛顿插值公式

9、计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有规律。,Home,若f(n+1)(x) 存在,30,知识研究,利用牛顿插值多项式近似求解的例子,31,知识研究,32,知识研究,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，利用差商表求差商,33,知识研究,解2：利用公式求差商,用这种方法解得得系数与方法1的相同。,34,知识研究,解3：利用拉格朗日方法求插值对多项式,求2次插值对多项式,=-1/

10、60 x2 + 5/12x + 3/5,35,知识研究,4.4 .1 差商及其性质,例2.13 已知 x=0, 2, 3, 5 对应的函数值为 y=1, 3, 2, 5 , 作三次Newton插值多项式。,36,知识研究,例2.14 求 的值，并估计其误差,解：令,，取 x0=4, x1=9, x2=6.25, 差商表,37,知识研究,在区间 4 , 9 上，,由,计算器计算结果：,N2(7)=2.7，差一些,例2.12中，计算结果为：,代入x=7,例2.14中，计算结果为：,N2(7)=2.64848，好一些,38,知识研究,4.4 .1 差商及其性质,例2.15 已知 f(x) = x7+

11、 x4+ 3x+ 1 求 f 20, 21, 27 及 f 20, 21, 27, 28 ,分析：本题 f(x)是一个多项式, 故应利用差商的性质,解: 由差商与导数之间的关系,39,知识研究,例2.16 给出f(x)的函数表如下，求4次Newton插 值多项式，并且由此计算f(0.596)的值,并 且估计误差 R4(0.596).,40,知识研究,解：首先计算出差商表如下：,41,知识研究,经计算得 N4(0.596) = 0.63192,现在试图进行误差估计： R4 (x) =|fx, x0, x1, x2, x3, x4 5(x)|,因为 x = 0.596，所以要进行以上的差商运算，需要知道f(0.596)的值，但是我们现在不知道f(0.596)的值。,怎么办？,可以利用 f(0.596)N4(0.596) = 0.63192 来计算差商，见下页。,42,知识研究,R4 (x