計算方法第四章插值方法演示

（優(yōu)選）計算方法第四章插值方法課件目前一頁\總數(shù)八十九頁\編于九點(diǎn)§4插值方法§4.1多項式插值問題的一般提法§4.2

拉格朗日(Lagrange)插值§4.3

差商與差分及其性質(zhì)§4.4

牛頓插值公式

§4.5

分段插值法§4.6曲線擬合的最小二乘法目前二頁\總數(shù)八十九頁\編于九點(diǎn)§4.0引言

插值法是廣泛應(yīng)用于理論研究和生產(chǎn)實踐的重要數(shù)值方法,它是用簡單函數(shù)(特別是多項式或分段多項式)為各種離散數(shù)組建立連續(xù)模型；為各種非有理函數(shù)提供好的逼近方法。眾所周知，反映自然規(guī)律的數(shù)量關(guān)系的函數(shù)有三種表示方法：

解析表達(dá)式

圖象法

表格法目前三頁\總數(shù)八十九頁\編于九點(diǎn)§4.0引言

許多數(shù)據(jù)都是用表格法給出的(如觀測和實驗而得到的函數(shù)數(shù)據(jù)表格)，可是，從一個只提供離散的函數(shù)值去進(jìn)行理論分析和進(jìn)行設(shè)計，是極不方便的,甚至是不可能的。因此需要設(shè)法去尋找與已知函數(shù)值相符，并且形式簡單的插值函數(shù)(或近似函數(shù))。另外一種情況是，函數(shù)表達(dá)式完全給定，但其形式不適宜計算機(jī)使用，因為計算機(jī)只能執(zhí)行算術(shù)和邏輯操作，因此涉及連續(xù)變量問題的計算都需要經(jīng)過離散化以后才能進(jìn)行。如數(shù)值積分方法、數(shù)值微分方法、差分方程以及有限元法等，都必須直接或間接地應(yīng)用到插值理論和方法。目前四頁\總數(shù)八十九頁\編于九點(diǎn)§4.1多項式插值問題的一般提法

當(dāng)精確函數(shù)y=f(x)非常復(fù)雜或未知時，在一系列節(jié)點(diǎn)x0…xn

處測得函數(shù)值

y0

=f(x0),…,yn

=f(xn)，

由此構(gòu)造一個簡單易算的近似函數(shù)

p(x)f(x)，滿足條件:p(xi)=f(xi)(i=0,…n)。

這里的p(x)稱為f(x)的插值函數(shù)。最常用的插值函數(shù)是…?

代數(shù)多項式、三角多項式、有理分式…目前五頁\總數(shù)八十九頁\編于九點(diǎn)

插值函數(shù)p(x)作為f(x)的近似，可以選自不同類型的函數(shù),如p(x)為代數(shù)多項式、三角多項式、有理分式；其函數(shù)性態(tài)可以是光滑的、亦可以是分段光滑的。其中，代數(shù)多項式類的插值函數(shù)占有重要地位：

(a)

結(jié)構(gòu)簡單、計算機(jī)容易處理、任何多項式的導(dǎo)數(shù)和積分也易確定，并且仍是多項式。(b)

著名的Weierstrass逼近定理(定義在閉區(qū)間上的任何連續(xù)函數(shù)f(x),存在代數(shù)多項式p(x)一致逼近f(x),并達(dá)到所要求的精度)。因此，我們主要考慮代數(shù)多項式的插值問題。目前六頁\總數(shù)八十九頁\編于九點(diǎn)x0

,

x1,…,xn插值節(jié)點(diǎn),

函數(shù)P(x)稱為函數(shù)y=f(x)的插值函數(shù)，區(qū)間[a,b]稱為插值區(qū)間。

目前七頁\總數(shù)八十九頁\編于九點(diǎn)例題:已知函數(shù)f(x)有如下數(shù)據(jù):求f(x)的插值多項式p(x)，并求f(x)在x=0.5處的近似值。目前八頁\總數(shù)八十九頁\編于九點(diǎn)目前九頁\總數(shù)八十九頁\編于九點(diǎn)

