數(shù)值分析第章插值法

1、2022-7-5第2章 插值法1第第2章章 插值法插值法/* Chapter 2 Interpolation */2.1 引言引言2.2 Lagrange插值插值2.3 差商與差商與 Newton插值插值2.4 帶導(dǎo)數(shù)條件的帶導(dǎo)數(shù)條件的Hermite插值插值2.5 分段低次插值分段低次插值2.6 三次樣條插值三次樣條插值2022-7-5第2章 插值法2&插值法是數(shù)值分析中的一個古老的分支。插值法是數(shù)值分析中的一個古老的分支。&等距節(jié)點內(nèi)插法等距節(jié)點內(nèi)插法隋朝數(shù)學(xué)家劉焯隋朝數(shù)學(xué)家劉焯(公元公元544-610年年)首先提出的首先提出的&不等距節(jié)點內(nèi)插法不等距節(jié)點內(nèi)插法唐朝數(shù)

2、學(xué)家張遂唐朝數(shù)學(xué)家張遂(公元公元683-727年年)首先提出的首先提出的&插值法在數(shù)值積分、數(shù)值微分、微分方程數(shù)值解、曲插值法在數(shù)值積分、數(shù)值微分、微分方程數(shù)值解、曲線曲面擬合、函數(shù)值近似計算中有著廣泛的應(yīng)用。線曲面擬合、函數(shù)值近似計算中有著廣泛的應(yīng)用。2.1 引言引言2.1.1 插值法的提出插值法的提出F以近似計算函數(shù)值為例說明插值法的應(yīng)用。以近似計算函數(shù)值為例說明插值法的應(yīng)用。歷史背景歷史背景2022-7-5第2章 插值法3插值法就是一種最簡單的重要方法插值法就是一種最簡單的重要方法函數(shù)的插值法的提出背景函數(shù)的插值法的提出背景實際問題中經(jīng)常要涉及到實際問題中經(jīng)常要涉及到函數(shù)值的計算

3、函數(shù)值的計算問題：問題：（1）如果如果函數(shù)表達式函數(shù)表達式本身比較復(fù)雜，且需要多次本身比較復(fù)雜，且需要多次重復(fù)計重復(fù)計算算時，計算量會很大；時，計算量會很大； （2）有的函數(shù)甚至有的函數(shù)甚至沒有表達式?jīng)]有表達式，只是一種，只是一種表格函數(shù)表格函數(shù)，而，而我們需要的函數(shù)值不在該表格中。我們需要的函數(shù)值不在該表格中。 對于這兩種情況，我們都需要尋找一個對于這兩種情況，我們都需要尋找一個計算方便且表計算方便且表達簡單達簡單的函數(shù)來的函數(shù)來近似代替近似代替，這就是，這就是數(shù)值逼近數(shù)值逼近問題。問題。 2022-7-5第2章 插值法4設(shè)函數(shù)設(shè)函數(shù)f(x)在區(qū)間在區(qū)間a,b上有定義，且已知在點上有定義，且

4、已知在點 ax0 x1 xn b 處的函數(shù)值處的函數(shù)值 y0 = f(x0), y1 = f(x1), yn = f(xn)，若存，若存在一簡單的函數(shù)在一簡單的函數(shù) P(x)，滿足條件，滿足條件P(xi) = f(xi) (i = 0,1, n)，就稱就稱P (x) 稱為稱為f(x) 的的插值函數(shù)插值函數(shù)。插值法插值法點點x0 , x1 , , xn 稱為稱為插值節(jié)點插值節(jié)點，區(qū)間，區(qū)間a,b稱為稱為插值區(qū)插值區(qū)間，間，求插值函數(shù)求插值函數(shù)P(x)的方法稱為的方法稱為插值法插值法。幾何幾何意義：意義：x0 x1x2x3x4xP(x) f(x)2022-7-5第2章 插值法5常用常用插值函數(shù)的類

