1、計 算 方 法,華中科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,第四章 插值方法,計算方法課程組,4 插值方法,4.1多項式插值問題的一般提法,4.2 拉格朗日(Lagrange)插值,4.3 差商與差分及其性質(zhì),4.4 牛頓插值公式,4.5 分段插值法,4.6曲線擬合的最小二乘法,4.0 引言,插值法是廣泛應(yīng)用于理論研究和生產(chǎn)實踐的重 要數(shù)值方法, 它是用簡單函數(shù)(特別是多項式或分 段多項式)為各種離散數(shù)組建立連續(xù)模型；為各種 非有理函數(shù)提供好的逼近方法。眾所周知，反映 自然規(guī)律的數(shù)量關(guān)系的函數(shù)有三種表示方法：,解析表達式,圖象法,表格法,4.0 引言,許多數(shù)據(jù)都是用表格法給出的(如觀測和實驗而得到的函數(shù)數(shù)據(jù)表

2、格)，可是，從一個只提供離散的函數(shù)值去進行理論分析和進行設(shè)計，是極不方便的, 甚至是不可能的。因此需要設(shè)法去尋找與已知函數(shù)值相符，并且形式簡單的插值函數(shù)(或近似函數(shù))。,另外一種情況是，函數(shù)表達式完全給定，但其形式不適宜計算機使用，因為計算機只能執(zhí)行算術(shù)和邏輯操作，因此涉及連續(xù)變量問題的計算都需要經(jīng)過離散化以后才能進行。如數(shù)值積分方法、數(shù)值微分方法、差分方程以及有限元法等，都必須直接或間接地應(yīng)用到插值理論和方法。,4.1 多項式插值問題的一般提法,當(dāng)精確函數(shù) y = f (x) 非常復(fù)雜或未知時，在一系列節(jié)點 x0 xn 處測得函數(shù)值 y0 = f (x0) , , yn = f (xn)，

3、由此構(gòu)造一個簡單易算的近似函數(shù) p(x) f(x)，滿足條件: p(xi) = f(xi) (i = 0, n)。 這里的 p(x) 稱為f(x) 的插值函數(shù)。,最常用的插值函數(shù)是 ? 代數(shù)多項式、三角多項式、有理分式,插值函數(shù) p (x) 作為 f (x) 的近似，可以選自不同類型的 函數(shù), 如 p (x) 為代數(shù)多項式、三角多項式、有理分式； 其函數(shù)性態(tài)可以是光滑的、亦可以是分段光滑的。其 中，代數(shù)多項式類的插值函數(shù)占有重要地位：,(a) 結(jié)構(gòu)簡單、計算機容易處理、任何多項式的導(dǎo)數(shù)和積分也易確定，并且仍是多項式。,(b) 著名的Weierstrass逼近定理(定義在閉區(qū)間上的 任何連續(xù)函數(shù)

4、 f(x) , 存在代數(shù)多項式p(x)一致逼近f(x), 并達到所要求的精度)。,因此，我們主要考慮代數(shù)多項式的插值問題。,x0 , x1, , xn 插值節(jié)點,函數(shù) P(x) 稱為函數(shù) y=f(x) 的插值函數(shù)， 區(qū)間 a, b 稱為插值區(qū)間。,例題:,已知函數(shù) f(x) 有如下數(shù)據(jù):,求 f(x) 的插值多項式 p(x)， 并求 f(x) 在 x=0.5 處的近似值。,插值的幾何意義,從幾何上看，插值就是求一條曲線 使其通過給定的 個點 ， 并且與已知曲線 有一定的近似度。,從幾何上看,曲線 P ( x) 近似 f ( x),插值方法的研究問題,曲線 P ( x) 近似 f ( x),求

