計算機方法-插值方法

1、14 插值方法插值方法4.1 1多項式插值問題的一般提法多項式插值問題的一般提法 4.2 拉格朗日拉格朗日(Lagrange)插值插值4.3 差商與差分及其性質差商與差分及其性質4.4 牛頓插值公式牛頓插值公式 4.5 分段插值法分段插值法4.6曲線擬合的最小二乘法曲線擬合的最小二乘法24.0 引言引言 插值法是廣泛應用于理論研究和生產(chǎn)實踐的重插值法是廣泛應用于理論研究和生產(chǎn)實踐的重要數(shù)值方法要數(shù)值方法, 它是用簡單函數(shù)它是用簡單函數(shù)(特別是多項式或分特別是多項式或分段多項式段多項式)為各種離散數(shù)組建立連續(xù)模型；為各種為各種離散數(shù)組建立連續(xù)模型；為各種非有理函數(shù)提供好的逼近方法。眾所周知，反映

2、非有理函數(shù)提供好的逼近方法。眾所周知，反映自然規(guī)律的數(shù)量關系的函數(shù)有三種表示方法：自然規(guī)律的數(shù)量關系的函數(shù)有三種表示方法： 解析表達式52)(3xxxfyyxsin 圖象法 表格法34.0 引言引言 許多數(shù)據(jù)都是用表格法給出的許多數(shù)據(jù)都是用表格法給出的(如觀測和實驗而得到的函數(shù)如觀測和實驗而得到的函數(shù)數(shù)據(jù)表格數(shù)據(jù)表格)，可是，從一個只提供離散的函數(shù)值去進行理論，可是，從一個只提供離散的函數(shù)值去進行理論分析和進行設計，是極不方便的分析和進行設計，是極不方便的, 甚至是不可能的。因此需甚至是不可能的。因此需要設法去尋找與已知函數(shù)值相符，并且形式簡單的插值函要設法去尋找與已知函數(shù)值相符，并且形式簡單

3、的插值函數(shù)數(shù)(或近似函數(shù)或近似函數(shù))。 另外一種情況是，另外一種情況是，函數(shù)表達式完全給定，但其形式不適宜函數(shù)表達式完全給定，但其形式不適宜計算機使用計算機使用，因為計算機只能執(zhí)行算術和邏輯操作，因此，因為計算機只能執(zhí)行算術和邏輯操作，因此涉及連續(xù)變量問題的計算都需要經(jīng)過離散化以后才能進行。涉及連續(xù)變量問題的計算都需要經(jīng)過離散化以后才能進行。如數(shù)值積分方法、數(shù)值微分方法、差分方程以及有限元法如數(shù)值積分方法、數(shù)值微分方法、差分方程以及有限元法等，都必須直接或間接地應用到插值理論和方法等，都必須直接或間接地應用到插值理論和方法。44.1 多項式插值問題的一般提法多項式插值問題的一般提法 當精確函數(shù)

4、當精確函數(shù) y = f (x) 非常復雜或未知時，在一系非常復雜或未知時，在一系列節(jié)點列節(jié)點 x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f (x0) , , yn = f (xn)， 由此構造一個簡單易算的近似函數(shù)由此構造一個簡單易算的近似函數(shù) p(x) f(x)，滿足條件，滿足條件: p(xi) = f(xi) (i = 0, n)。 這里的這里的 p(x) 稱為稱為f(x) 的插值函數(shù)。的插值函數(shù)。最常用的插值函數(shù)是最常用的插值函數(shù)是 ? 代數(shù)多項式、三角多項式、有理分式代數(shù)多項式、三角多項式、有理分式5 插值函數(shù)插值函數(shù) p (x) 作為作為 f (x) 的近似，可以選自不同類型的

5、的近似，可以選自不同類型的函數(shù)函數(shù), 如如 p (x) 為代數(shù)多項式、三角多項式、有理分式為代數(shù)多項式、三角多項式、有理分式；其函數(shù)性態(tài)可以是光滑的、亦可以是分段光滑的。其其函數(shù)性態(tài)可以是光滑的、亦可以是分段光滑的。其中，代數(shù)多項式類的插值函數(shù)占有重要地位：中，代數(shù)多項式類的插值函數(shù)占有重要地位： (a) 結構簡單、計算機容易處理、任何多項式的導數(shù)結構簡單、計算機容易處理、任何多項式的導數(shù)和積分也易確定，并且仍是多項式。和積分也易確定，并且仍是多項式。(b) 著名的著名的Weierstrass逼近定理逼近定理(定義在閉區(qū)間上的定義在閉區(qū)間上的任何連續(xù)函數(shù)任何連續(xù)函數(shù) f(x) , 存在代數(shù)多項

6、式存在代數(shù)多項式p(x)一致逼近一致逼近f(x),并達到所要求的精度并達到所要求的精度)。因此，我們主要考慮代數(shù)多項式的插值問題。因此，我們主要考慮代數(shù)多項式的插值問題。6x0 , x1, , xn 插值節(jié)點插值節(jié)點, 函數(shù)函數(shù) P(x) 稱為函數(shù)稱為函數(shù) y=f(x) 的插值函數(shù)，的插值函數(shù)，區(qū)間區(qū)間 a, b 稱為插值區(qū)間。稱為插值區(qū)間。 7例題例題: :已知函數(shù)已知函數(shù) f(x) 有如下數(shù)據(jù)有如下數(shù)據(jù):求求 f(x) 的插值多項式的插值多項式 p(x)，并求并求 f(x) 在在 x=0.5 處的近似值。處的近似值。89 插值的幾何意義插值的幾何意義 從幾何上看，插值就是求一條曲線從幾何上

7、看，插值就是求一條曲線 使其通過給定的使其通過給定的 個點個點 ， 并且與已知曲線并且與已知曲線 有一定的近似度。有一定的近似度。( )yP x1n( ,)iix y(0,1, )in( )yf xx 0 y y = p(x) a=x0 x1 x2 x3 xn=b (xi, yi)y = f (x)曲線曲線 P ( x) 近似近似 f ( x) 10插值方法的研究問題插值方法的研究問題（1）滿足插值條件的）滿足插值條件的P ( x) 是否是否存在唯一？存在唯一？（2）若滿足插值條件的）若滿足插值條件的P ( x) 存在，存在，如何構造如何構造P ( x)？（3）如何）如何估計估計用用P ( x

8、)近似替代近似替代 f ( x) 產(chǎn)生的產(chǎn)生的誤差？誤差？x 0 y y = p(x) a=x0 x1 x2 x3 xn=b (xi, yi)y = f (x)曲線曲線 P ( x) 近似近似 f ( x) 11求求 n 次多項式次多項式 使得使得:nnnxaxaaxP 10)(條件：無重合節(jié)點，即條件：無重合節(jié)點，即jixx ji 4.2 拉格朗日多項式拉格朗日多項式 /* Lagrange Polynomial */ 根據(jù)插值條件，有：根據(jù)插值條件，有：nnnnnnnnnnyxaxaaxPyxaxaaxPyxaxaaxP10111101000100)()()(其系數(shù)矩陣的行列式為其系數(shù)矩陣

9、的行列式為nnnnnnnxxxxxxxxxV111),(110010(),0,1,niipxyinVandermonde行列式行列式12), 2 , 1(nixi0)(),(010nijjinnxxxxxVnaaa,10注意到插值節(jié)點注意到插值節(jié)點兩兩相異，而兩兩相異，而故方程組故方程組(1)(1)有惟一解有惟一解于是滿足插值條件的多項式存在且惟一。于是滿足插值條件的多項式存在且惟一。nxxx,10nnnxaxaaxP10)(iinyxP)(由由n+1個不同插值節(jié)點個不同插值節(jié)點可以惟一確定一個可以惟一確定一個n次多項式次多項式滿足插值條件滿足插值條件( (唯一性唯一性) )ReturnRet

10、urn13n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求101( )Lxaa x=+使得使得111001)(,)(y1x1Ly0 x0L 可見可見 L1(x) 是過是過 ( x0 , y0 ) 和和 ( x1, y1 ) 兩點的直線。兩點的直線。l0(x)l1(x)4.2 拉格朗日多項式拉格朗日多項式 /* Lagrange Polynomial */ 線性插值線性插值基函數(shù)基函數(shù)1. 構造線性插值基函數(shù)的方法構造線性插值基函數(shù)的方法:iiiyxlyxxxxyxxxxxxxxyyyxL)()()(1010100101001010114線性插值與其基函數(shù)示意圖線性插值與其基函數(shù)

11、示意圖xy0 0( )yy lx1 1( )yy l x0 x1xO10 01 1( )( )( )L xy lxy l x0 x1xxy0y1y( )yf x1( )yL xO15顯然顯然, , 是過是過 、 、 三點的一條三點的一條拋物線。拋物線。),(11yx),(22yx已知已知 , , 求求 ，n = 2)(2xL使得使得200211222( )( )( )L xyL xyL xy=2( )L x00( ,)xy210210,yyyxxx16顯然顯然, , 是過是過 、 、 三點的一條三點的一條拋物線。拋物線。),(11yx),(22yx已知已知 , , 求求 ，n = 221021

12、0,yyyxxx)(2xL使得使得200211222( )( )( )L xyL xyL xy=仿照線性插值基函數(shù)的構造方法，令仿照線性插值基函數(shù)的構造方法，令)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl拋物線基拋物線基函數(shù)函數(shù)2()Lx稱其為拋物線插值基函數(shù)稱其為拋物線插值基函數(shù)(如上右圖所示如上右圖所示)。 2( )L x00( ,)xy17)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl拋物線插值基函數(shù)