5、型插值函數(shù)的類型代數(shù)代數(shù)插值：多項式插值插值：多項式插值, 0,)(0111 nnnnnaaxaxaxaxP有理有理插值：有理分式函數(shù)插值：有理分式函數(shù)三角三角插值：三角函數(shù)插值：三角函數(shù))()()(xQxPxPnm 2.1.2 多項式插值多項式插值/* Polynomial Interpolation */ ), 1 , 0()(niyxPii （1.3）bxxxan 10 設(shè)在區(qū)間設(shè)在區(qū)間 上給定上給定 個點個點,ba1 n上的函數(shù)值上的函數(shù)值 , ,求次數(shù)不超過求次數(shù)不超過 的多項式的多項式 ，使，使), 1 , 0)(nixfyii n)(xP多項式插值問題多項式插值問題 2022-7

6、-5第2章 插值法6由由插值條件插值條件得關(guān)于系數(shù)得關(guān)于系數(shù) 的的 元線性方程組元線性方程組naaa,101 n ,101111000010nnnnnnnnnyxaxaayxaxaayxaxaa（1.4） 問題：問題： P(x)是否存在？若存在，是否唯一？如何求？是否存在？若存在，是否唯一？如何求？nnxaxaaxP 10)(系數(shù)矩陣為系數(shù)矩陣為,1111100 nnnnnxxxxxxA（1.5）nnnnnxxxxxxA1010111 2022-7-5第2章 插值法7稱為稱為范德蒙德（范德蒙德（Vandermonde）矩陣）矩陣, ,由由 互異，故互異，故),1 ,0(nixi .0)(det

7、1, njiojijixxA因此線性方程組因此線性方程組（1.4）的解的解 存在且唯一存在且唯一. .naaa,10 結(jié)論結(jié)論定理定理1 設(shè)設(shè)x0 ,x1,xn 是是n+1個互異節(jié)點個互異節(jié)點,函數(shù)函數(shù)f(x)在這組節(jié)在這組節(jié)點的值點的值yk=f(xk)(k=0,1,n)是給定的，那么存在唯一的次是給定的，那么存在唯一的次數(shù)數(shù)n的的多項式多項式P (x)滿足滿足 P (xk)= yk, k=0,1,n。?P(x) 但遺憾的是但遺憾的是方程組方程組(1.4)是病態(tài)方程組是病態(tài)方程組,階數(shù)階數(shù)n越高，病態(tài)越高，病態(tài)越嚴(yán)重越嚴(yán)重。為此我們從另一途徑尋求獲得。為此我們從另一途徑尋求獲得P(x) 的方法

8、的方法-Lagrange插值和插值和Newton插值。（這兩種方法稱為基函數(shù)法）插值。（這兩種方法稱為基函數(shù)法）2022-7-5第2章 插值法8Interpolation polynomial 2022-7-5第2章 插值法92.2 拉格朗日多項式拉格朗日多項式 niyxPiin,., 0,)( 求求 n 次多項式次多項式 使得使得nnnxaxaaxP 10)(條件：條件：無重合節(jié)點，即無重合節(jié)點，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP P1(x) 是過是過 ( x0 , y0 ) 和和

9、 ( x1, y1 ) 兩點的直線。兩點的直線。)(1xP101xxxx 010 xxxx = y0 + y12.1.1 線性插值與拋物插值線性插值與拋物插值兩點式兩點式)()(0010101xxxxyyyxP 點斜式點斜式)(001010 xxxxxxy ()ff線性插值線性插值2022-7-5第2章 插值法10二次插值二次插值n = 2已知已知 x0 , x1 , x2; y0 , y1 ,y2 , 求求22102)(xaxaaxP 使得使得002,)(yxP112)(yxP 222)(yxP ,2020100 xaxaay 2121101xaxaay 2222102xaxaay 方程組求

10、解麻煩方程組求解麻煩拋物插值拋物插值 思路：思路：對于線性插值的對于線性插值的兩種形式解兩種形式解進行適當(dāng)?shù)姆治鲞M行適當(dāng)?shù)姆治? 從從中尋求規(guī)律得到中尋求規(guī)律得到拉格朗日插值拉格朗日插值(公式公式)和和牛頓插值牛頓插值(公式公式).我們先來看看如何得到我們先來看看如何得到二次拉格朗日插值公式二次拉格朗日插值公式.)(1xP101xxxx 010 xxxx = y0 + y1兩點式兩點式)()(0010101xxxxyyyxP 點斜式點斜式)(001010 xxxxxxy ()ff2022-7-5第2章 插值法11 首先首先, 線性插值的兩點式可看作是兩個特殊的一次線性插值的兩點式可看作是兩個特

11、殊的一次式的一種線性組合式的一種線性組合.101xxxx 010 xxxx )(1xP= y0 + y1 10)(iiiyxl對稱式對稱式l0(x)l1(x)實質(zhì)上實質(zhì)上0l（x）和）和1l（x）即是滿足函數(shù)表）即是滿足函數(shù)表 的一次插值多項式的一次插值多項式 ,稱稱l0(x)和和l1(x)為以為以x0,x1為節(jié)點的基本插為節(jié)點的基本插值多項式，也稱為值多項式，也稱為線性插值線性插值的的插值基函數(shù)插值基函數(shù) 。基函數(shù)的線性組合基函數(shù)的線性組合基函數(shù)法基函數(shù)法滿足滿足 li(xj)= ij 顯然有顯然有l(wèi)0(x)+ l1(x)1.其中，其中， l0(x)和和l1(x)滿足：滿足： l0(x0)=

12、1, l0(x1)=0, l1(x0)=0, l1(x1)=1, L1(x) L1(xj) 10)(iiiyxjl =yj2022-7-5第2章 插值法12啟發(fā)啟發(fā): :其中，其中，l0(x), l1(x), l2(x)都是都是二次多項式二次多項式，且應(yīng)滿足，且應(yīng)滿足滿足滿足(2.1) 的的 l i(x) 是否存在是否存在?若存在，具有什么形式呢若存在，具有什么形式呢?（2.1）二次二次Lagrange插值多項式為插值多項式為 L(x)= y0l0(x) + y1l1(x) + y2l2(x) 二次插值是否能由一些二次插值是否能由一些二次插值基函數(shù)二次插值基函數(shù)來線性組合？來線性組合？先考慮先

13、考慮 l0(x)。 l0(x) 0(x x1)(x x2), 其中其中 0 是待定系數(shù)。是待定系數(shù)。2022-7-5第2章 插值法13同理同理 l1(x) 1(x x0)(x x2), l2(x) 2(x x0)(x x1),1(x1x0)(x1x2)12(x2x0)(x2x1)1此即此即二次拉格朗日插值公式二次拉格朗日插值公式, 其中其中, l0(x), l1(x), l2(x)是滿足是滿足(2.1)的特殊的特殊(基本基本)二次插值多項式二次插值多項式;稱為稱為二次插值基函數(shù)二次插值基函數(shù).L2(x)= y0+ y1+ y2(x - -x0)(x - -x2)(x1- -x0)(x1- -x

14、2)(x - -x1)(x - -x2)(x0- -x1)(x0- -x2)(x - -x0)(x - -x1)(x2- -x0)(x2- -x1)0(x0 x1)(x0 x2)1 l0(x) 0(x x1)(x x2), 由由 l0( x0)=1，所以，所以 0(x0 x1)(x0 x2)1，則，則 L2(xj) 20)(iiiyxjl =yj2022-7-5第2章 插值法14n 1li(x)每個每個 li 有有 n 個根個根 x0 xi xn njj i jiniiixxCxxxxxxCxl00)().().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)

