第二章代數(shù)差值第1頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月2

某化學(xué)反應(yīng)中,在有限個(gè)時(shí)刻t(min)，測(cè)得生成物質(zhì)量濃度y(10-3g/cm3)的如下數(shù)據(jù)

那么在時(shí)刻t=5分，t=18分時(shí)的濃度是多少？ti12346810121416yi4.006.418.018.799.539.8610.3310.4210.5310.61

本章主要討論利用插值方法尋求函數(shù)的近似問題。

用函數(shù)來表示變量間的數(shù)量關(guān)系廣泛應(yīng)用于各學(xué)科領(lǐng)域,但在實(shí)際問題中,往往是通過實(shí)驗(yàn)、觀測(cè)以及計(jì)算等方法,獲得函數(shù)在一些點(diǎn)上的函數(shù)值。如何通過這些離散數(shù)據(jù)找出函數(shù)的一個(gè)滿足精度要求且便于使用的近似表達(dá)式,是經(jīng)常遇到的問題。例如：第2頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月§1多項(xiàng)式插值問題

3

設(shè)函數(shù)y=f(x)在區(qū)間[a,b]連續(xù),給定n+1個(gè)點(diǎn)已知

f(xk)=yk(k=0,1,…,n),在函數(shù)類中尋找一函數(shù)φ(x)

作為

f(x)

的近似表達(dá)式,使?jié)M足這時(shí)稱

y=f(x)為被插值函數(shù),

φ(x)

稱為插值函數(shù),xk稱為插值節(jié)點(diǎn),式(2.2)稱為插值條件,尋求插值函數(shù)φ(x)

的方法稱為插值方法.一、插值問題a≤x0<x1<…<xn≤b(2.1)φ(xk)=f(xk)=yk,k=0,1,…,n(2.2)第3頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月4

在構(gòu)造插值函數(shù)時(shí)，函數(shù)類的不同選取,P對(duì)應(yīng)各種不同的插值方法，這里我們主要研究函數(shù)類是代數(shù)多項(xiàng)式,，即所謂的多項(xiàng)式插值問題。

多項(xiàng)式插值，從幾何角度看，就是尋求n次代數(shù)曲線

y=pn(x)

通過個(gè)n+1

點(diǎn)(xk,yk)(k=0,1,…,n)作為

f(x)

的近似(如下圖).二、多項(xiàng)式插值問題第4頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月5(2.4)

用

Pn

表示所有次數(shù)不超過n的多項(xiàng)式函數(shù)類，若pn(x)∈Pn

，則

pn(x)=a0+a1x+…+anxn

是由n+1個(gè)系數(shù)唯一確定的。當(dāng)滿足如下的插值條件時(shí)得到關(guān)于系數(shù)a0、a1、…

、an

的線性方程組pn(xk)=f(xk)=yk,k=0,1,…,n(2.3)第5頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月6其系數(shù)行列式為Vandermonde(范德蒙)行列式只要

i≠j

就有xi≠xj

,因而

V(x0,x1,…,xn)≠0,于是方程組(2.4)有唯一解,也就是說,當(dāng)節(jié)點(diǎn)不重合時(shí),n+1個(gè)節(jié)點(diǎn)的插值條件能唯一確定一個(gè)n次插值多項(xiàng)式,從而有:

定理2.1

給定n+1

個(gè)互異節(jié)點(diǎn)

x0,x1,…,xn

上的函數(shù)值y0,y1,…,yn

,則滿足插值條件

pn(xk)=f(xk)=yk,k=0,1,…,n的n次插值多項(xiàng)式pn(x)

存在且唯一。

第6頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月7這樣只要求解方程組拉格朗日插值多項(xiàng)式牛頓插值多項(xiàng)式3.分段線性插值多項(xiàng)式4.三次樣條插值多項(xiàng)式便可確定插值多項(xiàng)式pn(x)

，但相對(duì)來講計(jì)算較復(fù)雜。然而，插值多項(xiàng)式的唯一性保證了無論用什么方法獲得滿足插值條件的多項(xiàng)式都是同一個(gè)多項(xiàng)式pn(x)

，因此可以采用其它更簡(jiǎn)便的方法來確定多項(xiàng)式。下面就介紹幾種常用的方法：(2.4)第7頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月§2Lagrange插值多項(xiàng)式8的函數(shù)值

已知

y=f(x)

在n+1

個(gè)點(diǎn)構(gòu)造n次多項(xiàng)式

pn(x),使得從而得到

f(x)

的近似計(jì)算式

