函數(shù)的插值法

1、北京科技大學(xué)數(shù)理學(xué)院北京科技大學(xué)數(shù)理學(xué)院 衛(wèi)宏儒衛(wèi)宏儒計算方法計算方法分段多項式插值分段多項式插值引言引言 我們已經(jīng)知道插值有多種方法：我們已經(jīng)知道插值有多種方法：Lagrange Lagrange 插插值、值、 NewtonNewton插值、插值、Hermit Hermit 插值等多種方式。插值插值等多種方式。插值的目的就是數(shù)值逼近的一種手段，而數(shù)值逼近，為的目的就是數(shù)值逼近的一種手段，而數(shù)值逼近，為的是得到一個數(shù)學(xué)問題的精確解或足夠精確的解。的是得到一個數(shù)學(xué)問題的精確解或足夠精確的解。那么，是否那么，是否插值多項式的次數(shù)越高，越能夠達(dá)到這插值多項式的次數(shù)越高，越能夠達(dá)到這個目的呢個目的呢？

2、現(xiàn)在，我們來討論一下這個問題。？現(xiàn)在，我們來討論一下這個問題。 我們已經(jīng)知道：我們已經(jīng)知道：f(x)f(x)在在n+1n+1個節(jié)點(diǎn)個節(jié)點(diǎn)x xi i(i=0(i=0，1 1，2 2，n) n) 上的上的n n次插值多項式次插值多項式Ln (x) Ln (x) 的余項為的余項為 (1)1( )( )( )( )(1)!nnnfR xf xL xxn 設(shè)想當(dāng)節(jié)點(diǎn)數(shù)增多時會出現(xiàn)什么情況。由插值余項可知，當(dāng)由插值余項可知，當(dāng)f(x)充分光滑時，余項隨充分光滑時，余項隨n增大增大而趨于而趨于0的，這說明可用增加節(jié)的，這說明可用增加節(jié)點(diǎn)的方法達(dá)到這個目的，那么實(shí)點(diǎn)的方法達(dá)到這個目的，那么實(shí)際是這樣嗎？際是

3、這樣嗎？ 1901 1901年龍格年龍格(Runge) (Runge) 給出一個例子給出一個例子: : 定義在區(qū)間定義在區(qū)間-1-1，11上，這是一個上，這是一個光滑函數(shù)，它的任意階導(dǎo)數(shù)都存在，對光滑函數(shù)，它的任意階導(dǎo)數(shù)都存在，對它在它在-1-1，11上作等距節(jié)點(diǎn)插值時，插上作等距節(jié)點(diǎn)插值時，插值多項式情況，見圖值多項式情況，見圖: :22511xxf )( 從圖中，可見，在靠近從圖中，可見，在靠近-1或或1時，余項會隨時，余項會隨n值增大而增大，如值增大而增大，如P12(0.96)=36!但但f(0.96)=0.25 從圖中，還可看見，在從圖中，還可看見，在0附近插附近插值效果是好的，即余項

4、較小，另一值效果是好的，即余項較小，另一種現(xiàn)象是插值多項式隨節(jié)點(diǎn)增多而種現(xiàn)象是插值多項式隨節(jié)點(diǎn)增多而振動更多。振動更多。 這種插值多項式當(dāng)節(jié)點(diǎn)增加時這種插值多項式當(dāng)節(jié)點(diǎn)增加時反而不能更好地接近被插之?dāng)?shù)的現(xiàn)反而不能更好地接近被插之?dāng)?shù)的現(xiàn)象，稱為象，稱為龍格現(xiàn)象龍格現(xiàn)象。 這個任意階可導(dǎo)的光滑函數(shù)之所以出這個任意階可導(dǎo)的光滑函數(shù)之所以出現(xiàn)這種現(xiàn)象，跟它在復(fù)平面上有現(xiàn)這種現(xiàn)象，跟它在復(fù)平面上有x=x=1/51/5是是奇點(diǎn)有關(guān)。奇點(diǎn)有關(guān)。 俄羅斯數(shù)學(xué)家伯恩斯坦在俄羅斯數(shù)學(xué)家伯恩斯坦在19161916年還給年還給出如下定理：出如下定理：定理：定理：函數(shù)函數(shù)f(x)=|x|f(x)=|x|在在-1-1，1

