数值计算方法 第4章插值法 44 Newton插值法 武汉大学数学与统计学院
数值计算方法 第 4 章 插 值 法 4.4 Newton 插值法 武汉大学数学与统计学院
上一讲的简单回顾 ●插值多项式的存在惟一性: 满足插值条件 n(x)=f(x),(i=0,1,2,,n) n次插值多项式Pn(x)=a0+a1x+a2x2+…+anxn存在而且惟 ●插值余项:Rx)=八(x)-Pn(x)=( Wn(x),5x∈(a,b) (n+ ● Lagrange插值多项式 Ln(x)=∑f(x,)1(x) 其中1((x-x)…(x-x=)x-x2)…(x-x)i=0,1,…,n X,-x )(x1-x+1)…(x-x) 称为 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)+C2(x-xo(x-x)+ +cn(x-x0)x-x1)(x-x2)…(x-x21) 使满足 Nn(x,)=f(x),i=0,,n 为了使Nn(x)的形式得到简化,引入如下记号 q(x)=(x-x1=)0-1(x) (x-x0)(x-x1)…(x-x1-1),i=1,2
一 基函数 问题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定义的n1个多项式9(x)(x)…9(x) 称为 Newton插值的以x,1x1,xn.为节点的基函数,即 N,(x=CoP(x)+c(x)+.+C(x) 可以证明这样选取的基函数是线性无关的,由此得 出的问题4.1的解便于求值而且新增加一个节点xn+1时 只需加一个新项Cn+1n1(x)即 n+1(x)=c0q(x)+cq(x)+…+Cn9n(x)+Cn+19n1(x) Pm+(x)=(x-xm)n(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),可以依次确定系数c,c1,cn.例如, 取x=xm,得co=Nn(x0)=f(x0) 取xx1,得N(x)=CG+c1(x1-x)=f(x1) N(x-c f(x-f(xo) 取x=x2,得 N(x2)=C+c(x2-x)+c2(x2-xx2-x)=f(x2)
依据条件(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 =
csN(x)2-c-c(x2)fx)-(x)-f(x)-(x) (x2-x)x2-x) (x2-x0)x2-x) f(x2)-f(x1)+ f (x,)-f(x f(x)-f() x X-X X1-Yo (x2-x0(x2-x) f (,)-f(x,f() -f( 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的一般方法,下面引进差商的概念.
二差商的定义 给定|ab中互不相同的点x0x1x2,,以及fx)在这些点处相 应的函数值f(xof(x1),f(x2)用记号 f(x0)-f(x1) 表示fx)在x0及x两点的一阶差商.用记号 f[x。,x12x2] f[x,x]-f[x12x2] 表示fx)在x0x1x2三点的二阶差商.一般地有了k-阶差商之后 可以定义fx)在x0x1yyx1的阶差商
二 差商的定义 给定[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 − = −
八x,x…,x-=21x…x-/12”到 三 Newton插值公式 由差商定义,有 f(r)=fxo+(c-xoflxscol fx ol= foxx+(x-x1flx, roxl fx, xo x=fxo x21+(c-x2flxxroxkid2I 八xx0,…xnl}=fx0,…yxnl+(xxn)/xx0,……,xnl 将以上各式,由下而上逐步代入,得到 fr)=fxo+(x-xofxo+(x-xo(x-xufxosixx2 +…+(x-x0)…(x-xn1)f(x0,…,yxn (5) +(x-x0)…(x-xn1)(x-xnD/Lx,x0,…xnl
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)
记 Na(x)=fx0)+(x-x0)fx0x1]+(x-x0)(x-x1)/(x0x12l +…+(x-x0)…(x-xn1)f{x0,…,nl Rn(x)=(x-x0)…x-xn)八{x,x0,…xnl=升xx0,… nw+1(x)(7) 则(5)可表示为 f(r=Nn()+rn(c) 显然,Nn(x)是次数不超过n的多项式,且有 Rn(x)=fLx,x0,…, noW+1(x)=0,=0,1,…,n 即 Nn(i =f(xi, i=0,1,,n 由此可知,如此构造的函数N(x)就是问题1的解,且 C;=f1x0,…,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)