第4章_插值與擬合-牛頓法

1、第第4 4章章 插值與擬合插值與擬合4.3 4.3 差商與牛頓插值公式差商與牛頓插值公式Lagrange Lagrange 插值多項(xiàng)式的基函數(shù)插值多項(xiàng)式的基函數(shù)：)()()()()()()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnjxxxxnjiiiji, 2 , 1 , 0)()(0優(yōu)點(diǎn)：優(yōu)點(diǎn)：形式對(duì)稱，有很強(qiáng)的規(guī)律性，便于記憶。形式對(duì)稱，有很強(qiáng)的規(guī)律性，便于記憶。 缺點(diǎn)：缺點(diǎn)：(1)(1) 重復(fù)計(jì)算多重復(fù)計(jì)算多, 導(dǎo)致計(jì)算量大；導(dǎo)致計(jì)算量大； (2)(2) 插值基函數(shù)插值基函數(shù) lj(x) 依賴于所有節(jié)點(diǎn)，當(dāng)增加插值依賴于所有節(jié)點(diǎn)，當(dāng)增加插值節(jié)

2、點(diǎn)時(shí)，原來(lái)已算出的所有節(jié)點(diǎn)時(shí)，原來(lái)已算出的所有 lj(x) 都需要重新計(jì)算，都需要重新計(jì)算，使使計(jì)算量加大。計(jì)算量加大。 l 差商及其性質(zhì)差商及其性質(zhì)l 牛頓插值公式牛頓插值公式l 牛頓插值余項(xiàng)牛頓插值余項(xiàng)l 差分以及等距節(jié)點(diǎn)牛頓插值多項(xiàng)式差分以及等距節(jié)點(diǎn)牛頓插值多項(xiàng)式4.3 差商與牛頓插值公式差商與牛頓插值公式Newton (16241727) 由線性代數(shù)知識(shí)可知由線性代數(shù)知識(shí)可知, , 任何一個(gè)任何一個(gè) n n 次多項(xiàng)式都可表示成次多項(xiàng)式都可表示成: :)()(,),)(, 1110100nxxxxxxxxxxxx這這n+1 n+1 個(gè)多項(xiàng)式的線性組合個(gè)多項(xiàng)式的線性組合. .問(wèn)：?jiǎn)枺菏欠窨?/p>