13、拋物線插值基函數(shù)于是于是拋物線基函數(shù)拋物線基函數(shù)020112201201021012202120()()()()()()( )()()()()()()( )iiixxxxxxxxxx xxL xyyyxx xxxxxxxxxxl x y=-=+-=18希望找到希望找到 li (x)，i = 0, , n 使得使得 li (xj) = ij ；然后令；然后令，則顯然有，則顯然有 Pn(xi) = yi 。每個每個 li 有有 n 個根個根 x0 , xi , xn一般情形一般情形)()( )()()()( )()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl ， k

14、 = 0, 1 , n ., )()( )()()(110nkkkxxxxxxxxAxl 令令k = 0, 1 , n .0111()()()()knkkkkkAxxxxxxxx() 1,kkl x由由 得得: :0()()）nnkkkLxfxlx0()()）nnkkkLxfxlx19設設 函數(shù)表函數(shù)表 則滿足插值條件的多項式則滿足插值條件的多項式（Lagrange）插值多項式）插值多項式 nkkknxlxfxL0)()( ）( )yf x, , ,(,(,( )(0 1.),ijiixxxf xinij()() (0,1. )，niiLxf xin其中其中, ., .0()(0,1,. )n

15、jkjkjjkxxlxknxx20以下的問題：如何分析以下的問題：如何分析插值的余項？插值的余項？ (1) (1) 先求先求插值基函數(shù)插值基函數(shù). . (2) (2) 構造構造插值多項式插值多項式. .構造插值多項式的方法：構造插值多項式的方法：21 x -1 0 1 2f (x) -2 -2 1 2 已知連續(xù)函數(shù)已知連續(xù)函數(shù) f (x) 的函數(shù)表如下：的函數(shù)表如下：求方程求方程 f (x)=0 在在(-1,2)內(nèi)的近似根。內(nèi)的近似根。例題例題22解：解：利用利用Lagrange插值法有插值法有 取初值取初值x=0.5，利用牛頓法求解可得，利用牛頓法求解可得 f (x) 在在(-1,2)內(nèi)的近

16、似根內(nèi)的近似根為為0.67433。 32591412 0 xxx解方程解方程x -1 0 1 2f(x) -2 -2 1 2 已知連續(xù)函數(shù)已知連續(xù)函數(shù)f (x)的函數(shù)表如下：的函數(shù)表如下：求方程求方程 f (x)=0 在在(-1,2)內(nèi)的近似根。內(nèi)的近似根。例題例題30121122210111201 01 021211122 1 121 20 21xxxxxxL xxx xxx x()()()()()()( )( )( )()()()()()()() ()() ()( )()()()-+-=-+- - - -+-+-+-+-+-3215914126xxx=-+-23 ，且，且 f 滿足條件滿足

17、條件 , Lagrange插值法插值余項插值法插值余項設節(jié)點設節(jié)點)1( nf在在a , b內(nèi)存在內(nèi)存在, 考察截斷誤差考察截斷誤差:)()()(xLxfxRnn , baCfn bxxxan 1024 Lagrange插值法的插值余項插值法的插值余項 ，且，且 f 滿足條件滿足條件 ,設節(jié)點設節(jié)點)1( nf在在a , b內(nèi)存在內(nèi)存在 , 截斷誤差截斷誤差(或插值余項或插值余項):, baCfn bxxxan 10(1)1( )( )( )( )( )(1)!nnnnfRxfxLxxn,( , )a b25 Lagrange插值法的插值余項插值法的插值余項 ，且，且 f 滿足條件滿足條件 ,

18、設節(jié)點設節(jié)點)1( nf在在a , b內(nèi)存在內(nèi)存在 , 截斷誤差截斷誤差(或插值余項或插值余項):, baCfn bxxxan 10(1)1( )( )( )( )( )(1)!nnnnfRxfxLxxn,( , )a b證明：由已知條件得到：證明：由已知條件得到：()0,0,1,nkR xkn于是有：于是有：011( )( )()()( )()( )nnnR xk x x xx xx xkxx其中其中 是與是與 x 有關的待定函數(shù)。有關的待定函數(shù)。( )k x26任意固定任意固定 x xi (i = 0, , n), 考察考察01( )( )( )( )()()()nntf tL tk x

19、txtxtx根據(jù)插值條件及余項定義，可知根據(jù)插值條件及余項定義，可知( ) t在點在點01,nxxxx故故處均為零，處均為零，在在( ) t , a b上有上有n+2個個零點，根據(jù)個個零點，根據(jù) Roll 定理定理 在在 的每兩個零點間至少有一個零點，故的每兩個零點間至少有一個零點，故在在 內(nèi)至少有內(nèi)至少有 一一 個零點，對個零點，對 再用再用Roll 定理，可定理，可知知 在在 內(nèi)至少有內(nèi)至少有 n 個零點，依此類推，個零點，依此類推， 在在 內(nèi)至少有一個零點，記為內(nèi)至少有一個零點，記為( ) t( ) t( ) t , a b( ) t( ) t , a b(1)( )nt , a b(

20、, )a b使得使得:(1)(1)( )( )(1)! ( )0nnfnk x(1)()( ),( ,)(1)!nfk xa bn27由于由于 是不能確定，因此我們并不能確定誤差的大小是不能確定，因此我們并不能確定誤差的大小但如能求出但如能求出 ，那么用，那么用 逼近逼近 的截斷誤差限是：的截斷誤差限是：當當 時，時，當當 時時( )nL x( )f x1n 12010111( )( )( )( )()(),22R xfxfxxxxx x 2n 230120211( )( )( )( )()()(),66,R xfxfxxxxxxx x (1)1()nnaxbm axfxM11( )( )(1

21、)!nnnMRxxn28當當 f (x) 為任一個次數(shù)為任一個次數(shù) n 的多項式時，的多項式時， , 可知，可知，即插值多項式對于次數(shù)即插值多項式對于次數(shù) n 的的多項式是精確的。多項式是精確的。0)()1( xfn0)( xRn注意注意29 給定給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是下面哪個是 l2(x) 的圖像？的圖像？問題問題30算例算例1 1LagrangeLagrange插值法插值法已知已知 ， ，用線性插值及拋物線插值計算用線性插值及拋物線插值計算 的值并估計截斷誤差。的值并估計截斷誤差。sin0.320.314567sin0.340.3

22、33487sin0.360.352274sin0.336731算例算例1 1LagrangeLagrange插值法插值法已知已知 ， ，用線性插值及拋物線插值計算用線性插值及拋物線插值計算 的值并估計截斷誤差。的值并估計截斷誤差。sin0.320.314567sin0.340.333487sin0.360.352274sin0.33670120.320.340.36xxx0120.3145670.3334870.352274yyy線性插值時取線性插值時取 解解: :010.32,0.34xx1sin0.3367(0.3367)0.3367 0.320.3367 0.340.3145670.33

23、34870.34 0.320.32 0.340.330365L32其截斷誤差為：其截斷誤差為：其中其中, , 因為因為可取可取于是：于是： 2101( )()() ,2MR xxxxx012max( )xx xMf ( )sin ,( )sinf xx fxx0121max sinsin0.3335xx xMxx 115sin0.3367(0.3367)10.3335 0.0167 0.00332(0.3367)0.92 10RL33用拋物線插值時，取所有節(jié)點，得到用拋物線插值時，取所有節(jié)點，得到2sin0.3367(0.3367 0.34)(0.3367 0.36)(0.3367 0.32)

24、(0.3367 0.36)0.3145670.333487(0.32 0.34)(0.32 0.36)(0.34 0.32)(0.34 0.36)(0.3367 0.32)(0.3367 0.34)0.352274(0.36 0.32)(0.36 0.3(0.4)0.3133674567)L4440.7689 103.89 100.5511 100.3334870.3522740.00080.00040.0000.3303 487余項討論：余項討論：其中：其中：32012( )()()() ,6MRxxxxxxx0120max( )cos0.828xx xMfxx 226(0.3367)sin

25、 0.3367(0.3367)10.8280.01670.0330.023360.17810RL34算例算例2 2LagrangeLagrange插值法插值法利用利用 100，121 的開方計算的開方計算 .由于由于: 解解: :115利用利用Lagrange插值法有插值法有 1110012110010121100121)(1xxxL于是于是, 71428.101110012110011510121100121115)115(1151 L115的精確值為的精確值為 10.72380529, 因此因此, 近似值近似值 10.71428 有有3 位有效數(shù)字位有效數(shù)字. ReturnReturn35

26、4.3 差商與差分差商與差分 Lagrange 插值雖然易算，但若要增加一個節(jié)點時，插值雖然易算，但若要增加一個節(jié)點時， 全部基函數(shù)全部基函數(shù) li (x) 都需重新算過。都需重新算過。尋求如下形式的插值多項式：尋求如下形式的插值多項式：01020101( )()()()()()nnnP xaa xxaxxxxaxxxx其中的其中的 為待定系數(shù)，由插值條件確定為待定系數(shù)，由插值條件確定.ia由線性代數(shù)的知識可知：任何一個由線性代數(shù)的知識可知：任何一個n次多項式都可以表示成次多項式都可以表示成011()()()nxxxxxx共共 n+1 個線性無關的多項式的線性組合。個線性無關的多項式的線性組合

27、。那么，是否可以將這那么，是否可以將這 n+1 個多項式作為插值基函數(shù)呢？個多項式作為插值基函數(shù)呢？1,0,x x01()(),x x x x36)()()()()(110102010nnxxxxxxaxxxxaxxaaxP設插值多項式設插值多項式P(x)具有如下形式：具有如下形式：(),0,1,iiP xfin000()P xfa)()(011011xxaafxP00fa 01011xxffa22012022021()()()()P xfaa xxaxxxx12010102022xxxxffxxffa 再繼續(xù)下去再繼續(xù)下去, ,待定系數(shù)的形式將更復雜待定系數(shù)的形式將更復雜, ,為此引入為此引

28、入 差差商和差分商和差分的概念的概念. .P(x)應滿足插值條件：應滿足插值條件：有：有：374.3.1 4.3.1 差商的概念差商的概念從零階差商出發(fā)，歸納地定義各階差商從零階差商出發(fā)，歸納地定義各階差商:稱稱 為函數(shù)為函數(shù) 關于點關于點 的的一階差商一階差商.( )f x111 ,iiiiiif xf xf x xxx1,iix x 一般地，一般地， 關于關于 的的 k 階差商階差商:( )f x1,iii kx xx12111, , ,iii kiii kiii ki kif xxxf x xxf x xxxx 記函數(shù)記函數(shù) 在在 的值的值 ，稱稱 為為 關于關于 的的零階差商零階差商。

29、( )f xix ( )iif xf x if xix( )f x38 一般地，一般地， 關于關于 的的 n 階差商階差商:( )f x01, ,nx xx12011010 , , , , ,nnnnf x xxf x xxf x xxxx n 階差商的概念階差商的概念39差商的基本性質差商的基本性質性質性質1 1：差商可表示為函數(shù)值的線性組合，即：差商可表示為函數(shù)值的線性組合，即：性質性質2 2：差商關于所含節(jié)點是對稱的，即：差商關于所含節(jié)點是對稱的，即：010011(),()()()()njnjjjjjjjnf xf x xxxxxxxxxx011010, ,nnnnf x xxf x x

30、xf xxx可用歸納法證明40差商的基本性質差商的基本性質性質性質3：性質性質4：設設 在在 存在存在 n 階導數(shù)，且階導數(shù)，且 則則 ，使得，使得:12011011 ,imiimmif xxxf x xxf xxxxx( )01( ),!nnff x xxn( , )a b ( )f x , a b , jxa b41差商的計算差商的計算-差商表差商表一階差商一階差商 二階差商二階差商三階差商三階差商四階差商四階差商ix0 x1x2x3x4x( )if x1()f x2()f x3()f x4()f x0()f x01,f x x12 ,f x x23,f x x34,f x x012,f

31、x x x123 ,f x x x234,f x x x0123,f x x x x1234 ,f x x x x01234 , , ,f x x x x x42已知已知ix()if x計算三階差商計算三階差商1 , 2 , 4 , 7 f解：列表計算解：列表計算 ix()ifx算例算例 1 , 2 , 4 , 7 1 / 2f434.3.2 4.3.2 差分差分 在前面的討論中，節(jié)點是任意分布的，但實際上在前面的討論中，節(jié)點是任意分布的，但實際上經(jīng)常遇經(jīng)常遇到等距節(jié)點的情況，這時插值公式可以得到簡化到等距節(jié)點的情況，這時插值公式可以得到簡化，為此，我，為此，我們先介紹差分的概念。們先介紹差分

32、的概念。 設函數(shù)設函數(shù) 在等距節(jié)點在等距節(jié)點上的值上的值 為已知，這里為已知，這里 為常數(shù)，稱為步長。為常數(shù)，稱為步長。( )f x0(0,1, )ixxih in( )iiff xh 下面來討論差分的定義。下面來討論差分的定義。44差分的定義差分的定義記號記號分別稱為分別稱為 在在 處以處以 為步長的為步長的 向前差分、向后差分、中心差分向前差分、向后差分、中心差分符號符號 、 、 分別稱為向前差分算子、向后差分算子、分別稱為向前差分算子、向后差分算子、中心差分算子中心差分算子. .1iiifff1iiifff1122()()22iiiiihhff xf xff ( )f xixh45高階差

33、分高階差分用一階差分可以定義二階差分用一階差分可以定義二階差分一般地可定義一般地可定義 m 階差分為：階差分為：中心差分定義為中心差分定義為: : 以此類推。以此類推。21212iiiiiiffffff 111mmmiiifff 111mmmiiifff 121iiifff 121iiifff 11222iiifff46不變算子不變算子 I、移位算子、移位算子 E定義定義從而可得：從而可得：于是得到：于是得到：同理，由于：同理，由于：得到：得到：由于：由于：得到：得到：由差分的定義及不變算子和移位算子有如下性質由差分的定義及不變算子和移位算子有如下性質: : kkIff1kkEff1()kkk

34、kkkfffEfIfEI fEI 1IE 1122EE111()kkkkkkfffIfEfIEf111122221122()kkkkkkfffE fEfEEf47差分的性質差分的性質性質性質1 1：各階差分均可用函數(shù)值表示，如：各階差分均可用函數(shù)值表示，如：性質性質2 2：某點的函數(shù)可用各階差分來表示：某點的函數(shù)可用各階差分來表示：00()( 1)( 1)nnnnjnjjkkkk njjjnnfEIfEffjj 100()( 1)( 1)nnnnn jj nn jkkkkj njjnnfIEfEffjj 00()nnnnjjn kkkkkjjnnfE fIfffjj 48性質性質3 3：差商與

35、差分有如下關系：差商與差分有如下關系：性質性質4 4：差分與導數(shù)有如下關系：差分與導數(shù)有如下關系：111,(1,2, )!mkkk mkmf xxxfmnm h111,(1,2, )!mkkk mkmf xxxfmnm h( )( ),(,)nnnkkk nfh fxx49差分的計算差分的計算kf( ) 22() 33() 44() 0f1f2f3f4f23()ff34()ff01()ff12()ff2224()ff2202()ff2213()ff3314()ff3303()ff4404()ffReturnReturn504.4 牛頓插值公式牛頓插值公式根據(jù)差商的定義，把根據(jù)差商的定義，把 看

36、成看成 上的一點，上的一點，可得：可得：x , a b000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010101 , ,()nnnnf x xxf x xxf x x xxxx514.4 牛頓插值公式牛頓插值公式根據(jù)差商的定義，把根據(jù)差商的定義，把 看成看成 上的一點，上的一點，可得：可得：x , a b000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010101 , ,()nnnnf x xxf x xxf x x xxxx0010( )(),()f xf xf

37、x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011 ,( )( )( )nnnnf x x xxxNxR x把后一式代入前一式把后一式代入前一式52其中其中 顯然顯然 滿足插值條件，且次數(shù)不超過滿足插值條件，且次數(shù)不超過 , ,它就它就是插值多項式，其系數(shù)為：是插值多項式，其系數(shù)為： 我們稱我們稱 為牛頓插值多項式為牛頓插值多項式. .0010( )(),()nNxf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx01101( )()()(1( )( )( ) ,( )!nnnnnnR xf

38、 xNxf x x xxxfxxxxn ( )nNxn01,iiaf x xx0,1,in( )nNx53( )f x 已知已知 的函數(shù)表，求的函數(shù)表，求4 次牛頓插值多項式次牛頓插值多項式, , 并求并求算例算例(0.596).f54從表中可以看到從表中可以看到4 階差商階差商幾乎為幾乎為0 0，故取，故取4 4次插值多項式即可，次插值多項式即可，于是：于是：0.400.400.410750.410750.550.550.578150.578151.116001.116000.650.650.696750.696751.186001.186000.280000.280000.800.800.

39、888110.888111.275731.275730.358930.358930.197330.197330.900.901.026521.026521.384101.384100.433480.433480.213000.213000.031340.031341.051.051.253821.253821.515331.515330.524930.524930.228630.228630.031260.03126-0.00012-0.00012解：列表計算解：列表計算 4( )(0.4)(0.4)(0.55)(0.4)(0.55)(0.60.41075 1.1665)(0.4)(0.55)

40、(0.65)(0.8)0.280.197330.03134N xxxxxxxxxxx 已知已知 的函數(shù)表，求的函數(shù)表，求4 次牛頓插值多項式次牛頓插值多項式, , 并求并求算例算例(0.596).f( )f x4(0.596)(0.596)0.63192fN550.400.400.410750.410750.550.550.578150.578151.116001.116000.650.650.696750.696751.186001.186000.280000.280000.800.800.888110.888111.275731.275730.358930.358930.197330.19

41、7330.900.901.026521.026521.384101.384100.433480.433480.213000.213000.031340.031341.051.051.253821.253821.515331.515330.524930.524930.228630.228630.031260.03126-0.00012-0.00012解：列表計算解：列表計算 已知已知 的函數(shù)表，求的函數(shù)表，求4 次牛頓插值多項式次牛頓插值多項式, , 并求并求算例算例(0.596).f( )f x截斷誤差為：截斷誤差為：40459( ) ,(0.596)3.63 10R xf xx4( )(0.

42、4)(0.4)(0.55)(0.4)(0.55)(0.60.41075 1.1665)(0.4)(0.55)(0.65)(0.8)0.280.197330.03134N xxxxxxxxxxx4(0.596)(0.596)0.63192fN56 和和 均是均是 n 次多項式次多項式, ,且均滿足插值條件且均滿足插值條件: : 由多項式的唯一性由多項式的唯一性, , ,因而因而, ,兩個公式兩個公式的余項是相等的的余項是相等的, ,即即 當插值多項式從當插值多項式從 n-1 次增加到次增加到 n 次時次時, ,拉格朗日型插值必須重新計算所有的基本插值多項式拉格朗日型插值必須重新計算所有的基本插值

43、多項式; ;而對于牛頓型插值而對于牛頓型插值, ,只需用表格再計算一個只需用表格再計算一個 n 階差商階差商, , 然后加上一項即可。然后加上一項即可。牛頓插值公式和牛頓插值公式和Lagrange插值公式比較插值公式比較( )nL x( )nNx ()()(), 0,1,niniiL xNxf xin ( )( )nnLxNx(1)01( ) ,( )( )(1)!nnnnff x x xxxxn ReturnReturn574.5 分段插值公式分段插值公式 在區(qū)間在區(qū)間 a, b 上用插值多項式上用插值多項式 P 逼近函數(shù)逼近函數(shù) f 時，時，f 和和P 在每個節(jié)點上的差異在每個節(jié)點上的差異

44、(理論上理論上)應該為零。自然，我們期望應該為零。自然，我們期望在一切中間點上也能很好地逼近在一切中間點上也能很好地逼近 f ，并且當插值點增加時，并且當插值點增加時這種逼近效果應該越來越好。這種逼近效果應該越來越好。 但上述的期望不可能實現(xiàn)的。當認識到這一點時，在數(shù)但上述的期望不可能實現(xiàn)的。當認識到這一點時，在數(shù)學界曾引起強烈的震動。學界曾引起強烈的震動。 20 世紀初，世紀初，Runge就給出了一個等距節(jié)點插值多項式就給出了一個等距節(jié)點插值多項式 不收斂到不收斂到 的例子。的例子。( )nLx( )f x58 設函數(shù)設函數(shù) ，在該區(qū)間在該區(qū)間 上取上取 個等距節(jié)點個等距節(jié)點, 構造構造 的

45、的 次次 拉格朗日插值多項式為拉格朗日插值多項式為21( ), 5,51f xxx 5,51n( )f xn5 10(0,1, )iixinn 2,4,6,8,20n 其其matlab的的lagrange.m文件及相關圖形如下文件及相關圖形如下.njnjiiijijnxxxxxxL002)()(11)(Runge 現(xiàn)象現(xiàn)象59% lagrange.mfunction y=lagrange (x0,y0,x)n=length(x0);m=length(x);for i=1:m z=x(i);s=0; for k=1:n L=1; for j=1:n if j=k L=L*(z-x0(j)/(x0

46、(k)-x0(j); end end s=s+L*y0(k); end y(i)=s;endy; Lagrange插值多項式插值多項式求插值的求插值的Matlab程序程序.60%Compare_Runge.mx=-5:0.1:5;z=0*x;y=1./(1+x.2);plot(x,z,k,x,y,r)axis(-5 5 -1.5 2);pause,hold onfor n=2:2:20 x0=linspace(-5,5,n+1); y0=1./(1+x0.2); x=-5:0.1:5; y1=lagrange(x0,y0,x); plot(x,y1), pauseendy2=1./(1+x0.

47、2);y=interp1(x0,y2,x);plot (x,y,k),hold offgtext(n=2),gtext(n=4),gtext(n=6)gtext(n=8),gtext(n=10)gtext(f(x)=1/(1+x2)比較不同的插值多項式次數(shù)對插值的影響比較不同的插值多項式次數(shù)對插值的影響61-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3

48、-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次數(shù)的不同次數(shù)的Lagrange插值多項式的比較圖插值多項式的比較圖Runge現(xiàn)象現(xiàn)象 62令令 ，則，則 ， 下表列出了下表列出了 和和 的值。的值。1/211()2nnnxxx1/255nxn2,4,20n 1/2()nnL x1/2()nR x63 結果表明結果表明,隨著隨著

49、 的增加，的增加， 的絕對值幾乎成倍地增的絕對值幾乎成倍地增加，這說明當加，這說明當 時時 在在 上不收斂。上不收斂。 Runge證明了，存在一個常數(shù)證明了，存在一個常數(shù) , 使得當使得當 時，時， ; 而當而當 時時 發(fā)散。發(fā)散。 說明說明: 并不是插值多項式的次數(shù)越高并不是插值多項式的次數(shù)越高, 插值效果越好插值效果越好, 精度精度也不一定是隨次數(shù)的提高而升高也不一定是隨次數(shù)的提高而升高, 這種現(xiàn)象在上個世紀初由這種現(xiàn)象在上個世紀初由Runge發(fā)現(xiàn)發(fā)現(xiàn), 故稱為故稱為Runge現(xiàn)象現(xiàn)象.n1/2()nR xn nL 5,53.63cxclim ( )( )nnL xf x xc ( )nL

50、 x64 分段線性插值特別簡單，從幾何上看，就是用分段線性插值特別簡單，從幾何上看，就是用折線逼近折線逼近曲線曲線。 分段線性插值的數(shù)學定義分段線性插值的數(shù)學定義 設設 是區(qū)間是區(qū)間 上的函數(shù)，在節(jié)點上的函數(shù)，在節(jié)點 上的函數(shù)值為上的函數(shù)值為 ，求一分段折線函數(shù)求一分段折線函數(shù) 滿足：滿足：（1 1） （2 2） 在在 上，上， 是一次多項式。是一次多項式。（3 3）則稱則稱 為為 的的分段線性插值函數(shù)分段線性插值函數(shù)。4.5.1 分段線性插值分段線性插值( )f x , a b01naxxxb01,nfff( ) , P xC a b(),0,1,iiP xf in1,iixx( )P x1

51、,iixx( )P x( )P x65 1,iixx0,1,1in( )P x易知易知, P(x) 是個折線函數(shù)，在每個區(qū)間是個折線函數(shù)，在每個區(qū)間上上,有有在在 a,b 上是連續(xù)的，但其一階導數(shù)是不連續(xù)的上是連續(xù)的，但其一階導數(shù)是不連續(xù)的. 1111( )iiiiiiiixxxxyyxxxxp x66 當當 時時, , 當當 時時, ,4.5.1 分段線性插值的基函數(shù)分段線性插值的基函數(shù)0i 10101001,( )0,xxxxxxxlxxxx1,2,1in11111111,( )( ,0,iiiiiiiiiiiiixxxxxxxl xxxxx xxxxxx 當當 時時, ,11110,(

52、),nnnnnnnnxxxlxxxxxxxxin67顯然顯然 是是 的線性組合：的線性組合： 在區(qū)間在區(qū)間 上的值為：上的值為：( )P x( )il x0( )( )niiiP xf l x11111( )iiiiiiiiiixxxxP xffxxxxxxx1,iixx，表達式表達式 在區(qū)間在區(qū)間上，只有上，只有是非零的，其它基函數(shù)均為零。即是非零的，其它基函數(shù)均為零。即注意注意( )P x1,iixx1( ) ,ilx( )il x11( )( )( )iiiiP xflxf l x68算例算例節(jié)點（如下表），求區(qū)間上分段線性插值函數(shù)，并利用節(jié)點（如下表），求區(qū)間上分段線性插值函數(shù)，并利用

53、它求出它求出21()1yfxx (4.5)f已知函數(shù)已知函數(shù)近似值。近似值。在區(qū)間在區(qū)間 0,5 上取等距插值上取等距插值69 ,1k k 11(1)( )(1)(1)(1)()kkkkxkx kP xyykkkky x kyx k (1) 0.5 , 0,10.5(2) 0.2(1), 1,2( )0.2(3) 0.1(2), 2,30.1(4) 0.05882(3), 3,40.05882(5) 0.038xxxxxxP xxxxxxxx 46(4),4,5xx (4.5)0.05882 (4.5 5) 0.03846 (4.5 4)0.04864P (4.5)0.047058823529

54、41f解解: : 在每個分段區(qū)間在每個分段區(qū)間于是，于是，實際值實際值: : 當當n=7 時，時， P(4.5)=0.04762270321996 ; 當當n=10時，時，P(4.5)=0.04705882352941由此可見，對于光滑性要求不高的插值問題，分段線性插值的由此可見，對于光滑性要求不高的插值問題，分段線性插值的效果非常好！計算也簡單效果非常好！計算也簡單!704.5.2 埃爾米特埃爾米特 (Hermite) 插值插值拉格朗日和牛頓均只保證函數(shù)插值；拉格朗日和牛頓均只保證函數(shù)插值；實際問題有時需要導數(shù)也插值；實際問題有時需要導數(shù)也插值；滿足這種需要的插值稱為埃爾米特插值滿足這種需要

55、的插值稱為埃爾米特插值. .71埃爾米特插值的一般提法為：埃爾米特插值的一般提法為： 設函數(shù)在節(jié)點設函數(shù)在節(jié)點 的函數(shù)值與導數(shù)值為：的函數(shù)值與導數(shù)值為：其中其中 是正整數(shù)，是正整數(shù)，尋求一個次數(shù)盡可能低的多尋求一個次數(shù)盡可能低的多項式項式 ，滿足：，滿足：埃爾米特插值的一般提法埃爾米特插值的一般提法01,nxxx( ),iif xf( ),iifxf ,(1)(1)( ),iimmiifxf0,1,in01,nm mm( )H x( )( )( ),kkiiHxf0,1,in0,1,1;ikm72 以如下數(shù)據(jù)構建埃爾米特插值以如下數(shù)據(jù)構建埃爾米特插值 埃爾米特插值埃爾米特插值算例算例73 以如

56、下數(shù)據(jù)構建埃爾米特插值以如下數(shù)據(jù)構建埃爾米特插值 埃爾米特插值埃爾米特插值算例算例共有共有 個條件，可唯一確定一個次數(shù)個條件，可唯一確定一個次數(shù)不超過不超過 的多項式的多項式 ，其形，其形式為：式為：目標：求出所有的目標：求出所有的 , ,方法：基函數(shù)法方法：基函數(shù)法. .22n21n21( )nHx21210121( )nnnHxaa xaxia(0,1, )in74可如下構造：可如下構造： 2100( )( )( )nnniiiiiiHxyxyx ( ),( )iixx 均為均為 2 n+1 次插值基函數(shù)次插值基函數(shù). . (),()0ikikikxx ()0,()ikikikxx 這樣這

57、樣 可表示為：可表示為：21( )nHx210( )( )( )nniiiiiHxyxyx顯然有：顯然有：21()nkkHxy21()nkkHxy75現(xiàn)在求現(xiàn)在求 及及 ，令令其中其中從而有：從而有：由此得：由此得： ，故：故： ，( )ix ( )ix 2( )() ( )iixaxb lx 011011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx2( )() ( )1iiiiixaxb lx ( )( )( )2() ( )0iiiiiiiiixl xal xaxb l x ()1iaxb2 ( )1iial x2 ( )iial x

58、12( )i iibxl x 76由由 的表達式可得：的表達式可得：于是得到：于是得到：同理可得同理可得( )il x01( )niikikk il xxx201( )12()( )niiikikk ixxxlxxx 2( )() ( )iiixxx lx 77例：例：已知已知233sin,214sin,216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計算插值計算 sin 50 并估計誤差。并估計誤差。 解：解：0 x1x2x185500 n = 1分別利用分別利用x0, x1 以及以及 x1, x2 計算計算4,610 xx利用利用216/4/6/21

59、4/6/4/)(1 xxxL這里這里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的實際誤差的實際誤差 0.010010.010013,421 xx 利用利用sin 50 0.76008, 00660. 018500538. 01 R內(nèi)插內(nèi)插 /* interpolation */ 的實際誤差的實際誤差 0.005960.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計算的要計算的 x 所在的區(qū)間的所在的區(qū)間的端點，插值效果較好。端點，插值效果較好。78n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3co