计算方法-Newton插值课件.pptx

1、第2次 Newton 插值计算方法(Numerical Analysis)1.牛顿插值多项式的概念2.差商及其性质3.牛顿插值多项式的系数与误差余项的导出 4.利用牛顿插值多项式近似求解的例子 牛顿插值多项式的概念3 均差与牛顿插值多项式拉格朗日插值多项式的优点与缺点 优点：结构对称，使用方便。缺点：由于是用基函数构成的插值，要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。，)x)(xx(x)x)(xx(x(x)l2101201)x)(xx(x)x)(xx(x(x)l1202102)x)(xx(x)x)(xx(x(x)l2010210例如：3个节点，抛物插值的

2、情况：若要新增加一个节点，而进行3次插值的时候，则需要重新计算(x)(x)，l(x)，ll321(x).并且增加l4 试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服这个缺点，即，每增加一个新节点时，只需在P(x)原来的表达式中增加相应的一项即可，而不改变P(x)的原来已经存在的表达式部分。这就是牛顿插值多项式的特点。可以证明,可将满足插值条件p(x0)=y0 ,p(x1)=y1，p(xn)=yn 的n次插值多项式,写成如下形式:)x(x)x)(xx(xa)x(xaa1n10n010其中ak(k=0,1,2,n)为待定系数。基函数：(x-x0),(x-x0)(x-x1),，(x-x

3、0)(x-x1)(x-xn-1)定义：给定n+1个插值节点x0 ,x1 ,xn,如下形式的插值多项式称为Newton插值多项式：)x x(x x)x x)(x xx x(x xa a)x x)(x xx x(x xa a)x x(x xa aa a(x x)N N1 1n n1 10 0n n1 10 02 20 01 10 0n n （3.12）其中ak(k=0,1,2,n)为待定系数。无x n ,将出现在系数中它满足以下的递推公式：)x x(x x)x x)(x xx x(x xa a(x x)N N(x x)N N1 1n n1 10 0n n1 1n nn n 牛顿插值多项式Nn(x)

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

5、,x,fx定义m阶差商2阶差商 fxi,xj,xk是指一般地,可定义xi,xi+1,xi+n上的n阶差商：ini1ni1iini2i1ini1iixxx,.,x,fxx,.,x,fxx,.,x,fx021021210 xxx,fxx,fxx,x,例如：fxikjikjkjixxx,fxx,fxx,x,fx为了方便地计算差商，需要建立差商表。表中的箭头指向表示更高阶差商所需要的低阶差商的参与。xifxifxi,xi+1fxi,xi+1,xi+2 fxi,xi+1,xi+2，xi+3x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2 fx0,x1,x2x3f(x3)fx2,x3 f

6、x1,x2,x3 fx0,x1,x2,x3fx1,x2-fx0,x1x2 x0fx1,x2 ,x3-fx0,x1,x2x3 x0 xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2,xi+3002832751256216402081923827493527125915612521650341910251949143649911055101261014例2.11 求 f(x)=x3在节点 x=0,2,3,5,6上 的各阶差商值。解解:计算得如下表计算得如下表性质1 函数 f(x)的 n 阶差商 f x0,x1,xn 可由 f(x0),f(x1),f(xn)的线性组合表

7、示：差商的性质01110010 xx)f(xxx)f(xx,fx)x)(xx(x)f(x)x)(xx(x)f(x)x)(xx(x)f(x，xx,fx120222101120100210n0knk1kk1kk0kkn10)x(x)x)(xx(x)x(x)f(xx.,x,fx验证同学自己验证真漂亮这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。应理解：右端分母中，xk-xk 项永远不出现。或者表示成nki0iikkn0kkkn10)x(x)(x其中,)(x)f(xx.,x,fxn0iik)x(x(x)以上公式可以利用如下的表达式直接验证性质2 差商具有对称性,即在k阶差商 中任意交换两个

8、节点 和 的次序,其值不变。x x,x x,f f x xk k1 10 0i ix xj jx x x x,f f x x x x,f f x x0 01 11 10 0即：x x,x x,.,x x,f f x x x x,x x,.,x x,f f x x1 1-n nn n1 10 0n n1 1-n n1 10 0学生自己验证以上两个公式 x x,x x,f f x x x x,x x,f f x x x x,x x,f f x x1 12 20 00 02 21 12 21 10 0性质3 若fx,x0,x1,xk 是 x 的 m 次多项式,则 fx,x0,x1,xk,xk+1是

9、x 的 m-1 次多项式。注意：右端分子为 m 次多项式,且由差商的对称性可知，当 x=xk+1 时,分子为0,故分子含有因子 xk+1 x，与分母相消后，右端为m-1 次多项式。证：由差商定义 xxx,x,xfx,x,x,x,fxx,x,x,xfx,1kk101kk101kk10常数性质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.所以 性质5 若f(x)存在k阶导数，则f

10、(x)的k阶差商 与其k阶导数之间有下列关系：)x xmma ax x,x xmmi in n(k k!()f f x x,x x,f f x xi in ni i0 0i in ni i0 0(k k)k k1 10 0证明：这个性质可直接用罗尔(Rolle)定理证明。Home牛顿插值多项式的系数与误差余项的导出 牛顿插值多项式的系数与误差余项的导出)x x(x x)x x)(x xx x(x xa a)x x)(x xx x(x xa a)x x(x xa aa a(x x)N N1 1n n1 10 0n n1 10 02 20 01 10 0n n 的系数ak(k=0,n)可根据以下插

11、值条件推出。n n,0 0,1 1,i i)f f(x x)(x xN Ni ii in n)f f(x xa a)(x xN N0 00 00 0n n)f f(x x)x x(x xa aa a)(x xN N1 10 01 11 10 01 1n n)f f(x x)x x)(x xx x(x xa a)x x(x xa aa a)(x xN N2 21 12 20 02 22 20 01 11 10 02 2n n)f f(x x)x x(x x)x x)(x xx x(x xa a)x x(x xa aa a)(x xN Nn n1 1n nn n1 1n n0 0n nn n0 0

12、1 11 10 0n nn n)f f(x xa a0 00 0 x x,f f x x)x x(x x)f f(x x)f f(x x)x x(x xa a)f f(x xa a1 10 00 01 10 01 10 01 10 01 11 1 x x,x x,f f x x x x,x x,f f x x)x x(x x x x,f f x x x x,f f x x)x x(x x x x,f f x x x x,f f x x)x x)(x xx x(x x)x x(x xa a)f f(x x)f f(x xa a2 21 10 02 20 01 11 12 20 01 12 20

13、01 12 21 10 02 20 01 12 20 02 20 02 21 10 02 22 2 一般，用数学归纳法可证明 从上述各个公式中可以解出：将a1=fx0 ,x1 代入下一个等式，得n n),0 0,1 1,(k k x x,x x,f f x xa ak k1 10 0k kn次牛顿(Newton)插值公式的表达式：)x(x)x)(xx(xx,x,fx )x)(xx(xx,x,fx )x(xx,fx)f(x(x)N1n10n10102100100n其余项 为牛顿插值多项式的误差。)x(x)x)(xxx(x,x,x,fx(x)Rn10n10n这里没有假设f(x)可导牛顿插值多项式余

14、项公式的推导：设x为区间a,b上的一点，可得：)x x(x xx xf f x x,)f f(x xf f(x x)0 00 00 0)x x(x x，x xx xf f x x,x x,f f x x x xf f x x,1 11 10 01 10 00 0)x x(x xx x，.,x xf f x x,x x,.,x x,f f x x x x，.,x xf f x x,n nn n0 0n n1 10 01 1-n n0 0从前往后，将后式逐渐带入到前式,即得：根据1阶差商的定义根据2阶差商的定义)x(xx,，xxfx,x,x,fx，xxfx,221021010)x x(x x)x

15、x)(x xx x(x xx x,x xf f x x,)x x(x x)x x)(x xx x(x xx x,x x,f f x x )x x)(x xx x(x xx x,x x,f f x x )x x(x xx x,f f x x)f f(x xf f(x x)n n1 10 0n n0 01 1n n1 10 0n n1 10 01 10 02 21 10 00 01 10 00 0(x x)R R(x x)N Nf f(x x)n nn n推导完毕(下一页PPT有3个节点情况的详细推导)。)x x(x x)x x)(x xx x(x xx x,x xf f x x,(x x)R R

16、n n1 10 0n n0 0n n设x为区间a,b上的一点，可得：将(2)式代入(1)式，得：牛顿插值多项式余项公式的仔细推导（以仅有3个插值节点 的2次插值为例）：210 x,x,x)x x(x xx xf f x x,)f f(x xf f(x x)0 00 00 0(1)x x(x x，x xx xf f x x,x x,f f x x x xf f x x,1 11 10 01 10 00 0(2)x(xx,，xxfx,x,x,fx，xxfx,221021010(3)x x(x x)x x(x x，x xx xf f x x,x x,f f x x)f f(x xf f(x x)0

17、01 11 10 01 10 00 0)()x)(xx(x，xxfx,)x(xx,fx)f(xf(x)10100100(4)将(3)式代入(4)式，得：)x)(xx(x)x(xx,，xxfx,x,x,fx)x(xx,fx)f(xf(x)1022102100100)(整理，得整理，得：)x)(xx)(xx(xx,，xxfx,)x)(xx(x x,x,fx)x(xx,fx)f(xf(x)210210102100100N2(x)R2(x)解释：由插值多项式的存在唯一性定理知，满足同一组插值条件的拉格朗日插值多项式P(x)与牛顿插值多项式Nn(x)实际上是同一个多项式011n1-nnnaxaxaxa

18、的形式以后，所得的表达式是相同的。即将P(x)和Nn(x)所得的多项式表达式，化为n0iin10n)x(xx,x,.,x,fx(x)R 若f(n+1)(x)不存在，则只有使用(*)式来表达误差。Newton插值多项式的误差(不要求f(x)光滑)(*)n0ii1)(nn)x(x1)!(n()f(x)R(*)若f(n+1)(x)存在，则Lagrange插值多项式的误差1)!(n()fx,x,.,x,fx1)(nn10仅在f(n+1)(x)存在情况下才成立。于是评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有规律。Home总结：n次牛顿(New

19、ton)插值公式的表达式为)x x(x x)x x)(x xx x(x xx x,x x,f f x x)x x(x xx x,f f x x)f f(x x(x x)N N1 1n n1 10 0n n1 10 00 01 10 00 0n n 余项 n n0 0i ii i1 1)(n nn n0 0i ii in n1 10 0n n)x x(x x1 1)!(n n()f f)x x(x xx x,x x,.,x x,f f x x(x x)R R若f(n+1)(x)存在利用牛顿插值多项式近似求解的例子 xifxi fxi,xi+1 fxi,xi+1,xi+2 fxi,xi+1,xi+

20、2,xi+3 x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2 fx0,x1,x2 x3f(x3)fx2,x3 fx1,x2,x3 fx0,x1,x2,x3 xifxifxi,xi+1fxi,xi+1,xi+21142(2-1)/(4-1)=1/393(3-2)/(9-4)=1/5(1/5-1/3)/(9-1)=-1/60N2(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 的平方根值，求7 7解1：考虑f(x)=x，利用差商表求差商 n n0 0k kn nk k1 1k

21、kk k1 1k kk k0 0k kk kn n1 10 0)x x(x x)x x)(x xx x(x x)x x(x x)f f(x x x x.,x x,f f x x x x,x x,)f f x xx x)(x xx x(x x x x,)f f x xx x(x x)f f(x x(x x)N N0 01 12 21 10 00 01 10 00 02 2解2：利用公式求差商x149f(x)1230 0.3 33 33 33 33 33 31 13 32 23 31 1x xx xf f(1 1)x xx xf f(0 0)x x,f f x x0 01 11 10 01 10

22、00 0.0 01 16 66 67 76 60 01 1(8 8)(5 5)3 3(3 3)(-5 5)2 2(-3 3)(-8 8)1 1)x x)(x xx x(x xf f(2 2)x x)(x xx x(x xf f(1 1)x x)(x xx x(x xf f(0 0)，x xx x,f f x x1 12 20 02 22 21 10 01 12 20 01 10 02 21 10 0用这种方法解得得系数与方法1的相同。解3：利用拉格朗日方法求插值对多项式求2次插值对多项式)(x(x241)(1(1)(x(x)x)(xx(x)x)(xx(x(x)l2010210949494x14

23、9f(x)123)(x(x151)x)(xx(x)x)(xx(x(x)l210120191)(x(x401)x)(xx(x)x)(xx(x(x)l120210241)()x-(-x2）-（41 9194 103562383342413403152241)(x(x403)(x(x152)(x(x2413*(x)l2*(x)l1*(x)lP(x)210=-1/60 x2+5/12x+3/5 例2.13 已知 x=0,2,3,5 对应的函数值为 y=1,3,2,5,作三次Newton插值多项式。xif(xi)1阶差商阶差商2阶差商阶差商3阶差商阶差商0123132-2/3553/10 x xx x,

24、x x,)f f x xx x)(x xx x)(x xx x(x x x x,x x,)f f x xx x)(x xx x(x x x x,)f f x xx x(x x)f f(x x(x x)N N0 01 12 23 32 21 10 00 01 12 21 10 00 01 10 00 03 3，3 3)2 2)(x xx x(x x1 10 03 32 2)x x(x x3 32 2-x x1 11-3/25/6例例2.14 求求 的值，并估计其误差的值，并估计其误差7 7解：令解：令x xf f(x x)，取，取 x0=4,x1=9,x2=6.25xf(x)f xi,xi+1f

25、xi,xi+1,xi+242936.25 2.50 0.2 24 49 92 23 30 0.1 18 81 18 82 29 96 6.2 25 53 32 2.5 5-0 0.0 00 08 80 08 84 46 6.2 25 50 0.2 20 0.1 18 81 18 82 2,差商表差商表9 9)4 4)(x x0 0.0 00 08 80 08 8(x x4 4)0 0.2 2(x x2 2 )x x)(x xx x(x xx x,x x,f f x x)x x(x xx x,f f x x)f f(x x(x x)N N1 10 02 21 10 00 01 10 00 02

26、22.64848230.0080830.22)7(N20.011719)41(83)x1(83(x)f55 在区间 4,9 上，由2.645751.7 计算器计算结果：6.25)9)(x4)(x(x3!)(f(x)R)3(20.00879|6.25)9).(74)(7(7|3!0.011719|(7)R|2N2(7)=2.7，差一些例2.12中，计算结果为：代入x=7例2.14中，计算结果为：N2(7)=2.64848，好一些例2.15 已知 f(x)=x7+x4+3x+1 求 f 20,21,27 及 f 20,21,27,28 分析：本题 f(x)是一个多项式,故应利用差商的性质解:由差商

27、与导数之间的关系 ()f fn n!1 1 x x,.,x x,f f x xn nn n1 10 00 0(x x)f f 7 7!(x x)f f(8 8)(7 7)，1 17 7!7 7!7 7!()f f,.,2 2,2 2f f 2 2(7 7)7 71 10 00 08 8!0 08 8!()f f,2 2,.,2 2,2 2f f 2 2(8 8)8 87 71 10 0例2.16 给出f(x)的函数表如下，求4次Newton插 值多项式，并且由此计算f(0.596)的值,并 且估计误差 R4(0.596).xif(xi)0.400.410750.550.578150.650.6

28、96750.800.888110.901.026521.051.25382xif(xi)1阶差商阶差商2阶差商阶差商3阶差商阶差商4阶差商阶差商0.40 0.410750.55 0.57815 1.116000.65 0.69675 1.18600 0.280000.80 0.88811 1.27573 0.358920.197300.90 1.02652 1.38410 0.433480.21303 0.031464次Newton插值多项式(需5个节点)如下：N4(x)=0.41075+1.116(x-0.4)+0.28(x-0.4)(x-0.55)+0.1973(x-0.4)(x-0.55

29、)(x-0.65)+0.03146(x-0.4)(x-0.55)(x-0.65)(x-0.8)解：首先计算出差商表如下：经计算得 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 来计算差商，见下页。xif(xi)1阶差阶差商商2阶差商阶差商3阶差商阶差商4阶差商阶差商5阶差商阶差商0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358920.197300.901.026521.384100.433480.213030.031460.5960.631921.298030.421910.214260.02674-0.02408R4(x)-0.02408 X(0.596-0.4)X(0.596-0.55)X(0.596-0.65)X(0.596-0.8)X(0.596-0.9)=-0.02408 X 0.196 X 0.046 X(-0.054)X(-0.204)X(-0.304)0.000000727作业：P48:1,2