數(shù)值計(jì)算方法與算法課件

第1章插值法1.1插值法1.2Lagrange插值1.3Newton插值1.4Hermite插值1.5分段線性插值1.6三次樣條插值1.7程序示例習(xí)題11.1插值法插值問(wèn)題的背景

在生產(chǎn)和實(shí)驗(yàn)中，函數(shù)f(x)或者其表達(dá)式不便于計(jì)算,或者無(wú)表達(dá)式而只有函數(shù)在給定點(diǎn)的函數(shù)值(或其導(dǎo)數(shù)值)，此時(shí)我們希望建立一個(gè)簡(jiǎn)單的而便于計(jì)算的近似函數(shù)

(x)，來(lái)逼近函數(shù)f(x)。

常用的函數(shù)逼近方法有：

?

插值法；

?

最小二乘法（或稱均方逼近）；

?

一致逼近等。插值法

插值法是函數(shù)逼近的重要方法之一，有著廣泛的應(yīng)用。簡(jiǎn)單地說(shuō)，插值法就是用給定的(未知)函數(shù)

f(x)的若干點(diǎn)上的函數(shù)值(或其導(dǎo)數(shù)值)來(lái)構(gòu)造f(x)的近似函數(shù)

(x)，要求

(x)與f(x)在給定點(diǎn)的函數(shù)值相等。

有很多種插值法，其中以拉格朗日(Lagrange)插值和牛頓(Newton)插值為代表的多項(xiàng)式插值最有特點(diǎn)，常用的插值還有Hermite插值，分段插值和樣條插值。函數(shù)可以未知，只需已知若干點(diǎn)上的值。

設(shè)f(x)為[a，b]上的函數(shù)，在互異點(diǎn)x0,x1,...,xn

處的函數(shù)值分別為f(x0)

,f(x1),…,f(xn)

,構(gòu)造一個(gè)簡(jiǎn)單函數(shù)

(x)作為函數(shù)

f(x)的近似表達(dá)式y(tǒng)=f(x)

(x),使

(xi)＝f(xi),

i＝0,1,2,

…,n

(1.0)則稱

(x)為關(guān)于節(jié)點(diǎn)x0,x1,...,xn的插值函數(shù)；稱x0,x1,...,xn

為插值節(jié)點(diǎn)；稱(xi,f(xi)),i=1,2,…,n為插值點(diǎn)；f(x)稱為被插值函數(shù)。(1.0)式稱為插值條件。這類問(wèn)題稱為插值問(wèn)題。

構(gòu)造出

(x)，對(duì)f(x)在[a,b]上函數(shù)值的計(jì)算，就轉(zhuǎn)化為

(x)在對(duì)應(yīng)點(diǎn)上的算。插值法的定義1.2Lagrange插值

選用代數(shù)多項(xiàng)式作為插值函數(shù)。Lagrange插值就是選用節(jié)點(diǎn)上的函數(shù)值作為插值條件。1.2.1

線性插值

給定兩個(gè)點(diǎn)(x0，y0)，(x1，y1），x0≠x1，確定一個(gè)一次多項(xiàng)式插值函數(shù)，簡(jiǎn)稱線性插值。待定系數(shù)法

設(shè)

L1(x)=a0+a1x,代入插值點(diǎn)當(dāng)x0≠x1時(shí)，方程組的解存在唯一。即插值條件：L1(xi)=f(xi)=yi,i=0,1解之得，

因此，

（1.1）式稱為一次Lagrange插值。

由求解過(guò)程知，用待定系數(shù)法，需要求解線性方程組，當(dāng)已知節(jié)點(diǎn)較多時(shí)，即方程的未知數(shù)多，計(jì)算量較大，不便向高階插值推廣。插值基函數(shù)法

分別構(gòu)造兩個(gè)節(jié)點(diǎn)上的一次函數(shù)，使其在本節(jié)點(diǎn)上的函數(shù)值為1，而在其他節(jié)點(diǎn)上的函數(shù)值為0。設(shè)l0(x),l1(x)分別為滿足上述條件的一次函數(shù)，即或簡(jiǎn)單地記為對(duì)于過(guò)兩個(gè)節(jié)點(diǎn)x0,x1的線性插值（1.1）式，令顯然，l0(x),l1(x)

滿足：

線性插值函數(shù)可以寫成節(jié)點(diǎn)上函數(shù)值的線性組合，即

L1(x)=l0(x)y0+l1(x)y1

．

稱l0(x),l1(x)

分別為x0,x1的插值基函數(shù)。線性插值誤差定理1設(shè)L1(x)為一次Lagrange插值函數(shù),若

f

(x)

一階連續(xù)可導(dǎo)，f"(x)在(a,b)上存在，則對(duì)任意給定的x∈(a,b),

至少存在一點(diǎn)ζ∈(a,b),使得證明

因?yàn)長(zhǎng)(xi)=f(xi),i=0,1,所以，R1(x0)=R1(x1)=0,

即

x0,x1為R1(x)的兩個(gè)根。因此，可設(shè)R1(x)為易知滿足插值條件：L1(xi)=yi,i=0,1可設(shè)

R1(x)=k(x)(x-x0)(x-x1).

固定任一

x，作輔助函數(shù)，令

則Ψ

(xi

)=0,i=1,2,Ψ

(x)=0,即Ψ

(t)有3個(gè)零點(diǎn)x0,x1,x。

假定，x0

<x<

x1,分別在[x0，x]和[x，x1]上應(yīng)用洛爾（Rolle）定理，可知，Ψ′(t)在每個(gè)區(qū)間上至少存在一個(gè)零點(diǎn)，ζ1，ζ2，使Ψ′(ζ1)=0，Ψ′(ζ2)=0(此即Ψ′(t)有2個(gè)零點(diǎn))。再利用洛爾定理知，