3、以將這是否可以將這 n+1n+1個(gè)多項(xiàng)式作為插值基函數(shù)？個(gè)多項(xiàng)式作為插值基函數(shù)？ 已知函數(shù)已知函數(shù) f(x) 的插值節(jié)點(diǎn)的插值節(jié)點(diǎn) xi 及相應(yīng)函數(shù)值及相應(yīng)函數(shù)值 , ,將上述線性無(wú)關(guān)的多項(xiàng)式取作將上述線性無(wú)關(guān)的多項(xiàng)式取作NewtonNewton插值法的基函數(shù)插值法的基函數(shù), ,即令：即令：),.,1 , 0(nifi101100)()()()(1)(jkkjjxxxxxxxxxx), 2 , 1(njNewtonNewton插值基函數(shù)插值基函數(shù)則相應(yīng)的插值多項(xiàng)式為則相應(yīng)的插值多項(xiàng)式為: : njjkkjnjjjnxxaaxaxP11000)()()(式中式中, , 為待定參數(shù)為待定參數(shù), ,

4、它們可利用插值條件它們可利用插值條件 來(lái)求來(lái)求, ,即令：即令：naaa,.,10iinfxP)(可以求得：可以求得：injjkkijinfxxaaxP 1100)()(),.,1 , 0(ni 000)(faxPn101101)()(fxxaaxPn00fa 01011xxffa21202202102)()()(fxxxxaxxaaxPn12010102022xxxxffxxffa323130331303203103)()()()()(fxxxxxxaxxxxaxxaaxPn23120101020213010103033xxxxxxffxxffxxxxffxxffaja依此類推依此類推, ,

5、可求得可求得 . .為標(biāo)記、推導(dǎo)、記憶方便為標(biāo)記、推導(dǎo)、記憶方便, ,給出給出差商差商定義定義, ,可得參數(shù)可得參數(shù) 的一般表達(dá)式。的一般表達(dá)式。),.,1 , 0(njaj這也太復(fù)雜這也太復(fù)雜了吧！了吧！為為 關(guān)于節(jié)點(diǎn)關(guān)于節(jié)點(diǎn) 的一階均差的一階均差( (差商差商) )kixxxf,)(4.3.1 4.3.1 差商及其性質(zhì)差商及其性質(zhì)1.1.差商的定義差商的定義: :設(shè)給定函數(shù)設(shè)給定函數(shù) 在在 個(gè)互異的節(jié)點(diǎn)個(gè)互異的節(jié)點(diǎn) 處的函數(shù)值為處的函數(shù)值為 , ,稱稱1)(nxfnnfffxxx,.,.,1010)(,ijxxffxxfijijji)(,kjixxxxfxxfxxxfjkjikikji為為

6、 關(guān)于節(jié)點(diǎn)關(guān)于節(jié)點(diǎn) 的二階差商的二階差商kjixxxxf,)(缺倒數(shù)第二個(gè)節(jié)點(diǎn)缺最后一個(gè)節(jié)點(diǎn)最后一個(gè)節(jié)點(diǎn)倒數(shù)第二個(gè)節(jié)點(diǎn)稱稱可見(jiàn)：一個(gè)高階差商可由兩個(gè)低一階的差商得到可見(jiàn)：一個(gè)高階差商可由兩個(gè)低一階的差商得到,110kkxxxxf1110210,kkkkkxxxxxfxxxxf缺倒數(shù)第二個(gè)節(jié)點(diǎn)缺最后一個(gè)節(jié)點(diǎn)稱稱kkxxxx,110為為 關(guān)于節(jié)點(diǎn)關(guān)于節(jié)點(diǎn) 的的 k 階差商階差商)(xf最后一個(gè)節(jié)點(diǎn)倒數(shù)第二個(gè)節(jié)點(diǎn)由此定義由此定義, ,顯然顯然: :00fa 01011xxffa12010102022xxxxffxxffa,10 xxf121020,xxxxfxxf,210 xxxf用歸納法可證：用歸

7、納法可證：,.,10kkxxxfa 將上述結(jié)果代入：將上述結(jié)果代入：njjkkjnxxxxxffxP110100)(,.,)()(xNninjjkkijinfxxaaxP 1100)()(),.,1 , 0(ni 2.2.差商的性質(zhì)差商的性質(zhì)性質(zhì)性質(zhì)1 1：差商與函數(shù)值的關(guān)系：差商與函數(shù)值的關(guān)系 f(x) 關(guān)于關(guān)于 的的 k 階差商是階差商是 f(x) 在這些點(diǎn)上在這些點(diǎn)上函數(shù)值的線性組合函數(shù)值的線性組合, ,即即kkxxxx,110kjiiijkjjkkxxxfxxxxf001101)(,10101)(jjiiijjxxxf100011010110,xxfxxfxxffxxf例如例如: :可

8、以用數(shù)學(xué)歸納法證明可以用數(shù)學(xué)歸納法證明利用對(duì)稱性利用對(duì)稱性, ,可對(duì)可對(duì) f(x) 關(guān)于關(guān)于 的的 k 階差商變形階差商變形kxxx,.,10,.,.,0211110kkkkkxxxxxfxxxxf00211211,xxxxxxfxxxxfkkkkkk01210121,xxxxxxfxxxxfkkkkkk注：上式是計(jì)算中常用的差商公式，可建立差商表注：上式是計(jì)算中常用的差商公式，可建立差商表. .缺第一個(gè)節(jié)點(diǎn)缺最后一個(gè)節(jié)點(diǎn)最后一個(gè)節(jié)點(diǎn)第一個(gè)節(jié)點(diǎn)性質(zhì)性質(zhì)2 2：對(duì)稱性：對(duì)稱性 差商對(duì)于定義它的節(jié)點(diǎn)而言是對(duì)稱的差商對(duì)于定義它的節(jié)點(diǎn)而言是對(duì)稱的, ,也就是說(shuō)任意也就是說(shuō)任意調(diào)換節(jié)點(diǎn)的次序調(diào)換節(jié)點(diǎn)的次

9、序, ,差商的值不變差商的值不變3. 3. 差商的計(jì)算方法：差商的計(jì)算方法：差商表差商表)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四階差商三階差商二階差商一階差商,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf規(guī)定函數(shù)值為規(guī)定函數(shù)值為零階差商零階差商!)(,.,)(10kfxxxfkk性質(zhì)性質(zhì)3:3:差商與函數(shù)導(dǎo)數(shù)之間的關(guān)系差商與函數(shù)導(dǎo)數(shù)之間的關(guān)系 當(dāng)當(dāng) f(k)(x) 在包含節(jié)點(diǎn)在包含節(jié)點(diǎn) x0, x1, , xk 的區(qū)間存在時(shí)的區(qū)間存在

10、時(shí), ,在在 x0, x1, , xk 之間必存在一點(diǎn)之間必存在一點(diǎn), ,使得使得內(nèi)容歸納內(nèi)容歸納NewtonNewton插值基函數(shù)插值基函數(shù): :101100)()()()(1)(jkkjjxxxxxxxxxx), 2 , 1(nj njjkkjnjjjnxxaaxaxP11000)()()(并形式上給出并形式上給出NewtonNewton插值多項(xiàng)式插值多項(xiàng)式: :naaa,.,10式中式中, , 待定待定. .,.,10kkxxxfa 通過(guò)引進(jìn)均差通過(guò)引進(jìn)均差/ /差商的概念差商的概念, ,可以將系數(shù)表示為：可以將系數(shù)表示為：4.3.2 4.3.2 牛頓插值公式牛頓插值公式為為 f (x)

11、 關(guān)于節(jié)點(diǎn)關(guān)于節(jié)點(diǎn) 的的 n 次次Newton插值多項(xiàng)式插值多項(xiàng)式. ),.,1 , 0(nixi1.1.定義定義: : 稱稱)()()()()(110102010nnnxxxxxxaxxxxaxxaaxNnkkjjkxxx ,x ,xfxf110100)()(nkkkxx ,x ,xfxf1100)()(- (1)由插值多項(xiàng)式的唯一性由插值多項(xiàng)式的唯一性, Newton 插值公式的余項(xiàng)插值公式的余項(xiàng)為為:)()!1()(11xnMxRnnn實(shí)用的余項(xiàng)估計(jì)式：實(shí)用的余項(xiàng)估計(jì)式：)()()()()(xLxfxNxfxRnnn)()!1()(1)1(xnfnn- (2)Lagrange插值多項(xiàng)式導(dǎo)

12、數(shù)型余項(xiàng)若將若將 視為一個(gè)節(jié)點(diǎn)視為一個(gè)節(jié)點(diǎn), ,則由一階均差定義則由一階均差定義 ), 1 , 0( , nixxi)(,)()(000 xxxxfxfxf)(,.,.,.,11011020nnnnxxxxxfxxxfxxxfxxxxfxxfxxxf101010,4.3.3 4.3.3 牛頓插值余項(xiàng)牛頓插值余項(xiàng))(,.,.,.,01010nnnnxxxxxfxxxfxxxf同理同理, ,由二階均差定義由二階均差定義有有有有)(,110100 xxxxxfxxfxxfxxxfxfxxf000)()(,因此可得因此可得: :)()()(000 xxx , xfxfxf)()(0110100 xxx

13、xx ,x , xfx ,xfxf)()()(10100100 xxxxx ,x , xfxxx ,xfxfnjjnnkkjjkxxx ,x ,x , xfxxx ,x ,xfxf010110100)()()()()(xRxNnnNewton插值多項(xiàng)式差商型余項(xiàng)njjnnxxxxxxfxN010)(,)(- (3)4.3.4 4.3.4 差分及其等距節(jié)點(diǎn)牛頓插值多項(xiàng)式差分及其等距節(jié)點(diǎn)牛頓插值多項(xiàng)式定義定義4.44.4 設(shè)設(shè) f (x) 在等距節(jié)點(diǎn)在等距節(jié)點(diǎn) 處的處的函數(shù)值為函數(shù)值為 稱稱,0khxxknk, 1 , 0,kfkkkfff12為為 f (x)在在 xk 處的處的 二階向前差分二階

14、向前差分為為 f (x)在在 xk 處的處的 一階向前差分一階向前差分kkkfff1等距節(jié)點(diǎn)插值是比較常見(jiàn)的情況等距節(jié)點(diǎn)插值是比較常見(jiàn)的情況, ,為簡(jiǎn)化計(jì)算為簡(jiǎn)化計(jì)算, ,引進(jìn)差分的概念引進(jìn)差分的概念. .依此類推依此類推: :kmkmkmfff111為為 f (x)在在 xk 處的處的 m 階向前差分階向前差分4433221100fxfxfxfxfxfxkk四階差分三階差分二階差分一階差分0f1f2f3f02f12f22f03f13f04f差分的計(jì)算方法差分的計(jì)算方法: :差分表差分表在在等距節(jié)點(diǎn)等距節(jié)點(diǎn)的前提下的前提下, ,差商與差分有如下關(guān)系差商與差分有如下關(guān)系: :,321iiiixx

15、xxf221223hhffii33! 3 hfiiiiiiiiixxxxxfxxxf321321,差商與差分的關(guān)系差商與差分的關(guān)系,1iixxfhfiiiiixxff11,21iiixxxfiiiiiixxxxfxxf2121,hhfhfii21222hfi依此類推：依此類推：,1miiixxxfmimhmf!差分表示的差分表示的 Newton Newton 插值公式插值公式NewtonNewton向前向前( (差分差分) )插值公式插值公式), 1 , 0( ,0nabhnkkhxxk記插值點(diǎn)：記插值點(diǎn)：)0(0tthxxnxxx,10如果節(jié)點(diǎn)如果節(jié)點(diǎn) 是等距的是等距的, 即即10)(kjjxx1000)(kjjhxthx-(7)(10kjkjth)(10kjhjt由差