插值的幾何意義

從幾何上看，插值就是求一條曲線使其通過給定的個點(diǎn)，并且與已知曲線有一定的近似度。從幾何上看x

0y

y=p(x)a=x0x1x2x3xn=b

?(xi,yi)y=f(x)曲線P

(

x)

近似f

(

x)

目前十頁\總數(shù)八十九頁\編于九點(diǎn)插值方法的研究問題（1）滿足插值條件的P

(

x)

是否存在唯一？（2）若滿足插值條件的P

(

x)

存在，如何構(gòu)造P(x)？（3）如何估計用P

(

x)近似替代f

(

x)產(chǎn)生的誤差？x

0y

y=p(x)a=x0x1x2x3xn=b

?(xi,yi)y=f(x)曲線P

(

x)

近似f

(

x)

目前十一頁\總數(shù)八十九頁\編于九點(diǎn)求n

次多項式使得:條件：無重合節(jié)點(diǎn)，即§4.2拉格朗日多項式

/*LagrangePolynomial*/

根據(jù)插值條件，有：其系數(shù)矩陣的行列式為Vandermonde行列式目前十二頁\總數(shù)八十九頁\編于九點(diǎn)注意到插值節(jié)點(diǎn)兩兩相異，而故方程組(1)有惟一解于是滿足插值條件的多項式存在且惟一。由n+1個不同插值節(jié)點(diǎn)可以惟一確定一個n次多項式滿足插值條件(唯一性)Return目前十三頁\總數(shù)八十九頁\編于九點(diǎn)n=1已知x0,x1;

y0,

y1，求使得111001)(,)(y1x1Ly0x0L==可見L1(x)是過(x0,y0)和(x1,y1)兩點(diǎn)的直線。l0(x)l1(x)§4.2拉格朗日多項式

/*LagrangePolynomial*/

線性插值基函數(shù)1.構(gòu)造線性插值基函數(shù)的方法:目前十四頁\總數(shù)八十九頁\編于九點(diǎn)線性插值與其基函數(shù)示意圖目前十五頁\總數(shù)八十九頁\編于九點(diǎn)顯然,是過、、三點(diǎn)的一條拋物線。已知,求，n=2使得目前十六頁\總數(shù)八十九頁\編于九點(diǎn)顯然,是過、、三點(diǎn)的一條拋物線。已知,求，n=2使得仿照線性插值基函數(shù)的構(gòu)造方法，令拋物線基函數(shù)稱其為拋物線插值基函數(shù)(如上右圖所示)。

目前十七頁\總數(shù)八十九頁\編于九點(diǎn)拋物線插值基函數(shù)于是拋物線基函數(shù)目前十八頁\總數(shù)八十九頁\編于九點(diǎn)希望找到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ù)八十九頁\編于九點(diǎn)設(shè)函數(shù)表則滿足插值條件的多項式（Lagrange）插值多項式其中,.目前二十頁\總數(shù)八十九頁\編于九點(diǎn)以下的問題：如何分析插值的余項？

(1)先求插值基函數(shù).

(2)構(gòu)造插值多項式.構(gòu)造插值多項式的方法：目前二十一頁\總數(shù)八十九頁\編于九點(diǎn)x-1

0

1

2f(x)-2

-2

12

已知連續(xù)函數(shù)f(x)的函數(shù)表如下：求方程f(x)=0在(-1,2)內(nèi)的近似根。例題目前二十二頁\總數(shù)八十九頁\編于九點(diǎn)解：利用Lagrange插值法有

取初值x=0.5，利用牛頓法求解可得f(x)在(-1,2)內(nèi)的近似根為0.67433。

解方程x-1

0

1

2f(x)-2

-2

12

已知連續(xù)函數(shù)f(x)的函數(shù)表如下：求方程f(x)=0在(-1,2)內(nèi)的近似根。例題目前二十三頁\總數(shù)八十九頁\編于九點(diǎn)

，且f