Ψ′(t)在[ζ1,ζ2]上至少有一個(gè)零點(diǎn)ζ，使Ψ″(ζ)=0。

對(duì)Ψ

(t)求2階導(dǎo)數(shù)得，

Ψ″(t)=f″(t)-2!k(x),

因?yàn)棣贰?ζ)=0，所以，有

k(x)

=f″(ζ)/2!。證畢。1.2.2

二次插值

給定3個(gè)互異插值點(diǎn)(xi,f(xi)),i=0,1,2，確定一個(gè)二次插值多項(xiàng)式函數(shù)，即拋物線插值（如圖）。待定系數(shù)法

設(shè)L2(x)=a0+a1x+a2x2,代入3個(gè)插值條件：

L2(xi)=f(xi)),i=0,1,2，解線形方程組可得a0,a1,a2。

插值基函數(shù)法構(gòu)造3個(gè)節(jié)點(diǎn)上2次插值基函數(shù)l0(x),l1(x),l2(x),使?jié)M足

li(xj)=δij

，i,j=0,1,2。

因?yàn)閘0(x)為2次插值基函數(shù),且l0(x1)=l0(x2)=0,所以可設(shè)l0(x)=A(x

-x1)(x-x2)。

由條件：l0(x0)=1，得同理可得，二次Lagrange插值多項(xiàng)式為容易驗(yàn)證滿足插值條件二次插值的誤差

定理

設(shè)L2(x)為二次Lagrange插值函數(shù),若f

(x)

∈C3[a，b]，則任給x∈(a,b),至少存在一點(diǎn)ζ=ζ(x)∈(a,b),使

提示：因?yàn)镽2(x0)=R2(x1)=R2(x2)=0,可設(shè)作輔助函數(shù)

易知，x0,x1,x2,x為Ψ(t)的4個(gè)零點(diǎn)，在4個(gè)點(diǎn)兩兩組成的區(qū)間上，應(yīng)用Rolle定理，然后再反復(fù)應(yīng)用Rolle定理即得證。

例1.1

給定sin11°=0.190809,sin12°=0.207912,求線性插

值，并計(jì)算sin11°30'和sin10°30'

。解

x0=11°,x1=12°,y0=0.190809,y1=0.207912，sin11°30'≈L1(11.5)=0.199361,sin10°30'≈L1(10.5)=0.182258.由定理1知，誤差為準(zhǔn)確值為：sin11°30’=0.199368sin10°30’=0.182236例1.2

給定sin11°=0.190809,sin12°=0.207912,

sin13°=0.224951,構(gòu)造二次插值，并計(jì)算

sin11°30′。

解x0=11,x1=12,x2=13,

y0=0.190809,y1=0.207912,y2=0.224951，

sin11°30′≈L2(11.5)=0.199369,

sin11°30′=0.199368.例1.3

