數(shù)值分析與計算方法 第一章 插值法

1、 本章內容 1.1 Lagrange插值多項式 1.2 Newton插值多項式 1.3 分段低次插值第一章第一章 插值法插值法/* Interpolation Method */Start from here 實際問題中，某些變量之間的函數(shù)關系是存在的，只能由實際問題中，某些變量之間的函數(shù)關系是存在的，只能由測量或實驗得到一系列的離散點上的函數(shù)值：測量或實驗得到一系列的離散點上的函數(shù)值：，nnyyyyyxxxxx210210問題的提出問題的提出( )yf x ？（1）有的函數(shù)沒有表達式，只是一種表格函數(shù)，而我們需要的有的函數(shù)沒有表達式，只是一種表格函數(shù)，而我們需要的函數(shù)值可能不在該表格中。函數(shù)

2、值可能不在該表格中。（2）如果函數(shù)表達式本身比較復雜，計算量會很大；如果函數(shù)表達式本身比較復雜，計算量會很大； 對于這兩種情況，我們都需要尋找一個計算方便且表達簡單對于這兩種情況，我們都需要尋找一個計算方便且表達簡單的函數(shù)的函數(shù) 來近似代替來近似代替 ，求求 的方法稱為的方法稱為插值法插值法。 P x( )f x P x( )( )( )P xf xP x以以近近似似，以以代代替替的性質近似代替的性質近似代替 性質性質 fx一、插值法基本思想一、插值法基本思想( )1f xn Def4.1 已Def4.1 已知知y=在y=在個互異節(jié)點上的值，若存在一個個互異節(jié)點上的值，若存在一個( ),()(

3、)0 1 2,iiiP xP xf xyin ， ，簡單函數(shù)簡單函數(shù)()()()()iiiP xfxxfxP xy 插值節(jié)點；插值節(jié)點；為為 的插值函數(shù)；的插值函數(shù)；被插函數(shù)被插函數(shù)插值條件插值條件求求 的方法稱為的方法稱為插值法插值法。()P xx0 x1x2x3x4xP(x) f(x)( )yP x ( )yf x 幾何意義：幾何意義：x注：注：簡單函數(shù)簡單函數(shù)常指：多項式函數(shù)、分段多項式函數(shù)、有理函數(shù)；常指：多項式函數(shù)、分段多項式函數(shù)、有理函數(shù)； 相應插值法稱為：相應插值法稱為：代數(shù)插值代數(shù)插值法、法、分段插值分段插值、有理函數(shù)插值有理函數(shù)插值；特別特別： 所求所求 是過兩點的直線是過兩

4、點的直線線性插值線性插值 所求所求 是過三點的二次曲線是過三點的二次曲線拋物插值拋物插值 12( )2( )1nPnPxx ， ，我們主要介紹我們主要介紹代數(shù)插值代數(shù)插值（插值函數(shù)為（插值函數(shù)為多項式多項式 的插值），的插值），相應的相應的 稱為稱為插值多項式插值多項式。( )nPx( )nPx二、插值多項式二、插值多項式( )npx的存在唯一性的存在唯一性證明：證明：01220001201002111122nnnnnnnnnnxxxyxxxyaaxaaaaaaaaa xya x ，只要證得只要證得 存在唯一即可，由存在唯一即可，由ia()njjpxy Th4.1 0120121()()0 1

5、( )nnjjjnnnxxxnpxyf xjnnpxaa xa xa x 已已知知， ， 是是， ， 的的 次次是是存存在在且且唯唯一一的的；個互異節(jié)點，則滿足插值個互異節(jié)點，則滿足插值多項式多項式條件條件0()0ijj i nxx 200021112111nnnnnnxxxxxxAxxx注：注：若若不限定次數(shù)不限定次數(shù)，則插值多項式，則插值多項式不唯一不唯一；如：如：若若 滿足插值條件，則滿足插值條件，則 亦滿足亦滿足0( )( )()nnniipxpxxx 法則，法則，n+1個插值條件唯一確定一個個插值條件唯一確定一個n次次插值多項式。插值多項式。Cramer由由Vandermond行列式