滿足條件,

Lagrange插值法插值余項設(shè)節(jié)點(diǎn)在[a,b]內(nèi)存在,考察截斷誤差:目前二十四頁\總數(shù)八十九頁\編于九點(diǎn)Lagrange插值法的插值余項

，且f

滿足條件,設(shè)節(jié)點(diǎn)在[a,b]內(nèi)存在,截斷誤差(或插值余項):目前二十五頁\總數(shù)八十九頁\編于九點(diǎn)Lagrange插值法的插值余項

，且f

滿足條件,設(shè)節(jié)點(diǎn)在[a,b]內(nèi)存在,截斷誤差(或插值余項):證明：由已知條件得到：于是有：其中是與x

有關(guān)的待定函數(shù)。目前二十六頁\總數(shù)八十九頁\編于九點(diǎn)任意固定xxi(i=0,…,n),考察根據(jù)插值條件及余項定義，可知在點(diǎn)故處均為零，在上有n+2個個零點(diǎn)，根據(jù)Roll定理

在的每兩個零點(diǎn)間至少有一個零點(diǎn)，故在內(nèi)至少有一個零點(diǎn)，對再用Roll定理，可知在內(nèi)至少有n

個零點(diǎn)，依此類推，在內(nèi)至少有一個零點(diǎn)，記為使得:目前二十七頁\總數(shù)八十九頁\編于九點(diǎn)由于是不能確定，因此我們并不能確定誤差的大小但如能求出，那么用逼近的截斷誤差限是：當(dāng)時，當(dāng)時目前二十八頁\總數(shù)八十九頁\編于九點(diǎn)當(dāng)

f(x)為任一個次數(shù)n

的多項式時，,可知，即插值多項式對于次數(shù)n的多項式是精確的。注意目前二十九頁\總數(shù)八十九頁\編于九點(diǎn)

給定xi=i+1,i=0,1,2,3,4,5.

下面哪個是l2(x)的圖像？問題目前三十頁\總數(shù)八十九頁\編于九點(diǎn)算例1Lagrange插值法已知，，用線性插值及拋物線插值計算的值并估計截斷誤差。目前三十一頁\總數(shù)八十九頁\編于九點(diǎn)算例1Lagrange插值法已知，，用線性插值及拋物線插值計算的值并估計截斷誤差。線性插值時取

解:目前三十二頁\總數(shù)八十九頁\編于九點(diǎn)其截斷誤差為：其中,因為可取于是：

目前三十三頁\總數(shù)八十九頁\編于九點(diǎn)用拋物線插值時，取所有節(jié)點(diǎn)，得到余項討論：其中：目前三十四頁\總數(shù)八十九頁\編于九點(diǎn)算例2Lagrange插值法利用100，121的開方計算.由于:

解:利用Lagrange插值法有于是,的精確值為10.72380529…,因此,近似值10.71428有3位有效數(shù)字.

Return目前三十五頁\總數(shù)八十九頁\編于九點(diǎn)§4.3差商與差分

Lagrange插值雖然易算，但若要增加一個節(jié)點(diǎn)時，全部基函數(shù)li(x)都需重新算過。尋求如下形式的插值多項式：其中的為待定系數(shù)，由插值條件確定.由線性代數(shù)的知識可知：任何一個n次多項式都可以表示成共n+1個線性無關(guān)的多項式的線性組合。那么，是否可以將這n+1個多項式作為插值基函數(shù)呢？目前三十六頁\總數(shù)八十九頁\編于九點(diǎn)設(shè)插值多項式P(x)具有如下形式：

再繼續(xù)下去,待定系數(shù)的形式將更復(fù)雜,為此引入差商和差分的概念.P(x)應(yīng)滿足插值條件：有：目前三十七頁\總數(shù)八十九頁\編于九點(diǎn)§4.3.1差商的概念從零階差商出發(fā)，歸納地定義各階差商:稱為函數(shù)關(guān)于點(diǎn)的一階差商.

一般地，關(guān)于的k