15、()()( niiinyxlxL0)()( Lagrange Polynomial與與 有關(guān)，而與有關(guān)，而與 無關(guān)無關(guān)節(jié)點節(jié)點f2.2.2 拉格朗日插值多項式拉格朗日插值多項式)()()()()()()(110110niiiiiiniiixxxxxxxxxxxxxxxxxl )., 1 , 0(ni 展開展開n 次插值多項式次插值多項式 :求次數(shù)求次數(shù)n的多項式的多項式Ln(x), 使其滿足使其滿足 Ln(x0)=y0 , Ln(x1)=y1 , . , Ln(xn)=yn 令令 Ln(x)=l0(x)y0 + l1(x)y1 + +ln(x)yn ., 0;, 1)(jijixlji2022

16、-7-5第2章 插值法15例例1 已知已知 ， ，用線性插值求，用線性插值求 的近似值的近似值.解：解：xy 9, 410 xx73, 210 yy基函數(shù)分別為基函數(shù)分別為949)(0 xxl494)(1 xxl)9(51 x)4(51 x插值多項式為插值多項式為L1(x)=l0(x)y0 + l1(x)y1)4(513)9(512 xx)4(513)9(512 xx)6(51 x7)7(1L 6 . 2 2022-7-5第2章 插值法16其中其中滿足條件滿足條件 nkkknxlyxL0)()( ), 1 , 0,(., 0;, 1)(nkjjkjkxljk)()()()()()()(1101

17、10nkkkkkknkkkxxxxxxxxxxxxxxxxxl )., 1 , 0()()(0njyxlyxLjnkjkkjn （2.9）易求得易求得 ),()()()(1101nkkkkkkknxxxxxxxxx ),()()(101nnxxxxxxx（2.10）記記.)()()()(011 nkknknknxxxxyxL （2.11）2022-7-5第2章 插值法17 注意注意: : 次插值多項式次插值多項式 通常是次數(shù)為通常是次數(shù)為 的多項式，的多項式，n)(xLnn特殊情況下次數(shù)可能小于特殊情況下次數(shù)可能小于 . .n注：注：若不將多項式次數(shù)限制為若不將多項式次數(shù)限制為 n ，則插值多

18、項式，則插值多項式不唯一不唯一。例如例如 也是一個插值也是一個插值多項式，其中多項式，其中 可以是任意多項式?？梢允侨我舛囗検?。 niinxxxpxLxP0)()()()()(xp例例2 求經(jīng)過求經(jīng)過A(0,1)，B(1,2)，C(2,3)三個點的二次三個點的二次Lagrange插值多項式插值多項式.解：解：.322110221100 yxyxyx，；，；，2120210121012002010212)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL 13)12)(02()1)(0(2)21)(01()2)(0(1)20)(10()2)(1( xxxxxxx

19、插值條件插值條件2022-7-5第2章 插值法18設(shè)節(jié)點設(shè)節(jié)點)1( nf在在(a , b)內(nèi)存在內(nèi)存在, 考察考察截斷誤差截斷誤差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 滿足條件滿足條件 , 2.2.3 插值余項插值余項 (Remainder)羅爾定理羅爾定理 設(shè)設(shè)f(x)在在a,b內(nèi)連續(xù)，在內(nèi)連續(xù)，在(a,b)內(nèi)可導(dǎo)，且有內(nèi)可導(dǎo)，且有 f(a)=f(b)；則在；則在(a,b)內(nèi)一定存在一點內(nèi)一定存在一點，使得，使得 。0)( f顯然顯然 Rn(xi ) =f(xi)-Ln(xi)=0 , i=0,1,n, 設(shè)設(shè)Rn(x)=K(x) n+1(x), 現(xiàn)在

20、任意固定一點現(xiàn)在任意固定一點 x a,b, xxi (i=0,1,n),引進輔助函數(shù)引進輔助函數(shù) g(t)=f(t)- Ln(t)-K(x) n+1(t), 則則g(t)在在(a,b)上具有上具有n+1階導(dǎo)數(shù)，在階導(dǎo)數(shù)，在 t= x0, x1, xn, x 諸點諸點處函數(shù)值皆等于零。處函數(shù)值皆等于零。即即g(t)在在a,b中有中有n+2個零點。個零點。由由羅爾定理羅爾定理知知g(t)在在a,b中有中有n+1個零點。個零點。2022-7-5第2章 插值法19如此反復(fù)，最后可推知如此反復(fù)，最后可推知g(n+1)(t)在在a,b中有中有1個零點個零點 ，即有，即有 g(n+1)( )=0, a b.

21、)()()()()()1(1)1()1()1(txKtLtftgnnnnnn )!1)()()1( nxKtfn則有則有0)()!1()()()1()1( xKnfgnn)!1()()()1( nfxKn從而從而)()()!1()()()()(10)1(nnnxxxxxxnfxLxfxR 截斷誤差截斷誤差存存在在時時成成立立)()1(xfn n = 1n = 2,)( )(21)()(21)(101021xxxxxxfxfxR ，,)()( )(61)(202102xxxxxxxxfxR ，（2.12）2022-7-5第2章 插值法20注：注：FF 通常不能確定通常不能確定 x , 而是估計而

22、是估計 , x (a,b) 將將 作為誤差估計上限。作為誤差估計上限。1)1()( nnMxf niinxxnM01|)!1(FF當(dāng)當(dāng) f(x) 為任一個次數(shù)為任一個次數(shù) n 的的多項式多項式時，時， , 可知可知 ，即插值多項式對于次數(shù)，即插值多項式對于次數(shù) n 的的多項多項式是式是精確精確的。的。0)()1( xfn0)( xRn當(dāng)當(dāng) 時，時，)()(nkxxfk, 0)()(0 xlxxxRniikikn0)()1(xfn, ,于是于是由此得由此得., 1 , 0,)(0nkxxlxkniiki （2.17）特別當(dāng)特別當(dāng) 時，時，0k. 1)(0 xlnii（2.18）)()(0 xlx

23、xLniikin 2022-7-5第2章 插值法21 例例3 證明證明 ，其中其中 是關(guān)于點是關(guān)于點 的插值基函數(shù)的插值基函數(shù). . 0)()(502xlxxiii)(xli510,xxx證明證明)()2()()(5022502xlxxxxxlxxiiiiiii )()(2)(50250502xlxxlxxxlxiiiiiiii . 02222 xxx2022-7-5第2章 插值法22例例4 已知已知233sin,214sin,216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計算插值計算 sin 50 并估計誤差。并估計誤差。 解：解：0 x1x2x18

24、5500 n = 1分別利用分別利用x0, x1 以及以及 x1, x2 計算計算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL這里這里)4,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,22sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.776143,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R選擇要計算的選擇要計算的 x 所在的區(qū)所在的區(qū)間的端點，插值效果較好。間的端點，插值效果

