Ch2.2 Newton插值

1、 牛頓插值牛頓插值 （Newtons Interpolation ） Lagrange 插值雖然易算，但若要增加一插值雖然易算，但若要增加一個節(jié)點時，個節(jié)點時，全部基函數(shù)全部基函數(shù) li(x) 都需要重新都需要重新計算。計算。能否重新在Pn中尋找新的基函數(shù) ？希望每加一個節(jié)點時，只附加一項上去即可。本講主要內(nèi)容本講主要內(nèi)容: Newton插值多項式的構(gòu)造插值多項式的構(gòu)造 差商的定義及性質(zhì)差商的定義及性質(zhì) 差分的定義及性質(zhì)差分的定義及性質(zhì) 等距節(jié)點等距節(jié)點Newton插值公式插值公式1,x - x0, (x - x0)(x - x1) ，(x-x0)(x-x1) (x-xn-1)是否構(gòu)成Pn的一

2、組基函數(shù)？01020101( )()()() .().()nnnN xA A x xA x x x xA x xx x 利用插值條件Nn(xj)=f(xj), j=0,1，n代入上式，得關(guān)于Ak (k=0,1，n)的線性代數(shù)方程組基函數(shù)0010111000100()10()1()()nninniAf xxxAf xxxxxAf x當(dāng)xj 互異時，系數(shù)矩陣非奇異，且容易求解10110()()f xf xAxx10212202110()()()()()/()f xf xf xf xAxxxxxxHow complex the expressions are!It is not a difficul