階差商:記函數(shù)在的值，稱為關(guān)于的零階差商。目前三十八頁\總數(shù)八十九頁\編于九點(diǎn)

一般地，關(guān)于的n階差商:n階差商的概念目前三十九頁\總數(shù)八十九頁\編于九點(diǎn)差商的基本性質(zhì)性質(zhì)1：差商可表示為函數(shù)值的線性組合，即：性質(zhì)2：差商關(guān)于所含節(jié)點(diǎn)是對稱的，即：可用歸納法證明目前四十頁\總數(shù)八十九頁\編于九點(diǎn)差商的基本性質(zhì)性質(zhì)3：性質(zhì)4：設(shè)在存在n階導(dǎo)數(shù)，且則，使得:目前四十一頁\總數(shù)八十九頁\編于九點(diǎn)差商的計算-差商表一階差商二階差商三階差商四階差商目前四十二頁\總數(shù)八十九頁\編于九點(diǎn)已知計算三階差商解：列表計算算例目前四十三頁\總數(shù)八十九頁\編于九點(diǎn)§4.3.2差分

在前面的討論中，節(jié)點(diǎn)是任意分布的，但實際上經(jīng)常遇到等距節(jié)點(diǎn)的情況，這時插值公式可以得到簡化，為此，我們先介紹差分的概念。設(shè)函數(shù)在等距節(jié)點(diǎn)上的值為已知，這里為常數(shù)，稱為步長。

下面來討論差分的定義。目前四十四頁\總數(shù)八十九頁\編于九點(diǎn)差分的定義記號分別稱為在處以為步長的

向前差分、向后差分、中心差分符號、、分別稱為向前差分算子、向后差分算子、中心差分算子.目前四十五頁\總數(shù)八十九頁\編于九點(diǎn)高階差分用一階差分可以定義二階差分一般地可定義m階差分為：中心差分定義為:

以此類推。目前四十六頁\總數(shù)八十九頁\編于九點(diǎn)不變算子I、移位算子E定義從而可得：于是得到：同理，由于：得到：由于：得到：由差分的定義及不變算子和移位算子有如下性質(zhì):

目前四十七頁\總數(shù)八十九頁\編于九點(diǎn)差分的性質(zhì)性質(zhì)1：各階差分均可用函數(shù)值表示，如：性質(zhì)2：某點(diǎn)的函數(shù)可用各階差分來表示：目前四十八頁\總數(shù)八十九頁\編于九點(diǎn)性質(zhì)3：差商與差分有如下關(guān)系：性質(zhì)4：差分與導(dǎo)數(shù)有如下關(guān)系：目前四十九頁\總數(shù)八十九頁\編于九點(diǎn)差分的計算Return目前五十頁\總數(shù)八十九頁\編于九點(diǎn)4.4牛頓插值公式根據(jù)差商的定義，把看成上的一點(diǎn)，可得：目前五十一頁\總數(shù)八十九頁\編于九點(diǎn)4.4牛頓插值公式根據(jù)差商的定義，把看成上的一點(diǎn)，可得：把后一式代入前一式目前五十二頁\總數(shù)八十九頁\編于九點(diǎn)其中

顯然滿足插值條件，且次數(shù)不超過,它就是插值多項式，其系數(shù)為：我們稱為牛頓插值多項式.目前五十三頁\總數(shù)八十九頁\編于九點(diǎn)

已知的函數(shù)表，求4次牛頓插值多項式,

并求算例目前五十四頁\總數(shù)八十九頁\編于九點(diǎn)從表中可以看到4階差商幾乎為0，故取4次插值多項式即可，于是：0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012解：列表計算

已知的函數(shù)表，求4次牛頓插值多項式,

并求算例目前五十五頁\總數(shù)八十九頁\編于九點(diǎn)0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012解：列表計算

已知的函數(shù)表，求4次牛頓插值多項式,

并求算例截斷誤差為：目前五十六頁\總數(shù)八十九頁\編于九點(diǎn)

和均是n次多項式,且均滿足插值條件:

