第二章插值法與數(shù)值微分

1、 實際中，f(x)多樣，復雜，通常只能觀測到一些離散數(shù)據(jù)；或者f(x)過于復雜而難以運算。這時我們要用近似函數(shù)g(x)來逼近f(x)。這個過程就是曲線擬合。 插值法在工程及建筑設計中應用十分廣泛。例如，已知一天24小時的逐時室外氣溫、綜合溫度、冷熱負荷等值，需要知道其他任意時刻的值，即可應用插值計算求得；又如，我國工業(yè)企業(yè)采取通風和空氣調節(jié)設計規(guī)范中，僅給出了有限個地區(qū)相應有限個方位的夏季太陽輻射熱總強度值，以及透過窗玻璃的太陽總輻射強度值，至于其它任意方位（0-350）的中間值，也要用插值法求得。因此，插值法的研究很有必要。 自然地，希望g(x)通過所有的離散點x0 x1x2x3x4xg(x

2、) f(x)本章學習插值法本章學習插值法1圖2曲線擬合幾何意義( )nP x( )yf x01,naxxxb01,nyyy( )nP x()0,1,niiPxyin01,nx xx ,a b( )f x01,nx xxn若節(jié)點互不相同，則滿足插值條件的 次多項式存在且唯一。（證略）2圖2插值函數(shù)幾何意義0 x1x2xnxxy已知函數(shù) 在結點 上的函數(shù)值 ，要求一個一次多項式 使之滿足 ， 其幾何意義就是通過A，B兩點作一條直線近似代替曲線 。( )yf x01,xx01,yy1( )P x100111(),( )P xyP xy( )f x優(yōu)點：優(yōu)點：計算簡單，以直線代替曲線。缺點：缺點：精度

3、低，誤差大。改進：改進：多用一些點。由解析幾何，我們立即可以得到的 表達式1( )P x011010110( )xxxxP xyyxxxx1( )P xx 這樣的 一般是 的一次多項式，即一次函數(shù)。這種插值稱為線性插值（或一次插值）。130453020 P (30)2.86.54.282045452000202.8xy解：取，11456.5xy，并將其代入線性插值公式，有2x1x0 x0y1y2( )P x2( )0,1,2iiP xyi幾何意義：通過三點A、B、C的拋物線代替曲線2y這樣的 是 的二次函數(shù)，其形式為：2( )P xx22012( )P xaa xa x其中 為待定常數(shù)。012