要制作三角函數(shù)sinx的值表，已知表值有四位小數(shù)，要求用線性插值引起的截?cái)嗾`差不超過(guò)表值的舍入誤差，試確定其最大允許的步長(zhǎng)。解f(x)=sinx,

設(shè)xi－１,xi為任意兩個(gè)插值節(jié)點(diǎn)，最大允許步長(zhǎng)記為

h=hi=xi

－xi－１，1.2.3n次Lagrange插值多項(xiàng)式已知n+1個(gè)互異插值節(jié)點(diǎn)

(xi,f(xi)),i=0,1,2,…,n,研究n次插值多項(xiàng)式的存在性及其表示形式。★存在性

設(shè)

n次多項(xiàng)式為代入插值點(diǎn)，即插值條件：Pn(xi)=f(xi),i=0,1,2,…,n,

得其范德蒙德(Vandermonde)行列式為：

所以，(1.6)的解存在唯一。

解出(1.6)的解a0,a1,…,an，代入(1.6)1即得n次插值多項(xiàng)式Pn(x)?！飊次插值多項(xiàng)式的構(gòu)造

有上面的討論知，用待定系數(shù)法要求解一個(gè)線性方程組，計(jì)算量大，實(shí)際中不可取。插值基函數(shù)法分別構(gòu)造x0,x1,…,xn上的n次插值基函數(shù)l0(x),l1(x),…,ln(x),滿足性質(zhì)：即節(jié)點(diǎn)基函數(shù)x0x1x2…xnl0(x)100…0l1(x)010…0l2(x)001…0………………ln(x)000…1先構(gòu)造l0(x)。有上表知，x1,x2,…,xn為l0(x)的零點(diǎn)，設(shè)

由l0(x0)=1，得同理可設(shè)由li(xi)=1，得于是，所以我們得到n次Lagrange插值多項(xiàng)式：容易驗(yàn)證，

Ln(xi)=f(xi),i=0,1,2,…,n.例1.4已知插值點(diǎn)

(-2.00,17.00),(0.00,1.00),(1.00,2.00),(2.00,17.00),

求三次插值，并計(jì)算f(0.6)。解先計(jì)算4個(gè)節(jié)點(diǎn)上的基函數(shù)：三次Lagrange插值多項(xiàng)式為：

f(0.6)≈L3(0.6)=-0.472.★n次插值多項(xiàng)式的誤差定理2設(shè)Ln(x)是[a,b]上過(guò)插值點(diǎn)(xi,f(xi))的n次Lagrange插值多項(xiàng)式，節(jié)點(diǎn)xi兩兩互異，若

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

則?x∈[a,b],存在ζ=ζ(x)

∈[a,b],使得證明提示：因?yàn)镽n(xi)=0,i=0,1,2,…,n,令作輔助函數(shù)顯然，Ψ(t)有n+2個(gè)零點(diǎn)x0，x1，…，xn，x，反復(fù)應(yīng)用Rolle定理，由Ψ(n+1)(ζ)=0,定理得證。Back★n次插值多項(xiàng)式的幾點(diǎn)說(shuō)明若|f(n+1)(x)|≤M,x∈[a,b],則由(1.9)得當(dāng)f(x)為不高于n次的多項(xiàng)式時(shí)，因?yàn)镽n(x)=0,則Ln(x)=f(x).

特別地，取f(x)=xk,k=0,1,2,…,n,則令k=0，可知n次Lagrange基函數(shù){li(x)}滿足即f(x)為不超過(guò)n次的多項(xiàng)式時(shí)，插值多項(xiàng)式就是被插函數(shù)本身實(shí)際計(jì)算中，如果f(x)的形式未知，也就無(wú)法求出f(n+1)(x)或估計(jì)出其較精確的上界。所以也就無(wú)法估計(jì)|Rn(x)|。我們采用事后估計(jì)，即給定n+2個(gè)節(jié)點(diǎn)，x0,x1,…,xn,xn+1,構(gòu)造兩個(gè)n次插值多項(xiàng)式Ln(x)和，用它們來(lái)估計(jì)|Rn(x)|。由定理2，得Th.2假定f(n+1)(x)在[a,b]內(nèi)連續(xù),且變化不大,即

f(n+1)(ζ1)≈f(n+1)(ζ2).(1.13)和(1.14)兩式相除，得解之得，于是，得誤差事后估計(jì)：即用求出的插值多項(xiàng)式來(lái)估計(jì)誤差?！飊次插值多項(xiàng)式的算法描述輸入節(jié)點(diǎn)數(shù)n、插值點(diǎn)(xi,yi)

(i=0,1,2,…,n)和要計(jì)算的函數(shù)點(diǎn)x。實(shí)現(xiàn)基函數(shù)li(x)和插值Ln(x):FORi=0,1,…,n

{tmp=1;FORj=0,1,…,i-1,i+1,…,n{tmp=tmp*(x-xj)/(xi-xj);(實(shí)現(xiàn)li(x)

)

}fx=fx+tmp*yi;(實(shí)現(xiàn)Ln(x)

)}輸出fx。2006年9月22日1.3Newton插值Lagrange插值的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：形式整齊、規(guī)范，理論上保證插值的存在唯一性。

缺點(diǎn)：計(jì)算量大、不具有承襲性。1.3.1差商及其性質(zhì)一階差商：f(x)關(guān)于點(diǎn)x0，x1的一階差商記為f[x0,x1]，二階差商：

f(x)關(guān)于點(diǎn)x0，x1，x2的二階差商記為f[x0,x1,x2],一般地，k階差商

f[x0,x1,…,xn]定義為：差商的性質(zhì)

性質(zhì)1k階差商f[x0,x1,…,xk]可表成節(jié)點(diǎn)上函數(shù)值f(x0),

f(x1),…,f(xk)的線性組合，即例如，k=2時(shí)，(1.17)性質(zhì)2各階差商具有對(duì)稱性,即改變差商中節(jié)點(diǎn)的次序不會(huì)

改變差商的值。設(shè)i0,i1,…,ik為0,1,…,k的任一排列,則

由性質(zhì)1知，任意改變節(jié)點(diǎn)的次序，只改變(1.17)式右端求和的次序，故其值不變。例如,由定義知，性質(zhì)3若f(x)為n次多項(xiàng)式，則一階差商f[x,xi]為n

?1次多項(xiàng)式。

由定義令x=xi,則分子為0,說(shuō)明分子中含有因子x

?

xi,與分母約去。性質(zhì)4若f(x)在[a,b]存在n+1階導(dǎo)數(shù)，xi∈[a,b],

i=0,1,…,n,固定x∈[a,b],則n+1

階差商與導(dǎo)數(shù)

存在如下關(guān)系：

差商的計(jì)算

★由差商的定義

一階差商是由節(jié)點(diǎn)上函數(shù)值定義的，二階差商是由一階差商定義的，…，依此構(gòu)造差商表：i

xif(xi)一階差商二階差商

三階差商

…n階差商0

x0f(x0)1

x1f(x1)f[x0,x1]2

x2f(x2)f[x1,x2]f[x0,x1,x2]3

x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]………………n

xnf(xn)f[xn?1,xn]f[xn?2,xn?1,xn]f[xn?3,…,xn]…

f[x0,x1,…,xn]Return例1.5計(jì)算(?2,17),(0,1),(1,2),(2,19)的一至三階差商。解

由表易知，

f[x0,x1]=f[?2,0]=?8

f[x0,x1,x2]=f[?2,0,1]=(?8?1)/(?2?1)=3

f[x0,x1,x2,x3]=f[?2,0,1,2]=(3?8)/(?2?2)=5/4i

xif(xi)f[xi

?1,xi]f[xi

?2,xi

?1,xi]f[xi

?3,xi

?2,xi

?1,xi]0

?2

171

01?82

12133

2191785/4例1.7★由差商與導(dǎo)數(shù)的關(guān)系（性質(zhì)4）例1.6對(duì)

f(x)=x7?x4+3x+1，

求

f[20,21]，f[x,20,21,…,26]和f[x,20,21,…,27]。解

顯然，

f(7)

(x)=7!,f(8)

(x)=0,由性質(zhì)4得1.3.2Newton插值★線性插值給定兩個(gè)插值點(diǎn)(x0,f(x0)),(x1,f(x1)),x0≠x1,設(shè)

N1(x)=a0+a1(x?x0)…………

直線的點(diǎn)斜式

代入插值點(diǎn)得，

于是得線性Newton插值公式由插值的唯一性知，L1(x)與N1(x)為同一多項(xiàng)式，只是表達(dá)形式不同而已?！?/p>

二次Newton插值給定三個(gè)互異插值點(diǎn)(xi,f(xi)),設(shè)代入插值條件：N2(xi)=f(xi),i=0,1,2,得二次Newton插值公式為★

n次Newton插值公式

給定n+1個(gè)插值點(diǎn)(xi,f(xi)),i=0,1,2,…,n,xi互異，類似地，有二階至n階差商的定義得(x?x0)×(x?x0)(x?x1)×

……(x?x0)…(x?xn?1)

上述所有n+1個(gè)等式相加，得其中，插值誤差為：n次Newton插值公式容易驗(yàn)證，Newton插值滿足插值條件：

Nn(xi)=f(xi),i=0,1,2,…,n.★關(guān)于Lagrange插值和Newton插值的幾點(diǎn)說(shuō)明由插值的唯一性質(zhì)，Ln(x)=Nn(x)。因此，他們的誤差也相同，即當(dāng)f(x)∈Cn+1[a,b]時(shí)，有故得差商的性質(zhì)42.

牛頓插值的誤差不要求函數(shù)的高階導(dǎo)數(shù)存在，所以更具有一般性。它對(duì)f(x)是由離散點(diǎn)給出的函數(shù)情形或f(x)的導(dǎo)數(shù)不存在的情形均適用。3.引入記號(hào):

f[x0]=f(x0),t0(x)=1,t1(x)=x?x0,t2(x)=(x?

x0)(x?

x1),…,

tn(x)=(x?

x0)(x?

x1)…

(x?

xn?1)，于是n次Newton插值公式可表為稱t0(x),

t1(x),t2(x),

…,

tn(x)為Newton插值的基函數(shù)，而且滿足如下關(guān)系：

ti(x)=ti?1(x)(x?xi?1),i=1,2,…,n；

ti(xj)=0，j<i，

ti(xj)≠0，j≥i。4.Newton插值具有承襲性質(zhì)，即

5.Newton插值公式的計(jì)算量

乘：1+2+…+(n?1)+n=n(n+1)/2

除：n+(n?1)+…+2+1=n(n+1)/2第i個(gè)節(jié)點(diǎn)以后非零例1.7給定四個(gè)插值點(diǎn)(?2,17),(0,1),(1,2),(2,19),計(jì)算

N2(0.9),N3(0.9)。解x0=?2，x1=0，x2=1，x3=2，由例1.5知，f[x0,x1]=?8，f[x0,x1,x2]=3，f[x0,x1,x2,x3]=5/4，所以，

N2(0.9)=17?8(0.9+2)+3(0.9+2)×0.9=1.63;N3(0.9)=N2(0.9)+1.25×0.9(0.9+2)(0.9?1)=1.30375.例1.5★

Newton插值的算法用牛頓插值公式，首先要計(jì)算各階差商值，然后再計(jì)算插值。牛頓插值由承襲性質(zhì)容易實(shí)現(xiàn)，關(guān)鍵是實(shí)現(xiàn)差商。1.

輸入初始數(shù)據(jù):節(jié)點(diǎn)數(shù)n,插值點(diǎn)序列{x，f(xi)},i=0,1,2,…,n,及要計(jì)算的函數(shù)點(diǎn)u；2.

形成差商表

g[k],k=1,2,…,n;（g[k]=f[x0,…,xk]）

3.

形成插值基函數(shù)及插值

t=1,newton=f(x0)

對(duì)i=1,2,…,nt=(u?xi?1)·t;(由tk=(u?xk?1)tk?

1

形成(u?x0)…

(u?xi?1)

)newton=newton+t·g[i]4.

輸出牛頓插值Nn(u)=newton。牛頓插值公式中只用到差商表中對(duì)角線上的差商，即

f[x0],

f[x0,x1],f[x0,x1,x2],…,f[x0,x1,…,xn].

可以分別用一維數(shù)組g[i]來(lái)存放這些差商，i=0,1,2,…,n.形成差商具體步驟：(1)

對(duì)g[i]初始化，即g[i]=f(i),i=0,1,2,…,n.(2)除了g[0](即f(x0))以外，其余函數(shù)值在計(jì)算一階差商后不再使用，因此可用來(lái)存放一階差商，即

g[j]=f[xj?1,xj],j=n,n?1,…,2,1(3)類似地，計(jì)算二階差商后，除g[1]=f[x0,x1]外,其余一階差商也不再使用,可用g[j]存放二階差商f[xj?2,

xj?1,xj],

即g[j]=f[xj?2,

xj?1,xj],j=n,n?1,…,2，…(4)最后，g[n]=f[x0,

x1,

…,xn].

差商表程序1計(jì)算差商算法：

fori=0tong[i]=f(xi)fork=1ton{forj=ntokg[j]=(g[j]–g[j?1])/(xj?xj?k)}1.4埃爾米特(Hermite)

插值★Hermite插值描述：

設(shè)f(x)具有一階連續(xù)導(dǎo)數(shù)，已知節(jié)點(diǎn)上的函數(shù)值和導(dǎo)數(shù)值，即(xi,f(xi)),(xi,f‘(xi)),i=0,1,2,…,n,若存在2n+1次多項(xiàng)式H2n+1(x)滿足則稱H2n+1(x)為f(x)關(guān)于節(jié)點(diǎn){xi}(i=0,1,2,…,n)的Hermite插值多項(xiàng)式。

記f(xi)=yi,f'(xi)=mi,i=0,1,2,…,n.★三次Hermite插值的構(gòu)造存在性給定f(xi)=yi,f'(xi)=mi,i=0,1.設(shè)代入插值條件:H3(xi)=f(xi),H'3(xi)=f'(xi),i=0,1,得其解存在唯一,解出a0,a1,a2,a3,

代入即得H3(x).基函數(shù)法每個(gè)節(jié)點(diǎn)上對(duì)應(yīng)兩套基函數(shù)：x0:h0(x),g0(x);x1:h1(x),g1(x),滿足或簡(jiǎn)記為

函數(shù)值導(dǎo)數(shù)值x0x1x0x1h0(x)h1(x)g0(x)g1(x)1000010000100001先構(gòu)造h0(x),設(shè)h0(x)=(a+bx)(x?x1)2

,

為方便計(jì)算，可設(shè)由h0(x0)=1,得a=1；由所以，同理設(shè)∵h(yuǎn)0(x1)=h'0(x1)=0∵g0(x0)=g0(x1)=0,g'0(x1)=0由g'0(x0)=1,得a=1。所以注：我們知道，過(guò)x0,x1兩點(diǎn)的Lagrange插值基函數(shù)為

顯然，于是，三次Hermite插值的基函數(shù)可表為到2n+1次三次Hermite插值多項(xiàng)式為

容易驗(yàn)證，當(dāng)f(x)∈C4[a,b]時(shí),三次Hermite插值的誤差為提示：設(shè)作輔助函數(shù)

固定x∈[a,b]，則φ(t)有三個(gè)零點(diǎn)x0,x1,x,且x0,x1為二重零點(diǎn)。反復(fù)應(yīng)用Rolle定理可證。2005年9月30日★高次Hermite插值的構(gòu)造——插值基函數(shù)法

給定

n+1個(gè)節(jié)點(diǎn)

x0,x1,…,xn上的函數(shù)值

f(xi)和導(dǎo)數(shù)值

f'(xi)，可以構(gòu)造

2n+1次Hermite插值多項(xiàng)式

滿足

其中，hi(x),gi(x)分別為對(duì)應(yīng)于函數(shù)值和導(dǎo)數(shù)值的不高于

2n+1次插值基函數(shù)，它們滿足完全仿照三次Hermite插值基函數(shù)的求法，可得

容易驗(yàn)證，

Hermite插值的誤差(定理)：

當(dāng)

f(x)∈C2n+2[a,b]時(shí),則存在ζ∈(a,b),使

提示：對(duì)li(x)取對(duì)數(shù)ln，并注意li(xi)=1見(jiàn)三次基例1.8給定

f(?1)=0,f(1)=4,f'(?1)=2,f'(1)=0,求H3(x),

并計(jì)算

f(0.5).解x0=?1,

x1=1,

f(0.5)≈H3(0.5)=3.5625.例1.9給定

f(0)=1,f(1)=2,f'(0)=2,構(gòu)造二次插值函數(shù)。解(1)公式法設(shè)f'(1)=m1，有三次Hermite插值公式得，

令

m1=0，得到二次Hermite插值函數(shù)

P2(x)

=?x2+2x+1.

(2)插值基函數(shù)法設(shè)節(jié)點(diǎn)

x0上的二次基函數(shù)為t0(x),g0(x),節(jié)點(diǎn)

x1上的二次基函數(shù)為t1(x),它們滿足

設(shè)

由t0(x0)

=1,即

b(0?1)=1,得

b=?1。

由t'0(x0)

=0,即

a(0?1)+a·0+b=0,得

a=?1。所以

同理可設(shè)，

分別由條件

(3)擴(kuò)展牛頓法

寫成差商表的形式，將帶導(dǎo)數(shù)的節(jié)點(diǎn)X0及其上的函數(shù)值重復(fù)一遍，無(wú)導(dǎo)數(shù)的節(jié)點(diǎn)X1不重復(fù)，即

x

f(x)f'(x)

x001

x1012

X1

x2121?1

★擴(kuò)展牛頓法——用牛頓差商表構(gòu)造Hermite插值

給定插值點(diǎn)

(xi,f(xi),f'(xi)),i=1,2,…,n,重新定義插值節(jié)點(diǎn)序列：

z2i=z2i+1=xi,

i=0,1,2,…,n,

即函數(shù)值取相應(yīng)節(jié)點(diǎn)上的函數(shù)值,即

f(z2i)

=f(z2i+1)

=f(xi),i=0,1,2,…,n；

對(duì)于一階差商，取

以偶數(shù)節(jié)點(diǎn)開(kāi)始以奇數(shù)節(jié)點(diǎn)開(kāi)始

二階以后的各階差商，直接按差商公式計(jì)算。由此得到差商型Hermite插值公式：差商表：

z

f(z)f[zi,zj]例1.10已知

計(jì)算

f(1.36)。解x

f(x)f

'(x)1.20.61.20.60.51.40.91.5

51.40.90.7?4

?45

1.61.1

1.0

1.5

13

145

1.5分段線性插值n次Lagrange插值多項(xiàng)式的誤差：

插值多項(xiàng)式與被插函數(shù)的逼近程度同分點(diǎn)的數(shù)目和位置有關(guān)。一般地，分點(diǎn)越多，逼近程度越好，但也有例外。

例如

將[?1,1]10等分，步長(zhǎng)

h=2/10=0.2,取節(jié)點(diǎn)

xi=?1+0.2i,i=0,1,2,…,10。以

(xi,f(xi))為插值點(diǎn)，構(gòu)造L10(x)：圖示Runge現(xiàn)象

插值多項(xiàng)式在插值區(qū)間上發(fā)生劇烈的震蕩。它揭示了高次插值多項(xiàng)式存在的缺陷。產(chǎn)生的原因誤差有截?cái)嗾`差和舍入誤差兩部分組成，而在插值的計(jì)算過(guò)程中，舍入誤差可能會(huì)擴(kuò)散或放大。返回分段線性插值

