第二章牛顿插值法

1、数值分析第二章 插值法均差与牛顿插值公式均差与牛顿插值公式Lagrange插值多项式的缺点插值多项式的缺点)(xljnjiiijixxxx0)()(nj,2 , 1 ,0我们知道我们知道,Lagrange,Lagrange插值多项式的插值基函数为插值多项式的插值基函数为理论分析中很方便，理论分析中很方便，但是但是当当插值节点增减插值节点增减时时全部插值全部插值基函数基函数就要随之就要随之变化变化，整个公式也将发生变化，这在，整个公式也将发生变化，这在实际计算中是很实际计算中是很不方便不方便的；的；Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函

2、数全部基函数 li(x) 都需重新算过。都需重新算过。两点直线公式(xk,yk)(xk+1,yk+1)11111111( )()( )(kkkkkkkkkkkkkkyyL xyxxxxxxxxL xyyxxxx点斜式）两点式）考虑点斜式，两点为(x0,y0)(x1,y1):1010010( )()yyP xyxxxx在此基础上增加一个节点(x2,y2)，则过这三个点的插值多项式21( )( )( )P xP xc xC(x)应是一个二次多项式。21( )( )( )P xP xc x2010021111()()()()P xP xyP xP xy所以有0101()()0 ,( )()()c x

3、c xc xa xxxx所以C(x)应是一个二次多项式。根据插值条件根据插值条件：222()P xy可以求出：221221221202120()()()()()()()pxp xyp xaxxxxxxxx重新写p2(x)：21102120001102021010201001011021222021( )( )( )()()()()()()()()()()()()P xP xc xyyyP xyxxxxxxxxxxxxaa xxaxxxxayyyaxxyP xaxxxx其中,ix设插值节点为nifi, 1 , 0,函数值为1,2 , 1 ,0,1nixxhiiiiihhmaxnifxPii, 1

4、 , 0,)(插值条件为具有如下形式设插值多项式)(xP01,na aa其中 为待定系数基函数基函数)()()()()(110102010nnxxxxxxaxxxxaxxaaxP)()()()()(110102010nnxxxxxxaxxxxaxxaaxPnifxPxPii, 1 , 0,)()(应满足插值条件000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa再继续下去待定系再继续下去待定系数的形式将更复杂数的形式将更复杂 。为此引入差商和差分的概念为此引入差

5、商和差分的概念 divided difference */),()()(,jijijijixxjixxxfxfxxf 1阶差商阶差商 /* the 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji 2阶差商阶差商定义定义2.2.nifxxfii, 1 , 0,)(处的函数值为在互异的节点设11101010111010,.,.,.,.,., kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶阶差差商商)()()()()()(4433221100 xfxxfxxfxxfx

6、xfxxfxkk四阶差商三阶差商二阶差商一阶差商差商的计算方法差商的计算方法( (表格法表格法):):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf规定函数值为规定函数值为零阶差商零阶差商差商表差商表差商具有如下性质差商具有如下性质: :且的线性组合表示可由函数值阶差商的,)(,),(),(,)()1(10110kkkxfxfxfxxxxfkxf,110kkxxxxfkikiiiiiiixxxxxxxxxf0110)()()()( Warning: my head is explo

7、dingWhat is the point of this formula?差商的值与差商的值与 xi 的顺序无关！的顺序无关！NewtonNewton插值公式及其余项插值公式及其余项,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf 12 n+11+ (x x0) 2+ + (x x0)(x xn 1) n+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)

8、ai = f x0, , xi NewtonNewton插值公式及其余项插值公式及其余项ix0 x1x2x3xif x0()f x1()f x2()f x3()f x1,iif x x 01,f xx12,f x x23,f xx12,iiif x xx 012,f xx x123,f x xx123 ,iiiif x xxx 0123,f xx xx00100121001110( )()() ,()() ,()()() ,nnnP xf xxxf x xxxxxf xx xxxxxxxf xx x NewtonNewton插值公式及其余项插值公式及其余项例：例： 已知已知x=1,4,9的平方

9、根为的平方根为1,2,3，利用牛顿基本差商，利用牛顿基本差商 公式求公式求 的近似值。的近似值。ix149ix1231,iif x x 2 10 333334 1. 320 294. 12 ,iiif x xx 0 20 333330 0166791. 7解：解：从而得二阶牛顿基本差商公式为从而得二阶牛顿基本差商公式为210 3333310 0166714( ).().()()P xxxx 272 69992( ).P 因此计算得因此计算得 的近似值为的近似值为7复习：复习：多项式插值问题：寻找一个多项式插值问题：寻找一个n次多项式，次多项式，满足下列插值条件：满足下列插值条件：niyxPii

10、n,2 , 1 ,0)(函数函数( )yf x在插值节点上的取值为：在插值节点上的取值为：bxxxxan210(),0,1,iif xy inLagrange Lagrange 插值方法插值方法0( )( )nniiiPxlx y njijjijixxxxxl0)()()(其中：其中：余项公式：余项公式：(1)1( )( )( )(1)!nnnfRxxn)()()(101nnxxxxxxxNewton Newton 插值方法插值方法00100120101011( )(),(),()(),()()()nnnnNxf xf xxxxf xxxxxxxf xxxxxxxxx 其中：其中：120110

11、10 ,kkkkf x xxf x xxf x xxxx余项公式：余项公式：00101( ) , . ,().()() , . ,( )nnnnnnRxf x xxxxxxxxf x xxx性质性质3 3练习练习74017018312 ,2 ,2 2 ,2 ,2 fxxxff已知 ，求及( )f x分析：本题是一个多项式，可利用差商的性质解：由差商与导数之间的关系(7)017( )7!2 ,2 ,2 177!ff！(8)018( )02 ,2 ,2 088!ff！上面我们讨论了节点任意分布的插值公式，但实际应上面我们讨论了节点任意分布的插值公式，但实际应用时经常会遇到等距节点的情形，这时插值公

12、式可以用时经常会遇到等距节点的情形，这时插值公式可以进一步简化，计算也简单多了，为了给出等距节点的进一步简化，计算也简单多了，为了给出等距节点的插值公式，我们先来看一个新概念；插值公式，我们先来看一个新概念；称处的函数值为在等距节点设, 1 , 0,)(0nkfkhxxxfkkkkkfff1处的一阶向前差分在为kxxf)(1, 1 ,0nk1kkkfff处的一阶向后差分在为kxxf)(nk,2 , 11122(/ 2)(/ 2)kkkkkff xhf xhff( )kf xx为在处的中心差分不在函数表上，要用到不在函数表上，要用到函数表上的值函数表上的值111122,kkkkkkffffffk

13、kkfff12处的二阶向前差分在为kxxf)(12kkkfff处的二阶向后差分在为kxxf)(利用一阶差分可以定义二阶差分利用一阶差分可以定义二阶差分差分差分kmkmkmfff111阶向前差分处的在为mxxfk)(阶向后差分处的在为mxxfk)(111kmkmkmfff可以用归纳法证明mkmkmff1kkff222kkff333kkff如差分差分4433221100fxfxfxfxfxfxkk四阶差分三阶差分二阶差分一阶差分0f1f2f3f02f12f22f03f13f04f差分表差分表4f3f2f1f42f32f22f43f33f44f差分与函数值之间的关系差分与函数值之间的关系010121

14、232,yyyyyyyyy 201021021213212232432222yyyyyyyyyyyyyyyyyy 2222()abaabb 1()abab 322010321032212143213222325432333333yyyyyyyyyyyyyyyyyyyyy 3223333()abaa babb 433010432104331215432143323265432464464464yyyyyyyyyyyyyyyyyyyyyyyy 4322443464()a baa ba babb 归纳可知，归纳可知，k阶差商可表示为阶差商可表示为 01111kii ki kiikkkkkkyyyCC

15、yCCy 在等距节点的前提下在等距节点的前提下, ,差商与差分有如下关系差商与差分有如下关系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hfxfii2222hfiiiiixxff112211,iiiiiixxxxfxxf,321iiiixxxxf312223hffii33! 3 hfi332121,iiiiiiiixxxxxfxxxf3322223hfxfii333! 3 hfi,1miiixxxf依此类推mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!即是等距节点如果节点,10nxxxnabhnkkhxxk, 1 ,0,0,

16、10kxxxfkkhkf!0由差商与向前差分的关系)(xNnnkkkxxxxff1100)(,Newton插值基本公式为如果假设thxx01.Newton向前向前(差分差分)插值公式插值公式10)(kjjxx)(xk1000)(kjjhxthx10)(kjhjtkkhkf!0nkf10)(10kjhjt!0kfknkf10 )(10kjjt)(xNnnkkkxxxxff1100)(,)(0thxNn)(xRn)()!1()(1)1(xnfnn则插值公式化为其余项)(0thxRn)!1()()1(nfnnjnjth01)(化为)(0thxRn)!1()()1(nfnnjnjth01)(!0kfknkf10 )(10kjjt)(0thxN