5、1上取上取n+1n+1個個等距節(jié)點(diǎn)等距節(jié)點(diǎn)x x0 0=-1, x=-1, xn n=1,=1,構(gòu)造構(gòu)造n n次插值多項式次插值多項式L Ln n (x)(x)，當(dāng)，當(dāng)n n增大時，除了增大時，除了-1-1，0 0，1 1，三點(diǎn)，三點(diǎn)外，在外，在-1-1，11中任何點(diǎn)處中任何點(diǎn)處L Ln n(x)(x)都不收斂都不收斂于于|x|x|。 上述現(xiàn)象和定理，告訴我們用高上述現(xiàn)象和定理，告訴我們用高次插值多項式是不妥當(dāng)?shù)?，從?shù)值計次插值多項式是不妥當(dāng)?shù)?，從?shù)值計算上可解釋為高次插值多項式的計算算上可解釋為高次插值多項式的計算會帶來舍入誤差的增大，從而引起計會帶來舍入誤差的增大，從而引起計算失真。因此，

6、實(shí)踐上作插值時一般算失真。因此，實(shí)踐上作插值時一般只用一次、二次最多用三次插值多項只用一次、二次最多用三次插值多項式。式。 那么如何提高插值精度呢？采用那么如何提高插值精度呢？采用分段插值分段插值是一種辦法。是一種辦法。 設(shè)設(shè)f(x)是定義在是定義在a,b上的函數(shù)，在上的函數(shù)，在a,b上節(jié)點(diǎn)上節(jié)點(diǎn) a= x0 x1x2xn-1xn=b,的函數(shù)值為的函數(shù)值為 y0 , y1 ,y2 ,yn-1 ,yn ,若函數(shù)若函數(shù) (x)滿足滿足條件條件 (1) (x)在區(qū)間在區(qū)間a , b上連續(xù)上連續(xù); (2) (x)在每個子區(qū)間在每個子區(qū)間xi , xi+1(i=0,1,2,n-1)上是上是次數(shù)為次數(shù)為m