25、較好。2022-7-5第2章 插值法23n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.7660444高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值但絕對不是次數(shù)越但絕對不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿2022-7-5第2章 插值法24Quiz: 給定給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是下面哪個是 l2(x)的

26、圖像？的圖像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 2124563 1 32 34 3 5 36()()()()()( )()()()()()xxxxxlx 2022-7-5第2章 插值法25 Lagrange插值插值公式公式(利用利用插值基函數(shù)插值基函數(shù)很容易得到很容易得到): 含義直觀含義直觀,結(jié)構(gòu)緊湊結(jié)構(gòu)緊湊,在理論分析中非常方便在理論分析中非常方便; 計算機上實現(xiàn)也很容易計算機上實現(xiàn)也很容易. 也有一些也有

27、一些缺點缺點： 一是一是計算量大計算量大，這是顯然的；另外，還有一個更嚴(yán)重的，這是顯然的；另外，還有一個更嚴(yán)重的缺點，當(dāng)插值節(jié)點增加時，缺點，當(dāng)插值節(jié)點增加時，全部插值基函數(shù)全部插值基函數(shù)均要隨之均要隨之變化變化，整個計算工作必須從頭開始：不僅原來的每一項都要改變，整個計算工作必須從頭開始：不僅原來的每一項都要改變，還要還要增加一項增加一項計算。計算。 為克服上述兩個缺點為克服上述兩個缺點, 努力：把插值多項式變形為努力：把插值多項式變形為便于計算便于計算的形式。的形式。 希望：希望：計算改變的過程中計算改變的過程中,盡可能能利用已有的計算結(jié)果盡可能能利用已有的計算結(jié)果. 下面我們將看到下面我

