数值计算方法 第4章插值法 44 Newton插值法 武汉大学数学与统计学院
数值计算方法 第 4 章 插 值 法 4.4 Newton 插值法 武汉大学数学与统计学院
上一讲的简单回顾 ●插值多项式的存在惟一性 满足插值条件 Pn(x)=fx,(i=0,1,2,…,n n次插值多项式Pa(x)=a0+a1x+a2x2+,…+amx存在而且惟 ●插值余项:Rx)=f(x)-Pa(x)= (n+1) mn(x),5∈(a,b) ● Lagrange插值多项式 Ln(x)=∑f(x)(x) 其中1(/(x-x)…(x-x)x-x)…(x-x)1=01.n (x1-x0)…(x1-x21)x1-x+1)…(x-xn) 称为 Lagrange插值基函数
上一讲的简单回顾 ● 插值多项式的存在惟一性: 满足插值条件 Pn (xi )=f(xi ), ( i=0,1,2,…,n) n次插值多项式Pn (x)=a0+a1x+a2x 2+……+anx n 存在而且惟一. ● 插值余项: Rn (x)= f(x)- Pn (x)= , ● Lagrange插值多项式 ( 1) 1 ( ) ( ) ( 1)! n x n f w x n + + + ( , ) x a b 0 ( ) ( ) ( ) n n i i i L x f x l x = = 0 1 1 0 1 1 ( ) ( )( ) ( ) ( ) ( ) ( )( ) ( ) i i n i i i i i i i n x x x x x x x x l x x x x x x x x x − + − + − − − − = − − − − 其中 ,i =0,1,…,n 称为Lagrange插值基函数
优点:具有严格的规律性,便于记忆 缺点:不具有承袭性即每当增加一个节点时,不仅要增加求 和的项数,而且以前的各项也必须重新计算 为了克服这一缺点,本讲将建立具有承袭性的插值公式 Newton插值公式 本讲主要内容: ● Newton插值多项式的构造 ●差商的定义及性质 ●差分的定义及性质 ●等距节点 Newton插值公式
优点: 具有严格的规律性,便于记忆. 缺点: 不具有承袭性,即每当增加一个节点时,不仅要增加求 和的项数,而且以前的各项也必须重新计算. 为了克服这一缺点,本讲将建立具有承袭性的插值公式— Newton插值公式. 本讲主要内容: ● Newton插值多项式的构造 ● 差商的定义及性质 ● 差分的定义及性质 ● 等距节点Newton插值公式
基函数 问题1求作n次多项式Nn(x) Nn(x)=Co+C(x-xo)+C,(x-xo(x-x)+ +Cn(x-xo(x-x(x-x2) (x-xu-pd) 使满足 Nn(x,)=f(x),i=0,1,…n 为了使N(x)的形式得到简化引入如下记号 (x)三1 q2(x)=(x-x21)21(x) =(x-x0)(x-x1)…(x-x1-1),i=1,2,n
一 基函数 问题1 求作n次多项式 使满足 ( ) N x n 0 1 0 2 0 1 0 1 2 1 ( ) ( ) ( )( ) ( )( )( ) ( ) n n n N x c c x x c x x x x c x x x x x x x x − = + − + − − + + − − − − ( ) ( ), 0,1, N x f x i n n i i = = (2) 为了使 N x n ( ) 的形式得到简化,引入如下记号 0 1 1 0 1 1 ( ) 1 ( ) ( ) ( ) ( )( ) ( ) , 1,2, i i i i x x x x x x x x x x x i n − − − = − = − − − = (3) (1)
定义由式(3)定义的n+1个多项式(x)9(x)…9,(x) 称为 Newton插值的以xm,x1…,xn为节点的基函数即 N,(x)=Co(x)+c9(x)+.+C,n(x) 可以证明,这样选取的基函数是线性无关的,由此得 出的问题41的解便于求值而且新增加一个节点xm+时 只需加一个新项Cn+1n1(x)即 n+1 )+C1(x)+…+cnn(x)+Ccn+(9n+1(x) 而 9n1(x)=(x-xn)1(x)
定义 由式(3)定义的n+1个多项式 称为Newton插值的以x0 ,,x1 ,…,xn为节点的基函数,即 可以证明,这样选取的基函数是线性无关的,由此得 出的问题4.1的解便于求值,而且新增加一个节点 xn+1时 只需加一个新项 即 而 0 1 ( ), ( ), , ( ) n x x x 0 0 1 1 ( ) ( ) ( ) ( ) N x c x c x c x n n n = + + + 1 1() c x n n + + 1 1() n n c x + + 1 1( ) n n c x + + 1 0 0 1 1 1 1 ( ) ( ) ( ) ( ) ( ) N x c x c x c x c x n n n n n + + + = + + + + 1 ( ) ( ) ( ) n n n x x x x + = − (4)
依据条件(2),可以依次确定系数cnc1,cn,例如, 取x=xm,1得co=Nn(x)=f(x) 取x=x1,得 =C +c,(x (x1)-Co_f(x1)-f(x) X-X 取x=x2得 N(x2)=+c(x2-x)+c(20x2-x)=(x)
依据条件(2),可以依次确定系数c0 ,c1 ,…,cn..例如, 取x=x0 ,,得 取x=x1 ,得 1 0 1 0 1 1 0 1 0 ( ) ( ) ( ) N x c f x f x n c x x x x − − = = − − 0 0 0 ( ) ( ) n c N x f x = = 1 0 1 1 0 1 ( ) ( ) ( ) N x c c x x f x n = + − = 取x=x2 ,得 0 1 2 0 2 2 0 2 1 2 c c x x c x x x x f x + − + − − = ( ) ( )( ) ( ) 2 ( ) N x n =
f(x1)-f(x) f(x,)-f(ro N(x1)-C0-C(x2-x) (, -rox,r) (x2-x)x2-x) f(x1)-f(x) f(x)-(x) (x)-f((2 x1-x0 (x2-x)( f(r2)-f(x,f(x)-f(x x2-x1 x 为了得到计算系数c的一般方法,下面引进差商的概念
. 1 0 2 0 2 0 2 0 1 2 0 1 0 2 2 0 2 1 2 0 2 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( )( ) n f x f x f x f x x x N x c c x x x x c x x x x x x x x − − − − − − − − = = − − − − 1 0 1 0 2 1 1 0 2 0 1 0 1 0 2 0 2 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) f x f x f x f x f x f x x x x x x x x x x x x x − − − + − − − − − = − − 2 1 1 0 2 0 2 1 1 0 ( ) ( ) ( ) ( ) ( ) f x f x f x f x x x x x x x − − = − − − − 为了得到计算系数ci的一般方法,下面引进差商的概念.
二差商的定义 给定|a,b中互不相同的点x0x1x2,,以及几x)在这些点处相 应的函数值f(x0)f(x1)2f(x2),…,用记号 f(x0)-f(x1) XI Xo-x1 表示f(x)在x0及x1两点的一阶差商用记号 f[x0,x1x2] f[x0,x一f[x1,x2 表示fx)在x0x1x2三点的二阶差商一般地,有了k-阶差商之后, 可以定义fx)在x0x1yx的阶差商
二 差商的定义 给定[a,b]中互不相同的点x0 ,x1 ,x2 ,…,以及f(x)在这些点处相 应的函数值f(x0 ),f(x1 ),f(x2 ),…,用记号 表示f(x)在x0及x1两点的一阶差商. 用记号 表示f(x)在x0 ,x1 ,x2三点的二阶差商. 一般地,有了k-1阶差商之后, 可以定义f(x)在x0 ,x1 ,..,xk的k阶差商 0 1 0 1 0 1 ( ) ( ) [ , ] f x f x f x x x x − = − 0 1 1 2 0 1 2 0 2 [ , ] [ , ] [ , , ] f x x f x x f x x x x x − = −
f[o,x,,,xkI-f[,x2, .,xI 三 Newton插值公式 由差商定义,有 f(x)=fxo+(x-xorflxs ol fx,=foxx+(x-xiflx, xoxxll fx, xox-fxoi2+(x-x2fxrorrir2I fx,x0,…xnl=f{x0,…yxnl+(xxn/lx, 将以上各式,由下而上逐步代入,得到 f(r)=fxo+(x-xofxo+(x-xo(x-xufroirr2I +…+(x-x0)…、(x-xn1)x1,…,xnl +(x-x0)…(x-xn1)(x-xn)/x,x0…xl
0 1 1 1 2 0 1 0 [ , , , ] [ , , , ] [ , , , ] k k k k f x x x f x x x f x x x x x − − = − 三 Newton插值公式 由差商定义,有 f(x)= f[x0 ]+(x-x0 )f[x,x0 ] f[x,x0 ]= f[x0 ,x1 ]+(x-x1 )f[x,x0 ,x1 ] f[x,x0 ,x1 ]= f[x0 ,x1 ,x2 ]+(x-x2 )f[x,x0 ,x1 ,x2 ] ……….. f[x,x0 ,…xn-1 ]= f[x0 ,…,xn ]+(x-xn )f[x,x0 ,….,xn ] 将以上各式，由下而上逐步代入，得到 f(x)= f(x0 )+(x-x0 ) f[x0 ,x1 ]+(x-x0 )(x-x1 ) f[x0 ,x1 ,x2 ] +…+(x-x0 )…(x-xn-1 ) f[x0 ,…,xn ] +(x-x0 )…(x-xn-1 )(x-xn )f[x,x0 ,…xn ] (5)
记 Nn()=f(o)+(x-xo fxo x+x-xo(x-xufxokirr2I +…+(x-x0)…(xxn1)fxo,…,x (6) Rn(x)=(x-x0)(xxa)xx0,…n}=fx,x0y…,xnlwn+1(x)(7 则(5)可表示为 f(x)=Nn(x)+rnO (8) 显然,N(x)是次数不超过n的多项式,且有 Rn(x)=fxx0…,nlwn+1(x1)=0,i0,1,…,n 即 (x)=f(x) i=0,1. 由此可知如此构造的函数N(x)就是问题1的解,且 c,÷=0,1
记 Nn (x)= f(x0 )+(x-x0 ) f[x0,x1 ]+(x-x0 )(x-x1 ) f[x0 ,x1 ,x2 ] +…+(x-x0 )…(x-xn-1 ) f[x0 ,…,xn ] (6) Rn (x)= (x-x0 )…(x-xn ) f[x,x0 ,…,xn ]= f[x,x0 ,…,xn ]wn+1(x) (7) 则(5)可表示为 f(x)= Nn (x)+ Rn (x) (8) 显然, Nn (x)是次数不超过n的多项式,且有 Rn (xi )= f[x,x0 ,…,xn ]wn+1(xi )=0, i=0,1,…,n 即 Nn (xi )= f(xi ) , i=0,1,…,n 由此可知,如此构造的函数Nn (x)就是问题1的解,且 ci =f[x0 ,…,xi ] , i=0,1,…,n (9)