由多項式的唯一性,,因而,兩個公式的余項是相等的,即當(dāng)插值多項式從n-1

次增加到n次時,拉格朗日型插值必須重新計算所有的基本插值多項式;而對于牛頓型插值,只需用表格再計算一個n階差商,然后加上一項即可。牛頓插值公式和Lagrange插值公式比較Return目前五十七頁\總數(shù)八十九頁\編于九點(diǎn)4.5分段插值公式

在區(qū)間[a,b]上用插值多項式P逼近函數(shù)f時，f和P在每個節(jié)點(diǎn)上的差異(理論上)應(yīng)該為零。自然，我們期望在一切中間點(diǎn)上也能很好地逼近f，并且當(dāng)插值點(diǎn)增加時這種逼近效果應(yīng)該越來越好。 但上述的期望不可能實現(xiàn)的。當(dāng)認(rèn)識到這一點(diǎn)時，在數(shù)學(xué)界曾引起強(qiáng)烈的震動。20世紀(jì)初，Runge就給出了一個等距節(jié)點(diǎn)插值多項式不收斂到的例子。目前五十八頁\總數(shù)八十九頁\編于九點(diǎn)

設(shè)函數(shù)，在該區(qū)間上取個等距節(jié)點(diǎn),構(gòu)造的次拉格朗日插值多項式為

其matlab的lagrange.m文件及相關(guān)圖形如下.Runge現(xiàn)象目前五十九頁\總數(shù)八十九頁\編于九點(diǎn)%lagrange.mfunctiony=lagrange(x0,y0,x)n=length(x0);m=length(x);fori=1:mz=x(i);s=0;

fork=1:nL=1;

forj=1:n

ifj~=kL=L*(z-x0(j))/(x0(k)-x0(j));

endend

s=s+L*y0(k);

end

y(i)=s;endy;Lagrange插值多項式求插值的Matlab程序.目前六十頁\總數(shù)八十九頁\編于九點(diǎn)%Compare_Runge.mx=-5:0.1:5;z=0*x;y=1./(1+x.^2);plot(x,z,'k',x,y,'r')axis([-55-1.52]);pause,holdonforn=2:2:20x0=linspace(-5,5,n+1);y0=1./(1+x0.^2);x=-5:0.1:5;y1=lagrange(x0,y0,x);plot(x,y1),pauseendy2=1./(1+x0.^2);y=interp1(x0,y2,x);plot(x,y,'k'),holdoffgtext('n=2'),gtext('n=4'),gtext('n=6')gtext('n=8'),gtext('n=10')gtext('f(x)=1/(1+x^2)')比較不同的插值多項式次數(shù)對插值的影響目前六十一頁\總數(shù)八十九頁\編于九點(diǎn)不同次數(shù)的Lagrange插值多項式的比較圖Runge現(xiàn)象目前六十二頁\總數(shù)八十九頁\編于九點(diǎn)令，則，下表列出了和的值。目前六十三頁\總數(shù)八十九頁\編于九點(diǎn)

結(jié)果表明,隨著的增加，的絕對值幾乎成倍地增加，這說明當(dāng)時在上不收斂。

Runge證明了，存在一個常數(shù),使得當(dāng)時，

;而當(dāng)時發(fā)散。說明:并不是插值多項式的次數(shù)越高,插值效果越好,精度也不一定是隨次數(shù)的提高而升高,這種現(xiàn)象在上個世紀(jì)初由Runge發(fā)現(xiàn),故稱為Runge現(xiàn)象.目前六十四頁\總數(shù)八十九頁\編于九點(diǎn)

分段線性插值特別簡單，從幾何上看，就是用折線逼近曲線。分段線性插值的數(shù)學(xué)定義設(shè)是區(qū)間上的函數(shù)，在節(jié)點(diǎn)上的函數(shù)值為，求一分段折線函數(shù)滿足：（1）（2）在上，是一次多項式。（3）則稱為的分段線性插值函數(shù)。4.5.1分段線性插值目前六十五頁\總數(shù)八十九頁\編于九點(diǎn)易知,P(x)是個折線函數(shù)，在每個區(qū)間上,有在[a,b]上是連續(xù)的，但其一階導(dǎo)數(shù)是不連續(xù)的.目前六十六頁\總數(shù)八十九頁\編于九點(diǎn)

