第五章插值與曲線擬合

1、計算方法河北大學電信學院5.1 5.1 問題的提出問題的提出 函數(shù)解析式未知函數(shù)解析式未知,通過實驗觀測得到的一組數(shù)據(jù)通過實驗觀測得到的一組數(shù)據(jù), 即在即在某個區(qū)間某個區(qū)間a, b上給出一系列點的函數(shù)值上給出一系列點的函數(shù)值 yi= f(xi) 或者給出函數(shù)表或者給出函數(shù)表y=f(x)y=p(x)xx0 x1x2xnyy0y1y2yn5.2 插值法的基本原理插值法的基本原理設函數(shù)設函數(shù)y=y=f( (x) )定義在區(qū)間定義在區(qū)間 a, b 上上, , 是是 a, b 上取定的上取定的n+1個互異節(jié)點個互異節(jié)點, ,且在這些點處的函數(shù)值且在這些點處的函數(shù)值 為已知為已知 , ,即即 若存在一個若

2、存在一個f(x)的近似函數(shù)的近似函數(shù) , ,滿足滿足則稱則稱 為為f( (x) )的一個的一個插值函數(shù)插值函數(shù), f( (x) )為為被插函數(shù)被插函數(shù), 點點xi為為插值節(jié)點插值節(jié)點, 稱稱(5.1)(5.1)式為式為插值條件插值條件, 而誤差函數(shù)而誤差函數(shù)R(x)= 稱為稱為插值余項插值余項, 區(qū)間區(qū)間 a, b 稱為稱為插值插值區(qū)間區(qū)間, 插值點在插值區(qū)間內(nèi)的稱為插值點在插值區(qū)間內(nèi)的稱為內(nèi)插內(nèi)插, 否則稱否則稱外插外插 nxxx,10)(,),(),(10nxfxfxf)(iixfy )(x), 2 , 1()()(nixfxii)(x(5.1)(5.1)()(xxf插值函數(shù)插值函數(shù) 在在

3、n+1個互異插值節(jié)點個互異插值節(jié)點 ( (i=0,1,n )處與處與 相等相等, ,在其它點在其它點x就用就用 的值作為的值作為f( (x) ) 的近似值。這一過程稱為的近似值。這一過程稱為插值插值，點，點x稱為插值點。換稱為插值點。換句話說句話說, , 插值就是根據(jù)被插函數(shù)給出的函數(shù)表插值就是根據(jù)被插函數(shù)給出的函數(shù)表“插出插出”所要點的函數(shù)值。用所要點的函數(shù)值。用 的值作為的值作為f( (x) )的近似值的近似值, ,不僅希不僅希望望 能較好地逼近能較好地逼近f( (x) ), ,而且還希望它計算簡單而且還希望它計算簡單 。由由于代數(shù)多項式具有數(shù)值計算和理論分析方便的優(yōu)點。所于代數(shù)多項式具有

4、數(shù)值計算和理論分析方便的優(yōu)點。所以本章主要介紹代數(shù)插值。即求一個次數(shù)不超過以本章主要介紹代數(shù)插值。即求一個次數(shù)不超過n n次的多次的多項式。項式。 )(xix)(ixf)(x)(x)(x0111)(axaxaxaxPnnnn0111)(axaxaxaxPnnnn滿足滿足 ), 2 , 1 , 0()()(nixfxPii則稱則稱P(x)P(x)為為f(x)f(x)的的n n次插值多項式。這種插值法通常稱次插值多項式。這種插值法通常稱為代數(shù)插值法。其幾何意義如下圖所示為代數(shù)插值法。其幾何意義如下圖所示 y y=P(x) y=f(x) y1 yn x0 x1 xn x 定理定理5.1 n次代數(shù)插值

5、問題的解是存在且惟一的次代數(shù)插值問題的解是存在且惟一的 證明證明: : 設設n n次多項式次多項式 0111)(axaxaxaxPnnnn是函數(shù)是函數(shù) 在區(qū)間在區(qū)間 a, ba, b上的上的n+1n+1個互異的節(jié)點個互異的節(jié)點 ( (i=0,1,2,i=0,1,2,n ),n )上的插值多項式上的插值多項式, ,則求插值多項式則求插值多項式P(x)P(x)的問題就歸結(jié)為求它的系數(shù)的問題就歸結(jié)為求它的系數(shù) ( (i=0,1,2,i=0,1,2,n ),n )。 )(xfy ixia由插值條件由插值條件: (: (i=0,1,2,i=0,1,2,n),n),可得可得 )()(iixfxp)()()

6、(01111011111100011010nnnnnnnnnnnnnnnnxfaxaxaxaxfaxaxaxaxfaxaxaxa 這是一個關于待定參數(shù)這是一個關于待定參數(shù) 的的n+1階線性方階線性方程組程組, ,其系數(shù)矩陣行列式為其系數(shù)矩陣行列式為 naaa,10niijjinnnnnnxxxxxxxxxxxV110212110200)(111 稱為稱為Vandermonde（范德蒙）行列式，因范德蒙）行列式，因xixj（當當ij），），故故V0。根據(jù)解線性方程組的克萊姆根據(jù)解線性方程組的克萊姆（Gramer）法則，方程組的解法則，方程組的解 存在惟一，從而存在惟一，從而P(x)P(x)被惟一

7、確定。被惟一確定。 naaa,10惟一性說明，不論用何種方法來構(gòu)造，也不論用何種惟一性說明，不論用何種方法來構(gòu)造，也不論用何種形式來表示插值多項式形式來表示插值多項式, ,只要滿足插值條件只要滿足插值條件(5.1)(5.1)其結(jié)其結(jié)果都是相互恒等的。果都是相互恒等的。 5.3 拉格朗日（拉格朗日（Lagrange）插值插值 為了構(gòu)造滿足插值條件為了構(gòu)造滿足插值條件 (i=0,1,2,n )的便于使用的插值多項式的便于使用的插值多項式P(x),P(x),先考察幾種簡單情形先考察幾種簡單情形, ,然后再推廣到一般形式。然后再推廣到一般形式。5.3.1 線性插值與拋物插值線性插值與拋物插值（1）線性

8、插值）線性插值線性插值是代數(shù)插值的最簡單形式。假設給定了函數(shù)線性插值是代數(shù)插值的最簡單形式。假設給定了函數(shù)f(x)f(x)在兩個互異的點在兩個互異的點 ， 的值，的值，, ,現(xiàn)要求用線性函數(shù)現(xiàn)要求用線性函數(shù) 近似地代替近似地代替f(x)f(x)。選選擇參數(shù)擇參數(shù)a和和b, 使使 。稱這樣的線性函數(shù)。稱這樣的線性函數(shù)P(x)P(x)為為f(x)f(x)的線性插值函數(shù)的線性插值函數(shù) 。)()(iixfxp0 x1x)(),(1100 xfyxfybaxxp)() 1 , 0)()(ixfxpii線性插值的幾何意義線性插值的幾何意義: :用用通過點通過點 和和 的直線近似地代替曲線的直線近似地代替曲

9、線 y=f(x)=f(x)由解析幾何知道由解析幾何知道, ,這條直線用點斜式表示為這條直線用點斜式表示為 )(,(00 xfxA)(,(11xfxB)()(001010 xxxxyyyxp10100101)(yxxxxyxxxxxp01011010)(,)(xxxxxlxxxxxl0)(, 1)(1000 xlxl1)(,0)(1101xlxl1)()(10 xlxl為了便于推廣，記為了便于推廣，記 這是一次函這是一次函數(shù)數(shù), ,且有性質(zhì)且有性質(zhì) y=f(x) p(x)=ax+b A(x.0,f(x.0) B(x.1,f(x.1) )(0)(1)(kikixlkiik 與與 稱為線性插值基函數(shù)

10、。且有稱為線性插值基函數(shù)。且有 )(0 xl)(1xl1 , 0,)(10kxxxxxlkjjjkjk于是線性插值函數(shù)可以表示為與基函數(shù)的線性組合于是線性插值函數(shù)可以表示為與基函數(shù)的線性組合 1100)()()(yxlyxlxp例例5.1 5.1 已知已知 , , , , 求求 10100 11121 115y解解: : 這里這里x0=100，y0=10，x1=121，y1=11, 利用線性插值利用線性插值 1110012110010121100121)(xxxp714.10)115(115py（2 2） 拋物插值拋物插值 拋物插值又稱二次插值，它也是常用的代數(shù)插值之一。拋物插值又稱二次插值，

11、它也是常用的代數(shù)插值之一。設已知設已知f(x)f(x)在三個互異點在三個互異點x0，x1，x2的函數(shù)值的函數(shù)值y0，y1，y2，要構(gòu)造次數(shù)不超過二次的多項式要構(gòu)造次數(shù)不超過二次的多項式使?jié)M足二次插值條件：使?jié)M足二次插值條件：這就是二次插值問題。其幾何意義是用經(jīng)過這就是二次插值問題。其幾何意義是用經(jīng)過3個點個點 的拋物線的拋物線 近似代替曲線近似代替曲線 , ,如下圖所示。因此也稱之為拋物插值。如下圖所示。因此也稱之為拋物插值。 0122)(axaxaxP)2 , 1 , 0()(iyxPii),(),(),(221100yxyxyx)(xPy )(xfy y y=L2(x) y0 y1 y1

12、y=f(x) O x0 x1 x2 x P(x)的參數(shù)的參數(shù)直接由插值條件決定，直接由插值條件決定，即即 滿足下面滿足下面的代數(shù)方程組：的代數(shù)方程組： 210,aaa210,aaa222221012121100202010yxaxaayxaxaayxaxaa222211200111xxxxxx該三元一該三元一次方程組次方程組的系數(shù)矩陣的系數(shù)矩陣 的行列式是范德蒙行列式，當?shù)男辛惺绞欠兜旅尚辛惺?，?時，時，方程組的解唯一。方程組的解唯一。 210 xxx為了與下一節(jié)的為了與下一節(jié)的Lagrange插值公式比較插值公式比較, ,仿線性插值仿線性插值, ,用用基函數(shù)的方法求解方程組。先考察一個特殊

13、的二次插值基函數(shù)的方法求解方程組。先考察一個特殊的二次插值問題：問題： 求二次式求二次式 , ,使其滿足條件：使其滿足條件： )(0 xl0)(,0)(, 1)(201000 xlxlxl這個問題容易求解。由上式的后兩個條件知這個問題容易求解。由上式的后兩個條件知: : 是是 的兩個零點。于是的兩個零點。于是 21,xx)(0 xl)()(210 xxxxcxl再由另一條件再由另一條件 確定系數(shù)確定系數(shù) 1)(00 xl)(12010 xxxxc)()()(2010210 xxxxxxxxxl從而導出從而導出 類似地可以構(gòu)造出滿足條件：類似地可以構(gòu)造出滿足條件：的插值多項式的插值多項式 0)(

14、, 0)(, 1)(210111xlxlxl)()()(2101201xxxxxxxxxl及滿足條件：及滿足條件： 的插值多項式的插值多項式 0)(,0)(, 1)(120222xlxlxl)()()(1202102xxxxxxxxxl這樣構(gòu)造出來的這樣構(gòu)造出來的 稱為拋物插值的基函數(shù)稱為拋物插值的基函數(shù) )(),(),(210 xlxlxl取已知數(shù)據(jù)取已知數(shù)據(jù) 作為線性組合系數(shù)作為線性組合系數(shù), ,將基函數(shù)將基函數(shù) 線性組合可得線性組合可得 210,yyy)(),(),(210 xlxlxl212021012101200201021)()()()()()()(yxxxxxxxxyxxxxxx

15、xxyxxxxxxxxxP容易看出容易看出, ,P(x)P(x)滿足條件滿足條件 )2 , 1 , 0()(iyxPii5.3.2 拉格朗日插值多項式拉格朗日插值多項式 我們看到我們看到, ,兩個插值點可求出一次插值多項式兩個插值點可求出一次插值多項式, ,而三而三個插值點可求出二次插值多項式。插值點增加到個插值點可求出二次插值多項式。插值點增加到n+1個時個時, ,也就是通過也就是通過n+1個不同的已知點個不同的已知點, ,來構(gòu)造一個次數(shù)為來構(gòu)造一個次數(shù)為n的代數(shù)多項式的代數(shù)多項式P(x)。與推導拋物插與推導拋物插值的基函數(shù)類似值的基函數(shù)類似, ,先構(gòu)造一個特殊先構(gòu)造一個特殊n次多項式次多項

16、式 的插的插值問題值問題, ,使其在各節(jié)點使其在各節(jié)點 上滿足上滿足 ), 1 , 0)(,(niyxii)(xliix0)(, 0)(, 1)(, 0)(, 0)(110nkkkkkkkkxlxlxlxlxl)(0)(1)(kikixlkiik即即 由條件由條件 ( ) ( )知知, , 都是都是n n次次 的零點的零點, ,故可設故可設 0)(ikxlki nkkxxxxx,1110)(xlk)()()()(1110nkkkkxxxxxxxxxxAxl其中其中 為待定常數(shù)。由條件為待定常數(shù)。由條件 , ,可求得可求得 kA1)(kkxlkA1)(0nkjjjkkxxA于是于是 nkjjjk

17、kxxA0)(1代入上式代入上式, ,得得nkjjjkjnkjjjknkjjjkxxxxxxxxxl000)()()(稱稱 為關于基點為關于基點 的的n n次插值基函數(shù)次插值基函數(shù)( (i=0,1,i=0,1,n),n) )(xlkix以以n+1個個n次基本插值多項式次基本插值多項式為基礎為基礎, ,就能直接寫出滿足插值條件就能直接寫出滿足插值條件的的n次代數(shù)插值多項式。次代數(shù)插值多項式。事實上，由于每個插值基函數(shù)事實上，由于每個插值基函數(shù)都是都是n次值多項式次值多項式, ,所以他們的線性組合所以他們的線性組合), 1 ,0)(nkxlk), 2 , 1 , 0()()(nixfxPiinny

18、xlyxlyxlxP)()()()(1100), 1 ,0)(nkxlknkkkyxlxP0)()(是次數(shù)不超過是次數(shù)不超過n n次的多項式次的多項式 , 稱形如（稱形如（5.8）式的插）式的插值多項式為值多項式為n次拉格朗日插值多項式。并記為次拉格朗日插值多項式。并記為 （5.8）)(xLn例例5.2 已知已知y=f(x)的函數(shù)表的函數(shù)表 求線性插值多項式求線性插值多項式, 并計算并計算x=1.5 的值的值X 1 3 y 1 225.1)5.1()5.1()1(2121311313)(10100101pfxxxyxxxxyxxxxxp解解: 由線性插值多項式公式得由線性插值多項式公式得例例5

19、.3 已知已知x=1, 4, 9 的平方根值的平方根值, 用拋物插值公式用拋物插值公式, 求求 (x0 x1)(x0 x2)(xx1)(xx2)y0+(x1x0)(x1x2)(xx0)(xx2)y1+(x2x0)(x2x1)(xx0)(xx1)y2p2(7) =x0=1, x1=4, x2=9y0=1, y1=2, y2=3 (14)(19)(74)(79)* 1 +(41)(49)(71)(79)* 2+(91)(94)(71)(74)* 3= 2.7p2(x) =7例例5.4 已知函數(shù)已知函數(shù)y=f(x)在節(jié)點上滿足在節(jié)點上滿足 x x0 x1 x2 y y0 y1 y2 求二次多項式求二

20、次多項式 p(x) = a0 + a1x + a2x2 使之滿足使之滿足 p(xi) = yi i=0, 1, 2解解: 用待定系數(shù)法用待定系數(shù)法, 將各節(jié)點值依次代入所求多項式將各節(jié)點值依次代入所求多項式, 得得解上述方程解上述方程, 將求出的將求出的a0, a1, a2 代入代入p(x) = a0 + a1x + a2x2 即得所求二次多項式即得所求二次多項式 201202012120122aa xa xyaa xa xyaa xa xy例例5.5 求過點求過點(0,1)、(1,2)、(2,3)的三點插值多項式的三點插值多項式13) 12)(02 () 1)(0(2) 21)(01 ()

21、2)(0(1) 20)(10 () 2)(1()(xxxxxxxxp解解:由由Lagrange 插值公式插值公式（給定的三個點在一條直線上）（給定的三個點在一條直線上）212021012101200201021)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxP例例5.6 已知已知f (x)的觀測數(shù)據(jù)的觀測數(shù)據(jù) x 0 1 2 4 f (x) 1 9 23 3 構(gòu)造構(gòu)造Lagrange插值多項式插值多項式解解 四個點可構(gòu)造三次四個點可構(gòu)造三次Lagrange插值多項式插值多項式: :基函數(shù)為基函數(shù)為 1478781)40)(20)(10()4)(2)(1()(

22、230 xxxxxxxlxxxxxxxl38231)41)(21)(01 ()4)(2)(0()(231xxxxxxxl2324541)42)(12)(02()4)(1)(0()(xxxxxxxl12181241)24)(14)(04()2)(1)(0()(233Lagrange插值多項式為插值多項式為 )()(303xlyxLkkk)(3)(23)(9)(3210 xlxlxlxl12144541123xxx為便于上機計算為便于上機計算, ,常將拉格朗日插值多項式常將拉格朗日插值多項式( (5.8)改寫成改寫成 nknkiiikiknxxxxyxL00)(34)()()()()(233322

23、1100 xxyxlyxlyxlyxlxp 例例5.7 已知已知f(x)的觀測數(shù)據(jù)的觀測數(shù)據(jù) x 1 2 3 4f(x) 0 -5 -6 3構(gòu)造插值多項式構(gòu)造插值多項式 解解: 四個點可以構(gòu)造三次插值多項式四個點可以構(gòu)造三次插值多項式, 將數(shù)據(jù)將數(shù)據(jù) 代入插值公式，有代入插值公式，有 這個例子說明這個例子說明p(x)的項數(shù)不超過的項數(shù)不超過n+1項，但可以有項，但可以有 缺項。缺項。 ttxxxxjkj j = 0 , ,k -1 ,k + 1 , ,n 輸 入 (xi,yi), n i= 0 ,1 , ,n 0 y 0 t 1 = t k = n ? 輸 出y y + t yk y k +

24、1 k n y 5.3.3 拉格朗日插值算法實現(xiàn)拉格朗日插值算法實現(xiàn) x0 x1 xixi+1 xn-1 xny=f(x)y=p(x)ab在插值區(qū)間在插值區(qū)間 a, b 上用上用插值多項式插值多項式p(x)近似代替近似代替f(x), 除了除了在插值節(jié)點在插值節(jié)點xi上沒有誤差外，在其它點上一般是存在誤上沒有誤差外，在其它點上一般是存在誤差的。差的。若記若記 R (x) = f(x) - p(x) 則則 R(x) 就是用就是用 p(x) 近似代替近似代替 f(x) 時的截斷誤差時的截斷誤差, 或稱或稱插值余項我們可根據(jù)后面的定理來估計它的大小。插值余項我們可根據(jù)后面的定理來估計它的大小。5.3.

25、4 插值多項式的誤差插值多項式的誤差 定理定理5.2 設設f(x)在在 a, b 有有n+1階導數(shù)，階導數(shù)， x0, x1, xn 為為 a, b 上上n+1個互異的節(jié)點個互異的節(jié)點, p(x)為滿足為滿足 p(xi) = f(xi) (i=1,2, , n) 的的n 次插值多項式，那么對于任何次插值多項式，那么對于任何x a, b 有有 插值余項插值余項)()!1()()()()()1(xnfxpxfxRn其中其中a b 且依賴于且依賴于xbaxxxxxxxxxniin,),()()()(010證明證明 ( 略略 ) 對于線性插值，其誤差為對于線性插值，其誤差為對于拋物插值（二次插值），其誤

26、差為對于拋物插值（二次插值），其誤差為baxxxxfxPxfxR,)()(21)()()(10 baxxxxxxfxPxfxR,)( )()(61)()()(210 例例5.8 已知已知 =100, =121, 用線性插值估計用線性插值估計 在在x=115時的截斷誤差時的截斷誤差xxf)(0 x1x解解: 由插值余項公式知由插值余項公式知 )()(21)(1xfxR 2341)( xxf)(81)(10231xxxxxR因為因為 )121115)(100115(81)115(231R23121,100max)121115)(100115(81)121115)(100115(1081301125

27、. 010615813例例5.9 已知已知x0=100, x1=121, x2=144,當用拋物插值求當用拋物插值求 在在x=115時的近似值，估計其的截斷誤差時的近似值，估計其的截斷誤差 0017. 010)144115)(121115)(100115(161)115()144)(121)(100(161)()()()(61)(52252210) 3(2RxxxxxRxxxxxxfxR解解( )f xx0201122012010210122021()()()()()()( )()()()()()()115(115) 10.772756x xx xx xx xx x x xp xyyyxx x

28、xxxxxxxxxp=2583)( xxf例例5.10 設設f(x)=x4, 用余項定理寫出節(jié)點用余項定理寫出節(jié)點 -1, 0, 1, 2的三次插值多項式的三次插值多項式 解解: 根據(jù)余項定理根據(jù)余項定理(4)0123432( )( )( )()()()()4!( )(1)(1)(2)( ) 22ff xpxx x x x x x x xxpxxxxxpxxxx )()!1()()()()(max111)1(xnMxRxfxpMxfnnnnbxa的截斷誤差限是：逼近那么，若能求出通常，在做誤差估計時5.4 牛頓插值多項式牛頓插值多項式 拉格朗日插值多項式結(jié)構(gòu)對稱，使用方便。拉格朗日插值多項式結(jié)

29、構(gòu)對稱，使用方便。但由于是用基函數(shù)構(gòu)成的插值，這樣要增加一個但由于是用基函數(shù)構(gòu)成的插值，這樣要增加一個節(jié)點時，所有的基函數(shù)必須全部重新計算，不具節(jié)點時，所有的基函數(shù)必須全部重新計算，不具備承襲性，還造成計算量的浪費。這就啟發(fā)我們備承襲性，還造成計算量的浪費。這就啟發(fā)我們?nèi)?gòu)造一種具有承襲性的插值多項式來克服這個去構(gòu)造一種具有承襲性的插值多項式來克服這個缺點，也就是說，每增加一個節(jié)點時，只需增加缺點，也就是說，每增加一個節(jié)點時，只需增加相應的一項即可。這就是牛頓插值多項式。相應的一項即可。這就是牛頓插值多項式。 由線性代數(shù)知由線性代數(shù)知,任何一個不高于任何一個不高于n次的多項式次的多項式, 都可

30、以都可以表示成函數(shù)表示成函數(shù))()( ,),)( , 1110100nxxxxxxxxxxxx的線性組合的線性組合, 也就是說也就是說, 可以把滿足插值條件可以把滿足插值條件p(xi)=yi (i=0,1,n)的的n次插值多項式次插值多項式, 寫成如下形式寫成如下形式)()()()(110102010nnxxxxxxaxxxxaxxaa其中其中ak (k=0,1,2,n)為待定系數(shù)為待定系數(shù),這種形式的插值多項這種形式的插值多項式稱為式稱為Newton插值多項式。我們把它記為插值多項式。我們把它記為Nn(x)即即)()()()()(110102010nnnxxxxxxaxxxxaxxaaxN（

31、5.12） 可見，牛頓插值多項式可見，牛頓插值多項式Nn(x)是插值多項式是插值多項式p(x)的另的另一種表示形式一種表示形式, 與與Lagrange多項式相比它不僅克服了多項式相比它不僅克服了“增加一個節(jié)點時整個計算工作重新開始增加一個節(jié)點時整個計算工作重新開始”的缺點的缺點, 且可且可以節(jié)省乘除法運算次數(shù)以節(jié)省乘除法運算次數(shù), 同時在同時在Newton插值多項式中用插值多項式中用到差分與差商等概念，又與數(shù)值計算的其他方面有密切到差分與差商等概念，又與數(shù)值計算的其他方面有密切的關系的關系.它滿足它滿足其中其中ak (k=0,1,2,n)為待定系數(shù)，形如（為待定系數(shù)，形如（5.12）的）的插值

32、多項式稱為插值多項式稱為牛頓牛頓(Newton)插值多項式插值多項式。 )()()()(1101nnnnxxxxxxaxNxN5.4 .1 差商及其性質(zhì)差商及其性質(zhì)定義定義 函數(shù)函數(shù)y= f(x)在區(qū)間在區(qū)間xi ,xi+1上的平均變化率上的平均變化率iiiiiixxxfxfxxf111)()(,自變量之差和因變量之差之比叫自變量之差和因變量之差之比叫差商差商 稱為稱為f(x)關于關于xi , xi+1 的一階差商的一階差商,并記為并記為fxi ,xi+1 二階差商二階差商iiiiiiiiixxxxfxxfxxxf212121,01102110,xxxxxfxxxfxxxfmmmmm階差商階差

33、商fxi,xj,xk是指是指fxi , xj , xk=fxj , xk- fxi , xj xk- xi一般的一般的,可定義區(qū)間可定義區(qū)間xi, xi+1 , xi+n上的上的n階差商為階差商為ininiiiniiiniiixxxxxfxxxfxxxf ,.,.,.,11211021021210,xxxxfxxfxxxf 例例如如：5.4 .1 差商及其性質(zhì)差商及其性質(zhì)差商表差商表xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2fx0,x1,x2x3f(x3)fx2,x3 fx1,x2,x3fx0

34、,x1,x2 ,x3fx1,x2- fx0,x1x2 x0 xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2 ,xi+200283275125621640208 1923827 493527125 9156125216 503419 10251949 14364991 105510 1261014 例例5.11 求求 f(xi)= x3在節(jié)點在節(jié)點 x=0, 2, 3, 5, 6上的各階差商值上的各階差商值解解: 計算得如下表計算得如下表00101121201223 ( ) , : f x x f(x) f , f , f , , yxyxxxyxx xxx xx

35、如果的函數(shù)值稱為零階差商則計算如下表231233121 nn-nn-n-n f , f , , f , f, yxxx xxyxxxxx01 ,nn, f xx xx在在n+1n+1個節(jié)點處各階差商的計算方法個節(jié)點處各階差商的計算方法5.4 .1 差商及其性質(zhì)差商及其性質(zhì)nknkkkkkkkknkiiikknkkknxxxxxxxxxxxfxxxxxfxxxf011100010)()()()()()()()(,其中這個性質(zhì)可用數(shù)學歸納法證明這個性質(zhì)可用數(shù)學歸納法證明性質(zhì)性質(zhì)1 函數(shù)函數(shù) f(x) 的的 n 階差商階差商 f x0, x1 , , xn 可由可由 函數(shù)值函數(shù)值 f (x0), f

36、 (x1 ), , f (xn ) 的線性組的線性組 合表示合表示, 且且5.4 .1 差商及其性質(zhì)差商及其性質(zhì)fx0 , x1=fx1 , x0f(x1)- f(x0)x1 x0f(x0)- f(x1)x0 x1=性質(zhì)性質(zhì)2 2 差商具有對稱性差商具有對稱性, ,即在即在k k階差商中階差商中 任意交換兩個節(jié)點任意交換兩個節(jié)點 和和 的次序的次序, ,其值不變。其值不變。 例如例如kxxxf,10ixjx0110,xxfxxf120021210,xxxfxxxfxxxf性質(zhì)性質(zhì)3 若若fx, x0, x1 , , xk 是是 x 的的 m 次多項式次多項式, 則則 fx, x0, x1 ,

37、xk , xk+1是是 x 的的 m-1 次多項式次多項式證：由差商定義證：由差商定義 右端分子為右端分子為 m 次多項式次多項式, 且當且當 x = xk+1 時時, 分子為分子為0 ,故分子含有因子故分子含有因子 xk+1 x，與分母相消后，右端與分母相消后，右端為為m-1 次多項式。次多項式。xxxxxxfxxxxfxxxxxfkkkkkk110110110,性質(zhì)性質(zhì)4 若若 f(x)是是n次多項式次多項式, 則則f x, x0, x1 , , xn 恒為恒為0 證：證： f (x)是是n次多項式，則次多項式，則f x, x0 是是 n-1次多次多 項式項式, f x, x0, x1 是

38、是 n-2 次多項式次多項式, 依次遞推依次遞推 ， f x, x0, x1 , , xn-1 是零次多項式，所以是零次多項式，所以 fx,x0,x1 ,xn 0性質(zhì)性質(zhì)5 5 k k階差商階差商 和和k k階導數(shù)之間有下階導數(shù)之間有下 列關系列關系 這個性質(zhì)可直接用羅爾（這個性質(zhì)可直接用羅爾（RolleRolle）定理證明定理證明kxxxf,10)max,min(!)(,00)(10iniinikkxxkfxxxf5.4.2 牛頓插值公式牛頓插值公式牛頓牛頓(Newton)插值多項式插值多項式 )()()()()(110102010nnnxxxxxxaxxxxaxxaaxN 的系數(shù)的系數(shù) 可

39、根據(jù)插值條件推出可根據(jù)插值條件推出, 即由即由 有有 naaa,10nixfxNiin, 1 , 0)()()()(000 xfaxNn)()()(101101xfxxaaxNn)()()()(21202201102xfxxxxaxxaaxNn )()()()()(1100110nnnnnnnnxfxxxxxxaxxaaxN這是關于這是關于 的下三角方程組的下三角方程組, ,可以求得可以求得 naaa,10)(00 xfa 10010101011,)()()()()(xxfxxxfxfxxaxfa2101210201202021022,)(,)()()()(xxxfxxxxfxxfxxxxxx

40、axfxfa一般，用數(shù)學歸納法可證明一般，用數(shù)學歸納法可證明 ), 1 , 0(,10nkxxxfakk所以所以n n次牛頓次牛頓( (Newton)Newton)插值公式為插值公式為 )()(,)(,)()(110100100nnnxxxxxxxxxfxxxxfxfxN其余項其余項 )()(,)(1010nnnxxxxxxxxxxfxR為牛頓插值多項式的誤差。由插值多項式的存在為牛頓插值多項式的誤差。由插值多項式的存在惟一性定理知，滿足同一組插值條件的拉格朗日惟一性定理知，滿足同一組插值條件的拉格朗日插值多項式插值多項式P(x)P(x)與牛頓插值多項式與牛頓插值多項式N Nn n(x(x)

41、)實際上是實際上是同一個多項式，僅是同一插值多項式的不同表達同一個多項式，僅是同一插值多項式的不同表達形式而已，因此得到牛頓插值多項式的誤差與拉形式而已，因此得到牛頓插值多項式的誤差與拉格朗日插值多項式的誤差也完全相等。故有格朗日插值多項式的誤差也完全相等。故有niinniinnxxnfxxxxxxfxR0) 1(010)()!1()()(,)()!1()(,) 1(10nfxxxxfnn 可以看出，牛頓插值公式計算方便，增加可以看出，牛頓插值公式計算方便，增加一個插值點，只要多計算一項，而一個插值點，只要多計算一項，而Nn(x)的的各項系數(shù)恰好是各階差商值，很有規(guī)律各項系數(shù)恰好是各階差商值，

42、很有規(guī)律 000,xxxfxfxxf fx0,x(x- x0) = f(x) - f(x0)f(x)+ fx0,x(x- x0)=f(x0)101001,xxxxfxxfxxxf fx1,x0,x(x-x1)=fx0,x-fx1,x0fx0,x+ fx1,x0,x(x-x1)= fx1,x0f(x)+ (x- x0) fx1,x0=f(x0)+ (x- x0) (x-x1) fx1,x0,x5.4.2 牛頓插值公式牛頓插值公式(另一種推導方法）另一種推導方法）f(x)=f(x0)+(x- x0)fx1,x0+(x- x0)(x-x1)fx1,x0,x201201012,xxxxxfxxxfxx

43、xxf fx1,x0,x = (x-x2) fx2,x1,x0,x +fx2,x1,x0f(x)=f(x0)+(x- x0)fx1,x0 + (x- x0)(x-x1)fx2,x1,x0 + (x- x0)(x-x1)(x-x2) fx2,x1,x0,x,.,).()(,.,).()(.,)(,)()()(011001110012100100 xxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn Nn(x)Rn(x)如當如當n=1時，時，f(x) = f(x0) + (x- x0)fx1,x0 + (x- x0)(x-x1) fx1,x0,xNn(x)= f

44、(x0) + (x- x0)fx1,x0()010001yyyxxxx 其中其中Nn(x)稱為稱為牛頓插值多項式牛頓插值多項式 Rn(x)稱為稱為牛頓插值余項牛頓插值余項5.4.2 牛頓插值公式牛頓插值公式xifxifxi,xi+1fxi,xi+1,xi+2fxi,xi+1,xi+2x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2fx0,x1,x2x3f(x3)fx2,x3fx1,x2,x3fx0,x1,x2 ,x3,.,).()(.,)(,)()()(01110012100100 xxxfxxxxxxxxxfxxxxxxfxxxfxNnnnnxifxifxi,xi+1fxi

45、,xi+1,xi+2114293N2(7)=1+(7-1)*0.33333+ (7-1)*(7-4)*(-0.01667)= 2.6999233333. 01412 2 . 04923 01667. 01933333. 02 . 0 + (x- x0) (x-x1) fx1,x0,x+ (x- x0) fx1,x0=f(x0)N(x)例例 5.12 已知已知 x = 1, 4, 9 的平方根值，求的平方根值，求解：解：7)!()(,.,)(10nfxxxfnn由由建起了差商和導數(shù)的關建起了差商和導數(shù)的關系系用導數(shù)代替牛頓插值多項式中的差商，有用導數(shù)代替牛頓插值多項式中的差商，有勒公式時，上式就

46、是常用的泰都趨于當010110)(102010,)()(!)()(! 2)()()()(xxxxxxxxxxnfxxxxfxxfxfxpnnnn 差商和導數(shù)的關系也可用羅爾定理證出，余項差商和導數(shù)的關系也可用羅爾定理證出，余項R(x) =f(x)- P(x)R(xi) =f(xi)- P(xi)=0 i=0,1, ,n Rn(n)(x) =f (n)(x)- Pn(n)(x)=f (n)(x)- f(x0)+(x-x0) fx0, x1+(x-x0)(x-x1) fx0, x1 , x2+(x-x0)(x-x1)(x-xn-1)fx0,x1,xn(n)=f (n)(x)- n! fx0,x1,

47、xnRn(xi)=0 (i=0,1,.,n)Rn( i)=0 (i=0,1,.,n-1)Rn(n)( )=0 (x0,x1,xn)Rn(n)( )=0=f (n)( )- n! fx0,x1,xn)!()(,.,)(10nfxxxfnn 即即R(xR(x) )在在xx0 0, , x xn n 有有n+1n+1個零點，根據(jù)羅爾定理個零點，根據(jù)羅爾定理R R(n)(n)(x(x) )在在xx0 0, , x xn n 有有1 1個零點，設為個零點，設為 ，即有即有 Rn(n)( )=0)!()(,.,)(10nfxxxfnn 增加新節(jié)點增加新節(jié)點x，并且并且f(x)為為(n+1)階可導時，有階可

48、導時，有(x0,x1,xn)!1()(,.,)1(10 nfxxxxfnn (x0,x1,xn,x),.,).()()(1010 xxxxfxxxxxxxRnnn ).()()!1()(10)1(nnxxxxxxnf (1)0( )()(1)!nniifxxn|f(x)(n+1)| Mn+110|( )|()|(1)!nnniiMR xxxn5.4.2 牛頓插值余項牛頓插值余項 例例5.13 已知已知 x=0, 2, 3, 5 對應的函數(shù)值為對應的函數(shù)值為 y=1, 3, 2, 5 , 作三次作三次Newton插值多項式。插值多項式。 xi f(xi) 一階差商一階差商 二階差商二階差商 三階

49、差商三階差商 0 1 2 3 1 3 2 -1 -2/3 5 5 3/2 5/6 3/10 所求的三次所求的三次Newton插值多項式為插值多項式為3001001201(),(),()()231(2)(2)(3)310Nf xf x xxxf x x xxxxxxx xx xx例例5.14 已知已知 f(x) = x7+ x4+ 3x+ 1 求求 f 20, 21, 27 及及 f 20, 21, 27, 28 分析：本題分析：本題 f(x)是一個多項式是一個多項式, 故應利用差商的性質(zhì)故應利用差商的性質(zhì)解解: 由差商與導數(shù)之間的關系由差商與導數(shù)之間的關系 ()01( 7 )(8 )( 7 )

50、017(8 )01781,()!()7 !,()0()7 !2 , 2 , 217 !7 !()02 , 2 , 2 , 208 !8 !nnfxxxfnfxfxffff 及知例例5.15 求求 并估計其誤差并估計其誤差的的值值7解：作函數(shù)解：作函數(shù) f(x) =x取取 x0=4, x1=9, x2=6.25 , 建立差商表建立差商表xf(x)f xi,xi+1,fxi,xi+1,xi+242936.25 2.5N2(7)= 2+ (7-4)*0.2+ (7-4)*(7-9)*(-0.00808)= 2.648482 . 04923 18182. 0925. 635 . 2 00808. 04

51、25. 62 . 018182. 0 f 3(x) =5)1(83x011719. 0)41(835 Rn (x)00879. 0| )25. 67)(97)(47( |! 3011719. 0 在區(qū)間在區(qū)間 4 , 9 上，上，余式近似余式近似 0.5 *10 -2, N2(7) = 2.64848 可舍入為可舍入為2.65.645751. 27 10|( )|()|(1)!nnniiMR xxxn| f(x)(n+1) | Mn+1由由5.4.4 等距節(jié)點插值等距節(jié)點插值等距節(jié)點等距節(jié)點 xi+1 - xi = h ，函數(shù)在等距節(jié)點上的值為函數(shù)在等距節(jié)點上的值為y0 , y1, , yn

52、，稱，稱 yi-1= yi - yi-1為函數(shù)為函數(shù)f(x) 在在xi-1, xi上的上的一階差分一階差分。稱稱 2yi-1= yi - yi-1= yi+1 - 2yi + yi-1為函數(shù)為函數(shù)f(x) 在在xi-1, xi+1上的上的二階差分二階差分。稱稱 kyi-1= k-1yi - k-1yi-1為函數(shù)為函數(shù)f(x) 在在xi-1, xi+k-1上的上的 k 階差分階差分。 當插值節(jié)點等距分布時當插值節(jié)點等距分布時, 被插值函數(shù)的變化率就可用差被插值函數(shù)的變化率就可用差分來表示分來表示, 這時牛頓插值公式的形式更簡單這時牛頓插值公式的形式更簡單, 計算量更小計算量更小xy y 2y 3

53、y 4yx0y0 x1y1x2y2x3y3x4y4 y0 = y1 y0 y1 = y2 y1 y2 = y3 y2 y3 = y4 y3 2y0 = y1 - y0 2y1= y2 - y1 2y2= y3 - y2 3y0= 2y1 - 2y0 3y1= 2y2 - 2y1 4y05.4.4 等距節(jié)點插值等距節(jié)點插值5.4.4 等距節(jié)點插值等距節(jié)點插值 y0= y1 y0 y1= y2 y1 y2= y3 y2= y2 2y1 +y0 2y0= y1 - y0 3y0= 2y1 - 2y0= y3 2y2 +y1 (y2 2y1 +y0)= y3 3y2 +3y1 y0 2y1= y2 -

54、 y1= y3 2y2 +y1(a-b)3=a3-3a2b+3ab2-b3(a-b)2=a2-2ab+b2 4y0= 3y1 - 3y0= y4 3y3 +3y2 y1 -(y3 3y2 +3y1 y0 )= y4 4y2 +6y2 4 y1 +y0 (a-b)4=a4-4a3b+6a2b2-4ab3+b3結(jié)論：各階差分中函數(shù)值的系數(shù)正好等于結(jié)論：各階差分中函數(shù)值的系數(shù)正好等于 ( (a-a-b)b)r r展開式中的系數(shù)展開式中的系數(shù)等距節(jié)點情況下等距節(jié)點情況下xi= x0+ih ，用差分表示差商：用差分表示差商：010110,xxxfxfxxf =y1 y0h= y01!hfx1 , x2=

55、y2 y1h= y11!hfx0,x1,x2=fx1,x2- fx0,x1x2 x0= y11!h y01!h2h= y1- y02h2= 2y02!h2fx1,x2,x3=fx3,x2- fx2,x1x3 x1= y21!h y11!h2h= y2- y12!h2= 2y12!h2fx0,x1,x2 ,x3= 2y12!h2 2y02!h23h= 2y1 - 2y02*3h3= 3y03!h3,.,10nxxxf ny0n!hn nNn(x)=常量常量例例5.16 計算計算 f (x) = x3在等距節(jié)點在等距節(jié)點0，1，2，3, 4上的各上的各 階差分值階差分值xy y 2y 3y0011

56、28327464 4y171937612186605.4.4 牛頓前插公式牛頓前插公式取間距為取間距為h, 等距節(jié)點等距節(jié)點 x0 x1 xn 順序建立牛頓差商公式順序建立牛頓差商公式,.,).()(,.,).()(.,)(,)()()(01100111001210000 xxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn fx0 , x1= y01!hfx0,x1,x2= 2y02!h2fx0,x1,x2 ,x3= 3y03!h3Nn(x)=y0+(x-x0) y01!h+(x-x0)(x-x1) 2y02!h2+ (x-x0)(x-x1) (x-xn-

57、1) ny0n!hn牛頓前插公式牛頓前插公式,.,).()(,.,).()(.,)(,)()()(011001110012100100 xxxxfxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnn Nn(x)Rn(x)0030200!)1).(1(.! 3)2)(1(! 2)1(! 1)(ynntttytttyttytyxPnn hxxt0 因因 , ,設設 , ,則則 ihxxi0thxx0), 1 , 0()(nihitxxixy y 2y 3y 4yx0y0 x1y1 y0 x2y2 y1 2y0 x3y3 y2 2y1 3y0 x4y4 y3 2y2 3y1

58、 4y00030200!)1).(1(.!3)2)(1(!2)1(!1)(ynntttytttyttytyxPnn 向后差分向后差分函數(shù)函數(shù)y=f(x), 若記若記y-1=f(x0-h), y-2=f(x0-2h),則各階向后差分則各階向后差分一階一階 y0= y0- y-1， y1= y1- y0， y2= y2- y1， 二階二階 2y0= y0- y-1= y0- y-1- (y-1- y-2 )= y0- 2y-1+ y-2 2y1= y1- y0 = y1- y0- (y0- y-1 ) = y1- 2y0+ y-1 K階階 ky0= k-1y0- k-1y-1 ky1= k-1y1

59、- k-1y0 同樣利用向后差分可以得到牛頓向后插值公式同樣利用向后差分可以得到牛頓向后插值公式其中其中 , ,公式公式 稱之為牛頓向后插值公式余項。稱之為牛頓向后插值公式余項。 nnnnnnnnfnntttfttftfthxNxN!) 1() 1(! 2) 1()()(2hxxtn/ )( nhxxfhnntttxRnn,),()!1()() 1()(0)1(1x-1 012y-11311解：解：建立差分表建立差分表xy y 2y 3y-1-10121320211 866hxxt0 5 .01)1()5 .0( 2*! 15 . 01 0*!2)15.0(5.0 6*!3)25 .0)(15

60、 .0(5 .0 = -1+1+0+0.375 = 0.375例例5.16 按下列數(shù)值表用按下列數(shù)值表用牛頓前插公式求牛頓前插公式求y(-0.5) 的近似值的近似值N3(x)002000!) 1() 1(! 2) 1()(fnntttfttftfthxNnn例例5.17 估計用線性插值法計算估計用線性插值法計算lg47時的誤差限時的誤差限10100101yxxxxyxxxxy 取取x0=45, x1=48,104548454748454847yyy 106666667. 03333333. 0yy =1.671898401解：應用解：應用n=1的拉格朗日插值公式的拉格朗日插值公式x424548