給定

n+1個(gè)插值點(diǎn)：(xi,f(xi)),i=0,1,2,…,n,在每個(gè)小區(qū)間[xi,xi+1]上作線性插值，節(jié)點(diǎn)

xi,xi+1上的基函數(shù)分別為：

顯然滿足

分段線性插值為：[xi,xi+1]上

區(qū)間[a,b]上的線性插值

p(x)就是將每個(gè)小區(qū)間[xi,xi+1]上的線性插值

pi(x)連接起來(lái),p(x)為[xi,xi+1]上不高于一次的多項(xiàng)式。即p(x)的圖形是一條以

(xi,f(xi))為折點(diǎn)的折線。

用分段線性插值逼近上述例子的效果，取

n=10。Runge現(xiàn)象例1.11已知

計(jì)算

f(1.2),f(3.3).解1.6三次樣條插值函數(shù)

分段線性插值：已知節(jié)點(diǎn)上的函數(shù)值，插值函數(shù)整體續(xù)。

三次Hermite插值：已知節(jié)上的函數(shù)值和導(dǎo)數(shù)值，插值函數(shù)具有一階連續(xù)的導(dǎo)數(shù)。為了得到光滑度更高的插值函數(shù)，引入樣條插值函數(shù)?！皹訔l”名詞來(lái)源于工程中船體和汽車等的外形設(shè)計(jì)：給出外形曲線上的一組離散點(diǎn)(樣點(diǎn))，如(xi,yi)，i=0,1,2,…,n,

