牛顿插值法学习教案

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

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

3、suy)有0101()()0 ,( )()()c xc xc xa xxxx所以C(x)应是一个(y )二次多项式。根据插值条件根据(gnj)插值条件：222()P xy可以求出：221221221202120()()()()()()()pxp xyp xaxxxxxxxx重新写p2(x)：第3页/共33页第四页，共33页。21102120001102021010201001011021222021( )( )( )()()()()()()()()()()()()P xP xc xyyyP xyxxxxxxxxxxxxaa xxaxxxxayyyaxxyP xaxxxx其中第4页/共33页第五

4、页，共33页。,ix设插值节点为nifi, 1 , 0,函数值为1,2 , 1 , 0,1nixxhiiiiihhmaxnifxPii, 1 , 0,)(插值条件为具有如下形式设插值多项式)(xP01,na aa其中 为待定系数基函数基函数(hnsh)(hnsh)()()()()(110102010nnxxxxxxaxxxxaxxaaxP第5页/共33页第六页，共33页。)()()()()(110102010nnxxxxxxaxxxxaxxaaxPnifxPxPii, 1 , 0,)()(应满足插值条件000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()(

5、)(12022021022xxxxaxxaafxP12010102022xxxxffxxffa再继续下去待定系再继续下去待定系数的形式数的形式(xngsh)将将更复杂更复杂 。为此引入差商和差分为此引入差商和差分(ch fn)的概念的概念第6页/共33页第七页，共33页。),()()(,jijijijixxjixxxfxfxxf 1阶差商阶差商 /* the 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji 2阶差商阶差商定义定义(dngy)2.(dngy)2.nifxxfii, 1 , 0,)(

6、处的函数值为在互异的节点设11101010111010,.,.,.,.,., kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶阶差差商商第7页/共33页第八页，共33页。)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四阶差商三阶差商二阶差商一阶差商差商的计算方法差商的计算方法( (表格表格(biog)(biog)法法):):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf规定规定(gudng)函数值为零阶差商函数

7、值为零阶差商差商表差商表第8页/共33页第九页，共33页。第9页/共33页第十页，共33页。差商具有差商具有(jyu)(jyu)如下如下性质性质: :且的线性组合表示可由函数值阶差商的,)(,),(),(,)()1(10110kkkxfxfxfxxxxfkxf,110kkxxxxfkikiiiiiiixxxxxxxxxf0110)()()()( Warning: my head is explodingWhat is the point of this formula?差商的值与差商的值与 xi 的顺序的顺序(shnx)无关！无关！第10页/共33页第十一页，共33页。NewtonNewton

8、插值公式插值公式(gngsh)(gngsh)及其余项及其余项第11页/共33页第十二页，共33页。,)()()(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)ai = f x0, , xi NewtonNewton插值公式插值公式(gngsh)

9、(gngsh)及其余项及其余项第12页/共33页第十三页，共33页。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 第13页/共33页第十四页，共33页。NewtonNewton插值公式插值公式(gngsh)(gngsh)及其余项

10、及其余项第14页/共33页第十五页，共33页。例：例： 已知已知x=1,4,9的平方根为的平方根为1,2,3，利用，利用(lyng)牛顿牛顿基本差商基本差商 公式求公式求 的近似值。的近似值。ix149ix1231,iif x x 2 10 333334 1. 320 294. 12 ,iiif x xx 0 20 333330 016679 1. 7解：解：从而得二阶牛顿从而得二阶牛顿(ni dn)基本差商公式为基本差商公式为210 3333310 0166714( ).().()()P xxxx 272 69992( ).P 因此计算得因此计算得 的近似值为的近似值为7第15页/共33页第

11、十六页，共33页。第16页/共33页第十七页，共33页。复习复习(fx)(fx)：多项式插值问题多项式插值问题(wnt)：寻找一个：寻找一个n次多项次多项式，满足下列插值条件：式，满足下列插值条件：niyxPiin,2 , 1 , 0)(函数函数(hnsh)( )yf x在插值节点上的取值为：在插值节点上的取值为：bxxxxan210(),0,1,iif xy in第17页/共33页第十八页，共33页。Lagrange Lagrange 插值方法插值方法(fngf)(fngf)0( )( )nniiiPxlx y njijjijixxxxxl0)()()(其中其中(qzhng)：余项公式余项公

12、式(gngsh)：(1)1( )( )( )(1)!nnnfRxxn)()()(101nnxxxxxxx第18页/共33页第十九页，共33页。Newton Newton 插值方法插值方法(fngf)(fngf)00100120101011( )(),(),()(),()()()nnnnNxf xf xxxxf xxxxxxxf xxxxxxxxx其中其中(qzhng)：12011010 ,kkkkf x xxf x xxf x xxxx余项公式余项公式(gngsh)：00101( ) , . ,().()() , . ,( )nnnnnnRxf x xxxxxxxxf x xxx第19页/共3

13、3页第二十页，共33页。性质性质3 3第20页/共33页第二十一页，共33页。练习练习(linx)74017018312 ,2 ,2 2 ,2 ,2 fxxxff已知 ，求及( )f x分析：本题是一个多项式，可利用差商的性质解：由差商与导数之间的关系(7)017( )7!2 ,2 ,2 177!ff！(8)018( )02 ,2 ,2 088!ff！第21页/共33页第二十二页，共33页。上面我们讨论上面我们讨论(toln)了节点任意分布的插值公式，但了节点任意分布的插值公式，但实际应用时经常会遇到等距节点的情形，这时插值公式实际应用时经常会遇到等距节点的情形，这时插值公式可以进一步简化，计

14、算也简单多了，为了给出等距节点可以进一步简化，计算也简单多了，为了给出等距节点的插值公式，我们先来看一个新概念；的插值公式，我们先来看一个新概念；第22页/共33页第二十三页，共33页。称处的函数值为在等距节点设, 1 ,0,)(0nkfkhxxxfkkkkkfff1处的一阶向前差分在为kxxf)(1, 1 ,0nk1kkkfff处的一阶向后差分在为kxxf)(nk,2 , 11122(/ 2)(/ 2)kkkkkff xhf xhff( )kf xx为在处的中心差分不在函数不在函数(hnsh)表上，表上，要用到函数要用到函数(hnsh)表表上的值上的值111122,kkkkkkffffff第

15、23页/共33页第二十四页，共33页。kkkfff12处的二阶向前差分在为kxxf)(12kkkfff处的二阶向后差分在为kxxf)(利用一阶差分利用一阶差分(ch fn)可以定义二阶差分可以定义二阶差分(ch fn)差分差分(ch fn)第24页/共33页第二十五页，共33页。kmkmkmfff111阶向前差分处的在为mxxfk)(阶向后差分处的在为mxxfk)(111kmkmkmfff可以(ky)用归纳法证明mkmkmff1kkff222kkff333kkff如差分差分(ch fn)第25页/共33页第二十六页，共33页。4433221100fxfxfxfxfxfxkk四阶差分三阶差分二阶

16、差分一阶差分0f1f2f3f02f12f22f03f13f04f差分表差分表4f3f2f1f42f32f22f43f33f44f第26页/共33页第二十七页，共33页。差分差分(ch fn)与函数值之间的关系与函数值之间的关系010121232,yyyyyyyyy 201021021213212232432222yyyyyyyyyyyyyyyyyy 2222()abaabb 1()abab 322010321032212143213222325432333333yyyyyyyyyyyyyyyyyyyyy 3223333()abaa babb 43301043210433121543214332

17、3265432464464464yyyyyyyyyyyyyyyyyyyyyyyy 4322443464()abaa ba babb 归纳归纳(gun)可知，可知，k阶差商可表示为阶差商可表示为 01111kii ki kiikkkkkkyyyCCyCCy 第27页/共33页第二十八页，共33页。在等距节点的前提下在等距节点的前提下, ,差商与差分差商与差分(ch fn)(ch fn)有如下关系有如下关系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hfxfii2222hfiiiiixxff112211,iiiiiixxxxfxxf第28页/共33页第二十

18、九页，共33页。,321iiiixxxxf312223hffii33! 3 hfi332121,iiiiiiiixxxxxfxxxf3322223hfxfii333! 3 hfi,1miiixxxf依此类推(y c li tu)mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!第29页/共33页第三十页，共33页。即是等距节点如果节点,10nxxxnabhnkkhxxk, 1 ,0,0,10kxxxfkkhkf!0由差商与向前(xin qin)差分的关系)(xNnnkkkxxxxff1100)(,Newton插值基本(jbn)公式为如果(rgu)假设thxx01.Newton向前向前(