7、的多項式的多項式; 則稱則稱 (x)是是f(x)在在a ,b上的上的分段分段m m次插值多項式。次插值多項式。 m=1稱為分段線性插值稱為分段線性插值 m=2稱為分段拋物線插值稱為分段拋物線插值定義：分段線性插值的構(gòu)造分段線性插值的構(gòu)造： 由定義，由定義， (x)在每個子區(qū)間在每個子區(qū)間xi , xi+1(i=0,1,2,n-1)上是一次插值多上是一次插值多項式項式;分段線性插值的余項：分段線性插值的余項：定理：定理：設(shè)設(shè)f(x)在在a,b上有二階連續(xù)導(dǎo)數(shù)上有二階連續(xù)導(dǎo)數(shù)f(x) ，且，且| f(x)| m2,記：記： h = max |xi+1-xi|,就有估計：就有估計： |f(x)- (

8、x) |=|R(x)| m2h2/8， xa, b。注意到注意到h隨分段增多而減少，因此用分段法提高精度是很好的途徑隨分段增多而減少，因此用分段法提高精度是很好的途徑.證明：證明：由由Lagrange 余項公式，當(dāng)余項公式，當(dāng)xxi, xi+1時時 |f(x)- (x) |=|R(x)| = |f( )(x-xi)(x- xi+1 )|/2! m2max |(x-xi)(x- xi+1 )|/ 2m2h2/8，上式右端與小區(qū)間的位置無關(guān)，證畢。上式右端與小區(qū)間的位置無關(guān)，證畢。11111 iiiiiiiiiixxxxxxxyxxxxyx,)(分段線性插值曲線圖：分段線性插值曲線圖：例：設(shè)例：設(shè)

9、 -1 x 1 (1)將將-1，1 10 等份，用分段線性插值近似計算等份，用分段線性插值近似計算f(-0.96)。 (2)將將-1，1 n 等份，用分段線性插值近似計算等份，用分段線性插值近似計算,問如何選擇問如何選擇步長步長h可使近似計算誤差可使近似計算誤差R10-4?解：解：(1)插值節(jié)點(diǎn)為插值節(jié)點(diǎn)為xi=-1+ i/5 (i=0,1,10),h=1/5因?yàn)橐驗(yàn)?-0.96-1,-0.8,取此區(qū)間為線性插值區(qū)間，其上的插值取此區(qū)間為線性插值區(qū)間，其上的插值函數(shù)為函數(shù)為所以f(-0.96) (-0.96)=0.0425322511xxf )(801129410801923020180208

10、01.)(.).(.).(.)()( xxxxfxfx(2)插值節(jié)點(diǎn)為插值節(jié)點(diǎn)為xi=-1+ ih (i=0,1,n),h=(b-a)/2=2/n由分段線性插值的余項估計：由分段線性插值的余項估計： |f(x)- (x) |=|R(x)| m2h2/8002801051210025117550251504211232222.)()(max|)(|)(|)()( hhxRxfmxxxfxxxfx 分段二次插值分段二次插值即：選取跟節(jié)點(diǎn)即：選取跟節(jié)點(diǎn)x最近的三個節(jié)最近的三個節(jié)點(diǎn)點(diǎn)xi-1,xi, xi+1進(jìn)行二次插值，即在區(qū)間進(jìn)行二次插值，即在區(qū)間xi-1, xi+1，取：?。?這種分段的低次插值

11、叫分段二次插值，在幾這種分段的低次插值叫分段二次插值，在幾何上就是用分段拋物線代替何上就是用分段拋物線代替y=f(x)y=f(x)，故分段二次，故分段二次插值又和分段拋物插值。插值又和分段拋物插值。 11112iikikjijikjikxxxxyxLxf)()()()( 實(shí)際上，上面介紹的分段低次插值，實(shí)際上，上面介紹的分段低次插值，雖然具有計算簡便，收斂性有保證，數(shù)值雖然具有計算簡便，收斂性有保證，數(shù)值穩(wěn)定性又好且易在計算機(jī)上實(shí)現(xiàn)等優(yōu)點(diǎn)，穩(wěn)定性又好且易在計算機(jī)上實(shí)現(xiàn)等優(yōu)點(diǎn)，但它卻不能保證整條曲線的光滑性，從而但它卻不能保證整條曲線的光滑性，從而不能滿足某些工程技術(shù)上的要求，從六十不能滿足某些

12、工程技術(shù)上的要求，從六十年代開始，首先由于航空、造船等工程設(shè)年代開始，首先由于航空、造船等工程設(shè)計的需要而發(fā)展起來的樣條插值（計的需要而發(fā)展起來的樣條插值（spline)spline)方法，既保留了分段低次插值的各種優(yōu)點(diǎn)，方法，既保留了分段低次插值的各種優(yōu)點(diǎn)，又提高了插值函數(shù)的光滑性，在許多領(lǐng)域又提高了插值函數(shù)的光滑性，在許多領(lǐng)域顯得越來越廣泛的應(yīng)用。顯得越來越廣泛的應(yīng)用。樣條插值樣條插值 分段插值存在著一個缺點(diǎn)分段插值存在著一個缺點(diǎn),就是會導(dǎo)致插值函數(shù)就是會導(dǎo)致插值函數(shù)在子區(qū)間的端點(diǎn)在子區(qū)間的端點(diǎn)(銜接處銜接處)不光滑不光滑,即導(dǎo)數(shù)不連續(xù)即導(dǎo)數(shù)不連續(xù),對于對于一些實(shí)際問題一些實(shí)際問題,不但要