28、們將看到,這是可能的。我們可以有具有這是可能的。我們可以有具有“承襲性承襲性”的所謂牛頓公式。的所謂牛頓公式。2022-7-5第2章 插值法26拉格朗日插值拉格朗日插值Ln(x)還可以寫成什么樣的表達式？還可以寫成什么樣的表達式？)(xLk記記 是關(guān)于節(jié)點是關(guān)于節(jié)點 的的k 次拉格朗日插值多項次拉格朗日插值多項式，則有式，則有kxxx,10)()()()(1101 kkkxxxxxxAxLxL2.3 均差與牛頓插值多項式均差與牛頓插值多項式 kjkjkjjjjjjjjxxxxxxxxxxxxxfA011110)()()()()()()()()()()()(112010 xLxLxLxLxLxL

29、xLxLnnn nkkknxLxLxLxL110)()()()( nkkkjjkjxxxxxxxxfxf1110010)()()()()()( 2022-7-5第2章 插值法27記記,210kxxxxf kjjkjxxf01)()( kjkjkjjjjjjjjxxxxxxxxxxxxxf011110)()()()()()(,)(,)(,)()(11010102100100 nnnxxxxxxxxxfxxxxxxxfxxxxfxfxL,)()()()(101101kkkkxxxfxxxxxxxLxL )(xNn 2022-7-5第2章 插值法28均差定義均差定義2.3.1 均差及其性質(zhì)均差及其性

30、質(zhì)/* divided difference */ 定義定義2 稱稱 為函數(shù)為函數(shù)f(x)關(guān)于點關(guān)于點x0,xk的的一階均差一階均差.稱稱 為為f(x) 的的二階均差二階均差.一般地一般地, 稱稱 為為 f(x) 的的k 階均差階均差(差商差商). fx0,xk =f(xk)- -f(x0)xk- -x0 fx0,x1,xk=fx0,xk- - fx0,x1xk- -x1 fx0,x1,xk=fx0, xk-2,xk- - fx0,x1, ,xk-1xk- -xk-1均差的基本性質(zhì)均差的基本性質(zhì) 1 n 階均差可表示為函數(shù)值階均差可表示為函數(shù)值f(x0), f(x1), f(xn)的線性組合的

31、線性組合,即即 fx0,x1,xn=f(xj)(xj- -xj+1)(xj- -xn)(xj- -xj-1)(xj- -x0) nj=0注：注：均差與節(jié)點的排列次序無關(guān)均差與節(jié)點的排列次序無關(guān)均差的對稱性均差的對稱性 fx0,x1,xn= fx1,x0,x2,xn= = fx1, , xn ,x02022-7-5第2章 插值法29 fx0,x1,xk=fx1, xk-1,xk- - fx0,x1, ,xk-1xk- -x02 由性質(zhì)由性質(zhì)1可得可得:FF 實際計算過程為實際計算過程為f (x0)f (x1)f (x2)f (xn 1)f (xn)f x0, x1f x1, x2 f xn 1,

32、 xnf x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1均差計算可列均差表如下：均差計算可列均差表如下：2022-7-5第2章 插值法30證明：證明：上式右端的分子是上式右端的分子是 的的m次多項式次多項式 ，記為，記為x則則( )h x為為m-1次多項式次多項式3 若若 是一個依賴于是一個依賴于 的的 次多項式，次多項式，則則 是關(guān)于是關(guān)于 的的 次多項式。次多項式。 ,.,0kxxxfx,.,10 kxxxfmx1 m1100,.,.,

33、 kkkxxxxfxxxf,.,10 kxxxf,.,.,)(100 kkxxfxxxfxg,.,.,)(10011 kkkkxxfxxxfxg0 )()()(1xhxxxgk ,.,)(,.,.,101100 kkkkkxxxxfxxxxfxxxf2022-7-5第2章 插值法31,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxP12 n+11+ (x x0) 2+ + (x x0)(x xn 1) n+1.)(,

34、)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)2.3.2 牛頓插值多項式牛頓插值多項式/* Newtons Interpolation */Nn(x)牛頓均差插值多項式牛頓均差插值多項式,顯然有顯然有Nn(xi)=f(xi)(i=0,1,2,n),)(,210221010 xxxxfxxxxxfxxxf 32022-7-5第2章 插值法32 fx0, x1,xn =f(n)()n!,ba 4 若若f(x)在在a,b上存在上存在n階導(dǎo)數(shù)階導(dǎo)數(shù), 且節(jié)點且節(jié)點x0,x1

35、,xn a,b,則則n階均差與導(dǎo)數(shù)關(guān)系如下階均差與導(dǎo)數(shù)關(guān)系如下: 析析nnnxxxnxNxfxR,1)()()(10個零點個零點有有 應(yīng)用應(yīng)用n次羅爾定理有次羅爾定理有 fx0, x1,xn =f(n)()n!,ba .)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn(x)余項形式余項形式)().(,.,100nnnxxxxxxxxxf Rn(x)注：注： 由由n(x) Ln(x)， 只是算法不同，故其余項也相同，只是算法不同，故其余項也相同，)(!)1()()(,.,1)1(10 xnfxxxxfnxnnn 2022-7-5第2章

36、插值法33 例例5 依據(jù)如下函數(shù)值表建立不超過依據(jù)如下函數(shù)值表建立不超過3次的拉格朗日插值次的拉格朗日插值多項式及牛頓插值多項式多項式及牛頓插值多項式Nn(x),并驗證插值多項式的唯一性并驗證插值多項式的唯一性. 解解: (1)拉格朗日插值多項式拉格朗日插值多項式Ln(x).插值基函數(shù)插值基函數(shù)xk0124f (xk)19233拉格朗日插值多項式為拉格朗日插值多項式為:121445411 )(3)(23)(9)()()(233210303xxxxlxlxlxlyxlxLiii,12181241)24)(14)(04()2)(1)(0()(,4541)42)(12)(02()4)(1)(0()(

37、,38231)41)(21)(01()4)(2)(0()(, 1478781)40)(20)(10()4)(2)(1()(233232231230 xxxxxxxlxxxxxxxlxxxxxxxlxxxxxxxl2022-7-5第2章 插值法34xkf (xk) 一階均差一階均差二階均差二階均差三階均差三階均差011922343(2) 牛頓插值多項式牛頓插值多項式Nn(x). 建立如下差商表建立如下差商表牛頓插值多項式為牛頓插值多項式為:121445411 )2)(1)(0(411) 1)(0(3)0(81)(233xxxxxxxxxxN411(3) 唯一性驗證唯一性驗證.通過比較牛頓插值多項

38、式和拉格朗日插值多項式通過比較牛頓插值多項式和拉格朗日插值多項式,知知: Nn(x) = Ln(x)這一事實與插值多項式的唯一性一致這一事實與插值多項式的唯一性一致. 814-103-82022-7-5第2章 插值法35注：注： 當(dāng)題目中沒有指明用哪一種方法建立插值多項式時，原則上拉格當(dāng)題目中沒有指明用哪一種方法建立插值多項式時，原則上拉格朗日插值方法和牛頓插值方法都可行，做題目時選較為方便的一種方法。朗日插值方法和牛頓插值方法都可行，做題目時選較為方便的一種方法。近似計算時，由于牛頓插值多項式的非整理形式可以直接寫成秦九韶算近似計算時，由于牛頓插值多項式的非整理形式可以直接寫成秦九韶算法的形

39、式，計算量小，且當(dāng)節(jié)點增加時只需增加一項，前面的工作依然法的形式，計算量小，且當(dāng)節(jié)點增加時只需增加一項，前面的工作依然有效，因而通常情況下牛頓插值比較方便，拉格朗日插值則沒有該優(yōu)點，有效，因而通常情況下牛頓插值比較方便，拉格朗日插值則沒有該優(yōu)點，但在理論證明上因其基函數(shù)的特點廣泛應(yīng)用。但在理論證明上因其基函數(shù)的特點廣泛應(yīng)用。.)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn(x).)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfNn+1(x)().(,.,1010nnnnxxxx

40、xxxxxf 2022-7-5第2章 插值法36差商表差商表i0123xi-2-112 (xi)531721練習(xí)練習(xí) 給出函數(shù)給出函數(shù)y= (x)的的函數(shù)表函數(shù)表寫出函數(shù)寫出函數(shù)y= (x)的的差商表，并求節(jié)點為差商表，并求節(jié)點為x0,x1的一次插值的一次插值x0,x1, x2的二次的二次插值和插值和x0,x1,x2,x3的三次插值多的三次插值多項式項式.ixi(xi)一階一階差商差商二階二階差商差商三階三階差商差商0123-2-112531721-2743-1-1N1(x)=5-2(x+2)=1-2x解解N2(x)=1-2x+3(x+2)(x+1) =3x2+7x+7N3(x)=3x2+7x

41、+7-(x+2)(x+1)(x-1)=-x3+x2+8x+92022-7-5第2章 插值法372.3.4 差分形式的牛頓插值公式差分形式的牛頓插值公式 設(shè)有等距節(jié)點，設(shè)有等距節(jié)點，其中稱為其中稱為步長步長。), 1 , 0(0nkkhxxkh 設(shè)設(shè) 點的函數(shù)值為點的函數(shù)值為 ，稱，稱 為為 處以處以 為步長的為步長的一一階（階（向前）差分向前）差分. .kx), 1 , 0)(nkxffkk,1kkkfffkxh 類似地稱類似地稱 為為 處的處的二二階差分階差分. .kkkfff12kx 一般地，一般地，knknknfff111 為為 處的處的 階差分階差分. .kxn（3.8）差分差分例例

42、f(x)=x2 , xi=i (i=1,2,n), 求求nf(xi),(i=1,n-1) n3解：解：f(xi)=f(xi+1)-f(xi)=(i+1)2-i2=2i+1 2f(xi )= f(xi+1)- f(xi)=2(i+1)+1-(2i+1)=23f(xi )= 2f(xi+1)- 2f(xi )= 2-2=0nf(xi)=0 n32022-7-5第2章 插值法38兩個常用算子符號兩個常用算子符號,kkff I,1 kkffEI 稱為稱為不變算子不變算子Eh稱為步長為稱為步長為 的的移位算子移位算子,)(1kkkkkkffffffIEIE 差分與函數(shù)值差分與函數(shù)值knknff) IE(

43、 kjnnjjfjn E)1(0（3.9）,)1(0jknnjjfjn 其中其中 為二項式展開系數(shù)為二項式展開系數(shù)!)1()1(jjnnnjn 反之反之可得可得 .0kjnjknfjnf （3.10）knf)I ( ,0kjnjfjn knknffE 2022-7-5第2章 插值法39,111hfxxffxxfkkkkkkk kkkkkkkkkxxxxfxxfxxxf 212121,2122kfh 均差與差分的關(guān)系均差與差分的關(guān)系,1!1,kmmmkkfhmxxf ).,2,1(nm （3.11）),()(fhfnnkn （3.12）其中其中 . .),(nkkxx差分表差分表差分與導(dǎo)數(shù)的關(guān)系

44、差分與導(dǎo)數(shù)的關(guān)系xi fi 2 3 n x0 f0 x1 f1x2 f2x3 f3xn-3 fn-3xn-2 fn-2xn-1 fn-1xn fnf0f1f2fn-3fn-2fn-12f02f12fn-32fn-23f03fn-3nf02022-7-5第2章 插值法40令令 ，用差分代替差商，用差分代替差商thxx002000! 2) 1()(fttftfthxPn,!) 1() 1(0fnntttn（3.13）),()!1()() 1()()1(1nnnfhnntttxR).,(0nxx（3.14）牛頓向前插值公式牛頓向前插值公式/* Newtons forward-difference f

45、ormula */給出給出 在在 xxfcos)( 1 .0,5 ,1 ,0, hkkhxk處的函數(shù)值，試用處的函數(shù)值，試用4次牛頓前插公式計算次牛頓前插公式計算 的近似值的近似值并估計誤差并估計誤差.)048. 0(f例例7解解 為使用牛頓插值公式，先構(gòu)造差分表為使用牛頓插值公式，先構(gòu)造差分表. . .)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfn(x)牛頓向前插值公式的余項牛頓向前插值公式的余項2022-7-5第2章 插值法4187758.050.04348.000920.092106.040.000035.003428.0000