將有彈性的細(xì)長(zhǎng)木條或鋼條(樣條)在樣點(diǎn)上固定，使其在其它地方自由彎曲，這樣樣條所表示的曲線，稱為樣條曲線(函數(shù))。

在數(shù)學(xué)上，它表現(xiàn)為近似于一條分段的三次多項(xiàng)式，它要求在節(jié)點(diǎn)處具有一階和二階連續(xù)導(dǎo)數(shù)。

定義

給定

[a,b]上

n+1個(gè)節(jié)點(diǎn)：a=x0<x1<…<xn=b及節(jié)點(diǎn)上的函數(shù)值

f(xi)=yi,i=0,1,2,…,n,若S(x)滿足：(1)S(xi)=yi,i=0,1,…,n;(2)S(x)在[xi,xi+1]上至多是一個(gè)三次多項(xiàng)式；(3)S(x)∈C2[a,b].

則稱S(x)為

f(x)關(guān)于節(jié)點(diǎn)

x0,x1,…,xn的三次樣條插值函數(shù)，稱xi為樣條節(jié)點(diǎn)。

在[xi,xi+1]上構(gòu)造一個(gè)三次多項(xiàng)式

共有

4n個(gè)未知量，因此需要

4n個(gè)條件。由定義中的

(1)知，有n+1個(gè)條件；由定義中的(3)知，有3n?3個(gè)條件，即