13、求一階導(dǎo)數(shù)連續(xù)不但要求一階導(dǎo)數(shù)連續(xù),而且要求二階而且要求二階導(dǎo)數(shù)連續(xù)。為了滿足這些要求導(dǎo)數(shù)連續(xù)。為了滿足這些要求,人們引入了人們引入了樣條插值樣條插值的概念。的概念。 所謂所謂“樣條樣條”(SPLINE)是工程繪圖中的一種工是工程繪圖中的一種工具具,它是有彈性的細(xì)長木條它是有彈性的細(xì)長木條,繪圖時繪圖時,用細(xì)木條連接相用細(xì)木條連接相近的幾個結(jié)點(diǎn)近的幾個結(jié)點(diǎn),然后再進(jìn)行拼接然后再進(jìn)行拼接,連接全部結(jié)點(diǎn)連接全部結(jié)點(diǎn),使之使之成為一條光滑曲線成為一條光滑曲線,且在且在結(jié)點(diǎn)處具有連續(xù)的曲率結(jié)點(diǎn)處具有連續(xù)的曲率。樣。樣條函數(shù)就是對這樣的曲線進(jìn)行數(shù)學(xué)模擬得到的。它條函數(shù)就是對這樣的曲線進(jìn)行數(shù)學(xué)模擬得到的。

14、它除了要求給出各個結(jié)點(diǎn)處的函數(shù)值外除了要求給出各個結(jié)點(diǎn)處的函數(shù)值外,只需提供兩個只需提供兩個邊界點(diǎn)處導(dǎo)數(shù)信息邊界點(diǎn)處導(dǎo)數(shù)信息,便可滿足對光滑性的不同要求。便可滿足對光滑性的不同要求。一、樣條函數(shù)的定義一、樣條函數(shù)的定義 設(shè)設(shè)f(x)是區(qū)間在是區(qū)間在a,b上的一個連續(xù)可微函數(shù)上的一個連續(xù)可微函數(shù),在區(qū)間在區(qū)間a,b上給定一組基點(diǎn)上給定一組基點(diǎn): a=x0 x1x2xn=b設(shè)函數(shù)設(shè)函數(shù)s(x)滿足條件滿足條件 (1) s(x)在每個子區(qū)間在每個子區(qū)間xi , xi+1(i=0,1,2,n-1)上是次上是次數(shù)不超過數(shù)不超過m的多項式的多項式; (2) s(x)在區(qū)間在區(qū)間a , b上有上有m-1階連

15、續(xù)導(dǎo)數(shù)階連續(xù)導(dǎo)數(shù); 則稱則稱s(x)是定義在是定義在a ,b上的上的m m次樣條函數(shù)次樣條函數(shù)。x0，x1，x2, 稱為稱為樣條結(jié)點(diǎn)樣條結(jié)點(diǎn),其中其中x1,xn-1稱為稱為內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn), , x0 , xn 稱為稱為邊界結(jié)點(diǎn)邊界結(jié)點(diǎn)。當(dāng)。當(dāng)m=3時時, ,便成為最常用的便成為最常用的三次樣條函數(shù)三次樣條函數(shù)。 二、二、三次樣條插值函數(shù)三次樣條插值函數(shù) 設(shè)設(shè)y = f(x)在點(diǎn)在點(diǎn) x0，x1，x2, xn的值為的值為y0，y1，y2, yn，若函數(shù)若函數(shù)S(x)滿足下列條件滿足下列條件 S(xi)=f(xi) =yi , i=0,1,2,n (1.1) 則稱則稱S(x)為函數(shù)為函數(shù)f(x)的的