5、n 次多項式 使得:,條件：無重合節(jié)點，即,4.2 拉格朗日多項式 /* Lagrange Polynomial */,Vandermonde行列式,注意到插值節(jié)點,兩兩相異，而,故方程組(1)有惟一解,于是滿足插值條件的多項式存在且惟一。,(唯一性),Return,n = 1,已知 x0 , x1 ; y0 , y1 ，求,使得,1,1,1,0,0,1,),(,),(,y1,x1,L,y0,x0,L,=,=,可見 L1(x) 是過 ( x0 , y0 ) 和 ( x1, y1 ) 兩點的直線。,4.2 拉格朗日多項式 /* Lagrange Polynomial */,線性插值基函數(shù),1.

6、構(gòu)造線性插值基函數(shù)的方法:,線性插值與其基函數(shù)示意圖,顯然, 是過 、 、 三點的一條拋物線。,已知 , 求 ，,n = 2,使得,顯然, 是過 、 、 三點的一條拋物線。,已知 , 求 ，,n = 2,使得,拋物線插值基函數(shù),于是,拋物線基函數(shù),希望找到 li (x)，i = 0, , n 使得 li (xj) = ij ；然后令,，則顯然有 Pn(xi) = yi 。,每個 li 有 n 個根 x0 , xi , xn,， k = 0, 1 , n .,k = 0, 1 , n .,由 得:,設(shè) 函數(shù)表 則滿足插值條件的多項式,（Lagrange）插值多項式,其中, .,以下的問題：如何分

7、析插值的余項？,(1) 先求插值基函數(shù). (2) 構(gòu)造插值多項式.,構(gòu)造插值多項式的方法：,已知連續(xù)函數(shù) f (x) 的函數(shù)表如下：,求方程 f (x)=0 在(-1,2)內(nèi)的近似根。,例題,解：利用Lagrange插值法有,取初值x=0.5，利用牛頓法求解可得 f (x) 在(-1,2)內(nèi)的近似根 為0.67433。,解方程,已知連續(xù)函數(shù)f (x)的函數(shù)表如下：,求方程 f (x)=0 在(-1,2)內(nèi)的近似根。,例題,，且 f 滿足條件 , Lagrange插值法插值余項,設(shè)節(jié)點,在a , b內(nèi)存在, 考察截斷誤差:, Lagrange插值法的插值余項, Lagrange插值法的插值余項,

8、證明：由已知條件得到：,于是有：,其中 是與 x 有關(guān)的待定函數(shù)。,故,處均為零，,在,上有n+2個個零點，根據(jù) Roll 定理,在 的每兩個零點間至少有一個零點，故 在 內(nèi)至少有 一 個零點，對 再用Roll 定理，可知 在 內(nèi)至少有 n 個零點，依此類推， 在 內(nèi)至少有一個零點，記為,使得:,由于 是不能確定，因此我們并不能確定誤差的大小 但如能求出 ，那么用 逼近 的截斷誤差限是： 當(dāng) 時， 當(dāng) 時,當(dāng) f (x) 為任一個次數(shù) n 的多項式時， , 可知， 即插值多項式對于次數(shù) n 的多項式是精確的。,注意,給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪

9、個是 l2(x) 的圖像？,問題,算例1,Lagrange插值法,已知 ， ， 用線性插值及拋物線插值計算 的值并估計截斷誤差。,算例1,Lagrange插值法,已知 ， ， 用線性插值及拋物線插值計算 的值并估計截斷誤差。,線性插值時取,解:,其截斷誤差為： 其中, 因為 可取 于是：,用拋物線插值時，取所有節(jié)點，得到,余項討論： 其中：,算例2,Lagrange插值法,利用 100，121 的開方計算 .,由于:,解:,利用Lagrange插值法有,于是,的精確值為 10.72380529, 因此, 近似值 10.71428 有3 位有效數(shù)字.,Return,4.3 差商與差分,Lagra

10、nge 插值雖然易算，但若要增加一個節(jié)點時， 全部基函數(shù) li (x) 都需重新算過。,由線性代數(shù)的知識可知：任何一個n次多項式都可以表示成,共 n+1 個線性無關(guān)的多項式的線性組合。,那么，是否可以將這 n+1 個多項式作為插值基函數(shù)呢？,設(shè)插值多項式P(x)具有如下形式：,再繼續(xù)下去,待定系數(shù)的形式將更復(fù)雜,為此引入 差商和差分的概念.,P(x)應(yīng)滿足插值條件：,有：,4.3.1 差商的概念,從零階差商出發(fā)，歸納地定義各階差商:,稱 為函數(shù) 關(guān)于點 的一階差商.,一般地， 關(guān)于 的 k 階差商:,記函數(shù) 在 的值 ， 稱 為 關(guān)于 的零階差商。,一般地， 關(guān)于 的 n 階差商:,n 階差商

11、的概念,差商的基本性質(zhì),性質(zhì)1：差商可表示為函數(shù)值的線性組合，即： 性質(zhì)2：差商關(guān)于所含節(jié)點是對稱的，即：,可用歸納法證明,差商的基本性質(zhì),性質(zhì)3： 性質(zhì)4：設(shè) 在 存在 n 階導(dǎo)數(shù)，且 則 ，使得:,差商的計算-差商表,已知,計算三階差商,解：列表計算,算例,4.3.2 差分,在前面的討論中，節(jié)點是任意分布的，但實際上經(jīng)常遇 到等距節(jié)點的情況，這時插值公式可以得到簡化，為此，我 們先介紹差分的概念。 設(shè)函數(shù) 在等距節(jié)點 上的值 為已知，這里 為常數(shù)，稱為步長。,下面來討論差分的定義。,差分的定義,記號 分別稱為 在 處以 為步長的 向前差分、向后差分、中心差分 符號 、 、 分別稱為向前差分

12、算子、向后差分算子、 中心差分算子.,高階差分,用一階差分可以定義二階差分 一般地可定義 m 階差分為： 中心差分定義為: 以此類推。,不變算子 I、移位算子 E,定義 從而可得： 于是得到： 同理，由于： 得到： 由于： 得到： 由差分的定義及不變算子和移位算子有如下性質(zhì):,差分的性質(zhì),性質(zhì)1：各階差分均可用函數(shù)值表示，如： 性質(zhì)2：某點的函數(shù)可用各階差分來表示：,性質(zhì)3：差商與差分有如下關(guān)系： 性質(zhì)4：差分與導(dǎo)數(shù)有如下關(guān)系：,差分的計算,Return,4.4 牛頓插值公式,根據(jù)差商的定義，把 看成 上的一點， 可得：,4.4 牛頓插值公式,根據(jù)差商的定義，把 看成 上的一點， 可得：,把后

13、一式代入前一式,其中 顯然 滿足插值條件，且次數(shù)不超過 ,它就 是插值多項式，其系數(shù)為： 我們稱 為牛頓插值多項式.,從表中可以看到4 階差商幾乎為0，故取4次插值多項式即可， 于是：,解：列表計算,已知 的函數(shù)表，求4 次牛頓插值多項式, 并求,算例,解：列表計算,已知 的函數(shù)表，求4 次牛頓插值多項式, 并求,算例,截斷誤差為：,和 均是 n 次多項式,且均滿足插值條件: 由多項式的唯一性, ,因而,兩個公式 的余項是相等的,即 當(dāng)插值多項式從 n-1 次增加到 n 次時, 拉格朗日型插值必須重新計算所有的基本插值多項式; 而對于牛頓型插值,只需用表格再計算一個 n 階差商, 然后加上一項

14、即可。,牛頓插值公式和Lagrange插值公式比較,Return,4.5 分段插值公式,在區(qū)間 a, b 上用插值多項式 P 逼近函數(shù) f 時，f 和P 在每個節(jié)點上的差異(理論上)應(yīng)該為零。自然，我們期望 在一切中間點上也能很好地逼近 f ，并且當(dāng)插值點增加時 這種逼近效果應(yīng)該越來越好。 但上述的期望不可能實現(xiàn)的。當(dāng)認(rèn)識到這一點時，在數(shù) 學(xué)界曾引起強烈的震動。,20 世紀(jì)初，Runge就給出了一個等距節(jié)點插值多項式 不收斂到 的例子。,設(shè)函數(shù) ， 在該區(qū)間 上取 個等距節(jié)點, 構(gòu)造 的 次 拉格朗日插值多項式為,其matlab的lagrange.m文件及相關(guān)圖形如下.,Runge 現(xiàn)象,%

15、lagrange.m function y=lagrange (x0,y0,x) n=length(x0);m=length(x); for i=1:m z=x(i);s=0; for k=1:n L=1; for j=1:n if j=k L=L*(z-x0(j)/(x0(k)-x0(j); end end s=s+L*y0(k); end y(i)=s; end y;,Lagrange插值多項式 求插值的Matlab程序.,%Compare_Runge.m x=-5:0.1:5;z=0*x;y=1./(1+x.2); plot(x,z,k,x,y,r) axis(-5 5 -1.5 2);

16、pause,hold on for n=2:2:20 x0=linspace(-5,5,n+1); y0=1./(1+x0.2); x=-5:0.1:5; y1=lagrange(x0,y0,x); plot(x,y1), pause end y2=1./(1+x0.2);y=interp1(x0,y2,x); plot (x,y,k),hold off gtext(n=2),gtext(n=4),gtext(n=6) gtext(n=8),gtext(n=10) gtext(f(x)=1/(1+x2),比較不同的插值多項式次數(shù)對插值的影響,不同次數(shù)的Lagrange插值多項式的比較圖,Run

17、ge現(xiàn)象,令 ，則 ， 下表列出了 和 的值。,結(jié)果表明,隨著 的增加， 的絕對值幾乎成倍地增加，這說明當(dāng) 時 在 上不收斂。 Runge證明了，存在一個常數(shù) , 使得當(dāng) 時， ; 而當(dāng) 時 發(fā)散。 說明: 并不是插值多項式的次數(shù)越高, 插值效果越好, 精度也不一定是隨次數(shù)的提高而升高, 這種現(xiàn)象在上個世紀(jì)初由Runge發(fā)現(xiàn), 故稱為Runge現(xiàn)象.,分段線性插值特別簡單，從幾何上看，就是用折線逼近 曲線。 分段線性插值的數(shù)學(xué)定義 設(shè) 是區(qū)間 上的函數(shù)，在節(jié)點 上的函數(shù)值為 ， 求一分段折線函數(shù) 滿足： （1） （2） 在 上， 是一次多項式。 （3） 則稱 為 的分段線性插值函數(shù)。,4.5.

18、1 分段線性插值,易知, P(x) 是個折線函數(shù)，在每個區(qū)間,上,有,在 a,b 上是連續(xù)的，但其一階導(dǎo)數(shù)是不連續(xù)的.,當(dāng) 時,當(dāng) 時,4.5.1 分段線性插值的基函數(shù),當(dāng) 時,顯然 是 的線性組合： 在區(qū)間 上的值為：,，,算例,解: 在每個分段區(qū)間,于是，,實際值:,當(dāng)n=7 時， P(4.5)=0.04762270321996 ; 當(dāng)n=10時，P(4.5)=0.04705882352941 由此可見，對于光滑性要求不高的插值問題，分段線性插值的 效果非常好！計算也簡單!,4.5.2 埃爾米特 (Hermite) 插值,拉格朗日和牛頓均只保證函數(shù)插值； 實際問題有時需要導(dǎo)數(shù)也插值； 滿足

19、這種需要的插值稱為埃爾米特插值.,埃爾米特插值的一般提法為： 設(shè)函數(shù)在節(jié)點 的函數(shù)值與導(dǎo)數(shù)值為： 其中 是正整數(shù)，尋求一個次數(shù)盡可能低的多 項式 ，滿足：,埃爾米特插值的一般提法,以如下數(shù)據(jù)構(gòu)建埃爾米特插值,埃爾米特插值,算例,以如下數(shù)據(jù)構(gòu)建埃爾米特插值,埃爾米特插值,算例,共有 個條件，可唯一確定一個次數(shù)不超過 的多項式 ，其形式為： 目標(biāo)：求出所有的 , 方法：基函數(shù)法.,這樣 可表示為：,顯然有：,現(xiàn)在求 及 ， 令 其中 從而有： 由此得： ， 故： ，,由 的表達式可得： 于是得到： 同理可得,解：,n = 1,分別利用x0, x1 以及 x1, x2 計算,利用,這里,而,sin

20、50 = 0.7660444,外推 /* extrapolation */ 的實際誤差 0.01001,利用,內(nèi)插 /* interpolation */ 的實際誤差 0.00596,內(nèi)插通常優(yōu)于外推。選擇要計算的 x 所在的區(qū)間的端點，插值效果較好。,n = 2,sin 50 = 0.7660444,2次插值的實際誤差 0.00061,高次插值通常優(yōu)于低次插值,Return,巴爾末(J.J.Balmer，1825-1898),特殊愛好: 數(shù)字游戲,職 業(yè): 數(shù)學(xué)教師，瑞士某女子中學(xué)，,兼巴塞爾大學(xué)無薪講師,“我能用公式把任意4個數(shù)字有規(guī)律地聯(lián)系起來”,4 Why?,信息量?,道家: 1生2，2生3，3生萬物,4 萬物？全部信息量?!,4 條譜線的波長數(shù)據(jù),實驗: 氫光譜譜線的波長數(shù)據(jù),巴爾末公式:,艱苦努力+天才,引子,1884年,4.6 曲線擬合的最小二乘法,物理實驗,實驗數(shù)據(jù),經(jīng)驗公式,天才,數(shù)學(xué): 一般方法？,引子(續(xù)）,問題,已知:,求 :,特點,實驗數(shù)據(jù),n 1,實驗值 yi 有誤差，個別點可能誤差還比較大。,方法:,多項式插值,點點通過,高次插值效果不好