3、t thing for a mathematician.We can use notation00()Af x1差商的定義差商的定義定義1：設(shè)有函數(shù)f (x)以及自變量的一系列互不相等的x0, x1, xn （即在i j時，x i xj）的值 f(xi) , 稱),()()(,jijijijixxjixxxfxfxxf 為f (x)在點xi , xj 處的一階差商，并記作f xi , xj， f xi , xj的幾何意義為過(xi , f(xi) )和(xj , f (xj ) 兩點處割線的斜率 。)(,kixxxxfxxfxxxfkikjjikji 稱為稱為f (x)在點在點xi, xj,

4、xk處的處的二階差商二階差商 。nnnnxxxxxfxxxfxxxf 02111010,稱為稱為f (x)在點在點x0, x1, xn處的處的n階差商階差商。特別地，規(guī)定特別地，規(guī)定f (x)在點在點xi,處的處的零階差商零階差商為為 f xi=f (xi)。利用插值條件和差商,可求出Nn(x)的系數(shù) Ai :00100011( )( ) , () , , ()() ()nnnN xf xf x x x xf xx x x x xx x 00010101(),nnAf xf xAf x xAf x xx0010010001010101( )( )( )( ) , ()( ) , ()( )(

5、) , ,()() ()kkkkN xf xN xf xf x x x xN xf x x x xNxN xf xxx x x xx x 因此，每增加一個結(jié)點，Newton插值多項式只增加一項，克服了Lagrange插值的缺點。 . xk f(xk) 一階差商一階差商 二階差商二階差商 三階差商三階差商 n 階差商階差商差商表差商表123onxxxxx0123 nf xf xf xf xf x0112231, ,nnf x xf x xf x xf xx01212321, ,nnnf x x xf x x xf xxx0123321 , , , nnnnf x x x xf xxxx0 1 ,

6、 , , nf x xx例1：氣溫函數(shù) y = f (x) 的一組觀測數(shù)據(jù)如下時間xi(時)10111213氣溫yi ()20222826求氣溫函數(shù)的近似函數(shù) N3(x)，并求N3(12.5)根據(jù)已知數(shù)據(jù)求出差商表由此表得:N3(x)= 20+2(x-10)+2(x-10)(x-11)-2(x-10)(x-11)(x-12) = -2x3+68x2-764x+2860N3(12.5) = 28.75xiyi一階差商一階差商二階差商二階差商三階差商三階差商1020112221228621326-2-4-2例2:給定f(x)=lnx的數(shù)據(jù)表xi 2.20 2.40 2.60 2.80 3.00f(

7、xi) 0.78846 0.87547 0.95551 1.02962 1.098611.構(gòu)造差商表2.分別寫出二次、四次Newton插值多項式解:差商表 2.200.788462.400.875470.435052.600.955510.400100.0873752.801.029620.370550.0738750.022503.001.098610.344950.064000.016460.00755iixf x一階差商二階差商三階差商 四階差商N2(x)=0.78846 +0.43505(x-2.20) - 0.087375(x-2.20) (x-2.40）N4(x)= 0.78846

8、 +0.43505(x-2.20） - 0.087375(x-2.20)(x-2.40) +0.0225(x-2.20)(x-2.40)(x-2.60) -0.00755(x-2.20)(x-2.40)(x-2.60)(x-2.80)11101010111010,.,.,.,.,., kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階差商：階差商： kiikikxxfxxf010)()(,., 事實上事實上其中其中,)()(01 kiikxxx kijjjiikxxx01)()( 差商的性質(zhì)性質(zhì)1（差商與函數(shù)值的關(guān)系)0101(),()kikinif xf xxx

9、x證：當(dāng) k=1時，等式成立。 當(dāng) k=2 時，有：011201202, ,f x xf x xf x x xxx0112020112()()()()1f xf xf xf xxxxxxx011201202, ,f x xf x xf x x xxx012010201120212()()()()()()()()()f xf xf xxxxxxxxxxxxx012010210122021()()()()()()()()()f xf xf xxxxxxxxxxxxx性質(zhì)2(差商的對稱性) 差商與節(jié)點的順序無關(guān)。差商與節(jié)點的順序無關(guān)。如: , ,ijkikjjikf x x xf x x xf x

10、x x證:由性質(zhì)1可得。性質(zhì)3(差商與導(dǎo)數(shù)的關(guān)系)若若f(x)在包含在包含k+1個互異節(jié)點的區(qū)間個互異節(jié)點的區(qū)間a,b上上k階可導(dǎo)階可導(dǎo),則：則：( )01( ), (a,b)!kkff x xxk此性質(zhì)在后面證明。 插值余項插值余項 /* Newtons Interpolation */,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n 11+ (x x0) 2+ + (x x0)(x xn 1) n 1.

11、)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，故其只是算法不同，故其余項也相同，即余項也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfkxnkn ),(,!)(,.,maxmin)(0 xxkfxxfkk 實際計算過程為實際計算過程為f (x0)f (x1)f (x2)f (xn 1)f (xn)f x0, x1f x1, x2 f x

12、n 1, xnf x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1注：1、所取節(jié)點是n+1個互異節(jié)點。2、等式的左邊是Newton插值余項，右邊是Larange插值余項。但由唯一性可知，二者可以通用，即根據(jù)具體情況來選擇。3、Newton插值余項更具有一般性。這是因為：對于f是由離散點給出的情形或f導(dǎo)數(shù)不存在的情形均適用。)(!)1()()(,.,1)1(10 xnfxxxxfkxnkn 差分，等距節(jié)點插值差分，等距節(jié)點插值如果 xi 是等距

13、節(jié)點，則 xi-xi-1 = h (i=1,2,n)，稱 h 0 為步長。則 xi = x0+ih ( i = 1, 2, , n )。由于這是一種特殊情況，所以牛頓插值公式仍然成立。不過，通過引入差分的概念，可以把牛頓插值公式表示得更加方便。一階向前差分一階向前差分 一階向后差分一階向后差分 當(dāng)節(jié)點當(dāng)節(jié)點等距等距分布時分布時:),.,0(0nihixxi 1. 差分及其性質(zhì)差分及其性質(zhì)1iiiyyy21121()()2iiiiiiiiiyyyyyyyyy 1iiiyyy1112)2iiiiiiiiiyyyyyyyyy 二階向前差分二階向前差分 二階向后差分二階向后差分 向前差分表向前差分表向

14、后差分表的計算與此類似向后差分表的計算與此類似.xiyiyi2yi3yinyix0y0 x1y1y0 x2y2y12y0 x3y3y22y13y0 xnynyn-12yn-23yn-3ny0性質(zhì)性質(zhì)2: ( 前差與后差的關(guān)系前差與后差的關(guān)系 )性質(zhì)性質(zhì)1: ( 差分與函數(shù)值各階差分均可表示為函數(shù)值差分與函數(shù)值各階差分均可表示為函數(shù)值 的線性組合的關(guān)系的線性組合的關(guān)系 )00( 1)( 1)mmjjimij mjmmmjjimij mjyC yyC y mmii myy mjkjkmjjkmkmkmfjm fjmfIfEf00)( 性質(zhì)性質(zhì)3: (函數(shù)值與差分的關(guān)系函數(shù)值與差分的關(guān)系 )性質(zhì)性質(zhì)

15、4 4: (差分與差商的關(guān)系差分與差商的關(guān)系)1111 ,!11 ,!miii mimmiii mimf x xxym hf x xxym h性質(zhì)性質(zhì)5: (差分與導(dǎo)數(shù)的關(guān)系差分與導(dǎo)數(shù)的關(guān)系) 設(shè) f (x) 有 m 階導(dǎo)數(shù)，則有關(guān)系式( )! ,( ) ()1mmmmym h f x xxh f xxiiii mii m給定等距節(jié)點 xi = x0+ih (i=1,2,n)。令x= x0+th , 0 xxn, 0tn, 則 i+1(x) = (x-x0) (x-x1) (x-xi) = t (t-1) (t-2) (t-i) hi+1。2. 等距節(jié)點的牛頓插值等距節(jié)點的牛頓插值牛頓公式牛頓

16、公式).(,.,.)(,)()(1000100 nnnxxxxxxfxxxxfxfxN 牛頓前插公式牛頓前插公式020000()(1)(1)(1)2!nnn(x)= Nx +tht t -t t -t -n+= y +ty +y +ynNDDDLL（1） 牛頓后插公式牛頓后插公式將節(jié)點順序倒置：).(,.,.)(,)()(101xxxxxxfxxxxfxfxNnnnnnnn 注：注：一般當(dāng)一般當(dāng) x 靠近靠近 x0 時用前插，靠近時用前插，靠近 xn 時用后時用后插，計算時分別用向前差分表和向后差分表插，計算時分別用向前差分表和向后差分表.22( )()(1)(1)(1)( 1)( 1)2!n

17、nnnnnnnnxNxtht tt ttnytyyynN=-+=- + -+ -LL實際中，插值點 x 有的靠近 ,有的靠近 ，用兩個差分表會很麻煩。由差分的性質(zhì)2得這個公式只用到向前差分表.用其最后一行的叫表后公式（2）,用其對角線上的值的公式叫表前公式（1）.12220( )()(1)(1)(1)( 1)( 1)2!nnnnnnnnNxNxthytyt tt ttnyyn-=-=-+-+-+ -VLVLV（2）0 xnx向前插值公式和向后插值公式的余項分別為:例3: 已知 y = f (x) 的函數(shù)值表如下:(1)100(1)1100( )()(1)(),(1)!( )()( 1)(1)(),(1)!nnnnnnnnnfR xthht ttnxxnfR xthht ttnxxnxxxx+=-+-=-+LLxi0.40.60.81.0yi1.51.82.22.8求 y = f (0.5) 和 y = f (0.9).這是一個等距節(jié)點的插值問題,構(gòu)造向前差分表由于 所以由表前公式得xiyiyi2yi3yi0.4 1.50.6 1