再附加2個(gè)邊界條件，就可得到4n個(gè)條件。三次分段樣條插值函數(shù)可唯一確定。

M關(guān)系式：用節(jié)點(diǎn)處的二階導(dǎo)數(shù)表示樣條插值函數(shù)。

m關(guān)系式：用節(jié)點(diǎn)處的一階導(dǎo)數(shù)表示樣條插值函數(shù)。1.6.1M關(guān)系式

引入記號(hào)：∵S(x)為[xi,xi+1]上的三次多項(xiàng)式,∴

S"(x)為一次函數(shù),我們用節(jié)點(diǎn)上的二階導(dǎo)數(shù)值Mi表示線性函數(shù)。設(shè)

其中，對(duì)(1.29)積分兩次,

得將S(xi)=yi,S(xi+1)=yi+1,代入(1.30)得到二元一次方程組,解得將C，D代入(1.30)式，得到[xi,xi+1]上的三次樣條插值函數(shù)在xi點(diǎn)，左導(dǎo)數(shù)=右導(dǎo)數(shù)Back例

令

(1.32)式為

n+1個(gè)未知數(shù)

M0,M1,…,Mn

的

n-1個(gè)方程組，補(bǔ)充兩個(gè)邊界條件后，方程組(1.32)就有唯一解。

（2005-10-9）返回例1.12程序2下面給出三種邊界條件：(1)

給定

M0,Mn的值，可以得到

n-1個(gè)未知量的

n-1個(gè)方程的方程組對(duì)角占優(yōu)的三對(duì)角帶狀矩陣M0=0,Mn=0時(shí)，稱為自然邊界條件back(2)給定條件：S'(x0)=m0,S'(xn)=mn,分別由[x0,x1],[xn-1,xn]上的三次樣條插值函數(shù)

此二式和(1.32)組成

n+1個(gè)方程的方程組：（3）若f(x)為以xn-x0為周期的周期函數(shù)，即y0=yn，則要求S(x)

也為周期函數(shù)，即S(x0)=S(xn),

于是有

即

m0=mn,M0=Mn,此時(shí)(1.32)變?yōu)閚個(gè)未知量、n個(gè)方程的方程組。即為關(guān)于M0,M1,…,Mn的等式例1.12已知離散點(diǎn):