6、行列式一、一、Lagrange插值多項式插值多項式 由由Th4.1Th4.1知，知， )(xpn中系數(shù)的計算只需求解一個中系數(shù)的計算只需求解一個 1n 元方元方 程組，程組，待定系數(shù)法計算復雜待定系數(shù)法計算復雜，且難以得到，且難以得到 式；下面來介紹式；下面來介紹構造法構造法。)(xpn的簡單表達的簡單表達的構造的構造 )(xpn1.2 Lagrange插值多項式插值多項式/* Lagrange Polynomial */niyxPiin,., 0,)( 求求 n 次多項式次多項式 使得使得nnnxaxaaxP 10)(條件：條件：無重合節(jié)點，即無重合節(jié)點，即jixx ji n = 1已知已知

7、 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP 可見可見 P1(x) 是過是過 ( x0 , y0 ) 和和 ( x1, y1 ) 兩點的兩點的直線直線。)()(0010101xxxxyyyxP 101xxxx 010 xxxx = y0 + y1l0(x)l1(x) 10)(iiiyxl10()ijijijl xij 1 1、基本插值多項式、基本插值多項式: :Lagrange插值多項式插值多項式0()niinil x yLx njijjijixxxxxl0)()()(與與 有關有關，而與而與 無關無關插值基函數(shù)插值基函數(shù)/ /

8、基本插值多項式基本插值多項式n 1希望找到希望找到n次次多項式多項式li(x)，i = 0, , n 使得使得 li(xj)= ij；然后令然后令 niiinyxlxP0)()(，則顯然有，則顯然有Pn(xi) = yi 。li(x)每個每個 li(x) 有有 n 個根個根 x0 xi-1 、 xi+1 xn j i jiiiixxCxl)(11)(n n次次Lagrange 插值插值多項式多項式節(jié)點節(jié)點y0110( )()()()()()niiiinijjj il xC xxxxxxxxCxx 01110111()()()()()( )()()()()()iiniiiiiiiinxxxxxx

9、xxxxl xxxxxxxxxxx 2 2、插值余項、插值余項-( )( )( )nnRxf xLx(1)1)1101( )( )( )(1)( )()(!( )()()()()( )()nnnnnnnfxa bfRxxnxxxxxxa ba bf xL xxx ， ， ，中中。其其Th4.2設設 個節(jié)點個節(jié)點 若若 在在 連續(xù)，連續(xù)， 在在 內存在，則內存在，則 1n ( )( )nixa bfxa b ， ，插值多項式的余項插值多項式的余項證明：證明：011()()()00( )( )()()( )( )nnnjjnjjnnRxf xLxjnxRxRxK xKxxxxxxxx ，是是；的零

10、點的零點設設引入引入輔助函數(shù)輔助函數(shù) 則則1( )( )( )( )nntRK xtt ，至少有至少有 個互異零點：個互異零點：( ) t 2n 01nx xxx， ， ，。，；即；即至少有一個零點至少有一個零點個零點；個零點；至少有至少有；個互異零點個互異零點至少有至少有同理：同理：；個互異零點個互異零點至少有至少有由由)()!1()()()!1()()(0)!1()()()!1()()()()()()()()(1)()(1)(1)1()1()1()1()1(1)1()1()1(xnfxRnfxKnxKfnxKRxKRbatntntntThRollennnnnnnnnnnnn 0( )1(

11、)1nkkf xlx ，；若若 則則若若 本身是次數(shù)本身是次數(shù)不超過不超過n的多項式，的多項式，則，則， 即即0( )0( )( )nnkknkf xLxRxlx y ，；2( )f x 通常是次數(shù)為通常是次數(shù)為n的多項式，特殊情形下可能的多項式，特殊情形下可能小于小于n,如如過三點的過三點的 若三點共線，則若三點共線，則 是一條直線是一條直線(一次一次)3( )nLx 2( )L x2( )yL x (111)1( )( )(1)(1)!nnnnnMRxxnfNotexM 若若，；則有余項則有余項(1)1( )( )( )(1)!nnnfRxxn 例例1：已知已知233sin,214sin,

12、216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計算插值計算 sin 50 并估計誤差。并估計誤差。 解：解：0 x1x2x185500 n = 1分別利用分別利用x0, x1 以及以及 x1, x2 計算計算4,610 xx利用利用1/4/6/6/411( )22/4/6xL xx 這里這里26 4423132( )( )sin ,( )sin ,( , )( , )sinsinf xx f ，而而21264( )( )( )()()!fR xxx 15()0.0107718R sin 50 = 0.7660444)185(50sin10 L0.776

13、143,421 xx利用利用sin 50 0.76008, 113/3/4/4/3( )23/42/Lxxx 21243( )( )( )()()!fR xxx 150.0066018R 內插內插通常優(yōu)于通常優(yōu)于外推外推。選擇。選擇要計算的要計算的 x 在區(qū)間的內部，在區(qū)間的內部，插值效果較好。插值效果較好。二次二次插值比插值比一次一次插插值精度高值精度高n = 24363646463464363234()()()()()()()()()()113( )()222(xxxxxL xx )185(50sin20 L0.765433264336433( )cos( )()()()()( )()!;

14、Rxxxxxfxx 250.0007718R 但絕對不是次數(shù)越但絕對不是次數(shù)越高就越好高就越好36 32(,)cos ，Lagrange插值多項式的缺點：插值多項式的缺點：基函數(shù)計算復雜；且已得的基函數(shù)計算復雜；且已得的 無用，需重新算過；無用，需重新算過； ( )nLx對于計算對于計算 1( )nLx 高次插值精度未必高；高次插值精度未必高；RungeRunge現(xiàn)象現(xiàn)象1( )( )nnLxLx ，比較比較n-1次及次及n次插值多項式次插值多項式若非常接近，則以若非常接近，則以n次插值次插值否則增加節(jié)點計算否則增加節(jié)點計算( )( )nLxfx ，1( )nLx 。通常方法：實用通常方法：實

15、用后驗估計后驗估計不知道選擇多少個插值節(jié)點為宜；不知道選擇多少個插值節(jié)點為宜； 本節(jié)內容提要本節(jié)內容提要 基本思想基本思想 NewtonNewton插值多項式的構造插值多項式的構造 均差均差( (差商差商) ) 定義、計算、性質定義、計算、性質 NewtonNewton插值多項式的誤差插值多項式的誤差差分及等距節(jié)點插值公式差分及等距節(jié)點插值公式1.3 Newton插值多項式插值多項式/* Newtons Interpolation */一、一、基本思想基本思想 缺點：缺點：增加節(jié)點時，需要計算增加節(jié)點時，需要計算 ，而已得的，而已得的 不能被利用；不能被利用； ( )nLx1( )nLx 為此

16、我們考慮對為此我們考慮對LagrangeLagrange插值多項式插值多項式進行進行改寫改寫； 由唯一性，僅是由唯一性，僅是形式上形式上的變化的變化 已知已知n+1個互異插值節(jié)點個互異插值節(jié)點 由插值多項由插值多項式的存在唯一性，可以構造式的存在唯一性，可以構造Lagrange插值多項式：插值多項式：01nxxx， ， ， ，00( )( )( )nninkkkkikii kxxLxlx ylxxx ，；期望期望： 的計算只需要對的計算只需要對 作一個簡單的修正作一個簡單的修正.( )nLx1( )nLx 1011( )( )()()()nnnnnLxLxxxxxxaax ， 待待定定；考慮考

17、慮1( )( )( )nnh xLxLx 是次數(shù)是次數(shù) 的多項式，且有的多項式，且有( )h xn 1()(0)()2101jnjnjjhxLnxLx ， ，；011( )()()()nnh xxxxxxxa ，由新增節(jié)點可以計算出由新增節(jié)點可以計算出 從而從而1( )( )nnLxLx ；na ，1011()()()()()()nnnnnnnnnnnxLxLxxxxxxxfaxx 取取，110110011001100()() ()()()()()()()()()nnknknnnnknnnniniiinnnikkikii knnnniniiif xlxf xLxLxaxxxxxxf xxxf

18、xxxxx 111000110000100()()()()()()()()()()()(nnknnkninkkiiii knnknnknikiiiinknnkkiknknkkiikf xf xxxxf xaxxxxxf xf xxxxxf xx ；此公式仍然比較麻煩！此公式仍然比較麻煩！ 二、二、差商（均差）差商（均差）1 1、定義定義：稱稱 為為 關于節(jié)點關于節(jié)點 的的一階差商一階差商/均差均差記作記作 表示表示 在區(qū)間在區(qū)間 上的變化率。上的變化率。()()jijif xf xxx ( )f xijxx，ijf xx，( )f xijxx，稱一階差商稱一階差商 的差商為的差商為 關于節(jié)關于

19、節(jié)點點 的的二階差商二階差商，記作：，記作：ijjkf xxf xx，( )f xijkxxx， ，jkijijkkif xxf xxf xxxxx ， ，；注：注：為統(tǒng)一記號，規(guī)定：為統(tǒng)一記號，規(guī)定： ()iifxf x ；稱為零階差商稱為零階差商類比：類比：導數(shù)：導數(shù)：差商（均差）：差商（均差）：0000( )()()limxxf xf xfxxx ；()()jiijjif xf xf xxxx ，；12011010nnnnfxxxfxxxfxxxxx ， ， ， ， ， ， ，；一般地，稱一般地，稱n-1階差商的差商為階差商的差商為n階差商階差商，有：，有： 實際計算過程為（實際計算過程

20、為（建立差商表建立差商表）f x0, x1f x1, x2 f xn 1, xnf x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn xn+1 f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1f (x0)f (x1)f (x2)f (xn 1)f (xn)x0 x1x2xn 1xn零階差商零階差商 一階差商一階差商 二階差商二階差商 n階差商階差商2 2、差商的計算差商的計算1421406171kkxf x一一二二三三四四-3-1/21/205/61/4-1/6-7/60-1/121/180

21、例例1 1： 12467()41011kkxf x已已知知：， 列列出出差差商商表表；解：解：可見，求各階均差是方便的，且可見，求各階均差是方便的，且 001f xf xx， ，012f xxx， ，位于差商表的對角線上。位于差商表的對角線上。3 3、差商性質差商性質 /* Property of divided difference */n階差商可以表示為階差商可以表示為 的線性組合的線性組合()kf x性質性質1 1111000()()()()(,.,).nkkkkkkkknnf xxxxxxxxxf x xx 證明：證明： 數(shù)學歸納法數(shù)學歸納法100101100110()()()(),f

22、 xf xf xf xf xxxxxxxx n=1；，；，時成立，即時成立，即設設 11111210010)()()()(mkmkiiikkmmkmkiiikkmxxxfxxxfxxxfxxxfmn)()()()(11001111010110121110 mkmkiiikkmkmkiiikkmmmmmxxxfxxxfxxxxxxxfxxxfxxxfmn，時，有：時，有：則則)()()()()()()()(1100101111101 miimkmkiiikkmkiiikkmiimmmxxxfxxxfxxxfxxxfxx01111011001100()()()()()()()()mmkmmmkim

23、ikiiiii kmkmkkiii kf xxxf xf xf xxxxxxx 得證。得證。性質性質2 差商具有對稱性，即差商具有對稱性，即 的值與節(jié)點的值與節(jié)點 的順序無關。的順序無關。01,nf xxxix由性質由性質1 1易知：調換兩個節(jié)點的位置，相當于右端易知：調換兩個節(jié)點的位置，相當于右端改變求改變求和次序。和次序。性質性質4 4 0100( )( ) , ,.,!(min,.,max,.,)nnnnff x xxnxxxx n階差商和階差商和n階導數(shù)之間存在如下關系：階導數(shù)之間存在如下關系：性質性質3n 次多項式次多項式的的 k 階差商階差商 當當 時是時是 n-k 次多項式，而當

24、次多項式，而當 kn 時其值時其值恒等于零。恒等于零。011 ,kf x xxx kn 用用fx,x0,xl=xm驗證即可驗證即可。，；即即，至至少少有有一一個個零零點點個個互互異異零零點點；至至少少有有個個互互異異零零點點；至至少少有有個個互互異異零零點點，由由有有；即即：，由由于于，；令令，其其中中；)(!)(0!)()()(0)()()(1)()(1)(100)()()()()()()()()(10)()()()()(10110010banfaxxxfanfLfRbaxRnxRnxRThRollenxRnkxRxLxfxRxxxfaxxxxxxaxxaaxLnnnnnnnnnnnnnkn

25、nnnnnnn 證明：證明：三、三、NewtonNewton插值多項式插值多項式/* Newtons Interpolation */1 1、定義：、定義：,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n 11+ (x x0) 2+ + (x x0)(x xn 1) n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100

26、nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 4( )(1)(1)(2)(1)(2)(45436760118)(1)(2)(4)(60)Nxxxxxxxxxxx ；例例2： 解：解： 12467()410114kkxf xNewton給定數(shù)據：，求次插值多項式；先求差商表（上例已求出），先求差商表（上例已求出），4 4次牛頓插次牛頓插值多項式為：值多項式為：2、余項余項： (1)1( )( )( )( )(1)!nnnff xNxxn ；帶余項的帶余項的Newton插值公式插值公式 ；，的的任任意意性性，可可得得：由由；，從從而而：其其中中；，則則有有：，增增

27、加加節(jié)節(jié)點點，；得得，已已知知互互異異節(jié)節(jié)點點)()()()()()()()()()()()()(1101101110110 xxxxxfxNxfxxxxxxfxNxfxfxNxxxxxfxNxNxbaxxNxxxnnnnnnnnnnnnn 證明：證明：；，階連續(xù)導，則：階連續(xù)導，則：上有上有，在在若若)(!)1()()()(!)1()(1)(1)1()1(10 xnfxNxfnfxxxxfnbaxfnnnnn 比較可知，比較可知， 與與 的確只是形式上的不同，的確只是形式上的不同，Newton插值多項式便于計算，而插值多項式便于計算，而Lagrange插值插值多項式多用于理論推導。多項式多用

28、于理論推導。 注注： ( )nNx( )nLx性質性質2 2例：例：習題習題4-8設設 互不相同，證明互不相同，證明并寫出并寫出 的的n次次Newton插值多項式。插值多項式。01011 2()kkiif xxxknax ， ， ， ， ；011( )nf xa xxxax ，且且 ， ， ， ，( )f x證明證明( (歸納法歸納法) ) 010121111()1()mmiimmiif xxxaxf xxxax ， ， ，；， ， ，；設設 時成立，即時成立，即km 011()()axax ；1010111xxaxax010101()()1f xkf xxf xxx ，11010111()(

29、)()mmmiiiixxaxax 10101011111()(1()mimmmiiixxaaxaxaxx 01112101101mmmmf xxxf xxkmxf xxxxx ，有有：， ， ， ， ， ，得證。得證。( )f x001001011( )()()()()nnnNxf xf xxxxf xxxxxxxxx ， ， ，0001101011()()()()()()(nnxxxxxaxaxaxaxaxaxxxx ；的的n次次Newton插值多項式插值多項式 本節(jié)內容提要本節(jié)內容提要|基本概念 有限差(向前差分、向后差分、中心差分)|差分的計算 |差分的性質等距節(jié)點插值公式 1.4 差分

30、與等距節(jié)點插值公式差分與等距節(jié)點插值公式 /* Interpolation Formulae with Equal Spacing */ 上節(jié)談論了節(jié)點任意分布的上節(jié)談論了節(jié)點任意分布的Newton插值公式，實際應插值公式，實際應用時常碰到等距節(jié)點的情形，即：用時常碰到等距節(jié)點的情形，即： hnjjhxxj，2100 步長步長 此時公式可進一步簡化，同時可以避開除法運算，此時公式可進一步簡化，同時可以避開除法運算，引入差分的概念。引入差分的概念。 前前 言言稱稱為為 在在 處以處以h為步長的二階向前差分，簡稱二階差分為步長的二階向前差分，簡稱二階差分1211221()()2jjjjjjjjjj

31、ffffffffff ( )jf xx設等距節(jié)點設等距節(jié)點 處的函數(shù)值處的函數(shù)值為為 稱稱 處以處以h為步長的一階向前差分，簡稱一階差分，記作：為步長的一階向前差分，簡稱一階差分，記作： ()，jjf xf 00 1 2， ，jxxjh jn jf 一、差分一、差分1 1、定義：、定義：11( )() (為 在jjjjjffff xf xxx 注：注： 類似可以定義：類似可以定義：一般地，稱一般地，稱 為為 處以處以h為步長的為步長的m階向前差分，簡稱階向前差分，簡稱m階差分。階差分。111( )mmmjjjjf xxfff 在在1111211211()()()()jjjjjjjjjjjjmm

32、jmjjff xf xffffffffffff ；一階后差：一階后差：二階后差：二階后差：m階后差：階后差：前差、后差、中心差前差、后差、中心差 統(tǒng)稱為統(tǒng)稱為有限差有限差； 有限差算子有限差算子 ， 1122211111122()()22jjjjjjmmjjjjjjmjhhff xf xffffffffff ；一階中心差：一階中心差：二階中心差：二階中心差：m階中心差：階中心差：000()()()jjjjjjf xf xffxff ； 為統(tǒng)一記，規(guī)定零階有限差為：為統(tǒng)一記，規(guī)定零階有限差為： 2 2、差分的計算（以前差為例）、差分的計算（以前差為例）4433322222131211104030

33、2000432fxffxfffxffffxfffffxfffffxkkkkkk 列差分表列差分表例：例： 解：解：列出差分表；列出差分表；，已知：已知：27181163)(43210kkxfx2340316211318427kkkkkkxfffff 35792220003 3、性質性質 歸納法證明歸納法證明 利用利用函數(shù)值函數(shù)值表示高階表示高階有限差有限差：； nijininiinjinijnhinxfCfCf00)()1()1( 利用利用各階差分各階差分表示表示函數(shù)值函數(shù)值：； nijiinnijiinjjnxfCfCnhxff00)()( 差商差商與與差分差分之間的關系：之間的關系： 1!

34、kiiii kkffxxxkh ， ，；，成立；，成立；，時，有：時，有：則當則當；，；，時結論成立，時結論成立，設設；，時，時，1010101101211011210100010110!)1()1(!1!)2()()(1)1( kkkkkkkknkkkkkkhkfhkhkffxxxxxfxxxfxxxfknhkfxxxfhkfxxxfknhfxxxfxfxxfn證明：證明： 將將Newton插值公式中各階差商用相應差分代替，可插值公式中各階差商用相應差分代替，可得各種形式的等距節(jié)點插值多項式，以下介紹常用得各種形式的等距節(jié)點插值多項式，以下介紹常用Newton前插與后插公式。前插與后插公式。

35、記節(jié)點記節(jié)點則則000 1 2jjnxxjhxxth ， ， ；令令，0101()()( )(1)()nnnjjnjxxtxt ttn hj h ；二、等距節(jié)點插值公式二、等距節(jié)點插值公式001001011( )()()()()nnnNxf xf xxxxf xxxxxxxxx ， ， ，；由由Newton插值公式：插值公式：NewtonNewton前插公式前插公式上述公式中用上述公式中用差分差分代替代替差商差商001,!,kkkff xxxk h 010100()()!nkknkikkNxthfhtifk h 00111()()!knkfft ttkk 2000011211.!.!nffft

36、t tft ttnn 例例： 解解：304560()kkxf x已已知知：，1 12 23 32 22 22 2求二次牛頓前求二次牛頓前插公式插公式2130224523602kkkkxfff 12121322 132 212取差分表第一行數(shù)據，取差分表第一行數(shù)據，得得Newton前插公式：前插公式：20200(3015 )(1)2!fNtfftt t 1112132 21224(1)tt t 前前插插公公式式；求求，已已知知：Newtonxfxkk27181163)(43210例：例： 解：解：2340316211318427kkkkkkxfffff 3579222000取差分表第一行數(shù)據，得

37、取差分表第一行數(shù)據，得Newton前插公式：前插公式：230040040( )(1)(1)(2)2!3!(1)(2)(3)4!ffNtfftt tt ttft ttt (3)31tt t ； 牛頓牛頓向后插值向后插值公式公式 /* Newtons backward-difference formula */當插值點當插值點 位于插值區(qū)間右端點位于插值區(qū)間右端點 附近時附近時 nxx10nxxtht 令令將節(jié)點順序將節(jié)點順序倒置倒置：).(,.,.)(,)()(101xxxxxxfxxxxfxfxNnnnnnnn 上述公式中用上述公式中用差分差分代替代替差商差商0110,!kkkkyf xxx

38、xk h ()n ixxti h 22011112.!nnnnyyyy tt tt tt nn 110()()!knkkn knnnkkiyNxthyhtik h 111()()!knn knkyyt ttkk 稱之為牛頓稱之為牛頓向后插值向后插值公式公式注：注：一般當一般當 x 靠近靠近 x0 時用前插公式，靠近時用前插公式，靠近 xn 時用后插公式，故時用后插公式，故兩種公式亦稱為兩種公式亦稱為表初公式表初公式和和表末公式表末公式。插值插值余項余項1111111()()( ) ()()()!( )nnnnnnt nfRfht ttnnCfh 注注：若插值點位于節(jié)點中部，則可利用中心差分構造

39、：若插值點位于節(jié)點中部，則可利用中心差分構造 StirlingStirling插值插值、BesselBessel插值插值等；等； 用于用于高精度要求高精度要求的函數(shù)插值，現(xiàn)已少用！的函數(shù)插值，現(xiàn)已少用！ 例例 給定給定f(x)在等距節(jié)點上的函數(shù)值表如下在等距節(jié)點上的函數(shù)值表如下: xi 0.4 0.6 0.8 1.0 f(xi) 1.5 1.8 2.2 2.8分別用分別用Newton向前和向后差分公式求向前和向后差分公式求f(0.5)及及f(0.9)的近似值的近似值 解解 先構造向前差分表如下先構造向前差分表如下: xi fi fi 2 2fi 3 3fi 0.4 1.5 0.6 1.8 0.

40、3 0.8 2.2 0.4 0.1 1.0 2.8 0.6 0.2 0.1 x0=0.4, h=0.2, x3=1.0. 分別用差分表中分別用差分表中對角線上對角線上的值的值和和最后一行最后一行的值的值,得得Newton向前和向后插值公式如下向前和向后插值公式如下:33(1)(1)(2)(0.40.2 )1.50.30.10.123!(1)(1)(2)(1 0.2 )2.80.60.20.123!t tt ttNttt tt ttNtt(1) (2)當當 x=0.5時時, ,用公式用公式(1),(1),這時這時t=(x-x0)/h=0.5. 將將t=0.5代代入入(1),(1),得得 f (0

41、.5)N3(0.5)=1.64375.當當x=0.9時時, , 用公式用公式(2), (2), 這時這時t=(x3-x)/h=0.5. 將將t=0.5代入代入(2), (2), 得得 f (0.9)N3(0.9)=2.46875. go 分段分段 本節(jié)內容提要本節(jié)內容提要|Hermite插值 方法概述、幾何意義、誤差估計1.5 埃爾米特插值埃爾米特插值/* Hermite Interpolation */不僅要求函數(shù)值重合，而且要求若干階不僅要求函數(shù)值重合，而且要求若干階導數(shù)導數(shù)也重合。也重合。即：要求插值函數(shù)即：要求插值函數(shù) (x) 滿足滿足 (xi) = f (xi), (xi) = f

42、(xi), (mi) (xi) = f (mi) (xi).注：注： N 個條件可以確定個條件可以確定 階多項式。階多項式。N 1要求在要求在1個節(jié)點個節(jié)點 x0 處直到處直到m0 階導數(shù)都重合的插階導數(shù)都重合的插值多項式即為值多項式即為Taylor多項式多項式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx 其余項為其余項為)1(00)1(00)()!1()()()()(mmxxmfxxfxR 一般只考慮一般只考慮 f 與與f 的值。的值。例：例：設設 x0 x1 x2, 已知已知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多項式求多項式 P(x

43、) 滿足滿足 P(xi) = f (xi)，i = 0, 1, 2，且且 P(x1) = f (x1), 并估計誤差。并估計誤差。模仿模仿 Lagrange 多項式的思想，設多項式的思想，設解：解：首先，首先，P 的階數(shù)的階數(shù) = 3 213)()()()()( 0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh 又又: h0(x0) = 1 C0 )()()()()(202102210 xxxxxxxxxh h2(x)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh

44、由余下條件由余下條件 h1(x1) = 1 和和 h1(x1) = 0 可解?？山狻Ｅc與h0(x) 完全類似。完全類似。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx h1又又: (x1) = 1 C1 可解?？山?。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1),()()()()()(221033xxxxxxxKxPxfxR !4)()()4(xfxK 與與 Lagrange 分析分析完全類似完全類似一般地，已知一般地，已知 x0 , , xn 處有處有 y0 , , yn 和和 y0 ,

45、 , yn ，求，求 H2n+1(x) 滿足滿足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：解：設設 ni)()()( 0iixhxhyixH2n+1 n 0iyi其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hihi(x)有根有根 x0 , , xi , , xn且都是且都是2重根重根 )()()(2xlBxAxhiiii ijjijixxxxxl)()()(由余下條件由余下條件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和 Bi )()(21 )(2xlxxxlxhiiiii (

46、x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx hi又又: (xi) = 1 Ci = 1 hi)(x)(ili2(x)xx 設設,.210baCfbxxxann 則則20)22()()!22()()( niixnnxxnfxR x0 x1x2x3x4xH9(x) f(x) 9( )yH x ( )yf x 全導數(shù)的全導數(shù)的Hermite插值多項式的插值多項式的幾何意義幾何意義如如n=1時時Hermite插值多項式插值多項式 為為3( )Hx220011301010110102201001101101 21 2( )( )(

47、 )( )()( )()xxx xx xxxH xf xf xxxxxxxxxx xx xf xx xf x x xxxxx 求求Hermite多項式的基本步驟：多項式的基本步驟： 寫出相應于條件的寫出相應于條件的hi(x)、 hi(x) 的組合形式；的組合形式； 對每一個對每一個hi(x)、 hi(x) 找出盡可能多的條件給出的根；找出盡可能多的條件給出的根； 根據多項式的總階數(shù)和根的個數(shù)寫出表達式；根據多項式的總階數(shù)和根的個數(shù)寫出表達式； 根據尚未利用的條件解出表達式中的待定系數(shù)；根據尚未利用的條件解出表達式中的待定系數(shù)； 最后完整寫出最后完整寫出H(x)。 余項余項： (22)2211(

48、 )( )( )( )(22)!；nnnff xHxxn 帶余項的帶余項的HermiteHermite插值公式插值公式 例例已知已知 且在且在 處有處有求一個次數(shù)不超過求一個次數(shù)不超過3的多項式的多項式 111()0 1 2()iif xyixfxm ，33( )iiP xP xy ，31110 1 2()()Pximfx ，且且。021201021012012210120()()()()()()()()()()( )()( )()xxxxxxxxxxxxxxxxxxxxxxlxxlxxlx ，；32001122( )( )( )( )( )P xL xlx ylx ylx y 求求；令令；其

49、其中中解解3232( )( )( )( )( )( )Q xPP xL xQxxL x 令令，那那么么是是012( )()()()AQ xA xxxxxx 令令， 待待定定；至少至少3次多項式，次多項式， 三個零點，那么三個零點，那么012xxx且且有有，1021201010210121021012120212()()()()()()()()xxxxxyyxxxxxxxxxxyA xxxxmxxxxA ？32012( )( )()()()P xL xA xxxxxx 代代入入可可得得：；312111()()()PxLxQ xm 由導數(shù)插值條件由導數(shù)插值條件余項，記余項，記 的單根，的單根，的二

50、重根，的二重根，302( )( )( )( )R xf xP xxxR x ，是是1( )xR x是是2012( )( )()() ()( )R xK xxxxxxxK x 令令，待待定定；2012( )( )( )()() ()RK xxxtttttx 令令( ) t 021()xxxx，二二重重 ；在插值區(qū)間內有在插值區(qū)間內有5個零點個零點由由RolleTH ， 在區(qū)間內至少存在一個零在區(qū)間內至少存在一個零點點(4)( ) t ，4441( )( )( ) 4!0( )( )4!fK xK xf （ ）（ ）（ ），則有則有42012( )( )()() ()4!fR xxxxxxx （）

51、。 本節(jié)內容提要本節(jié)內容提要|分段線性插值 方法概述、幾何意義、誤差估計|分段二次插值 幾何直觀、方法概述、誤差估計三次樣條插值簡介 1.3 分段低次插值分段低次插值/* piecewise Interpolation */1111()( )( )( )( )( )()!nnnnfRxf xL xxn 1 1、從插值余項角度分析、從插值余項角度分析隨著節(jié)點個數(shù)增加到隨著節(jié)點個數(shù)增加到某個值某個值，誤差反而會增加。，誤差反而會增加。一、高次插值評述一、高次插值評述 為了提高為了提高插值精度插值精度，一般來說應該，一般來說應該增加增加插值節(jié)點的個數(shù)，插值節(jié)點的個數(shù)，這從插值余項的表達式也可以看出，

52、但不能簡單地這樣認為，這從插值余項的表達式也可以看出，但不能簡單地這樣認為，原因是原因是前提條件是前提條件是 有有足夠階連續(xù)導數(shù)足夠階連續(xù)導數(shù)(即函數(shù)足夠光滑即函數(shù)足夠光滑)，但隨著節(jié)點個數(shù)的增加，這個條件一般很難成立但隨著節(jié)點個數(shù)的增加，這個條件一般很難成立。( )f x注意下面圖中注意下面圖中曲線曲線的變化情況！的變化情況！例：例： 在在 5, 5上考察上考察 的的Ln(x)。取。取211( )f xx 1050(,., )ixi inn -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端點端點附近變化附近變化越大，稱為越

53、大，稱為Runge 現(xiàn)象現(xiàn)象Ln(x) f (x) 2n ( )yf x 5n 10n RungeRunge現(xiàn)象現(xiàn)象：注：注：高次插值可能出現(xiàn)：在插值區(qū)間高次插值可能出現(xiàn)：在插值區(qū)間中部誤差較小中部誤差較小， 而在而在端點附近誤差較大端點附近誤差較大的情形。的情形。RungeRunge現(xiàn)象現(xiàn)象RungeRunge現(xiàn)象說明并非節(jié)點越多（插值多項式次數(shù)現(xiàn)象說明并非節(jié)點越多（插值多項式次數(shù)越高），誤差越?。辉礁撸?，誤差越??； 。不總收斂到不總收斂到)()(xfxPn高次插值的缺點高次插值的缺點RungeRunge現(xiàn)象的存在；現(xiàn)象的存在；克服方法克服方法分段低次插值分段低次插值；分段插值的構造方法分段

54、插值的構造方法將將插值區(qū)間插值區(qū)間劃分為若干個小區(qū)間（通常取劃分為若干個小區(qū)間（通常取等距劃分等距劃分）abix1ix 采用采用低次低次插值插值( )iP x在區(qū)間在區(qū)間 上得到上得到分段函數(shù)分段函數(shù) , a b00111211( ),( ),( )( ),nnnp xxx xp xxx xxpxxxx ( )f x 11,111( )01iiiiiiiiix xx xLxyyxxxinx ，；1 0011 11211111( )( )( )( )( )( )nnnLxxxxLxxxxL xLxfxLxxxx ，令令，那那么么，一、分段線性插值一、分段線性插值/* piecewise line

55、ar interpolation */ 1 1、方法概述：、方法概述：在每個區(qū)間在每個區(qū)間 上，用上，用1次多項式次多項式 (直線直線) 逼近逼近 f (x):1,iix x 01naxxxb ，101maxiiiii nhxxhh 令令，分段分段線性線性插值插值函數(shù)函數(shù)2 2、幾何意義：、幾何意義： 分段線性插值從整體上看，逼近效果是較好的，但失分段線性插值從整體上看，逼近效果是較好的，但失去了原函數(shù)的去了原函數(shù)的光滑性光滑性。3 3、誤差估計：、誤差估計：111()( )( )()()2!iiiiiiiff xLxxxxxx x ，由由于于，122max()(88iiixx xiihfxh

56、f 1221(01()()(1)(1)iiiiiiiiixxt htxxhxxxxt thtt h ，那那么么， 211()()1(1)014)4iiixxhttxtx 易易知知，那那么么11021201max( )( )max()80( )( )max( )(08)ii niiia xnbf xLxhff xLfxxhh ， 只依賴于二階導函數(shù)的界只依賴于二階導函數(shù)的界 )()(2有有界界，前前提提：xfbaCxf 1 1、幾何直觀：、幾何直觀： 二、分段二次插值二、分段二次插值/* Piecewise Square Interpolation */ 分段拋物線弧段近似分段拋物線弧段近似 (

57、 )f x在每個區(qū)間在每個區(qū)間 上，用上，用2次多次多項式項式 (拋物線拋物線) 逼近逼近 f (x)。222(0 11)kkxxkm ， ，2 0022 2242222( )( )( )( )nnnSxxxxSxxxxSxSxxxx ，令令；，012naxxxbnm ，2 22221212222( )( )( )( )kkkkkkkSxlx ylx ylx y ，2 2、方法概述：、方法概述：2222 0022 22432222131( )( )( )()21)( )(nnnnnnnnnxxSxSxxxxSxxxnxxSxSxxSxmxxxx ，在在，上上作作二二次次插插值值，令令，；，分段

58、分段二次插值二次插值函數(shù)函數(shù)3 3、誤差估計：、誤差估計：2222 22212233222()( )( )()()()3!()6maxax(m)6kkkxxxkkkkkkkkkkkhff xSxxxxxxxfxhxhxfhh ，其其中中， 3( )f xCa b 前前提提：，22 23( )( )max( )( )max60 (0)( )axbkkf xSxf xhfxhxS ，。 收斂性好，計算簡單；亦可根據其具體情況收斂性好，計算簡單；亦可根據其具體情況 在不在不同區(qū)間上采用不同次數(shù)的插值公式；同區(qū)間上采用不同次數(shù)的插值公式； 分段函數(shù)雖然在節(jié)點處連續(xù)但未必可導，因而分段函數(shù)雖然在節(jié)點處連

59、續(xù)但未必可導，因而 光光滑度較差滑度較差。克服方法克服方法 三次樣條插值三次樣條插值優(yōu)點優(yōu)點缺點缺點 分段插值存在著一個缺點分段插值存在著一個缺點, ,就是會導致插值函數(shù)在就是會導致插值函數(shù)在子區(qū)間的端點子區(qū)間的端點( (銜接處銜接處) )不光滑不光滑, ,即導數(shù)不連續(xù)即導數(shù)不連續(xù), ,對于一些實對于一些實際問題際問題, ,不但要求一階導數(shù)連續(xù)不但要求一階導數(shù)連續(xù), ,而且要求二階導數(shù)連續(xù)。而且要求二階導數(shù)連續(xù)。為了滿足這些要求為了滿足這些要求, ,人們引入了人們引入了樣條插值樣條插值的概念。的概念。 1.5 樣條插值函數(shù)樣條插值函數(shù)所謂所謂“樣條樣條”(SPLINE)是工程繪圖中的一種工具是

60、工程繪圖中的一種工具, ,它是有它是有彈性的細長木條彈性的細長木條, ,繪圖時繪圖時, ,用細木條連接相近的幾個結點用細木條連接相近的幾個結點, ,然后再進行拼接然后再進行拼接, ,連接全部結點連接全部結點, ,使之成為一條光滑曲線使之成為一條光滑曲線, ,且在結點處具有連續(xù)的曲率。樣條函數(shù)就是對這樣的曲且在結點處具有連續(xù)的曲率。樣條函數(shù)就是對這樣的曲線進行數(shù)學模擬得到的。它除了要求給出各個結點處的線進行數(shù)學模擬得到的。它除了要求給出各個結點處的函數(shù)值外函數(shù)值外, ,只需提供兩個邊界點處導數(shù)信息只需提供兩個邊界點處導數(shù)信息, ,便可滿足對光便可滿足對光滑性的不同要求。滑性的不同要求。一、樣條函