4、aaa， ，若將A，B，C三點分別代入上式會得到一個有唯一解的三元一次方程，從而 即可確定，但求起來比較麻煩。012aaa， ，0111)B)( )yyyP x0因為點A(x ， (x，滿足方程，故可設2101( )( )()()P xP xa xxxx，即01201010110( )()()xxxxP xyya xxxxxxxxa其中 為待定常數(shù)。2002112222()()()( )P xyP xyP xyaP x由上式不難看出，。若再用條件，就可求出常數(shù) ，從而求得的表達式。0201122012010210122021()()()()()()( )()()()()()()x x x xx

5、 x x xx x x xP xyyyx x x xx x x xx x x x20100202012001011021( )+ ()()yyyyxxxxxxxxP xyxxxxxxxxxx稍加整理即得拋物插值公式。解:用線形插值求解問題1）00111001012111xyxy取，；，可求得115 121115 1001151011 10.71428100 121121 100與所求平方根的實際值10.72387比較，得到了具有三位有效數(shù)字的結果10.71428 。用拋物插值求解問題2） 001122100101211114412xyxyxy取，；，；，可求得17443590115101112

6、10.722755519244831012與平方根實際值10.7238比較，10.72275551具有四位有效數(shù)字，顯然比線形插值的結果好。一般地說，拋物插值比線形插值近似程度要好些。 ( )yf x( )0,1,iiyf xin( )nP x( )nP x( )niiP xy0,1,in3.( )ix插值基函數(shù)的特點，帶入插值節(jié)點時有：1xn.每一項都是關于 的 次多項式；21n.每個多項式有項；1()0ijjijxx- xij，故，應該有一些(的連乘積，()0jijx ijx以保證對于任意的 （），有，( )ix且還應該有自己的系數(shù)。0( )( )( )( )nniiiiinn+1Pxx

7、yx yPx所以估計有個節(jié)點的一般形式的代數(shù)插值多項式應形如：，只要求出的表達形式也就求出了。0000( )(0,1,)n( )()1( )00,1,nijiP xy inxxxin為了構造滿足要求的多項式，我們先來解決一個簡單問題：求一個 次多項式，使之滿足條件，從而可設0001( )niixaxxa（， 為待定常數(shù)。00()1x再由，可求得10011()()nniiiiaxxxx111()0( )10,2,ixxinn同理可作出滿足條件，的 次多項式為( )1()00,1,1,1,iiijxxjiinn一般地可作出滿足條件，的 次多項式為1110011( )()()nniiiiiixxxx

8、x100( )()()nniijjjjj ij ixxxxx3.3.拉格朗日插值公式：拉格朗日插值公式：010,1,1( )( )( )( )0,1,nniiinnxxxP xyin取便得到個多項式，。以這些多項式為基礎，容易看出要構造滿足條件，的多項式，只需取00( )nnjniijijj ixxP xyxx 這就是所要求的插值多項式，稱為拉格朗日（拉格朗日（Lagrange）插值多項式插值多項式。當n=1時，就得出線形插值多項式線形插值多項式， n=2時，就得出拋物插值多項式拋物插值多項式。 （1 1）流程圖：）流程圖：（2 2）算法功能：）算法功能：用Lagrange插值公式，對給定的n

9、組 數(shù)據(jù)進行插值計算。（3 3）算法簡介：）算法簡介：121122,(),(),()nnnnx xxyf xyf xyf xxf(x)對給定的 個插值節(jié)點及其對應的函數(shù)值使用拉格朗日插值公式，計算在 點處對應的函數(shù)值。,11( )( )( )nnikn kn kkikii kxxyf xy LxLxxx，其中，12,nnx xx個元素的一維實數(shù)組，存放給指定的插值節(jié)點。（5 5）程序使用說明）程序使用說明：12,nnyy個元素的一維實數(shù)組，存放與插值節(jié)點相對應的函數(shù)值y。n整型量，給定插值節(jié)點的個數(shù)。X實型量，插值點。輸出參數(shù)： y 實型指針，接受調用程序傳送的一個實型量的地址，在程序結束時，

10、該實型量返回計算結果。注：注：該實型量中原有內容將被破壞。( )( )nP xf x用近似代替，存在誤差。( )( )( )( )nnnR xf xP xP x記：，稱為插值多項式的余項。2.2.誤差估計：誤差估計：01011,min(,)max(,( )( )( )()1)!nnk=nn0nnfR xxnxxx- xxx xxx xx對于給定的插值點 有，其中 ( )=（） ， 是與 有關的點，它位于與之間。xx)()()()(),()()()()(xxpxfxtxtptftnn當 為節(jié)點時，兩邊皆為0，顯然成立。下設 不為節(jié)點。作輔助函數(shù)即使在這些點之間存在一點依次類推使個點個點之間存在在

11、這個點處使在這個點個點之間存在在這再按羅爾定理使個之間存在個點在故按羅爾定理顯然, 0)(,; 0,1; 0,1,0)()()(,1,2,0)()()()()1(10101010 nnnnnnnnnnnxxxxnxxxx0)()()()()1()1()1(nnnnxpf(1)(1)( ),( )0; ( )1,( )(1)!nnnnp ttnptttntn注意為 的 次多項式 必有為 的次多項式 必有；可知上式可化為(1)( )( )( )(1)!0( )nnf xpxfnx111|( ) |( ) |( ) |(1)!nnnnfxmMRxxn根據(jù)余項公式，若能估計出的上界，那么將有即即 問題

12、得證。問題得證。這個定理所講的余項用起來有一定的困難 ，因為實際計算時，只是給出 的一張數(shù)據(jù)表，并未給出具體的解析式子，故 并不知道，所以 也就無法得到。 ( )f x( )f x1( )nf12| ( )|()()()(),0nif xMx-xx-xx-xx-xxxx那么提供的上界 這項要求顯然是不切實際。但此結論在理論上有它的一定價值。其價值在于給出了余項的表達式，可以觀察到，余項里含有因子，故當插值點 離插值節(jié)點 比較遠時，效果可能較差若點 位于插值區(qū)間內，插值過程稱為內插否則成為外推，一般說來，外推比內插效果差。012011,( )x x xx xf xz僅以三個插值節(jié)點的情形為例。我

13、們先用作線性插值，求出的一個近似值，記為 。011010110 xxxxzyyxxxx02xx然后取 和 再求得一個結果：022020220 xxxxzyyxxxx1101()( )()()2!ff xzxxxx2202()( )()()2!ff xzxxxx2( )()fxff1假定在插值區(qū)間內改變不大，將上面兩個式子相除。消去近似相等的 (與，結果有1122( )( )f xzxxf xzxx111212( )()xxf xzzzxx( )( )nP xf x插值函數(shù)和函數(shù)的誤差可以通過兩個插值函數(shù)之差來估計。這種用計算的結果來估計誤差的辦法，通常稱為事后估計，在計算中是常用的，這種估計誤

14、差的方法，將貫穿我們計算方法這門課程的始終。 0101( )xxxf xe令，寫出的一次插值多項式，并估計插例：值誤差。10101(0)1,(1)xxffe解：記，；01( )xf xexx則以 ，為插值節(jié)點的一次插值多項式為1101101011010( )11 (1)0 11 0 xxxxxxP xyyeexxxxx ( )( )xxfxefxe 因為，所以誤差為1111( )( ) (0) (1)822411R xfxxx 11, )251 (1)(2xxxf取等矩節(jié)點 ，作拉格朗日插值多項式 。當 時，函數(shù) 及插值多項式 的圖形如下所示。由圖可見，在區(qū)間-0.2，0.2上 比較接近 ,但

15、在區(qū)間-1，1兩端則誤差很大。當 增大時，部分區(qū)間上插值多項式截斷誤差偏大的現(xiàn)象更重。這種現(xiàn)象稱龍格現(xiàn)象龍格現(xiàn)象。), 1 , 0(/21ninixi( )nP x10n)(xfy 10( )yPx10( )Px)(xfn-11x0.51.01.5y0龍格現(xiàn)象7n解決方法：分段插值01nxxxn應用低階插值的關鍵是恰當?shù)靥暨x插值結點。余項公式說明，選取的結點 離插值點 越近，誤差 就越小，因而插值效果也就越好。因此，應當盡量在插值點的鄰近選取插值結點。 kxx|nR2.分段插值：把整個插值區(qū)間分成若干個小區(qū)間，在每 個小區(qū)間上進行低次插值。 以三個節(jié)點為例，公式為：11111111111111

16、()()()()()()()()()()()()iiiiiiiiiiiiiiiiiiiiixxxxxxxxy=yyxxxxxxxxxxxxyxxxx1x0 x0y1ynynx01nxxxixxf(x)若計算處的近似值1111,i-1iiiiixxxxxxx（）選取節(jié)點與，使，然后在小區(qū)間上作線性插值。11111( )( )iiiiiiiixxxxf xP xyyxxxx稱為分段線性插值-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81112iiixxxx（ ）選取距點 最近的三個節(jié)點， ，作二次插值11211( )( )()iijkk ij ikjj k

17、xxf xP xyxx 稱為分段拋物插值，其節(jié)點的選取方法為：011111111|12,3,2kkkkkkkknnxxxkxxxxxxxikxxxxxxxnxxxkn，且，且。011,nxxx01,nxxx且1()()() , 1,niniiNxNxf xin110( )()()nnnqxaxxxx同樣01 ( )()()nnnqxaxxxx1( )( )( )nnnNxNxqx承襲性承襲性：11( )( )( )nnnNxNxqx1nP為實數(shù)01001 ( )()()()nnnNxaa xxaxxxx而且有：0001011012012022021201001( )( )( )()( )( )

18、()()()( )( )()()()( )nnnnnnnnnnnN xaf xN xaa xxf xN xaa xxa xxxxf xN xaa xxa xxxxf x這樣：00()af x10110()()f xf xaxx20212120()()1f xf xaaxxxx30312323010()()11f xf xaaaxxxxxx10011010100( )(), ,kkkkf xf xf x xxxf xxf xxf xxxx稱為k階差商稱為1階差商定義：差商差商00()af x1010110( )(),f xf xaf x xxx20212120201021021()()11 ,

19、,f xf xaaxxxxf xxf x xf xx xxx由歸納：0,nnaf xx此處用到差商的一個性質： （用歸納法易證） 對稱性：00,kkiif xxf xx定義關鍵：找不同的元素相減作分母0,0,kiik是的任意排列00,()xf x11,( )xf x22,()xf x,()nnxf x01,f x x21,f x x1,nnf xx210,f x x x12,nnnf xxx0,nf xx1、先構造差商表2點Newton型插值1010010()()( )()()f xf xN xf xxxxx2、利用差商表的最外一行，構造插值多項式0010001( )(),(),()()nnn

20、Nxf xf x xxxf xxxxxx00011 ( )( ) ( ) ,()()( )()nnnniniiiiiiinNxL xxf xf xxxxxxxxxx的系數(shù)一樣性質2誤差00100100 Newton( ) ( )( ), ()() ( )( )( )( ), ()()niinniinnnnnnnnxNxxaNtN tf xx a txtxNaf af aN af xx a axax另一方面設插值為則有為顯然10(),(1 ) !nnffxxan性質310( ) ( ) ( )()()(1)!nnnnfN xR xxxxxn同樣的誤差為00011( ),()()()()ninii

21、iiiiinf xf xxxxxxxxxx00,nniif xxf xx0( ),( )!nnff xxn0,( )( ), ,0,nnka knf xPxf xxkn推論：若什么是樣條什么是樣條: : 是 指飛機或輪船等的制造過程中為描繪出光滑的外形曲線(放樣)所用的工具樣條本質上是一段一段的三次多項式拼合而成的曲線在拼接處,不僅函數(shù)是連續(xù)的,且一階和二階導數(shù)也是連續(xù)的1946年,Schoenberg將樣條引入數(shù)學,即所謂的樣條函數(shù)一、三次樣條插值函數(shù)定義1. 01, , nax xxba b為區(qū)間的一個分割( ) , :S xa b如果函數(shù)在區(qū)間上滿足條件(1)( ),( ),( ) ,

22、S x S x Sxa b都在區(qū)間上連續(xù)1(2)( ),kkS xxx在每個小區(qū)間上都是三次多項式( ) , S xa b則稱為區(qū)間上的三次樣條函數(shù)01(3)( ),nf xx xx如果函數(shù)在節(jié)點處的函數(shù)值為(),0,1,jjf xyjn( )S x而三次樣條函數(shù)滿足(),0,1,jjS xyjn( )( ) , S xf xa b則稱為在上的三次樣條插值函數(shù)-(1)二、三次樣條插值多項式01( ),nf xx xx如果函數(shù)在節(jié)點處的函數(shù)值為(),0,1,jjf xyjn01, , nax xxba b為區(qū)間的一個分割( )( ),S xf x如果是的三次樣條插值函數(shù) 則其必滿足(),1jjS

23、 xyjk klim( )(),1,1jjjxxS xS xmjnlim( )(),1,1jjxxSxSxjnlim( )(),1,1jjjxxS xS xyjn-(2)( )(42)S xn要滿足上述四組 共個 條件( ) , ,S xa b在上必然是分段函數(shù) 即00111211( ),( ) ,( ),nnnSxxx xS xxx xSxxxx( )S x1( ),(),kkkSxx x是上的 兩點 三次樣條插值多項式 滿足()kjjSxy1lim( )lim( )kkkkxxxxSxSx1lim( )lim( )kkkkxxxxSxSx1lim( )lim( )kkkkxxxxSxSx1

24、,2,1kn42n共個條件,1jk k-(3)-(4)1( ),4kkkSxxx是上的三次樣條插值多項式 應有 個待定的系數(shù)( )4S xn即要確定必須確定個待定的系數(shù)少兩個條件少兩個條件并且我們不能只對插值函數(shù)在中間節(jié)點的狀態(tài)進行限制也要對插值多項式在兩端點的狀態(tài)加以要求也就是所謂的邊界條件:第一類(一階)邊界條件:00()S xf()nnS xf第二類(二階)邊界條件00()Sxf()nnS xf第三類(周期)邊界條件0( )( )01lim( )lim( )nppnxxxxSxSx1,2p -(5)-(6)-(7)加上任何一類邊界條件(至少兩個)后( )44S xnn確定必須確定個待定的

25、系數(shù)的條件正好也是個一般使用第一、二類邊界條件,即()kjjSxy1lim( )lim( )kkkkxxxxSxSx1lim( )lim( )kkkkkxxxxSxSxm1lim( )lim( )kkkkxxxxSxSx1,2,1kn0,1,jn1,2,1kn1,2,1kn00()S xf()nnS xf-(8)00()Sxf()nnS xf或常用第二類邊界條件(),0,1,jjS xmjn設1( ),( )kkkf xx xSx逐個求在小區(qū)間上的三次插值多項式1( ),kkkSxxxHermite將表示為上的兩點三次插值多項式( )kSx( )( )( )( )( )3011011( )(

26、)( )( )( )kkkkkkkkkHxyxyxmxmx11112kkkkxxyxx21kkkxxxxkkmxx211kkkxxxx21kkkxxxx11kkmxx112kkkkxxyxx211kkkxxxx-(9)2132()( )()kkkkkkhxxSxxxyh21132()()kkkkkhxxxxyh212()()kkkkxxxxmh2112()()kkkkxxxxmh加以整理后可得( ),kSx對求二階導數(shù) 并整理后得1136(2 )( )()kkkkkkxxxSxyyh12624kkkkxxxmh112642kkkkxxxmh-(10)-(11)10,1,1kkkhxxkn令，1

27、lim( )lim( )kkkkxxxxSxSx1,2,1kn由條件lim( )kkxxSx126()kkkyyh4kkmh12kkmh1lim( )kkxxSx1216()kkkyyh112kkmh14kkmh由于以上兩式相等,得111111112()kkkkkkkmmmhhhh112213()kkkkkkyyyyhh1,1kn1,1nn共個個方程個未知量111,kkhh用除上式的兩邊 并加以整理 得112kkkkkmmmkg1kkkkhhh11kkkkhhh1113()kkkkkkkkkyyyyghh1,1kn-(12)1,1kn1,1nn共個個方程個未知量(12)式稱為基本方程組如果問題要求滿足第一類(一階)邊界條件:00()S xf()nnS xf-(5)00mf nnmf -(5)基本方程組(12)化為n-1階方程組1121102mmgf112kkkkkkmmmg2,3,2kn121112nnnnnnmmgf-(13)即將(13)式化為矩陣形式122334221222222nnn12321nnmmmmm11023211nnnngfggggf-(14)這是一個三對角方程組如果問題要求滿足第二類(二階自然)邊界條件:00()Sxf(