計算方法牛頓插值

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

2、)(x - x1) ，(x-x0)(x-x1) (x-xn-1)是否構(gòu)成是否構(gòu)成P Pn n的一組基函數(shù)的一組基函數(shù)？01020101( )()()() .().()nnnN xAA x xA x x x xA x xx x 利用插值條件利用插值條件Nn(xj)=f(xj), j=0,1，n代入上式，代入上式，得關(guān)于得關(guān)于Ak (k=0,1，n)的線性代數(shù)方程組的線性代數(shù)方程組基函數(shù)基函數(shù)0010111000100()10()1()()nninniAf xxxAf xxxxxAf x當(dāng)當(dāng)xj 互異時，系數(shù)矩陣非奇異，且容易求解互異時，系數(shù)矩陣非奇異，且容易求解10110()()f xf xAx

3、x10212202110()()()()()/()f xf xf xf xAxxxxxxHow complex the expression are!It is not a difficult thing for a mathematician.We can use notation00()Af x 差商差商( (亦稱均差亦稱均差) ) /* divided difference */),()()(,jijijijixxjixxxfxfxxf 稱為在稱為在xi,xj處的處的1階差商階差商)(,kixxxxfxxfxxxfkikjjikji 稱為在稱為在xi,xj,xk處的處的2階差商階差商k階

4、差商：階差商：01112010,kkkkf xxxf x xxf xxxxx利用插值條件和差商,可求出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( )( )( )( ) , ()( ) , ()( )( ) , ,()()()kkkkN xf xN xf xf x x x xN xf x x x xNxN xf xxx xx xx x 因此，每增加一個結(jié)點，Newton插值多項式只增加

5、一項，克服了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 , , , nf x xx例例1:1:給定f(x)=lnx的數(shù)據(jù)表 xi 2.20 2.40 2.60 2.80 3.00f(xi) 0.78846 0.87547 0.95551 1.02

6、962 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 +0.43505(x-2.20） - 0.0873

7、75(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)差商具有如下性質(zhì)niiinxxfxxxf010)( )(,.,性質(zhì)性質(zhì)1 (差商與函數(shù)值的關(guān)系差商與函數(shù)值的關(guān)系)00, , ,ijnjinf xxxxf xxxx性質(zhì)性質(zhì)2 （對稱性）：（對稱性）：差商的值與結(jié)點排列順序無關(guān)(1)01( ),.,(1)!nnf x xxxnf，01( ) , 1, , , , nf xa bnx xx xa ba b設(shè)在上有階導(dǎo)數(shù)且則存在使得性質(zhì)性質(zhì)3(差商與導(dǎo)數(shù)的關(guān)系差商與導(dǎo)數(shù)

8、的關(guān)系),)()()(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 證明：(1)011( ), .,( )( )(1) !nnnnff xxxxxn，(1)01( ),.,(1)!nnf x xxxnf，定理：定

9、理：NewtonNewton插值多項式的余項為 Rn（x）= fx0 ,x1, xn， x n+1（x）其中 n+1 (x）=(x - x0)(x - x1 )(x - x2 )(x - xn)F由插值多項式的由插值多項式的唯一性可知唯一性可知 Nn(x) Ln(x)，故其余項也相同，即故其余項也相同，即4.4.3 等距節(jié)點的等距節(jié)點的Newton插值公式與差分插值公式與差分一階向前差分一階向前差分 /* forward difference */一階向后差分一階向后差分 /* backward difference */一階中心差分一階中心差分 /* centered difference

10、*/當(dāng)節(jié)點當(dāng)節(jié)點等距等距分布時分布時:),., 0(0nihixxi ( )()( )iiif xf xhf x( )( )()iiif xf xf xh( )()()22iiihhf xf xf x一般地一般地,稱稱k階差分的差分為階差分的差分為k+1階差分階差分,如二階如二階向前和向后差分分別為向前和向后差分分別為22( )( )( ()( )()( )(2 )2 ()( )( )( )( ( )()( )()( )2 ()(2 )iiiiiiiiiiiiiiiiiif xf xf xhf xf xhf xf xhf xhf xf xf xf xf xhf xf xhf xf xhf xh

11、 計算各階差分可按如下差分表進(jìn)行計算各階差分可按如下差分表進(jìn)行.2300110222102333210231230niiiiiinnnnnnxfffffxfxffxfffxffffxfffff其中其中差分具有如下性質(zhì)00( 1),( 1)!()!kkkjjkkjjikij kikij kjjjkfC ffC fkCj kj 性質(zhì)性質(zhì)1(差分與函數(shù)值的關(guān)系差分與函數(shù)值的關(guān)系) 各階差分均可表各階差分均可表示為函數(shù)值的線性組合示為函數(shù)值的線性組合:kkii kff性質(zhì)性質(zhì)2(前差與后差的關(guān)系前差與后差的關(guān)系):0,()!,0,nkknPknfxa h nknkn性質(zhì)性質(zhì)3(多項式的差分多項式的差分

12、) 若若f(x)Pn(n次多項式類次多項式類), 則則性質(zhì)性質(zhì)4(差分與差商的關(guān)系差分與差商的關(guān)系):11,!,!kiiiikkkiiiikkffxxxkhffxxxkh1( )! ,( ),()kkiiii kkkii kfk h f x xxh fxx性質(zhì)性質(zhì)5(差分與導(dǎo)數(shù)的關(guān)系）差分與導(dǎo)數(shù)的關(guān)系）020000( )()(1)(1) (1)1!2!nnnN xN xthtt tt tt nffffn (11)稱公式稱公式(11)(11)為為NewtonNewton向前差分插值公式向前差分插值公式,其余項為其余項為1(1)00(1)()( )()( )(1)!(,)nnnnnt ttnR x

13、R xthhfnx x(12)利用這些性質(zhì)利用這些性質(zhì),可將可將Newton公式進(jìn)一步簡化為公式進(jìn)一步簡化為11110( )() () ,()()() ,nnnnnnnnnN xf xxxf x xxxxxxxf x xx令令x=xn-th, 則當(dāng)則當(dāng)x0 xxn時時,0tn.利用差商與向后差利用差商與向后差分的關(guān)系分的關(guān)系, , 式式(13)(13)可簡化為可簡化為(13)如果將如果將Newton插值公式插值公式改為按節(jié)點改為按節(jié)點xn,xn-1,x0的次的次序排列的序排列的NewtonNewton插值公式插值公式, ,即即(1)110( )( )()( 1)(1)()(1)!nnnnnnn

14、fRxRxthht ttnnxx其余項為其余項為注：注：一般當(dāng)一般當(dāng) x 靠近靠近 x0 時用前插，靠近時用前插，靠近 xn 時用后插，時用后插，故兩種公式亦稱為故兩種公式亦稱為表初公式表初公式和和表末公式表末公式。22( )()(1)(1)2!(1)(1)(1)!nnnnnnnnnNxNxtht tftfft ttnfn 稱式稱式(14)(14)為為NewtonNewton向后差分插值公式向后差分插值公式(14)例例 給定f(x)在等距節(jié)點上的函數(shù)值表如下: xi 0.4 0.6 0.8 1.0 f(xi) 1.5 1.8 2.2 2.8分別用Newton向前和向后差分公式求f(0.5)及f(0.9)的近似值. 解解 先構(gòu)造向前差分表如下: xi fi fi 2 2fi 3 3fi 0.4 1.5 0.6 1.8 0.3 0.8 2.2 0.4 0.1 1.0 2.8 0.6 0.2 0.1 x0=0.4, h=0.2, x3=1.0. 分別用差分表中對角線上的值和最后一行的值,得Newton向前和向后插值公式如下:33(1)(1)