(1.1,0.4000),(1.2,0.8000),(1.4,1.6500),(1.5,1.8000),取自然邊界條件

M0=Mn=0,構(gòu)造三次樣條插值函數(shù)，并計(jì)算

f(1.25).解

n=3.

∵

h0=x1-x0=0.1,h1=0.2,h2=0.1,因此，分段的三次樣條插值函數(shù)為由(1.32)計(jì)算得From(1.31)(1.33)1.6.2m關(guān)系式

——用一階導(dǎo)數(shù)表示的樣條插值函數(shù)

給定插值點(diǎn)

(xi,yi),設(shè)S'(xi)=mi,

i=0,1,2,…,n,則

[xi,xi+1]上的三次Hermite插值為

確定出

m0,m1,…,mn,代入(1.35),可得[a,b]上的三次樣條插值令

hi=xi+1-xi,∵S(x)∈C2[a,b],對(duì)(1.35)求二階導(dǎo)數(shù)

令

x

xi+=xi+0,在

[xi,xi+1]上得到xi點(diǎn)的右導(dǎo)數(shù)，

同理，在

[xi-1,xi]上構(gòu)造三次樣條插值

S(x),在

[xi-1,xi]上得點(diǎn)xi的左導(dǎo)數(shù)，三種邊界條件：

1.7程序示例程序1

計(jì)算牛頓插值Nn(x).給定(xi,yi),i=0,1,2,…,n,xi互異。

算法描述：Step1Inputn,(xi,yi),i=0,1,2,…,n,andx;diff[j]=f(xj),j=0,1,2,…,n計(jì)算k階差商

fork=1tonforj=ntok各階差商的存儲(chǔ)Step2計(jì)算Nn(x)

形成插值基函數(shù)及插值

t=1,newton=f(x0)

對(duì)i=1,2,…,nt=(x?xi?1)·t;//(由tk=(x?xk?1)tk?

1

形成(x?x0)…

(u?xi?1)

)newton=newton+t·diff[i]

Step4

輸出牛頓插值Nn(x)=newton。Step3實(shí)現(xiàn)差商、基函數(shù)和牛頓插值

for(i=0;i<=n;i++)diff[i]=points[i].y;for(i=0;i<=n;i++){for(j=0;j>i;j--){diff[j]=(diff[j]-diff[j-1])/(points[j].x-points[j-1-i].x);}}temp=1;newton=diff[0];for(i=0;i<n;i++){temp=temp*(x-points[i].x);newton=newton+temp*diff[i+1];}程序2

計(jì)算三次樣條插值S(x)。給定(xi,yi),i=0,1,2,…,n,

xi互異;二階導(dǎo)數(shù)的端點(diǎn)值M0,Mn。

算法描述：Step1Inputn,(xi,yi),i=0,1,2,…,n,andx;Step2

計(jì)算(1.32)中的參數(shù)Step3

用追趕法求M1,M2,…,Mn-1,((5.29),(5.30))：Step4

由(1.31)式計(jì)算Step5輸出S(x)。習(xí)題1答案和提示1.1

L2(0)=3.001.2

L2(-1.2)=0.508571,L2(1.2)=2.3085711.3提示：1.4

提示1.5

提示

f(105)≈L2(105)=10.24812.1.6f(1.2)≈N2(1.2)=2.4016.

1.10

1.111.12

求得4個(gè)基函數(shù)：1.13

1.14同理得第2章數(shù)值微分和數(shù)值積分2.1

數(shù)值微分2.2

數(shù)值積分2.3

復(fù)化數(shù)值積分2.4

重積分計(jì)算2.5

高斯型積分公式2.6

程序示例2.1數(shù)值微分導(dǎo)數(shù)與差商的關(guān)系

數(shù)值微分取成導(dǎo)數(shù)的近似值，即差商。2.1.1差商型數(shù)值微分?jǐn)?shù)值微分用向前差商表示

截?cái)嗾`差：用Taylor展式，存在ζ∈[x0,x0+h]，數(shù)值微分用向后差商表示

同理得截?cái)嗾`差數(shù)值微分用中心差商表示

截?cái)嗾`差：由Taylor展式，數(shù)值微分的幾何意義設(shè)定最佳步長(zhǎng)

計(jì)算數(shù)值微分時(shí)產(chǎn)生的誤差有截?cái)嗾`差和舍入誤差兩部分組成。由數(shù)值微分公式產(chǎn)生截?cái)嗾`差，有原始數(shù)據(jù)產(chǎn)生舍入誤差。一般情況，步長(zhǎng)h越小，誤差也越小，但步長(zhǎng)太小，會(huì)引起誤差的增長(zhǎng)。因此，實(shí)際計(jì)算時(shí)，需要選擇一個(gè)最佳步長(zhǎng)。用中心差商分析數(shù)值微分的誤差。

①截?cái)嗾`差：

∵f(x0-h)≈f(x0+h)有效數(shù)字嚴(yán)重?fù)p失②舍入誤差：

設(shè)e

為計(jì)算f(x0-h)和f(x0+h)時(shí)的最大舍入誤差，可以證明，舍入誤差量不超過(guò)e/h。于是得到計(jì)算數(shù)值微分的總誤差為實(shí)際計(jì)算中，采用事后估計(jì)方法來(lái)選去步長(zhǎng)h/2：若h越小，舍入誤差越大，并產(chǎn)生病態(tài)D(h)表示數(shù)值微分計(jì)算公式例2.2對(duì)函數(shù)y=ex,選取不同的步長(zhǎng)進(jìn)行計(jì)算f