第8頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月一、線性插值（n=1）9求解L1(x)=a1x+a0已知使得f(x)≈L1(x),x∈[x0,x1].根據(jù)點(diǎn)斜式得到如果令則稱l0(x),l1(x)為一次插值多項(xiàng)式的基函數(shù)。這時(shí)：并稱其為一次Lagrange插值多項(xiàng)式。f(x)≈L1(x)=y0l0(x)+y1l1(x)第9頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月二、拋物線插值（n=2）10求解L2(x)=a2x2+a1x+a0使得f(x)≈L2(x),x∈[x0,x2].關(guān)于二次多項(xiàng)式的構(gòu)造采用如下方法：令已知并由插值條件得到L2(x)=A(x-x1)(x-x2)+B(x-x0)(x-x2)+C(x-x0)(x-x1)L2(x0)=y0,L2(x1)=y1

,L2(x)=y2第10頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月11于是得到則有這時(shí)：f(x)≈L2(x)=y0l0(x)+y1l1(x)+y2l2(x)…緊湊格式如果令并稱其為二次Lagrange插值多項(xiàng)式。第11頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月12另外，如果再引進(jìn)記號(hào)

則其導(dǎo)數(shù)為

而且

于是

第12頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月13這樣，就得到二次拉格朗日插值多項(xiàng)式的三種表示形式…緊湊格式

這樣就得到在區(qū)間[a,b]上關(guān)于

f(x)的近似計(jì)算式…基函數(shù)表示

………………ω3(x)表示式

下面給出n次拉格朗日插值多項(xiàng)式的構(gòu)造。第13頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月三、n次Lagrange插值多項(xiàng)式14已知n+1組離散數(shù)據(jù)按照二次Lagrange插值多項(xiàng)式的構(gòu)造方法，令：將插值條件Ln(x0)=y0

代入，得到：同理，由插值條件Ln(x1)=y1

，得到：第14頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月15由插值條件Ln(xn)=yn,得將代入下式：得到：第15頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月16也就是第16頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月17…緊湊格式

…基函數(shù)表示

引進(jìn)基函數(shù)則有第17頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月18還有一種表示式……………ωn+1(x)

表示式

其中ωn+1(x)=(x-x0)(x-x1)…(x-xn).

從而就得到了在區(qū)間[a,b]上的關(guān)于函數(shù)f(x)的n次多項(xiàng)式近似計(jì)算式：

關(guān)于這樣的近似計(jì)算，需要在計(jì)算機(jī)上進(jìn)行，一般我們利用緊湊格式設(shè)計(jì)程序，程序的流程圖如下：

第18頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月19開始輸入

y=0，j=0

t=1

j=n?N

j=

j+1輸出yY結(jié)束第19頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月20

例：某化學(xué)反應(yīng)中,在有限個(gè)時(shí)刻t(min)，測(cè)得生成物質(zhì)量濃度y(10-3g/cm3)的如下數(shù)據(jù)

那么在時(shí)刻t=5分，t=16.4分時(shí)的濃度是多少？ti12346810121416yi4.006.418.018.799.539.8610.3310.4210.5310.61解：編寫程序進(jìn)行計(jì)算(1).先編寫Lagrange插值算法子程序(2).再編寫主程序Lagrange2調(diào)用子程序。(3).計(jì)算在t=5，t=16.4的濃度值，并畫出曲線圖。第20頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月21%lagrange.mfunctiony=lagrange(x0,y0,x)n=length(x0);m=length(x);fork=1:mz=x(k);s=0.0;forj=1:np=1.0;

fori=1:n

ifi~=jp=p*(z-x0(i))/(x0(j)-x0(i));

end

ends=p*y0(j)+s;endy(k)=s;end%lagrange2.mx0=[12 346810121416];y0=[4.006.418.018.799.539.8610.3310.4210.5310.61];x=[1:0.1:16];y=lagrange(x0,y0,x);x1=5;x2=16.4;y1=lagrange(x0,y0,x1)y2=lagrange(x0,y0,x2)plot(x0,y0,'.k','markersize',20)holdonplot(x,y,'-r','markersize',30)holdonplot(x1,y1,'*b','markersize',8)holdonplot(x2,y2,'*b','markersize',8)legend('原數(shù)值點(diǎn)','Lagrange曲線',2)第21頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月22計(jì)算結(jié)果：y(5)=9.2300,y(16.4)=6.5872第22頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月四、插值余項(xiàng)（誤差估計(jì)）23

定理2.2：設(shè)

f(x)∈Cn[a,b],f(n+1)(x)

在(a,b)內(nèi)存在，x0,x1,…,xn

是

[a,b]

中的n+1個(gè)互異節(jié)點(diǎn)，則當(dāng)x∈[a,b]

時(shí),n