16、三次樣條插值函數(shù)三次樣條插值函數(shù), 簡稱簡稱三次樣條三次樣條。 構(gòu)造三次樣條插值函數(shù)的方法有很多，這里介紹一個常用構(gòu)造三次樣條插值函數(shù)的方法有很多，這里介紹一個常用的方法：的方法：三彎矩插值法三彎矩插值法 記記Mi = S(xi), f(xi)= fi= = yi , ,考慮它在任一考慮它在任一區(qū)間區(qū)間xi, ,xi+1上的上的形式形式.根據(jù)三次樣條的定義可知根據(jù)三次樣條的定義可知 ,S(x)S(x)的二階導(dǎo)數(shù)的二階導(dǎo)數(shù)S(x)S(x)在每一個在每一個子區(qū)間子區(qū)間xxi i,x,xi+1i+1 ( i=0,1,2, ( i=0,1,2,n-1),n-1)上都是線性函數(shù)。上都是線性函數(shù)。于是在于

17、是在xi, ,xi+1 上上S(x)=Si(x)的二階導(dǎo)數(shù)表示成的二階導(dǎo)數(shù)表示成 (1.2) 其中其中 hi= xi+1xi . 對對S(x)連續(xù)積分兩次連續(xù)積分兩次,并利用插值條件并利用插值條件S(xi)= yi ,得到得到 三、三次樣條函數(shù)的構(gòu)造三、三次樣條函數(shù)的構(gòu)造,)( 111S iiiiiiiixxxhxxMhxxMx x x i , x i+1 S”(x) M i , M i+1 )()()()()(iiiiiiiiiiiiiiiixxhMhyxxhMhyhxxMhxxMx 6666S1113131 因此，只要能求出所有的因此，只要能求出所有的 M M i i ，就能求出樣條，就能

18、求出樣條插值函數(shù)插值函數(shù)S(x). S(x). 下面考慮下面考慮M Mi i的求法的求法。,)()()(1112121622S iiiiiiiiiiiiiixxxhMMhyyhxxMhxxMx則由連續(xù)性則由連續(xù)性 S S (x(xi-i-)= S)= S (x(xi+i+) ,(i=1,2,) ,(i=1,2,n-1) ,n-1) 得得 i iM Mi-1i-1+2M+2Mi i+i iM Mi+1i+1= d= di i 其中其中 1111116)(,iiiiiiiiiiiiihhhyyhyydhhhu 上面的方程組有上面的方程組有n-1n-1個方程，但有個方程，但有n+1n+1個變量個變量

19、M Mi i，故需故需兩個方程才能求唯一解，為此引入下列邊界條件兩個方程才能求唯一解，為此引入下列邊界條件：下面介紹幾種常用的邊界條件下面介紹幾種常用的邊界條件 第一型邊界條件第一型邊界條件： 已知已知f(x)在兩端點(diǎn)的導(dǎo)數(shù)在兩端點(diǎn)的導(dǎo)數(shù)f(a)和和f(b) ，要求，要求S(a) = f(a) , S(b) = f(b)第二型邊界條件第二型邊界條件：已知已知f(x)在兩端點(diǎn)的二階導(dǎo)數(shù)在兩端點(diǎn)的二階導(dǎo)數(shù)f(a)和和f(b) ，要求，要求 S(a)=M0 = f(a) , S(b)=Mn= f(b) 特別當(dāng)特別當(dāng) S(a)= S(b) =0時，時，S(x)稱為自然三次樣條。稱為自然三次樣條。 第三

20、型邊界條件第三型邊界條件： 已知已知f(x)是以是以b -a為周期的周期函數(shù)為周期的周期函數(shù) ，要求，要求S(x)滿滿 足周期條件足周期條件 S (a) = S(b) , S(a+)= S(b-) , S(a+)= S(b-) 三次樣條插值問題加上第三次樣條插值問題加上第i i型邊界條件稱為第型邊界條件稱為第i i型插值問題（型插值問題（i i，）可以證明第，）可以證明第i i型插值問題的解是存在且唯型插值問題的解是存在且唯一的。他們對應(yīng)如下的三對角方程組：一的。他們對應(yīng)如下的三對角方程組： 2 0 0 M0 d0 1 1 2 1 M1 d1 . . . . . . . . . = . (*)

21、 . . . . . n-1 n-1 2 n-1 Mn-1 dn-1 n n 2 Mn dn 對于第一型插值問題，取對于第一型插值問題，取 0 0=1=1，n n=1,=1,對于第二型插值問題，取對于第二型插值問題，取0 0=0=0，n n=0=0 對于第三型插值問題，利用周期性，可導(dǎo)出對于第三型插值問題，利用周期性，可導(dǎo)出其中 , nnydyd2200 nnnnnndMMMMM2110)(),(nnnnnnhyyyhdyhyyhd101011066 11110116)(,nnnnnnnnnnhhhyyhyydhhhu 以上各組條件與方程組以上各組條件與方程組(*)聯(lián)立，可以解出未知參聯(lián)立，可

22、以解出未知參數(shù)數(shù)M M0 0，M M1 1 , ,M,Mn n，然后代入，然后代入S(x) S(x) 表達(dá)式，即可求表達(dá)式，即可求得樣條函數(shù)得樣條函數(shù) 。 上面構(gòu)造方法中上面構(gòu)造方法中MiMi相應(yīng)于力學(xué)中細(xì)梁在相應(yīng)于力學(xué)中細(xì)梁在x xi i處截面的處截面的彎矩，每一個方程中又至多出現(xiàn)相鄰的三個彎矩，每一個方程中又至多出現(xiàn)相鄰的三個M Mi i，通常，通常稱為三彎矩法。稱為三彎矩法。 總結(jié)以上論述，可得求三次樣條的步驟為：總結(jié)以上論述，可得求三次樣條的步驟為：（1 1）確定邊界條件，判定是第幾型插值問題；）確定邊界條件，判定是第幾型插值問題；（2 2）根據(jù)所確定的條件計算各值，形成方程組）根據(jù)所

23、確定的條件計算各值，形成方程組(*)；（3 3）解三對角方程組）解三對角方程組(*)，求得，求得M0， M1 ， M2, Mn ；（4 4）將求得的）將求得的Mi值代回值代回S(x)的表達(dá)式中，的表達(dá)式中， 從而可求得函數(shù)從而可求得函數(shù)y=f(x)在任一點(diǎn)的近似值在任一點(diǎn)的近似值S(x)。 四、例題四、例題 例例1 1 已知函數(shù)已知函數(shù)f(x）的數(shù)值表如下：的數(shù)值表如下： x x 2 2 4 4 6 6 f(x) 3 3 7 7 13 13 f(x) 1 1 -1 -1 試求試求f(x) 在在2,62,6上的三次樣條插值函數(shù)。上的三次樣條插值函數(shù)。解：這是第一類邊界條件的問題這是第一類邊界條件

24、的問題 ，n=2,hn=2,hi i=h,=h,由公由公式：式： 1 1 =1 =1/2 ，d1 =3/2=3/2； n n =0 =1 ， d0=3,=3,d2=-12=-12 得方程組得方程組 2 2 M0 + + M1 = 3= 3 0.5 0.5 M0 + + 2M1 +0.5+0.5 M2 = 1.5= 1.5 M1 +2+2 M2 = -12= -12解得解得 M0 =0.25 , =0.25 , M1 =2.5 =2.5 M2 = -7.25= -7.25故所求的三次樣條插值函數(shù)故所求的三次樣條插值函數(shù) - (1/48)(x-41/48)(x-4）3 3 + (5/24)(x-2+ (5/24)(x-2）3 3 -(17/12) -(17/12)（x-4x-4）+(8/3)(x-2), x2+(8/3)(x-2), x2，44S(x)=S(x)= - (5/24)(x-65/24)(x-6）3 3 - (29/48)(x-4- (29/48)(x-4）3 3 -(8/3) -(8/3