46、10.000955.095534.030.000002.000025.002473.000012.000980.098007.020.000013.001493.000993.099500.010.000500.000000.100.0)(325432 fffffxfxkk差差分分表表表取取, 1 . 0,048. 0hx則則,48. 01 . 00048. 00hxxt得得 )048. 0(4P048. 0cos)048. 0(f)00500. 0(48. 000000. 1)00993. 0(2) 148. 0)(48. 0()00013. 0)(248. 0)(148. 0)(48. 0

47、(! 31)00012. 0)(348. 0)(248. 0)(148. 0)(48. 0(! 4199885. 02022-7-5第2章 插值法42誤差估計誤差估計554)4)(3)(2)(1(! 5)048.0(htttttMR,105845.17其中 .565.06 .0sin5M48.0 t2022-7-5第2章 插值法432022-7-5第2章 插值法442.4 埃爾米特插值埃爾米特插值 假設(shè)函數(shù)假設(shè)函數(shù)y=f(x)是是 在在a,b上有一定光滑性的函數(shù)上有一定光滑性的函數(shù),在在a,b 上有上有n+1個互異點個互異點xoxn, f(x)在這些點上取值在這些點上取值yo.yn.求一個求一

48、個確定的函數(shù)確定的函數(shù)p(x)在上面在上面n+1個點上滿足個點上滿足p(xi)=yi i=0,1,n.這是這是最簡單的插值問題最簡單的插值問題,如果除了知道如果除了知道f(x)在插值節(jié)點上的取值外在插值節(jié)點上的取值外,還知道還知道f(x)在插值節(jié)點在插值節(jié)點xi上的上的 1min階導(dǎo)數(shù)，如何來構(gòu)造插階導(dǎo)數(shù)，如何來構(gòu)造插值函數(shù)呢值函數(shù)呢? Hermite插值就是既滿足插值節(jié)點插值就是既滿足插值節(jié)點xi的函數(shù)值條件的函數(shù)值條件又滿足微商條件的插值函數(shù)。又滿足微商條件的插值函數(shù)。 Hermite插值也叫帶指定微商值的插值插值也叫帶指定微商值的插值,它要構(gòu)造一個插它要構(gòu)造一個插值函數(shù)值函數(shù),不但在給定

49、節(jié)點上取函數(shù)值不但在給定節(jié)點上取函數(shù)值,而且取已知微商值，使而且取已知微商值，使插值函數(shù)和被插函數(shù)的密和程度更好插值函數(shù)和被插函數(shù)的密和程度更好 。2022-7-5第2章 插值法452.4.1 重節(jié)點均差與泰勒插值重節(jié)點均差與泰勒插值 定理定理3 設(shè)設(shè) 為為 上的相異上的相異節(jié)點，則節(jié)點，則 是其變量的連續(xù)函數(shù)是其變量的連續(xù)函數(shù). .nnxxxbaCf,10,ba,10nxxxf)()()(lim,lim000000 xfxxxfxfxxfxxxx 重節(jié)點的一階均差重節(jié)點的一階均差)(,lim,0100001xfxxfxxfxx 重節(jié)點均差重節(jié)點均差),(,!)(,0)(10nnnxxnfxx

50、xf )(! 1)(lim,0000 xffxxfx 重節(jié)點的二階均差重節(jié)點的二階均差)(21! 2)(lim,lim,021000000201xffxxxfxxxfxxxxx 2022-7-5第2章 插值法46).(!1,lim,0)(100000 xfnxxxfxxxfnnxxi （4.1）令令),2, 1(0nixxi.)(!)()()()(00)(000nnnxxnxfxxxfxfxP （4.2）這實際上是在點這實際上是在點 附近逼近附近逼近 的一個帶導(dǎo)數(shù)的插值多項的一個帶導(dǎo)數(shù)的插值多項式，它滿足條件式，它滿足條件0 x)(xf., 1 ,0),()(0)(0)(nkxfxPkkn （

51、4.3）重節(jié)點的重節(jié)點的n階均差階均差泰勒插值泰勒插值泰勒多項式泰勒多項式.)(,)(,)(102100100 xxxxxxxfxxxxfxf).(,.,100 nnxxxxxxfPn(x)泰勒插值多項式泰勒插值多項式2022-7-5第2章 插值法47一個埃爾米特插值多項式，余項為一個埃爾米特插值多項式，余項為,)()!1()()(10)1( nnnxxnfxR ),(ba（4.4）泰勒插值是牛頓插值的極限形式，是只在一點泰勒插值是牛頓插值的極限形式，是只在一點 給出給出 個插值條件所得到的個插值條件所得到的 次埃爾米特插值多項式次埃爾米特插值多項式. . 0 xn1n2.4.2 兩個典型的埃

52、爾米特插值兩個典型的埃爾米特插值不完全導(dǎo)數(shù)的不完全導(dǎo)數(shù)的Hermite插值插值 考慮滿足條件考慮滿足條件 及及 的插值多項式及其余項表達式的插值多項式及其余項表達式. . )2, 1 ,0()()(ixfxPii)()(11xfxP多項式的曲線通過多項式的曲線通過),(,(),(,(),(,(221100 xfxxfxxfx)(,)()(0100 xxxxfxfxP )(,10210 xxxxxxxf 故故),)()(210 xxxxxxA 2022-7-5第2章 插值法48.)(,)(,)(210121001101xxxxxxxfxxxxfxfA 可由條件可由條件 確定確定)()(11xfx

53、P A通過計算通過計算余項余項可設(shè)可設(shè)),()()()(2210 xxxxxxxkxR 其中其中 為待定函數(shù)為待定函數(shù). . )(xk).()()()()()(2210 xtxtxtxktPtftg 構(gòu)造構(gòu)造a, b上有四個零點上有四個零點x， x0，x1，x2 ；其中；其中x1為為 二重零點二重零點. 利利用用Rolly定理，知定理，知g(t)在在x0，x1，x2 ，x組成的三個小區(qū)間內(nèi)組成的三個小區(qū)間內(nèi)至少各有一個零點，記為至少各有一個零點，記為 1, 2, 3 ，加上，加上x1 ，在，在a, b上至上至少有少有4個零點個零點., 0)(!4)()()4()4( xkfg 反復(fù)應(yīng)用羅爾定理

54、，得反復(fù)應(yīng)用羅爾定理，得 在在 內(nèi)至少有一個內(nèi)至少有一個零點零點，)()4(tg),(ba故有故有),()()(! 41)(2210)4(xxxxxxfxR (4.5)余項表達式為余項表達式為 2022-7-5第2章 插值法49 例例8 給定給定 試求試求 在在 上的三次埃爾米特插值多項式上的三次埃爾米特插值多項式 ，使它滿足，使它滿足并寫出余項表達式并寫出余項表達式. .,49, 1,41,)(2102/3xxxxxf)(xf49,41)(xP),2, 1 ,0()()(ixfxPii),()(11xfxP由題意可求出由題意可求出,827)49(, 1)1(,81)41(210 ffffff

55、.23)1(,23)(2/1 fxxf構(gòu)造均差表構(gòu)造均差表 解解 101982749301167814111iifx均差表4-表2.3011,67,21010 xxxfxxf令令).49)(1)(41()1)(41(3011)41(6781)( xxxAxxxxP2022-7-5第2章 插值法50可得可得.22514)40116723(1516A故故,25145023345026322514)49)(1)(41(22514)1)(41(3011)41(6781)(23xxxxxxxxxxP余項余項).49,41()49()1)(41(169! 41)49()1)(41(! 4)()()()(2

56、2/52)4( xxxxxxfxPxfxR 由條件由條件 ，可得，可得23)1()1(fP,23)45(4343301167)1(AP2022-7-5第2章 插值法51,)()()()()(11113 kkkkkkkkmxmxyxyxxH (4.7)基函數(shù)法基函數(shù)法 插值節(jié)點取為插值節(jié)點取為 及及 ，插值多項式為，插值多項式為 ，插值條，插值條件為件為kx1kx)(3xH其中其中 是關(guān)于節(jié)點是關(guān)于節(jié)點 及及 的三次的三次埃爾米特插值基函數(shù)，分別滿足埃爾米特插值基函數(shù)，分別滿足)(),(),(),(11xxxxkkkkkx1kx,)(3kkyxH ,)(3kkmxH .)(;)(113113kk

57、kkmxHyxH(4.6)完全導(dǎo)數(shù)完全導(dǎo)數(shù)兩點三次埃爾米特插值兩點三次埃爾米特插值插值多項式插值多項式, 1)( kkx , 0)(1 kkx , 0)(1 kkx ,0)( kkx ,0)( kkx , 1)( kkx , 0)(1 kkx , 0)(1 kkx , 0)(1 kkx , 1)(11 kkx , 0)(1 kkx . 1)(11 kkx ,0)(1 kkx ,0)(1 kkx , 0)(1 kkx , 0)(11 kkx 2022-7-5第2章 插值法52 ,)(211 kkkkxxxxbaxx根據(jù)給定條件可令根據(jù)給定條件可令顯然顯然, 0)(1 kkx , 0)(1 kkx

58、 再利用再利用, 1)( baxxkkk 及及, 02)(1 axxbaxxkkkkk , 1)( kkx , 0)()(1 kkkkxx , 0)(1 kkx 解得解得,21,211 kkkkkxxxbxxa于是求得于是求得.21)(2111 kkkkkkkxxxxxxxxx 同理可得同理可得2111121)( kkkkkkkxxxxxxxxx (4.8)(4.9)2022-7-5第2章 插值法53 ,)(211 kkkkkxxxxxxax 為求為求 ，由給定條件可令，由給定條件可令)(xk直接由直接由 ，得到，得到1)(axkk ,)(211 kkkkkxxxxxxx (4.10) .)(

59、2111 kkkkkxxxxxxx (4.11),0)()(1 kkkkxx , 1)( kkx , 0)(1 kkx 同理同理2022-7-5第2章 插值法54最后代入，得最后代入，得12112111211121113)()(2121)( kkkkkkkkkkkkkkkkkkkkkkkkmxxxxxxmxxxxxxyxxxxxxxxyxxxxxxxxxH(4.12).,(,)()(! 41)(1212)4(3kkkkxxxxxxfxR(4.13)余項余項 ，)()()(33xHxfxR2022-7-5第2章 插值法55重節(jié)點均差構(gòu)造重節(jié)點均差構(gòu)造Hermite插值插值Newton形式的形式的

60、Hermite插值插值求一個四次插值多項式求一個四次插值多項式 ，滿足，滿足)(xH40)1(,10)1(,0)1(;2)0(,1)0( HHHHH例例9并寫出插值余項的表達式。并寫出插值余項的表達式。解：解：構(gòu)造差商表構(gòu)造差商表2022-7-5第2章 插值法56根據(jù)根據(jù)Newton插值公式插值公式 )(xH2222)1(5)1(6321 xxxxxx插值余項插值余項32)5()1(!5)()( xxfxR10 2022-7-5第2章 插值法57 ., 1 , 0 ,)( ,)( )(12 , 1 , 0,)()(1112121210njyxHyxHxHnnjyxfyxfbxxxannjjnjjnnjjjjn 滿滿足足次次