1第五章 函數(shù)的插值及其數(shù)值計算§1 插值的基本概念插值方法是數(shù)值分析中一個很古老的分支，它有著悠久的歷史。插值理論和方法也是現(xiàn)代數(shù)值分析中最基本的內容之一，它在數(shù)值積分，曲線曲面擬合，求微分方程數(shù)值解等方面有著廣泛的應用。在工程技術與科學研究中，有時對一個函數(shù)只知道它在某些點上的數(shù)值，為了進一步研究其性質，需要用其他函數(shù)去近似代替它，這時就可以用插值方法。有時候，雖然函數(shù)有解析表達式，但形式過于復雜，為了便于處理，先在某些點上取值作表格函數(shù)，再通過插值建立易于處理的新函數(shù)，這也是插值理論的一個應用。先介紹一般的插值概念。設 ， 。已知它在 個互異的點 ， 處的函數(shù)值 ，)(xfba,1n0xn0y， ，即：1yn， ，1，niiyxf)(求解插值問題就是從函數(shù)類 中求 使)(x， ，1，n （1.1）iiyx)(02這里的 稱為被插函數(shù)， 稱為插值區(qū)間，)(xfba,， ，1 ，n ，稱為插值節(jié)點， （1.1）式稱為插值條件，而 和ix0 )(x分別為插值函數(shù)和插值函數(shù)類。通常選定的插值函數(shù)類是有限維線性空間，它可看成是某一組基張成的線性空間：niix0)(niixSpa0)(對 ，有 使得nia0niixax0)()(于是確定函數(shù) 歸結為確定數(shù)列 。)(xni從理論上看，插值問題包含以下內容：（1）確定 的基 ，一般地說基不唯一，選擇合適的基可以簡化nii0)(問題的解法；（2）討論滿足（1.1）的 的存在性，求法及唯一性；)(x（3）尋找插值問題的截斷誤差，即余項： )()(xfR的表達式與估計。3§2 多項式插值本節(jié)選取常用的多項式函數(shù)類作插值函數(shù)類。多項式函數(shù)屬于解析函數(shù)類，形式簡單，計算方便，其導數(shù)與不定積分易于求出。下面把不超過 n 次的多項式函數(shù)類記為 nP2.1 Lagrange 插值設已知 ， 在相異節(jié)點 ， ， 上的函數(shù)值)(xfba,0x1nx， ， 1， ， n， 取 = ，下面求 的插值函數(shù)。iiyf)(0nP)(f設，201() npxaxa插值的基本問題是，尋求如上的 ，使得 ，()()iipy， 1， ， n.0i該問題等價于求解下列線性方程組： 2010011201nnnaxaxy 上述線性方程組的系數(shù)矩陣為：4200112nnnxxA A 的行列式為（稱為 Vandermonde 行列式） 20011012(,)nnnnxxWx 根據(jù)線性代數(shù)的知識知道 010(,)()njijixx注意到諸 互不相同，從而 ，上述線性方程組存在唯ix,W一解。這說明滿足條件（1.1）的插值多項式是存在的，而且還是唯一的。定理 2.1 設 ， 為 上的 n+1 個相異的節(jié)點，)(xfba,0nixba,，i=0，1 ， ， n，則滿足)(iixfy，i=0，1 ， ， n()iipxy的 是存在并且唯一的。()pxnP從定理 2.1 的證明可看到，要求插值多項式 p(x),可以通過求解一個線性方5程組得到。但這樣做不但計算復雜，且難于得到 p(x)的簡單表達式。為了求得便于使用的簡單的插值多項式 p(x)， 可以如§1 所述，選擇 的適當?shù)幕?。nP先構造 n 次插值基函數(shù) ，i=0，1 ， ， n 使)(xlinP， ， 1， ， n， （2.1）1()0ijijjlxi， i由當 時， 可知：ij)(jixl， 1， ， n （2.2）0()niikklxc0i其中 是待定常數(shù)，它可由 定出：i )(ixl； ， 1， ， n。10()niikkc0i代入（2.2）得：i=0， 1， ， n0()nkikixl再作 00()()nn kiiiikixLxylxy易知 ，即為所求的插值函數(shù)。nP6這種具有 性質的基稱為對偶基，以后我們還會多次構造針對不同問題的ij對偶基。記 ，則 ，10()nnkkxx10()()nniikkxx，10()()nnkkiixx， i=0，1 ， ， n，1()niiilx10()nniiixLy例 2.1 已知 ，節(jié)點為 ， ， ，求xf)(102x4)(2xL解 ， )(1fy， 。0y 1)(fy863)4(2)(20 xxl 21 1()(54)()l)3(6)4()(22 xxxl722017()()84iLxylx2.2 插值多項式的插值余項現(xiàn)在考慮用 近似 所產(chǎn)生的誤差，即插值余項)(xLn)(f)(xLfxRnn當 在 上 n+1 階可導時，可以把 化為便于估計的形式，)(xfba, R先設 ，i=0，1 ， ， n，作輔助函數(shù)，1()()()nFtfLtKxtba,其中 滿足：()Kx（2.3）1()()0nnfxx當 x 不為插值節(jié)點時 ，這樣的 是存在的。10K于是 ， ， ， 是 的 n+2 個相異的零點，依次對 ，0txnx)(tF)(tF， 應用 Rolle 定理可知存在 使)(F)(tn ba,0= (1)(1)()1!nnfKxn從而8(1)!nfKx代入（2.3）式得：，(1)1()!nnnfRxxba,若 x 等于某一 ，則 ， 故任取 上式也成立。i1()0nRnx,于是得出：定理 2.2（多項式插值的余項） 設 在 上 n+1 階可導，則存在)(xfba,使ba, (1)1() ()!nnnnfRxfLxx注：由上式可知，當 時， ，特別當 時，可得：fP)(fnf（2.4）0()1nilx例 2.2 考察四位常用對數(shù)表作線性插值的誤差。解 設 ， ， 0.4343。xflg)(2lg)(xef設 x 位于 和 之間：1 ，則0019， 1012lg()()eRxx0x1記表距 ，得01h 4)(max21010 hx2110.3(lg)(8LR= 220549.hx當 h=0.01 時，（2.5）61149.5)(lgxL再考慮舍入誤差，設， i=0，1iiiffy)(其中 是表值， 是舍入誤差，則：ifi，i=0，1 （2.6）50iiify把以 ， ，i=0，1 構造的線性插值分別記為 ， ，注意到i )(xL*1，i=0， 1 在 上非負及（2.5） ， （2.6）式，則線性插值的舍入誤差)(xli 0,x*21()()RL101100()()iiylxfl10ma(),iifli10()ilx= 51可見舍入誤差比截斷誤差大一個量級。此時整個誤差不超過 6512().4910Rx2.52.3 Newton 插值Lagrange 插值公式的缺點是，當插值節(jié)點的個數(shù)有所變動時（例如為了提高精度，有時需要增加節(jié)點個數(shù)） ，Lagrange 插值基函數(shù) ，)(xlii=0，1 ， ， n 就要隨之發(fā)生變化，從而整個公式的結構也要發(fā)生變化，這在計算實踐中是不方便的。為了克服上述缺點，在這一節(jié)中我們引入 Newton 插值公式。11令 表示 n 個節(jié)點 ， ， 上的 n-1 次插值多項式，由于)(1xNn0x11x， i= 0，1 ， ， n-1iini yN)()所以 101()()()nn nxcxx此處 c 為常數(shù)，由條件，可以定出 )()(110nnnxxNyc因此，n+1 個節(jié)點 ， ， 上的 n 次插值多項式也可以寫成下列形0x1式： 010011()()()()n n nNaaxx Newton 插值公式的系數(shù)如何確定?為此我們引進差商的概念。設已知不同的自變量 上的函數(shù)值n,10，i=0，1， ， n， 稱)(ixf，(),ijijfxffji為 的一階差商（式均差） 。一階差商的一階差商)(xf ,()ijjkijkfxfxfxi12叫做 的二階差商。一般說來，我們稱 n-1 階差商的一階差商)(xf 01201 0,nnnfxfxf 為函數(shù) 的 n 階差商。)(xf根據(jù)差商定義設 為一動點，,ab0011000()(),()nnnfxfxxfffx 只要把后一式代入前一式，即得： 001001201(),(),()fxfxf ),()nnnxfxx :()nNxR其中 且滿足插值條件，稱為 Newton 插值公式。而nP 為插值余項。()nx01,()nfx用數(shù)學歸納法易證明 n 階差商 1010(),niifxfx為了作數(shù)值計算常利用形式如下的差商表13x 一階差商 二階差商 三階差商)(f001x)(1f01,fx222012,fx3x)(3f3,fx30123,fx插值公式（2.9）中的系數(shù)就是上表中帶下劃線的項。因此當已知，i=0，1， ， n 時，利用差商表可以很容易地算出的各階差商的)(iixfy值。因為在 n+1 個不同的點 ， ， 上取給定值的次數(shù)不超過 n 的多0x1nx項式是唯一的，所以次數(shù)相同的 Newton 插值多項式與 Lagrange 插值多項式是恒等的，它們的差異僅是書寫形式不同而已，但是這種差異卻為計算實踐帶來了很大的方便，實際上，對于 Newton 插值公式來說，當需要增加一個插值點時，只需要在原插值多項式的后面再添加一個新項就可以了。2.6 Hermite 插值為了理論和應用上的需要，有時不但要求插值函數(shù) p(x)在節(jié)點處的函數(shù)值與被插值函數(shù) f(x)相同，而且要求在節(jié)點處的導數(shù)值也相等，這就導致了下面的14Hermite 插值。給定 f(x) 在 n1 個互異的節(jié)點 處的函數(shù)值 及導01,nx ()iifxy數(shù)值 ，i=0 ， 1， ， n， 要求一個次數(shù)不超過 2n1 次的多項式()ifxy滿足21nH， i=0，1 ， ， n， 2121(),()niiniiHxyxy（219）我們從構造 Lagrange 插值多項式的方法得到啟發(fā)，設法構造 Hermite 插值問題的對偶基。即構造兩組次數(shù)都是 2n1 次的多項式 01()jjlxl和i=0，1 ， ， n 使其滿足：i， j=0，1 ， ， n 0011(),();jiijjijlxlx（220）則滿足插值條件（2.19）的 2n1 次多項式就是（221）2100()()()nnnjjHxylxylx由（220）知 是 的二重零點，因此可設,ijjl20()(j jxablx其中 a， b 為待定常數(shù)， j=0，1 ， ， n 是 2.1 節(jié)中定義的 n 次jl15Lagrange 插值基函數(shù)，于是只要選擇常數(shù) a， b 滿足2()(1)(0jjjjaxbllxl整理有 ()12()0jjjabxl解上述方程得： ()12jjalbx類似于上述做法，令： 21()(j jlcdl同理可求得 jdx將 a,b,c,d 代入（ 2.21）并整理可得 2210()()()nnjjjjjHxyxylx定理 2.4 Hermite 插值問題（ 2.19）的解是存在且唯一的。證明 存在性上面已證。為證唯一性，假設有另一 也滿足條2121()nnQxP件（2.19） ，令： ，易知 是212121()()()nnnxQHxP,0,i16的二重零點，于是，次數(shù)不超過 2n1 的多項式 有 2n2 個零點，()x ()x必 從而 。02121()()nnQxHHermite 插值函數(shù)的誤差與 Lagrange 插值的誤差估計十分類似，有如下定理，讀者可仿照定理 2.2 自己證明。定理 2.5 （Hermite 插值的余項） 設 在 上 2n+2 階可導，x)(xfba,和諸 皆位于區(qū)間 內，則存在 使ixba,ba,(2)221211()()!nnnnfRxfHxx2.7 Newton-Hermite 插值公式本節(jié)討論一類具有重節(jié)點的多項式插值方法，即 Newton-Hermite 插值方法。因為此類插值問題要求在節(jié)點處滿足任意給定的導數(shù)條件，所以也常被稱為切觸插值問題。設 （2.22）1x2sx，為事先指定的實數(shù)，其中 為正()0,;,hkky 1,s整數(shù)（2.23）121ns17我們要構造一個次數(shù)不高于 n 的多項式 ，使)(xpnP， （2.24）)()(hkhyxpsk,1;,0 下面我們用類似于 Newton 插值的方法來解這個問題。第一步：根據(jù)（2.22） ， （2.24）式寫出數(shù)列（2.25）ssxxx,2211 （2.25）中， 連續(xù)寫 次，再將（2.25）中的數(shù)據(jù)重新順序編號，得到kk（2.26）nx,10（2.26）稱為有重節(jié)點的插值節(jié)點組。第二步：對于節(jié)點組（2.26）和插值條件（2.24） ，用 2.3 節(jié)中同樣的方法作出差商表。這里對重節(jié)點的差商作補充規(guī)定： ()()1,!hhkkkhfxyfx個第三步：寫出形如（2.10）的 ， 就是所要求的 Newton-)(Nn)(nHermite 插值多項式例 2.5 設節(jié)點為 ，設求 ， 使0123,xx()Hx5P18， ， ，1(3) 2H2)0(1)(H， ，4 。()解 重寫節(jié)點組 并作差商表：1,03,x 一階差商 二階差商 三階差商 四階差商 五階差商)(f-3 21-3 4-3 810 2 2570 2 1 3619261 1 1 0 81381453623 235()(3)()()()()2487Hxxxxx即為所求之插值多項式。19§3 分段線性插值討論了 Lagrange 插值法以后，自然會問：當插值節(jié)點無限加密時，必在 上收斂于 嗎？)(xLnba,)(xf即使對于性質很好的函數(shù)，答案也是否定的。Runge 指出，無窮次可微函數(shù) 21)(xf在 上用等距節(jié)點插值時，在區(qū)間兩端會產(chǎn)生劇烈振蕩的現(xiàn)象。圖 3.15,給出了 與 的示意圖。可以證明：在等距節(jié)點下當 )(xf)(10Lx時， 收斂于 。而 > 時 不收斂。63.n)(xf)(Ln20圖 3.1因此在實際實用中，往往不采用高次插值多項式，而改用分段的低次插值多項式去近似函數(shù)。由于分段的低次插值多項式對函數(shù)通常有較好的逼近性態(tài)，因而近年來有著十分廣泛的應用。其中突出的如樣條函數(shù)。本段先介紹分段線性插值。設 ， ，已知它在節(jié)點 上的函數(shù))(xfyba,0xa1bxn值 ，i=0，1， ， n。 試求 ， 使i )(xIb,（1） ，i=0，1 ， ， n；iyxI)(（2） 在 ，i=0，1 ， ， n 上是一次多項式。,i滿足上述條件的 稱之為 在 上以 為節(jié)點的分段線性插值)(xI)(xfba,nix0多項式。滿足所述條件的 是存在的，只要把在 ，i=0，1 ， ， n-1 上)(I ,i的線性插值多項式逐段拼接起來就得出 了。)(xI， ，i=0，1 ， ， n1 ；iiiixyxyI 11)( ,i對于分段線性插值多項式我們也可以構造 型的基，只要令：ij210)/()(110xxl 其 他 點 10x)/()()11jjjj xxl 其 他 點 11jjxj=1，2， ， n-10)/()()11nn xxl 1nnx他顯然有 i,j=0，1， ， n。因此 可表示為ijijxl)( )(I0()jiIxylx記 ，i=0，1， ， n-1， 。對于 時iiixh1 1ma()inh0h趨向于 的收斂問題，有)(xI)(f定理 3.1 （分段線性插值收斂的充分條件）若 在 上連續(xù)，則當)(xfba,時， 在 上一致收斂于 。0h)(xIba, )(xf證 由 的連續(xù)性， ，i= 0，1， ， n-1，)(xf1,i使 和 分別取得 在 上的最大值 和1,iixii)(xfi iM最小值 ，于是im22，)()(iiffxIf 1,ix再由 在 上的一致連續(xù)性， 0， 0 使 ， ，)(xfba, uvba, 時，有 。于是當 h 時， ， 使vu)(vfu,xk10nk 證畢。)()(kkffxIf由定理 3.1 可知，剛才我們討論的 Runge 函數(shù)， ，21)(xf它在等距節(jié)點組上的 n 次插值多項式 不收斂，而其在同一節(jié)點5,x )(xLn組上的分段線性插值多項式一致收斂于 。)(f§4 三次樣條插值雖然分段線性插值 較好地解決了收斂問題，但是 在內節(jié)點上通常)(xI )(xI是不可導的。而在實際應用中，如高速飛行器的機翼設計、船體放樣等，需要分段插值函數(shù)有二階可導性。為此，下面討論三次樣條插值。4.1 三次樣條函數(shù)樣條（Spline）本來是在船體放樣繪制光滑曲線時用的一種細木條。用壓鐵把細木條固定在一些已知點上，細木條就形成一條相當光滑的曲線。23數(shù)學上的樣條函數(shù)是從這個物理模型中抽象出來的，其中常用的三次樣條函數(shù)的定義如下：對函數(shù) ， 與 上的一組節(jié)點：)(xS,ba, 0x1bxn若（1） 在 ，i=0，1， ， n-1 上都是三次多項式，)(xS,i（2） 在 上有二階連續(xù)導函數(shù)，ba則稱 為 上以 為節(jié)點的三次樣條函數(shù)。)(x,nix0若再要求：（3） ， i=0，1， ， n()()iiSyf則稱 為 上以 為節(jié)點的 的插值三次樣條函數(shù)。x,banix0)(xf4.2 三次樣條插值的計算設給定一區(qū)間 ，且,ba 0x1bxn任意給定一組常數(shù) ， ， ，要求構造一個插值三次樣條函數(shù) ，0y1ny )(xS使得如下插值條件得以滿足：24，j=0，1 ， ， n （4.1）jyxS)(今以 表示 ，j=0，1， ， n 。由于 為分段 3 次多項式，jMj )(xS所以 在區(qū)間 上為一線性函數(shù)。因而它可由過 與)(jxS,jjx ),1jjM兩點的線性插值函數(shù),j（ ） （4.2）jjjj hxxS11)( jjx1所決定，其中 。1jjjh為了最后求出 在 上的表達式，只須對（4.2）式積分兩次，并)(xS,jj定出積分常數(shù)就夠了。當 時，,1jjxjjjj hxMhxS6)(6)()( 3131 jjjjjj hxMyy 1221 )6()( （4.3）jjjj hxhxxS2)(2)()(' 11（4.4）16jjjjyM25由（4.3）可知，為求 ，關鍵是設法確定各個 ，j=0，1 ， ， n。而)(xSjM為了求得各個 ，必須引用樣條節(jié)點處的光滑連接條件jM（4.5）)()0(jjxSx按（4.4）有 jjjj hyMhxS1136)( 111(0)jjjjj jj由（4.5）可得連續(xù)性方程111636jjjjjj MhhMj=1， ， n1 （4.6）jjyy11它給出了 n+1 個未知數(shù) ，j= 0，1， ， n 的 n-1 個方程式，按它尚不足以j唯一確定 。還須補充兩個“邊界條件” ，這有下述幾種情況：jM（1）假定 。于是按照前面公式，可得方程：nybSa)(,)(026（47）)(6211010nnnn hyM（2）假定 ，相當于直接給出 ， .0(),)Sayb 0Myn無論（1）或（2） ，均可概括為（4.8）0102nndM引入記號， ，j=1 ， 2， ， n-1 （4.9）1jjhjj則（4.6）可改寫為 1111 /)(/)(62 jj jjjjjjj hhyyMj=1，2， ， n-1 （4.10）所以由（4.8） ， （4.10）確定的線性方程組為27= （4.11） 2020112110nn nMM1210ndd1210其中 ，j=0，1 ， ， n-1 表示（4.11）的右端項。jd如果滿足條件)(xSj=0，1，2. （4.12）)()( bajj則稱之為以 b-a 為周期的三次周期樣條函數(shù)。顯然，對于 3 次周期樣條函數(shù)，應該要求（4.10）對 j=n 的情況也成立，如果再注意到 的性質，而把nM0（4.10）中的 換成 ，則相應于 3 次周期樣條函數(shù)的方程組為0Mn= （4.13） 20002011332 11nn nM12321ndd1232128其中 10,nnnnhM線性代數(shù)方程組（4.11）?？捎米汾s法來求解，而方程組（4.13）則可把先作為參數(shù)，求解其中 n-1 個方程中的 n-1 個未知數(shù) ，n 1M， （其解依賴于 ） ，然后代入最后一個方程以求出 ，同時21nn n， ， ，也隨之確定了。1M4.3 誤差界與收斂性三次樣條函數(shù)的收斂性與誤差估計比較復雜，這里不加證明地給出一個主要結果。定理 4.1 設 ， 為滿足第一類或第二類邊界條件的三4(),fxCab)(xS次插值樣條函數(shù)，令 ，則有估計式101m,0,1iiiinhn()()(4)a| |,2kk kkxbfxfxh其中 01253,.3848CC這個定理不但給出了三次樣條插值函數(shù) S(x)的誤差估計，且指出了當時，S(x) 及其一階導數(shù) S(x) 和二階導數(shù) S(x) 均分別一致收斂于 f(x)，hf(x)， f(x).29B-樣條函數(shù)空間上面導出的三次樣條插值函數(shù)分別在每個子區(qū)間上有一表達式，這在應用上和理論分析中都很不方便，如果利用基函數(shù)表示往往更為方便。設給定一組節(jié)點 （5.1）0x1Nx1又設分段函數(shù)滿足條件：1于每個區(qū)間 ，j=0， ， N 上， 是一個次數(shù)不超過 n 的,1j )(xS實系數(shù)代數(shù)多項式；2 于 上具有直到 n-1 階的連續(xù)導函數(shù)。則稱 為 n)(xS), )(xSy次樣條函數(shù)。常把以（5.1）為節(jié)點的 n 次樣條函數(shù)的總體記為 ，,1Nn稱為樣條節(jié)點。Nx,1下面來給出樣條函數(shù)類 中任一樣條函數(shù)的一般表達式。nS),(1Nx對于任意給定的以（5.1）為節(jié)點的 n 次樣條函數(shù) ，12(),)NSxxn根據(jù)定義，其在每個子區(qū)間 ，j=0， ， N 上均為一 n 次多項式，特,1jx別地，于子區(qū)間 內是一 n 次多項式，不妨設其為,(1)(xpP30今考慮 于 上的表達式。由定義， 于 上的表達式仍)(xS,21 )(xS,21為一 n 次多項式。若設該 n 次多項式為 ，并考慮下述 n 次多項式的性質：)(qn)()(xpxnn按 n 次樣條函數(shù)的定義， 與 于點 處的值及 1 階、2 階，一直pnq1到 n-1 階導數(shù)值皆相等：，i= 0， ， n-1)()(11xinin亦即，i= 0， ， n-1)(1i是故 是 的 n 重根，即 含 這個因子，由于 是一 n1x)(xn)()(x次多項式，所以存在某常數(shù) ，使得：1C（5.2）nx)()1亦即（5.3）nnnCpxq)()(1它說明 于區(qū)間 上的表達式恰為其前一區(qū)間上的表達式加上)(xS,21的某一常數(shù)倍，這樣一來， 于 上的統(tǒng)一表達式應為：n1)(xS,231（5.4）1112(),()nnpxxSxC為把（5.4）式寫成一個統(tǒng)一的表達式，引入記號（5.5）0),0max(xm)(則（5.4）所示的 又可緊湊地表示為)(xSnnxCp)(12()x繼續(xù)采用這種分析方法，可得 于整個實軸上的表達式為（5.6）1()()NnnjjjSxpx)(x此即為下述定理所敘述的事實定理 5.1 任一 均可唯一地表現(xiàn)為),()21NxxnS（5.7）1(NnnjjjpC)(x其中 ， ，j=1， ， N 為實數(shù)。)xpnPj顯然，由（5.7）式所給出的任一函數(shù) 必然滿足 n 次樣條函數(shù)的定義，)(xS亦即 ，因而定理 5.1 可進一步寫成：),()21NnxSx32定理 5.2 為使 必須且只須存在 和 N),()21NxxSn)(xpnP個實數(shù) 使得（5.7）式成立：NC,211()()Nnnjjxpx()x定理 5.1 和定理 5.2 說明函數(shù)系 1,.,(),.()nnnN構成 n 次樣條函數(shù)類 的一組基，線性空間 的S21Nx S),(1Nx維數(shù)為 N+n+1。