'(1.15),觀察

誤差的變化規(guī)律，確定最佳步長(zhǎng)。解用中心差商表示的數(shù)值微分計(jì)算公式得到：

h

f

'(1.15)errorh

f'(1.15)error

0.13.1630-0.00480.053.1590

-0.00080.093.1622-0.00400.04

3.1588

-0.00060.083.1613-0.00310.033.1583-0.00010.073.1607-0.00250.023.15750.00070.063.1600-0.00180.013.15500.0032實(shí)際計(jì)算時(shí)，準(zhǔn)確誤差難以得到，∵|D(0.05)-D(0.04)|<ε,其中，ε

=2×10-4最小。所以取h

=0.04。2.1.2差值型數(shù)值微分

給定(xi,f(xi)),i=0,1,2,…,n,構(gòu)造Ln(x),則代入節(jié)點(diǎn)xj,j=0,1,2,…,n,得到例2.3

給定三個(gè)差值點(diǎn)(xi,f(xi)),i=0,1,2,求過(guò)三個(gè)節(jié)點(diǎn)的數(shù)

值微分。解記將x=xi代入f'(x),得到三點(diǎn)數(shù)值微分公式：取n=2，由(2.5)1式，得三點(diǎn)公式的截?cái)嗾`差分別為：將f(x1)和f(x2)在x0點(diǎn)Taylor展開(kāi)，也可得截?cái)嗾`差為O(h2)。2.1.3樣條插值數(shù)值微分

給定差值點(diǎn)(xi,f(xi)),假定S'(xi)=mi,i=0,1,2,…,n,由“m關(guān)系式”得三次樣條插值函數(shù)：mi由“m關(guān)系式”確定的方程組求得。2.2數(shù)值積分

數(shù)值積分是用來(lái)求解定積分中被積函數(shù)是以離散點(diǎn)形式(xi,f(xi))給出；或被積函數(shù)無(wú)法求出的情形。它是定積分計(jì)算的一種近似方法。在微積分中，定積分是Riemann和的極限，即

數(shù)值積分就是取定積分極限中的有限項(xiàng)的和，即其中，xi稱為積分節(jié)點(diǎn),αi

稱為積分系數(shù)。

我們的任務(wù)就是確定積分系數(shù)αi

，使I(f)≈In(f)。具體地，就是用插值多項(xiàng)式近似代替被積函數(shù)f(x)來(lái)確定αi。

★代數(shù)精度

設(shè)[a,b]上以xi為積分節(jié)點(diǎn)的數(shù)值積分公式為若對(duì)任意次數(shù)不超過(guò)m次的多項(xiàng)式成立

In(xk)=I(xk),k=0,1,2,…,m,

而對(duì)m+1次多項(xiàng)式有In(xm+1)≠

I(xm+1),

則稱公式In(f)具有m階代數(shù)精度。

顯然，對(duì)任意次數(shù)不超過(guò)m

次的多項(xiàng)式f(x)有，

In(f)=I(f)。2.2.1插值型數(shù)值微分

給定[a,b]上的點(diǎn)列(xi,f(xi)),i=0,1,2,…,n,構(gòu)造Ln(x),則

注

對(duì)于一般的函數(shù)f(x)，En(f)≠0,但若f(x)為次數(shù)小于

n的多項(xiàng)式時(shí)，因?yàn)閒(n+1)(x)=0,∴En(f)=0。因此

n次插值多項(xiàng)式形式的數(shù)值積分公式至少有n階代數(shù)精度。

例2.4建立[0,2]上節(jié)點(diǎn)為x0=0,x1=0.5,x2=2的數(shù)值積分公式。

解n=2，I2(f)=α0

f(x0)+α1

f(x1)+α2

f(x2).

因?yàn)閿?shù)值積分公式為:2.2.2Newton-Cotes積分

將[a,b]n等分，步長(zhǎng)h=(b-a)/n,等分節(jié)點(diǎn)xi=a+ih

(i=0,1,2,…,n)作為數(shù)值積分節(jié)點(diǎn)，構(gòu)造Lagrange插值多項(xiàng)式Ln(x)：稱(*)式為“Newton-Cotes積分”。其中，

稱為Newton-Cotes積分系數(shù)?！锾菪畏e分公式(n=1)

以(a,f(a))和(b,f(b))構(gòu)造線性插值L1(x):

其中，稱為Newton-Cotes積分系數(shù)。于是得梯形積分公式：

如果被積函數(shù)分別用f(a),f(b)和

f((a+b)/2)來(lái)代替，可分別得到左矩形、右矩形和中心矩形積分公式：幾何意義:

梯形積分公式的代數(shù)精度：分別取f(x)=x,x2，則

所以，代數(shù)精度為1。

截?cái)嗾`差：已知線性插值的截?cái)嗾`差為

積分中值定理：連續(xù)、不變號(hào)★辛普森(Simpson)積分公式(n=2)

將[a,b]2

等分，等分節(jié)點(diǎn)x0

=a，x1

=(a+b)/2，x2

=b作為積分節(jié)點(diǎn)，構(gòu)造二次Lagrange插值多項(xiàng)式L2(x)：Newton-Cotes積分系數(shù)為：Simpson積分公式為代數(shù)精度：驗(yàn)證分別將f(x)=1,x,x2,x3將代入(2.8)，有所以，Simpson積分公式的代數(shù)精度為3。幾何意義：Simpson積分公式的截?cái)嗾`差（定理）：證明因?yàn)樵摴降拇鷶?shù)精度為3，為了應(yīng)用該公式，我們可以構(gòu)造一個(gè)三次插值多項(xiàng)式