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

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

2、點時，原來已算出的所有節(jié)點時，原來已算出的所有 lj(x) 都需要重新計算，都需要重新計算，使使計算量加大。計算量加大。 l 差商及其性質(zhì)差商及其性質(zhì)l 牛頓插值公式牛頓插值公式l 牛頓插值余項牛頓插值余項l 差分以及等距節(jié)點牛頓插值多項式差分以及等距節(jié)點牛頓插值多項式4.3 差商與牛頓插值公式差商與牛頓插值公式Newton (16241727) 由線性代數(shù)知識可知由線性代數(shù)知識可知, , 任何一個任何一個 n n 次多項式都可表示成次多項式都可表示成: :)()(,),)(, 1110100nxxxxxxxxxxxx這這n+1 n+1 個多項式的線性組合個多項式的線性組合. .問：問：是否可

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

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

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

6、 關(guān)于節(jié)點關(guān)于節(jié)點 的二階差商的二階差商kjixxxxf,)(缺倒數(shù)第二個節(jié)點缺最后一個節(jié)點最后一個節(jié)點倒數(shù)第二個節(jié)點稱稱可見：一個高階差商可由兩個低一階的差商得到可見：一個高階差商可由兩個低一階的差商得到,110kkxxxxf1110210,kkkkkxxxxxfxxxxf缺倒數(shù)第二個節(jié)點缺最后一個節(jié)點稱稱kkxxxx,110為為 關(guān)于節(jié)點關(guān)于節(jié)點 的的 k 階差商階差商)(xf最后一個節(jié)點倒數(shù)第二個節(jié)點由此定義由此定義, ,顯然顯然: :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) 在這些點上在這些點上函數(shù)值的線性組合函數(shù)值的線性組合, ,即即kkxxxx,110kjiiijkjjkkxxxfxxxxf001101)(,10101)(jjiiijjxxxf100011010110,xxfxxfxxffxxf例如例如: :可

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

9、序, ,差商的值不變差商的值不變3. 3. 差商的計算方法：差商的計算方法：差商表差商表)()()()()()(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ù)導數(shù)之間的關(guān)系差商與函數(shù)導數(shù)之間的關(guān)系 當當 f(k)(x) 在包含節(jié)點在包含節(jié)點 x0, x1, , xk 的區(qū)間存在時的區(qū)間存在

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

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

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

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

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

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