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

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

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

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

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

6、式存在代數多項式p(x)一致逼近一致逼近f(x),并達到所要求的精度并達到所要求的精度)。因此，我們主要考慮代數多項式的插值問題。因此，我們主要考慮代數多項式的插值問題。6x0 , x1, , xn 插值節點插值節點, 函數函數 P(x) 稱為函數稱為函數 y=f(x) 的插值函數，的插值函數，區間區間 a, b 稱為插值區間。稱為插值區間。 7例題例題: :已知函數已知函數 f(x) 有如下數據有如下數據:求求 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) 產生的產生的誤差？誤差？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)(條件：無重合節點，即條件：無重合節點，即jixx ji 4.2 拉格朗日多項式拉格朗日多項式 /* Lagrange Polynomial */ 根據插值條件，有：根據插值條件，有：nnnnnnnnnnyxaxaaxPyxaxaaxPyxaxaaxP10111101000100)()()(其系數矩陣的行列式為其系數矩陣

9、的行列式為nnnnnnnxxxxxxxxxV111),(110010(),0,1,niipxyinVandermonde行列式行列式12), 2 , 1(nixi0)(),(010nijjinnxxxxxVnaaa,10注意到插值節點注意到插值節點兩兩相異，而兩兩相異，而故方程組故方程組(1)(1)有惟一解有惟一解于是滿足插值條件的多項式存在且惟一。于是滿足插值條件的多項式存在且惟一。nxxx,10nnnxaxaaxP10)(iinyxP)(由由n+1個不同插值節點個不同插值節點可以惟一確定一個可以惟一確定一個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 */ 線性插值線性插值基函數基函數1. 構造線性插值基函數的方法構造線性插值基函數的方法:iiiyxlyxxxxyxxxxxxxxyyyxL)()()(1010100101001010114線性插值與其基函數示意圖線性插值與其基函數

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=仿照線性插值基函數的構造方法，令仿照線性插值基函數的構造方法，令)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl拋物線基拋物線基函數函數2()Lx稱其為拋物線插值基函數稱其為拋物線插值基函數(如上右圖所示如上右圖所示)。 2( )L x00( ,)xy17)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl拋物線插值基函數

13、拋物線插值基函數于是于是拋物線基函數拋物線基函數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設設 函數表函數表 則滿足插值條件的多項式則滿足插值條件的多項式（Lagrange）插值多項式）插值多項式 nkkknxlxfxL0)()( ）( )yf x, , ,(,(,( )(0 1.),ijiixxx f xinij()() (0,1. )，niiLxf xin其中其中, ., .0()(0,1,. )

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

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

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

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

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

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

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

22、0.333487sin0.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

23、.3334870.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用拋物線插值時，取所有節點，得到用拋物線插值時，取所有節點，得到2sin0.3367(0.3367 0.34)(0.3367 0.36)(0.3367 0.

24、32)(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)

25、sin 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 位有效數字位有效數字. ReturnRetur

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

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

28、為此引入 差差商和差分商和差分的概念的概念. .P(x)應滿足插值條件：應滿足插值條件：有：有：374.3.1 4.3.1 差商的概念差商的概念從零階差商出發，歸納地定義各階差商從零階差商出發，歸納地定義各階差商:稱稱 為函數為函數 關于點關于點 的的一階差商一階差商.( )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 記函數記函數 在在 的值的值 ，稱稱 為為 關于關于 的的零階差商零階

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：差商可表示為函數值的線性組合，即：差商可表示為函數值的線性組合，即：性質性質2 2：差商關于所含節點是對稱的，即：差商關于所含節點是對稱的，即：010011(),()()()()njnjjjjjjjnf xf xxxxxxxxxxx011010,nnnnf xxxf x xx

30、f xxx可用歸納法證明40差商的基本性質差商的基本性質性質性質3：性質性質4：設設 在在 存在存在 n 階導數，且階導數，且 則則 ，使得，使得:12011011 ,imiimmif xxxf xxxf 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 x

31、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 差分差分 在前面的討論中，節點是任意分布的，但實際上在前面的討論中，節點是任意分布的，但實際上經常遇經常遇到等距節點的情況，這時插值公式可以得到簡化到等距節點的情況，這時插值公式可以得到簡化，為此，我，為此，我們先介紹差分的概念。們先介紹差分的概

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

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

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

35、分有如下關系：差商與差分有如下關系：性質性質4 4：差分與導數有如下關系：差分與導數有如下關系：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 牛頓插值公式牛頓插值公式根據差商的定義，把根據差商的定義，把 看成

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

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

38、x x xxxfxxxxn ( )nNxn01,iiaf x xx0,1,in( )nNx53( )f x 已知已知 的函數表，求的函數表，求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.888110

39、.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)(0.65)

40、(0.8)0.280.197330.03134N xxxxxxxxxxx 已知已知 的函數表，求的函數表，求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.197330.9

41、00.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.596).f( )f x截斷誤差為：截斷誤差為：40459( ) ,(0.596)3.63 10R xf xx4( )(0.4)(0.4

42、)(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 分段插值公式分段插值公式 在區間在區間 a, b 上用插值多項式上用插值多項式 P 逼近函數逼近函數 f 時，時，f 和和P 在每個節點上的差異在每個節點上的差異(理論上理論

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

45、格朗日插值多項式為拉格朗日插值多項式為21( ), 5,51f xxx 5,51n( )f xn5 10(0,1, )iixinn 2,4,6,8,20n 其其matlab的的lagrange.m文件及相關圖形如下文件及相關圖形如下.njnjiiijijnxxxxxxL002)()(11)(Runge 現象現象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(k)-x0

46、(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.2);y=i

47、nterp1(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)比較不同的插值多項式次數對插值的影響比較不同的插值多項式次數對插值的影響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-2-101

48、2345-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)不同次數的不同次數的Lagrange插值多項式的比較圖插值多項式的比較圖Runge現象現象 62令令 ，則，則 ， 下表列出了下表列出了 和和 的值。的值。1/211()2nnnxxx1/255nxn2,4,20n 1/2()nnL x1/2()nR x63 結果表明結果表明,隨著隨著 的增加，的

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

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

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

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

53、出21()1yfxx (4.5)f已知函數已知函數近似值。近似值。在區間在區間 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.04705882352941f解解:

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

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

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

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

58、 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/214/6/4/)(1 xx

59、xL這里這里)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內插內插 /* interpolation */ 的實際誤差的實際誤差 0.005960.00596內插通常優于外推。選擇內插通常優于外推。選擇要計算的要計算的 x 所在的區間的所在的區間的端點，插值效果較好。端點，插值效果較好。78n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)