第二章牛頓插值法

1、精選課件數(shù)值分析第二章 插值法均差與牛頓插值公式均差與牛頓插值公式精選課件Lagrange插值多項式的缺點插值多項式的缺點)(xljnjiiijixxxx0)()(nj,2 , 1 ,0我們知道我們知道,Lagrange,Lagrange插值多項式的插值基函數(shù)為插值多項式的插值基函數(shù)為理論分析中很方便，理論分析中很方便，但是但是當(dāng)當(dāng)插值節(jié)點增減插值節(jié)點增減時時全部插值全部插值基函數(shù)基函數(shù)就要隨之就要隨之變化變化，整個公式也將發(fā)生變化，這在，整個公式也將發(fā)生變化，這在實際計算中是很實際計算中是很不方便不方便的；的；Lagrange 插值雖然易算，但若要增加一個節(jié)點時，插值雖然易算，但若要增加一個

2、節(jié)點時，全部基函數(shù)全部基函數(shù) li(x) 都需重新算過。都需重新算過。精選課件兩點直線公式(xk,yk)(xk+1,yk+1)11111111( )()( )(kkkkkkkkkkkkkkyyL xyxxxxxxxxL xyyxxxx點斜式）兩點式）考慮點斜式，兩點為(x0,y0)(x1,y1):1010010( )()yyP xyxxxx在此基礎(chǔ)上增加一個節(jié)點(x2,y2)，則過這三個點的插值多項式21( )( )( )P xP xc xC(x)應(yīng)是一個二次多項式。精選課件21( )( )( )P xP xc x2010021111()()()()P xP xyP xP xy所以有0101(

3、)()0 ,( )()()c xc xc xa xxxx所以C(x)應(yīng)是一個二次多項式。根據(jù)插值條件根據(jù)插值條件：222()P xy可以求出：221221221202120()()()()()()()pxp xyp xaxxxxxxxx重新寫p2(x)：精選課件21102120001102021010201001011021222021( )( )( )()()()()()()()()()()()()P xP xc xyyyP xyxxxxxxxxxxxxaa xxaxxxxayyyaxxyP xaxxxx其中精選課件,ix設(shè)插值節(jié)點為nifi, 1 , 0,函數(shù)值為1,2 , 1 ,0,1n

4、ixxhiiiiihhmaxnifxPii, 1 , 0,)(插值條件為具有如下形式設(shè)插值多項式)(xP01,na aa其中 為待定系數(shù)基函數(shù)基函數(shù))()()()()(110102010nnxxxxxxaxxxxaxxaaxP精選課件)()()()()(110102010nnxxxxxxaxxxxaxxaaxPnifxPxPii, 1 , 0,)()(應(yīng)滿足插值條件000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa再繼續(xù)下去待定系再繼續(xù)下去待定系數(shù)的形式將更復(fù)

5、雜數(shù)的形式將更復(fù)雜 。為此引入差商和差分的概念為此引入差商和差分的概念精選課件 divided difference */),()()(,jijijijixxjixxxfxfxxf 1階差商階差商 /* the 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji 2階差商階差商定義定義2.2.nifxxfii, 1 , 0,)(處的函數(shù)值為在互異的節(jié)點設(shè)11101010111010,.,.,.,.,., kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階階差差商商精選課

6、件)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四階差商三階差商二階差商一階差商差商的計算方法差商的計算方法( (表格法表格法):):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf規(guī)定函數(shù)值為規(guī)定函數(shù)值為零階差商零階差商差商表差商表精選課件精選課件差商具有如下性質(zhì)差商具有如下性質(zhì): :且的線性組合表示可由函數(shù)值階差商的,)(,),(),(,)()1(10110kkkxfxfxfxxxxfkxf,110kkxxxxfkikiiiiiiixxxx

7、xxxxxf0110)()()()( Warning: my head is explodingWhat is the point of this formula?差商的值與差商的值與 xi 的順序無關(guān)！的順序無關(guān)！精選課件NewtonNewton插值公式及其余項插值公式及其余項精選課件,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf 12 n+11+ (x x0) 2+ + (x x0)(x xn 1) n+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).

8、(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)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 xxxxx

9、xxf xx x 精選課件NewtonNewton插值公式及其余項插值公式及其余項精選課件例：例： 已知已知x=1,4,9的平方根為的平方根為1,2,3，利用牛頓基本差商，利用牛頓基本差商 公式求公式求 的近似值。的近似值。ix149ix1231,iif x x 2 10 333334 1. 320 294. 12 ,iiif x xx 0 20 333330 016679 1. 7解：解：從而得二階牛頓基本差商公式為從而得二階牛頓基本差商公式為210 3333310 0166714( ).().()()P xxxx 272 69992( ).P 因此計算得因此計算得 的近似值為的近似值為7精

10、選課件精選課件復(fù)習(xí)：復(fù)習(xí)：多項式插值問題：尋找一個多項式插值問題：尋找一個n次多項式，次多項式，滿足下列插值條件：滿足下列插值條件：niyxPiin,2 , 1 ,0)(函數(shù)函數(shù)( )yf x在插值節(jié)點上的取值為：在插值節(jié)點上的取值為：bxxxxan210(),0,1,iif xy in精選課件Lagrange Lagrange 插值方法插值方法0( )( )nniiiPxlx y njijjijixxxxxl0)()()(其中：其中：余項公式：余項公式：(1)1( )( )( )(1)!nnnfRxxn)()()(101nnxxxxxxx精選課件Newton Newton 插值方法插值方法0

11、0100120101011( )(),(),()(),()()()nnnnNxf xf xxxxf xxxxxxxf xxxxxxxxx其中：其中：12011010 ,kkkkf x xxf x xxf x xxxx余項公式：余項公式：00101( ) , . ,().()() , . ,( )nnnnnnRxf x xxxxxxxxf x xxx精選課件性質(zhì)性質(zhì)3 3精選課件練習(xí)練習(xí)74017018312 ,2 ,2 2 ,2 ,2 fxxxff已知 ，求及( )f x分析：本題是一個多項式，可利用差商的性質(zhì)解：由差商與導(dǎo)數(shù)之間的關(guān)系(7)017( )7!2 ,2 ,2 177!ff！(8)

12、018( )02 ,2 ,2 088!ff！精選課件上面我們討論了節(jié)點任意分布的插值公式，但實際應(yīng)上面我們討論了節(jié)點任意分布的插值公式，但實際應(yīng)用時經(jīng)常會遇到等距節(jié)點的情形，這時插值公式可以用時經(jīng)常會遇到等距節(jié)點的情形，這時插值公式可以進一步簡化，計算也簡單多了，為了給出等距節(jié)點的進一步簡化，計算也簡單多了，為了給出等距節(jié)點的插值公式，我們先來看一個新概念；插值公式，我們先來看一個新概念；精選課件稱處的函數(shù)值為在等距節(jié)點設(shè), 1 , 0,)(0nkfkhxxxfkkkkkfff1處的一階向前差分在為kxxf)(1, 1 ,0nk1kkkfff處的一階向后差分在為kxxf)(nk,2 , 111

13、22(/ 2)(/ 2)kkkkkff xhf xhff( )kf xx為在處的中心差分不在函數(shù)表上，要用到不在函數(shù)表上，要用到函數(shù)表上的值函數(shù)表上的值111122,kkkkkkffffff精選課件kkkfff12處的二階向前差分在為kxxf)(12kkkfff處的二階向后差分在為kxxf)(利用一階差分可以定義二階差分利用一階差分可以定義二階差分差分差分精選課件kmkmkmfff111階向前差分處的在為mxxfk)(階向后差分處的在為mxxfk)(111kmkmkmfff可以用歸納法證明mkmkmff1kkff222kkff333kkff如差分差分精選課件4433221100fxfxfxfx

14、fxfxkk四階差分三階差分二階差分一階差分0f1f2f3f02f12f22f03f13f04f差分表差分表4f3f2f1f42f32f22f43f33f44f精選課件差分與函數(shù)值之間的關(guān)系差分與函數(shù)值之間的關(guān)系010121232,yyyyyyyyy 201021021213212232432222yyyyyyyyyyyyyyyyyy 2222()abaabb 1()abab 322010321032212143213222325432333333yyyyyyyyyyyyyyyyyyyyy 3223333()abaa babb 433010432104331215432143323265432

15、464464464yyyyyyyyyyyyyyyyyyyyyyyy 4322443464()abaa ba babb 歸納可知，歸納可知，k階差商可表示為階差商可表示為 01111kiikikiikkkkkkyyyCCyCCy 精選課件在等距節(jié)點的前提下在等距節(jié)點的前提下, ,差商與差分有如下關(guān)系差商與差分有如下關(guān)系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hfxfii2222hfiiiiixxff112211,iiiiiixxxxfxxf精選課件,321iiiixxxxf312223hffii33! 3 hfi332121,iiiiiiiixxxx

16、xfxxxf3322223hfxfii333! 3 hfi,1miiixxxf依此類推mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!精選課件即是等距節(jié)點如果節(jié)點,10nxxxnabhnkkhxxk, 1 , 0,0,10kxxxfkkhkf!0由差商與向前差分的關(guān)系)(xNnnkkkxxxxff1100)(,Newton插值基本公式為如果假設(shè)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