次Lagrange插值多項(xiàng)式的截?cái)嗾`差為：(2.5)

證明：令x

是[a,b]中任意固定的數(shù)，如果

x是插值節(jié)點(diǎn)xi,則(2.5)左右兩端均為零，等式(2.5)成立。如果x不是節(jié)點(diǎn)

xi

，作輔助函數(shù)如下：其中，ωn+1(x)=(x-x0)(x-x1)…(x-xn).第23頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月24其中ωn+1(x)=(x-x0)(x-x1)…(x-xn).可以檢驗(yàn)同理可得而且可知

(t)在區(qū)間[a,b]內(nèi)有n+2個(gè)零點(diǎn):x0、x1、…、xn

、x.

由Rolle定理可知，

(t)的導(dǎo)函數(shù)

’(t)在(a,b)內(nèi)有n+1個(gè)零點(diǎn)：再利用Rolle中值定理可知

’’(t)

在(a,b)內(nèi)有n個(gè)零點(diǎn)。以此類推，可知

(n+1)(t)在(a,b)內(nèi)至少有1個(gè)零點(diǎn)。第24頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月25即而根據(jù)求得于是從而得到誤差估計(jì)式：第25頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月26對(duì)于誤差估計(jì)式如果存在，則可以估計(jì)誤差限：當(dāng)n=1時(shí)第26頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月27于是，得到如下Lagrange插值多項(xiàng)式及其誤差估計(jì)這里f(x)=Ln(x)+Rn(x)當(dāng)f(x)≈Ln(x)

時(shí)，誤差為Rn(x)。第27頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月28例2.1已知分別用線性插值和二次插值計(jì)算sin0.3367.解：設(shè)（1）.取x0,x1

作線性插值于是關(guān)于誤差，由得到：第28頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月29（2）.取x0,x1,x2

作二次插值得到關(guān)于誤差，由得到第29頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月本節(jié)(§2)要點(diǎn)30掌握Lagrange插值多項(xiàng)式的構(gòu)造方法及具體結(jié)構(gòu)掌握Lagrange插值多項(xiàng)式誤差分析方法和結(jié)果3.編寫Lagrange插值多項(xiàng)式計(jì)算程序進(jìn)行實(shí)際計(jì)算練習(xí)：已知函數(shù)y=f(x)的如下離散數(shù)據(jù)x012y2312(1).試用線性插值求函數(shù)在x=1.5處的近似值。(2).試用二次插值求函數(shù)在x=1.5處的近似值。第30頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月§3差商及Newton插值多項(xiàng)式一、差商及其性質(zhì)31

Lagrange

插值多項(xiàng)式的優(yōu)點(diǎn)是格式整齊規(guī)范，但其缺點(diǎn)是：當(dāng)需要增加節(jié)點(diǎn)時(shí)，其基函數(shù)都要發(fā)生變化，需要重新計(jì)算，這在實(shí)際計(jì)算中會(huì)影響效率。下面介紹的Newton插值法會(huì)彌補(bǔ)這一不足。1.差商的定義設(shè)y=f(x)在n+1個(gè)互異點(diǎn)

x0,x1,…,xn處的函數(shù)值為：則稱為f(x)關(guān)于點(diǎn)xi,xj

的一階差商。第31頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月32并稱為f(x)關(guān)于點(diǎn)xi,xj,xk

的二階差商。一般地，稱k-1

階差商的一階差商為f(x)關(guān)于點(diǎn)x0,x1,…xk的k

階差商。第32頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月33例如，已知f(x)在的函數(shù)值為：可以求得第33頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月342.差商的性質(zhì)性質(zhì)1：k階差商是由函數(shù)值的線性組合而成，即其中證明：以k=2進(jìn)行證明。由得到第34頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月35由得到從而第35頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月36證明：以k=1

為例性質(zhì)2:差商具有對(duì)稱性,即k階差商f[x0,

x1,…,xk-1,xk]

中，任意調(diào)換xi,xj

的次序，其值不變。以k=2為例第36頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月37性質(zhì)3：若f(x)為一n次多項(xiàng)式，則f[x,x0]為關(guān)于x的n-1次多項(xiàng)式。證明：已知由于故類似的可以得到：也就是說，對(duì)多項(xiàng)式求一次差商，次數(shù)降低一次。第37頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月383.差商的計(jì)算

為構(gòu)造Newton插值多項(xiàng)式方便起見，計(jì)算差商時(shí)，采用列表的方式進(jìn)行。

第38頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月39

例2.2

已知函數(shù)y=f(x)

的如下離散數(shù)據(jù)(1,0)、(2,2)、(4,12)、(5,20)、(6,70)，試求其各階差商.

解：列差商表計(jì)算xy一階差商二階差商三階差商四階差商1022412520670

2

5

8

50

1

1

21

0

5

1第39頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月二、Newton插值多項(xiàng)式40

對(duì)于區(qū)間[a,b]內(nèi)的離散點(diǎn)及相應(yīng)的函數(shù)值，計(jì)算如下差商：可以求得：第40頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月41依次將下式帶入上式得到：第41頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月42則可以將函數(shù)f(x)

表示成：令：容易驗(yàn)證因此Nn(x)滿足插值條件，是一個(gè)n次插值多項(xiàng)式。第42頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月43并稱為n次Newton插值多項(xiàng)式。如果f(x)≈Nn(x)

則誤差為：由Newton插值多項(xiàng)式的結(jié)構(gòu)可以看出，在構(gòu)造Newton插值多項(xiàng)式時(shí)，必須首先計(jì)算各階差商。關(guān)于Newton插值多項(xiàng)式，有以下幾個(gè)特點(diǎn)：第43頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月441.Newton插值多項(xiàng)式與Lagrange插值多項(xiàng)式的誤差相同

這是因?yàn)镹ewton插值多項(xiàng)式與Lagrange插值多項(xiàng)式滿足相同的插值條件因此，Newton插值多項(xiàng)式與Lagrange插值多項(xiàng)式的誤差相同。這樣，由得到這個(gè)表達(dá)式給出了n+1

階差商與n+1

階導(dǎo)數(shù)之間的關(guān)系式。

Nn(xi)=f(xi),i=0,1,…,n,Ln(xi)=f(xi),i=0,1,…,n為什么?第44頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月45例2.3已知，試求其如下差商解：由差商與導(dǎo)數(shù)的關(guān)系式得到第45頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月462.Newton插值多項(xiàng)式具有遞推式由Newton插值多項(xiàng)式可知所以，具有遞推公式：由此可知：當(dāng)求出n-1次插值多項(xiàng)式后，再增加一個(gè)節(jié)點(diǎn)時(shí)，只需要增加一項(xiàng)的計(jì)算即可。第46頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月47

例2.3已知f(x)

的五組數(shù)據(jù)(1.0)、(2,2)、(3,12)、(4,42)、(5,116),求N4(x)。如果再增加一個(gè)節(jié)點(diǎn)(6,282),求出N5(x)，并計(jì)算N4(1.5)、N5(1.5).解：先由前五組數(shù)據(jù)列差商表10223124425116210307441022240.5得到：如果，再增加一點(diǎn)(6,282),就在上表中增加一行計(jì)算差商。628216646810.1第47頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月48由Newton公式的遞推式得到：得到：練習(xí)題：已知離散數(shù)據(jù)(1,0)、(2,2)、(4，12）、(5,20)

求3次牛頓插值多項(xiàng)式，增加一點(diǎn)(6,70)后，再求出4次牛頓插值多項(xiàng)式。第48頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月本節(jié)(§3)要點(diǎn)491.掌握差商及其性質(zhì)，導(dǎo)數(shù)與差商的關(guān)系2.掌握Newton

插值多項(xiàng)式的構(gòu)造方法及具體結(jié)構(gòu)3.掌握Newton插值多項(xiàng)式的誤差結(jié)果4.編寫Newton插值多項(xiàng)式計(jì)算程序進(jìn)行實(shí)際計(jì)算思考題：如何實(shí)現(xiàn)差商表和Newton插值多項(xiàng)式的程序設(shè)計(jì)。

第49頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月50for(j=0;j<=n-1;j++)for(i=n;i>=j+1-1;i--)y0[i]=(y0[i]-y0[i-1])/(x0[i]-x0[i-j]);第一步：計(jì)算差商N(yùn)ewton插值多項(xiàng)式程序設(shè)計(jì)xjyj一階差商二階差商三階差商F[j]x0y0F[0]x1y1f[x0,x1]F[1]x2y2f[x1,x2]f[x0,x1,x2]F[2]x3y3f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,,x3]F[3]fori=1:n-1forj=n:-1:i+1y0(j)=(y0(j)-y0(j-1))/(x0(j)-x0(j-i));endend第50頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月51for(k=0;k<=m;k++){z[k]=y0[0];for(j=1;j<=n;j++){t=1.0;for(i=0;i<=j-1;i++)t=t*(x[k]-x0[i]);z[k]=z[k]+t*y0[j];}第二步：計(jì)算m個(gè)點(diǎn)的函數(shù)值fork=1:mz(k)=y0(1);fori=2:nt=1.0;forj=1:1:i-1t=t*(x(k)-x0(j));endz(k)=z(k)+t*y0(i);endendfor(j=0;j<=n-1;j++)for(i=n;i>=j+1-1;i--)y0[i]=(y0[i]-y0[i-1])/(x0[i]-x0[i-i]);第51頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月52關(guān)于離散數(shù)據(jù)：構(gòu)造了lagrange插值多項(xiàng)式：Newton插值多項(xiàng)式：第52頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月§4分段插值多項(xiàng)式4.1高次插值的龍格現(xiàn)象53

根據(jù)插值條件構(gòu)造的插值多項(xiàng)式作為函數(shù)的近似,有很大局限性，插值多項(xiàng)式的次數(shù)隨著節(jié)點(diǎn)個(gè)數(shù)的增多而升高，但高次插值多項(xiàng)式的近似效果有時(shí)并不理想，看下面的例子。取等距節(jié)點(diǎn)對(duì)于求出可構(gòu)造Lagrange插值多項(xiàng)式Ln(x).第53頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月54

n=10時(shí)，插值多項(xiàng)式

L10(x)

的計(jì)算結(jié)果見下圖：第54頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月55

從圖中可見，在x=0附近L10(x)

對(duì)f(x)

有較好的近似，而點(diǎn)x

距零點(diǎn)越遠(yuǎn)，近似效果越差，以至于完全失真。實(shí)際上，當(dāng)n→∞

時(shí)，在|x|<0.36….

范圍內(nèi),L10(x)收斂于f(x),而在這個(gè)區(qū)間外,L10(x)

是不收斂的。這個(gè)現(xiàn)象被稱為Runge（龍格）現(xiàn)象。Runge現(xiàn)象表明，為減小近似誤差，盲目地提高插值多項(xiàng)式次數(shù)是不可取的，實(shí)際上，很少采用高于7次的插值多項(xiàng)式。因此，只能通過縮小插值區(qū)間的辦法達(dá)到減小誤差的目的，這就是下面要討論的低次分段插值多項(xiàng)式。第55頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月4.2分段線性插值56為了提高近似程度，可以考慮用分段線性插值來逼近原函數(shù)。如下圖所示：設(shè)

y=f(x)

在節(jié)點(diǎn)a=x0<x1<…<xn=b

處的函數(shù)值為yi=f(xi),i=0,1,2,…,n.第56頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月57

這時(shí)的插值函數(shù)為分段函數(shù)：

在區(qū)間[xi-1,xi]上的線性函數(shù)為誤差為：第57頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月58

易見,S(x)是平面上以點(diǎn)(xi,yi)(i=0,1,2,..,n)

為節(jié)點(diǎn)的折線。有如下的特點(diǎn)：（1）S(x)

在[xi-1,xi]上為次數(shù)不超過一次的多項(xiàng)式。

若f(x)C2[a,b]

，由線性插值的誤差公式：（2）S(x)∈C[a,b];

（3）S(x)∈C1[xi-1,xi];得到第58頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月59則有：令可以按如下的方式考慮：關(guān)于整體誤差：第59頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月60可見，當(dāng)

h→0

時(shí)，分段線性插值S(x)

收斂于f(x)

。

若記

則對(duì)任一

x∈[a,b]都有

于是，我們?cè)倏紤]在節(jié)點(diǎn)處可導(dǎo)的插值多項(xiàng)式的構(gòu)造。

值的注意的是：分段線性插值函數(shù)S(x)雖然有很好的收斂性質(zhì)，且在整個(gè)插值區(qū)間[a,b]上是連續(xù)的，但插值函數(shù)S(x)在節(jié)點(diǎn)處卻不光滑。也就是說，S(x)在節(jié)點(diǎn)處的一階導(dǎo)數(shù)不一定存在（或不連續(xù)）！第60頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月4.3分段Hermite插值

61

分段線性插值多項(xiàng)式S(x),在插值區(qū)間[a,b]上只能保證連續(xù)性，而不光滑。要想得到在插值區(qū)間上光滑的分段插值多項(xiàng)式，可采用分段Hermite插值。

如果已知函數(shù)y=f(x)

在節(jié)點(diǎn)a=x0<x1<…<xn=b

處的函數(shù)值和導(dǎo)數(shù)值：則在小區(qū)間[xi-1,xi]

上有四個(gè)插值條件：故能構(gòu)造一個(gè)三次多項(xiàng)式Hi(x)，我們稱其為三次埃爾米特(Hermite)插值多項(xiàng)式。

yk=f(xk),yk’=f’(xk),k=0,1,…,nyi-1=f(xi-1),yi=f(xi),y’i-1=f’(xi-1),yi’=f’(xi),第61頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月62其中Hi(x),x∈[xi-1,xi]滿足條件：這時(shí)，在整個(gè)[a,b]上可以用分段三次Hermite插值多項(xiàng)式來逼近f(x)

。第62頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月63關(guān)于

Hi(x)

的構(gòu)造，我們可以通過基函數(shù)來進(jìn)行：由插值條件：可以給出基函數(shù)滿足的條件為：第63頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月64由于

i-1(x)滿足條件：我們稱

為三次Hermite插值基函數(shù)。所以

i-1(x)

應(yīng)該具有以下形式：下面來求基函數(shù)：再將代入可得而且第64頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月65將得到類似地有：代入下式：第65頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月66代入下式得到這樣，便求出了分段三次Hermite插值多項(xiàng)式：第66頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月67

【定理】若f(x)∈C3[a,b]，且f(4)(x)在(a,b)內(nèi)存在，則在[xi-1,xi

]

上有其中Proof：1）當(dāng)x為xi-1或xi時(shí)，上式顯然成立；2）當(dāng)x不為xi-1，xi時(shí)，作輔助函數(shù)則有關(guān)于誤差，有如下定理：第67頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月68

如果記則有：即反復(fù)應(yīng)用Rolle中值定理可知在內(nèi)至少有一個(gè)零點(diǎn)，使得，而將t=

i

代入上式可得結(jié)論。定理證畢。第68頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月69關(guān)于整體誤差，若

f(x)∈C4[a,b],則可按如下方式考慮：記則有：

于是,當(dāng)h→0

時(shí)，R(x)→0。說明分段三次Hermite插值H(x)

收斂于f(x)

。第69頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月70

上節(jié)中的分段低次插值有很好的收斂性，但其光滑性不夠理想，為了提高光滑性，就得增加節(jié)點(diǎn)上的導(dǎo)數(shù)插值條件，這顯然是困難的。

由H(x)的表達(dá)式，可以的知它有如下特性：（2）H(x)

C1[a,b];（3）H(x)

C2[xi-1,xi].

（1）H(x)

在[a,b]上是分段函數(shù)，且在每個(gè)[xi-1,xi]是一個(gè)三次多項(xiàng)式;比分段線性插值的光滑性要好一些。

理想的結(jié)果是：構(gòu)造一個(gè)多項(xiàng)式，在不增加已知條件的情況下，既有好的逼近效果，又有好的光滑性。下一節(jié)討論這樣的問題。第70頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月

本節(jié)(§4)問題712.分段線性插值有何優(yōu)缺點(diǎn)？如何估計(jì)誤差？

4.如何分段線性插值算法的程序設(shè)計(jì)？1.何為高次插值的Runge現(xiàn)象，應(yīng)如何避免？

3.分段三次Hermite插值有何優(yōu)缺點(diǎn),如何估計(jì)誤差5.如何構(gòu)造滿足以下條件的插值多項(xiàng)式并估計(jì)誤差？第71頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月§5三次樣條插值72

在解決實(shí)際問題時(shí)，有時(shí)對(duì)插值函數(shù)曲線的光滑性有較高的要求，如機(jī)翼形線、船體放樣型值線、汽車外形型值線等，都要求有二階的光滑度，即具有二階連續(xù)導(dǎo)函數(shù)。

2)分段線性插值函數(shù)，逼近程度較好，但光滑性差；

然而，1)高階插值曲線(Lagrange、Newton插值曲線)雖然具有較好的光滑性，但會(huì)出現(xiàn)Runge現(xiàn)象；3)分段三次Hermite插值，逼近程度好，光滑性也比較好，但需增加更多的插值條件，有些場(chǎng)合不實(shí)用，且節(jié)點(diǎn)處的二階導(dǎo)數(shù)也不一定連續(xù)。

第72頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月73

理想的結(jié)果是：在不增加更多條件的情況下，構(gòu)造出的插值多項(xiàng)式，既不出現(xiàn)Runge現(xiàn)象，也有很好的逼近程度，同時(shí)還有很好的光滑性。下面討論的樣條函數(shù)就具有這樣的特性！

所謂三次樣條一詞來源于一種繪圖工具：樣條尺，柔軟富有彈性，作圖時(shí)可用它作出不同彎曲程度的光滑曲線。在實(shí)際工作中，技術(shù)人員利用這種樣條尺來繪制光滑曲線，樣條尺是用易彎曲的材料做成，如易彎曲的木條等。

在樣條尺上加壓鐵固定，可以強(qiáng)制它通過平面圖上的固定點(diǎn)(xi,yi),i=0,1,2,…,n，然后繪圖人員再沿著這條變形的樣條尺畫出曲線，這種曲線稱為樣條曲線，樣條曲線具有很好的光滑性。第73頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月74

當(dāng)我們用直尺作曲線時(shí)，得到左圖的形狀；當(dāng)用樣條尺作圖時(shí)，會(huì)得到右圖的形狀，具有好的光滑性。

下面，我們從理論上對(duì)這一曲線進(jìn)行研究，并著重給出三次樣條函數(shù)的構(gòu)造方法。第74頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月5.1樣條(Spline）函數(shù)的定義75

已知函數(shù)

y=f(x)

在節(jié)點(diǎn)

a=x0<x1<…<xn=b

處的函數(shù)值為如果函數(shù)S(x)

滿足條件：

（1）S(x)是一個(gè)分段的m次多項(xiàng)式，且S(xk)=yk

；則稱

S(x)

是m次樣條插值函數(shù)。（2）S(x)

在[a,b]具有m-1階連續(xù)導(dǎo)數(shù)。1.m次樣條函數(shù)的定義yk=f(xk)

,k=0,1,2,…,n第75頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月76

2.

三次樣條函數(shù)的定義

已知函數(shù)y=f(x)

在節(jié)點(diǎn)a=x0<x1<…<xn=b

處的函數(shù)值為如果函數(shù)S(x)

滿足條件：

（1）S(x)

是一個(gè)分段的三次多項(xiàng)式，且S(xk)=yk；則稱S(x)

是三次樣條插值函數(shù)。（2）S(x)

在[a,b]具有二階連續(xù)導(dǎo)數(shù)。yk=f(xk)

,k=0,1,2,…,n第76頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月77

S(x)的具體形式為：

其中Si

在上[xi-1,xi]

是三次多項(xiàng)式

有四個(gè)待定常數(shù)。這樣S(x)

共有4n個(gè)待定常數(shù)要確定。

根據(jù)已知條件及三次樣條函數(shù)的性質(zhì)，一共有已知條件。(n+1)+(n-1)+(n-1)+(n-1)=4n-2也就是說，需要4n個(gè)條件來確定這些系數(shù)。還缺兩個(gè)條件，一般通過增加邊界條件來補(bǔ)充。第77頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月78常用的邊界條件有以下幾種：邊界條件1：

邊界條件2：

邊界條件3：假定函數(shù)y=f(x)是以b-a

為周期的周期函數(shù)，這時(shí)要求S(x)

也是周期函數(shù)，即

這樣我們便可以求出唯一的三次樣條函數(shù)來。第78頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月5.2樣條函數(shù)的求解1.三轉(zhuǎn)角算法79由n+1組數(shù)據(jù)

只要求出在區(qū)間[xi-1,xi]上的三次多項(xiàng)式

Si(x)

i=1,2,…,n即可。加邊界條件構(gòu)成的三次樣條函數(shù)為分段函數(shù)a=x0<x1<…<xn=b,yk=f(xk)

,k=0,1,2,…,n第79頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月80已知Si(x)

滿足條件

由于

Si(x)

是三次多項(xiàng)式，還缺少兩個(gè)條件。在這里假設(shè)

Si(x)

在兩個(gè)端點(diǎn)的導(dǎo)數(shù)值已知：(2.1)(2.2)(2.1)、(2.2)

滿足三次Hermite插值多項(xiàng)式的條件，故可以得到：第80頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月81上式給出了Si(x)

的表達(dá)式，但是表達(dá)式中的mi-1和mi還是未知的，還需要求出mi-1、mi

來才具體求出了三次樣條函數(shù)。

這時(shí)，根據(jù)三次樣條函數(shù)的定義：S(x)

在[a,b]上具有二階連續(xù)導(dǎo)函數(shù)，可知在節(jié)點(diǎn)

xi處第81頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月82而：于是，由兩邊求導(dǎo)得：Si(x)Si+1(x)第82頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月83于是同理可得第83頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月84根據(jù)二階導(dǎo)數(shù)連續(xù)性條件

,即及

得到

第84頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月85用

除等式兩側(cè)得到將等式

合并整理得：第85頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月86令：簡(jiǎn)化為這是一個(gè)方程組，可以進(jìn)一步寫為：第86頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月87

式（2.3）給出了n+1個(gè)未知數(shù)

m0,m1,…,mn

的n-1個(gè)方程，若要求解出來，還需要補(bǔ)充兩個(gè)方程，這時(shí)可以考慮所給定的邊界條件。（2.3）第87頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月88得到這樣，我們只需要求出

m0,m1,…,mn

即可。邊界條件1：這時(shí)的方程改寫為：第88頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月89或者，表示為矩陣方程(2.4)由于λk+μk=1,方程（2.4）的系數(shù)矩陣是嚴(yán)格對(duì)角占優(yōu)矩陣，方程（2.4）有惟一解，并可用追趕法求解。第89頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月90便得到三次樣條函數(shù)：解出m0,m1,…,mn

以后，代入下式第90頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月91也就是：邊界條件2：

已知：故可以得到

第91頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月92將與前面得到的方程組：結(jié)合構(gòu)成一個(gè)含n+1個(gè)未知量和n+1個(gè)方程的方程組，便可求解出m0,m1,…,mn

：第92頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月93求解此方程組，也可以求出三次樣條函數(shù)。(2.5)或者表示為矩陣方程第93頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月94由第一個(gè)等式和第二個(gè)等式得到

y0=yn,m0=mn邊界條件3：周期邊界條件由第三個(gè)等式說明：再由第94頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月95即：得到由m0=mn

整理為第95頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月96在等式兩邊同除以得到令得到第96頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月97結(jié)合，與將得第97頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月98并將

表示為矩陣方程：(2.6)

其系數(shù)矩陣稱作周期三對(duì)角矩陣，也是嚴(yán)格對(duì)角占優(yōu)，因而方程組有唯一解。第98頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月三次樣條函數(shù)三轉(zhuǎn)角算法的實(shí)現(xiàn)流程99Step1:輸入節(jié)點(diǎn)x0,x1,…,xn

,函數(shù)值y0,y1,…,yn、

邊界條件及

x.Step3:根據(jù)邊界條件，求解相應(yīng)的方程得到

m0,m1,…,mnStep2:計(jì)算Step4:判斷

x∈[xi-1,xi]

?Step5:計(jì)算

y≈si(x)Step6:輸出

y第99頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月100三次樣條函數(shù)曲線圖第100頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月101設(shè)

例2-4已知函數(shù)y=f(x)

的如下數(shù)據(jù),試求其在區(qū)間[0,3]上的三次樣條插值函數(shù)S(x)。

解這里邊界條件是求得第101頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月102已知由方程組及得到方程組解得第102頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月103這樣便求得代入表達(dá)式便得到所求的三次樣條函數(shù)第103頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月本節(jié)(§5-1、2)要點(diǎn)104什么是三次樣條函數(shù)？三次樣條函數(shù)的邊界條件是如何給出的？三次樣條函數(shù)的三轉(zhuǎn)角算法是如何構(gòu)造的？如何設(shè)計(jì)程序?qū)崿F(xiàn)三轉(zhuǎn)角算法？畫出流程圖。三對(duì)角線性方程組和一般線性方程組如何求解？完成P49習(xí)題2-12、2-13。第104頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月2.三彎矩算法105

只要求出在區(qū)間[xi-1,xi]上的三次多項(xiàng)式

Si(x)

i=1,2,…,n

即可。在這里我們采用另一種方法進(jìn)行求解，并稱為三彎矩算法。加邊界條件構(gòu)成的三次樣條函數(shù)為分段函數(shù)a=x0<x1<…<xn=b,yk=f(xk)

,k=0,1,2,…,n對(duì)于離散點(diǎn)及其上的函數(shù)值：第105頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月106已知Si(x)

滿足條件

Si(xi-1)=yi-1，Si(xi)=yi(2.1)在此假設(shè)

Si”(xi-1)

=Mi-1,Si”(xi)

=Mi

(2.2)對(duì)于三次多項(xiàng)式Si(x)

，其二階導(dǎo)函數(shù)Si(xi-1)為線性函數(shù)，故可設(shè)積分兩次得到(2.3)第106頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月107可以求得：再由條件

Si(xi-1)=yi-1，Si(xi)=yi(2.1)(2.3)代入(2.3)得到：再根據(jù)：Si(x)Si+1(x)及第107頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月108這時(shí)于是根據(jù)得到也就是第108頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月109兩邊同除以上式得令則有這是含有n-1個(gè)方程的線性方程組，具體形式為：第109頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月110

該線性方程組含有n+1個(gè)未知量，要解出唯一的一組解來，還需要補(bǔ)充兩個(gè)方程，這可以有邊界條件來實(shí)現(xiàn)。第110頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月111邊界條件1：

也就是由得即第111頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月112再由得即結(jié)合可以得到求解M0、M1、…、Mn的線性方程組。第112頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月113其中方程組(2.6)的矩陣形式為第113頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月114邊界條件2：

這說明這時(shí)方程組直接轉(zhuǎn)化為恰定方程組第114頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月115矩陣形式為(2.9)第115頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月116邊界條件3：

由得第116頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月117代入得令第117頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月118則結(jié)合得第118頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月119矩陣形式為第119頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月120針對(duì)三種邊界條件求解相應(yīng)的方程組(2.9)第120頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月121得到M0、M1、…、Mn后代入就可以得到三次樣條函數(shù)并把以上算法稱作三彎矩算法。第121頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月122

例2-5

求三次樣條插值函數(shù)S(x)，滿足自然邊界條件(S”(x0)=S”(xn)=0)，已知離散數(shù)據(jù)如下：

i01234xi0.250.300.390.450.53yi0.5000.54770.62450.67080.2780

解：已知M0=M4=0，先求出步長(zhǎng)h1=0.05,h2=0.09,h3=0.06,h4=0.08,再計(jì)算第122頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月123代入方程組得到解得M0=0,M1=-1.8806,M2=-0.8836,

M3=-1.0261,M4=0.(2.9)第123頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月124代入得到第124頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月5.3三次樣條插值函數(shù)的誤差估計(jì)1.如果f(x)C[a,b]，且劃分的網(wǎng)格比125其中一致有界，則當(dāng)時(shí)，S(x)一致收斂于f(x).2.如果f(x)C4[a,b]，且S(x)滿足邊界條件I、II,則即h0時(shí)，如果劃分比

一致有界，第125頁(yè)，課件共132頁(yè)，創(chuàng)作于2023年2月5.4三次樣條插值函數(shù)的程序設(shè)計(jì)1.三對(duì)角方程求解的追趕法126#include<stdio.h>#include<math.h>intcetrd(doubleb[],intn,intm,doubled[]){intk,j;doubles;

if(m!=(3*n-2)){printf("error\n");return(-2);}

for(k=0;k<=n-2;k++){j=3*k;s=b[j];

if(fabs(s)+1.0==1.0)

{printf("fail\n");return(0);}b[j+1]=b[j+1]/s;d[k]=d[k]/s;b[j+3]=b[j+3]-b[j+2]*b[j+1];d[k+1