當(dāng)時,

當(dāng)時,4.5.1分段線性插值的基函數(shù)

當(dāng)時,目前六十七頁\總數(shù)八十九頁\編于九點(diǎn)顯然是的線性組合：

在區(qū)間上的值為：，表達(dá)式在區(qū)間上，只有是非零的，其它基函數(shù)均為零。即注意目前六十八頁\總數(shù)八十九頁\編于九點(diǎn)算例節(jié)點(diǎn)（如下表），求區(qū)間上分段線性插值函數(shù)，并利用它求出已知函數(shù)近似值。在區(qū)間[0,5]上取等距插值目前六十九頁\總數(shù)八十九頁\編于九點(diǎn)解:在每個分段區(qū)間于是，實際值:

當(dāng)n=7時，P(4.5)=0.04762270321996;當(dāng)n=10時，P(4.5)=0.04705882352941由此可見，對于光滑性要求不高的插值問題，分段線性插值的效果非常好！計算也簡單!目前七十頁\總數(shù)八十九頁\編于九點(diǎn)4.5.2埃爾米特(Hermite)插值拉格朗日和牛頓均只保證函數(shù)插值；實際問題有時需要導(dǎo)數(shù)也插值；滿足這種需要的插值稱為埃爾米特插值.目前七十一頁\總數(shù)八十九頁\編于九點(diǎn)埃爾米特插值的一般提法為：設(shè)函數(shù)在節(jié)點(diǎn)的函數(shù)值與導(dǎo)數(shù)值為：其中是正整數(shù)，尋求一個次數(shù)盡可能低的多項式，滿足：埃爾米特插值的一般提法目前七十二頁\總數(shù)八十九頁\編于九點(diǎn)

以如下數(shù)據(jù)構(gòu)建埃爾米特插值

埃爾米特插值算例目前七十三頁\總數(shù)八十九頁\編于九點(diǎn)

以如下數(shù)據(jù)構(gòu)建埃爾米特插值

埃爾米特插值算例共有個條件，可唯一確定一個次數(shù)不超過的多項式，其形式為：目標(biāo)：求出所有的,方法：基函數(shù)法.目前七十四頁\總數(shù)八十九頁\編于九點(diǎn)可如下構(gòu)造：均為2n+1次插值基函數(shù).這樣可表示為：顯然有：目前七十五頁\總數(shù)八十九頁\編于九點(diǎn)現(xiàn)在求及，令其中從而有：由此得：，故：，目前七十六頁\總數(shù)八十九頁\編于九點(diǎn)由的表達(dá)式可得：于是得到：同理可得目前七十七頁\總數(shù)八十九頁\編于九點(diǎn)例：已知分別利用sinx的1次、2次Lagrange插值計算sin50

并估計誤差。解：n=1分別利用x0,x1

以及x1,x2

計算利用這里而sin50=0.7660444…)185(50sin10pL0.77614外推/*extrapolation*/

的實際誤差0.01001

利用sin500.76008,內(nèi)插/*interpolation*/

的實際誤差0.00596內(nèi)插通常優(yōu)于外推。選擇要計算的x

所在的區(qū)間的端點(diǎn)，插值效果較好。目前七十八頁\總數(shù)八十九頁\編于九點(diǎn)n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實際誤差0.00061高次插值通常優(yōu)于低次插值Return目前七十九頁\總數(shù)八十九頁\編于九點(diǎn)巴爾末，1825-1898)

特殊愛好:數(shù)字游戲職業(yè):數(shù)學(xué)教師，瑞士某女子中學(xué)，兼巴塞爾大學(xué)無薪講師“我能用公式把任意4個數(shù)字有規(guī)律地聯(lián)系起來”4