《計(jì)算方法》教案

課程名稱：計(jì)算方法

適用專業(yè)：醫(yī)學(xué)信息技術(shù)

適用年級(jí)：二年級(jí)_______

任課教師：張利萍

編寫(xiě)時(shí)間：2011年8月

新疆醫(yī)科大學(xué)工程學(xué)院張利萍

教案目錄

《計(jì)算方法》教學(xué)大綱.................................4

一、課程的性質(zhì)與任務(wù)........................................................4

二、課程的教學(xué)內(nèi)容、基本要求及學(xué)時(shí)分配.....................................4

三、課程改革與特色..........................................................5

四、推薦教材及參考書(shū)........................................................5

《計(jì)算方法》教學(xué)日歷.................錯(cuò)誤!未定義書(shū)簽。

第一章緒論...........................................6

第1講緒論有效數(shù)字........................................................6

第2講誤差...............................................................

第二章線性方程組的直接法............................14

第3講直接法、高斯消去法..................................................14

第4講高斯列主元消去法....................................................22

第5講平方根法、追趕法....................................................29

第三章插值法與最小二乘法...........................31

第6講機(jī)械求積、插值型求積公式...........................................32

第7講牛頓柯特斯公式、復(fù)化求積公式.......................................37

第8講高斯公式、數(shù)值微分..................................................42

第9講

第10講

第12講

第四章數(shù)值積分與數(shù)值微分...........................48

第11講歐拉公式、改進(jìn)的歐拉公式..........................................48

第12講龍格庫(kù)塔方法、亞當(dāng)姆斯方法........................................52

第13講收斂性與穩(wěn)定性、方程組與高階方程..................................56

第14講

第15講

第五章微分常微分方程的差分方法.....................59

第16講迭代收斂性與迭代加速...............................................60

第17講牛頓法、弦截法.....................................................64

第18講

第19講

第20講

第六章線性方程組的迭代法...........................67

第21講迭代公式的建立...................................................68

2

第22講

第23講

第24講向量范數(shù)、迭代收斂性71

第25講

3

《計(jì)算方法》教學(xué)大綱

課程名稱：計(jì)算方法/ComputerNumericalAnalysisB

學(xué)時(shí)/學(xué)分：54/4

先修課程：高等數(shù)學(xué)、線性代數(shù)、高級(jí)語(yǔ)言程序設(shè)計(jì)（如：Matlab語(yǔ)言）

適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、信息管理與信息系統(tǒng)

開(kāi)課學(xué)院（部）、系（教研室）：醫(yī)學(xué)工程技術(shù)學(xué)院、醫(yī)學(xué)信息技術(shù)專業(yè)

一、課程的性質(zhì)與任務(wù)

計(jì)算方法是一門專業(yè)必修課。當(dāng)前，由于科學(xué)技術(shù)的快速發(fā)展和計(jì)算機(jī)的廣泛應(yīng)用，

學(xué)習(xí)和掌握計(jì)算機(jī)上常用的數(shù)值計(jì)算方法及有關(guān)的基礎(chǔ)理論知識(shí),并能用某種高級(jí)語(yǔ)言（如

Matlab語(yǔ)言）將這些常用算法編程實(shí)現(xiàn)，這對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來(lái)說(shuō)是非常重要的。

本課程著重介紹進(jìn)行科學(xué)建設(shè)所必須掌握的一些最基本、最常用的算法，向高等院校

有關(guān)專業(yè)的學(xué)生普及計(jì)算方法的知識(shí).

二、課程的教學(xué)內(nèi)容、基本要求及學(xué)時(shí)分配

（一）教學(xué)內(nèi)容

1.引論

數(shù)值分析的研究對(duì)象、誤差及有關(guān)概念、數(shù)值計(jì)算中應(yīng)注意的一些原則。

2.線性代數(shù)方程組的數(shù)值解法

Gauss消去法、Gauss消去法的矩陣形式、主元消去法、三角分解法、迭代法、迭代法

的收斂條件及誤差估計(jì)。

3.插值方法

Lagrange插值、Newton插值、分段插值、Hermite插值、三次樣條插值、數(shù)據(jù)擬合的

最小二乘法。

4.數(shù)值積分與微分

機(jī)械求積、Newton-Cotes求積公式、復(fù)化求積、Romberg求積算法、Gauss求積公式、

數(shù)值微分。

5.常微分方程初值問(wèn)題的數(shù)值解法

Euler方法及其改進(jìn)、龍格-庫(kù)塔（Runge-Kulta）方法、線性多步法、收斂性與穩(wěn)定性、

一階方程組與高階方程。

6.方程求根的數(shù)值方法

二分法、迭代法、迭代過(guò)程的加速、Newton迭代法、Newton迭代法的幾種變形。

（二）基本要求

1.了解數(shù)值分析的研究對(duì)象、掌握誤差及有關(guān)概念。

2.正確理解使用數(shù)值方法求方程的解的基本思想、數(shù)學(xué)原理、算法設(shè)計(jì)。

3.了解插值是數(shù)值逼近的重要方法之一，正確理解每一種算法的基本思想、計(jì)算公式、

算法設(shè)計(jì)、程序框圖設(shè)計(jì)和源程序。

4.掌握數(shù)值積分的數(shù)學(xué)原理和程序設(shè)計(jì)方法。

5.能夠使用數(shù)值方法解決一價(jià)常微分方程的初值問(wèn)題。

6.理解和掌握使用數(shù)值方法對(duì)線性方程組求解的算法設(shè)計(jì)。

（三）學(xué)時(shí)分配

本課程的理論教學(xué)時(shí)數(shù)為54學(xué)時(shí)分配如下表:

速學(xué)環(huán)節(jié)

課程輻、、、學(xué)時(shí)講課

引論4

線性代數(shù)方程組的數(shù)值解法6

插值方法12

數(shù)值積分與微分10

常微分方程初值問(wèn)題的數(shù)值解法10

方程求根的數(shù)值方法10

總復(fù)習(xí)2

合計(jì)54

（四）課程內(nèi)容的重點(diǎn)、難點(diǎn)

重點(diǎn)：Lagrange插值、Newton插值、分段插值、Heimite插值、三次樣條插值、機(jī)械

求積、Newlon-Coies求積公式、復(fù)化求積、Romberg求積算法。

難點(diǎn)：Gauss消去法、Gauss消去法的矩陣形式、主元消去法、三角分解法、迭代法、

迭代法的收斂條件及誤差估計(jì)。

三、課程改革與特色

本課程是一門重要的專業(yè)基礎(chǔ)課。數(shù)值計(jì)算方法既是一門古老的學(xué)科，又是一門新興

的學(xué)科。電子計(jì)算機(jī)的產(chǎn)生和發(fā)展極大地促進(jìn)了數(shù)值計(jì)算方法的發(fā)展。只有把數(shù)值計(jì)算方

法和程序設(shè)計(jì)緊密結(jié)合起來(lái)，把算法變?yōu)橛?jì)算機(jī)能直接執(zhí)行的程序，才能真正使計(jì)算機(jī)幫

助人們解決各種復(fù)雜的計(jì)算任務(wù)。

本課程試圖將數(shù)值計(jì)算方法和程序設(shè)計(jì)方法學(xué)融為一體，這也是一種嘗試。

四、推薦教材及參考書(shū)

推薦教材：《計(jì)算機(jī)數(shù)值方法》（第三版），主編：施吉林、劉淑珍、陳桂芝，出版社:

高等教育出版社，出版時(shí)間：2005年3月

參考書(shū)：

《數(shù)值計(jì)算方法和算法》，主編：張韻華、奚梅成、陳效群，出版社：科學(xué)出版社，出

版時(shí)間：2002年3月

《NumericalAnalysis》，主編：RichardL.Burden,出版社：高等教育出版社影印，出

版或修訂時(shí)間：2003

《數(shù)值分析》，主編：金聰、、熊盛武，出版社：武漢理工大學(xué)出版社，出版時(shí)間：2003

年8月

5

第一章緒論

一、教學(xué)目標(biāo)及基本要求

通過(guò)對(duì)本章的學(xué)習(xí)，使學(xué)生對(duì)了解涉及工程和科學(xué)實(shí)驗(yàn)中常見(jiàn)的數(shù)學(xué)問(wèn)題，其中包括

線性方程組、函數(shù)插值、離散數(shù)據(jù)的擬合、微積分、微分方程等，這些問(wèn)題是其他數(shù)學(xué)問(wèn)

題的基礎(chǔ)。

二、教學(xué)內(nèi)容及學(xué)時(shí)分配

本章主要介紹數(shù)值分析的研究對(duì)象及誤差的概念。具體內(nèi)容如下：

第1-2學(xué)時(shí)講授內(nèi)容：計(jì)算方法的研究?jī)?nèi)容、對(duì)象與特點(diǎn)；誤差的基本概念。

三、教學(xué)重點(diǎn)難點(diǎn)

1.教學(xué)重點(diǎn)：誤差、誤差種類：誤差分析：誤差與有效數(shù)字的關(guān)系.

2.教學(xué)難點(diǎn)：誤差分析、誤差與有效數(shù)字的關(guān)系。

四、教學(xué)中應(yīng)注意的問(wèn)題

多媒體課堂教學(xué)為主。適當(dāng)提問(wèn)，加深學(xué)生對(duì)概念的理解。

第1講緒論

基本求解步驟

編程上機(jī)

計(jì)算結(jié)果

數(shù)學(xué)模型是通過(guò)科學(xué)實(shí)驗(yàn)或者觀察分析一系列數(shù)據(jù)后，用數(shù)學(xué)作為工具近似地描述客觀事

物的一種數(shù)學(xué)表達(dá)式。在數(shù)學(xué)模型中，往往包含了若干參量，這些物理參數(shù)通常由實(shí)驗(yàn)儀

器測(cè)得，根據(jù)儀器的精密程度，物理參數(shù)的確定也會(huì)產(chǎn)生一定的誤差。

在建立了數(shù)學(xué)模型之后，并不能立刻用計(jì)算機(jī)直接求解，還必須尋找用計(jì)算機(jī)計(jì)算這些數(shù)

學(xué)模型的數(shù)值方法，即將數(shù)學(xué)模型中的連續(xù)變量離散化，轉(zhuǎn)化成一系列相應(yīng)的算法步驟，

編制出正確的計(jì)算程序，再上機(jī)計(jì)算得出滿意的數(shù)值結(jié)果。

算法：從給定的已知量出發(fā)，經(jīng)過(guò)有限次四則運(yùn)算及規(guī)定的運(yùn)算順序，最后求出未知量的

數(shù)值解，這樣構(gòu)成的完整計(jì)算步驟稱為算法。

計(jì)算多項(xiàng)式p(x)=31+4x2-2x+6的值。

算法1：由X計(jì)算出x',3后再進(jìn)行計(jì)算。

需乘法5次，加法3次。

6

〃(x)=x[x(3x+4)—2J+6

需乘法3次，加法3次。

一般地，計(jì)算n次多項(xiàng)式的值

nnx

巴(%)=anx+an_xx~+…++4

P_,、?i〃(〃+i)

如若按4"1有14次乘法運(yùn)算，計(jì)算K(x)共需"2++〃=1—次乘法和〃次加

法運(yùn)算。

采用：秦九韶算法(1247)有遞推公式：

%)=工(舊.《(『+%)+噎+.+4)+%從內(nèi)往外一層一層計(jì)算，社巳表示第k層

以=(...(atlx+a,^)x+...+an_k.x)x+an_k

[匕=%TX+4T

Vo=4

需乘法n次，加法n次，存儲(chǔ)單元n+3個(gè)。

對(duì)算法所要考慮的問(wèn)題,包括如下：

?計(jì)算速度

例如，求解一個(gè)20階線性方程組，用消元法需3000次乘法運(yùn)算；而用克萊姆法則要進(jìn)行

9.7X1O20次運(yùn)算,如用每秒1億次乘法運(yùn)算的計(jì)算機(jī)要30萬(wàn)年。

7

?存儲(chǔ)量

大型問(wèn)題必要考慮計(jì)算機(jī)的數(shù)據(jù)存貯。

?數(shù)值穩(wěn)定性

在大量計(jì)算中,舍入誤差是積累還是能控制,這與算法有關(guān)。

實(shí)際算法往往表現(xiàn)為某種無(wú)窮遞推過(guò)程

算法的精度控制

方程根的二分法求解

/(幻在［〃,切上單調(diào)連續(xù)，f(a)f(b)<0,根據(jù)連續(xù)函數(shù)性質(zhì)，/(處在［?力內(nèi)一定有實(shí)的零點(diǎn),

即方程〃幻=0在［。,川內(nèi)一定有唯一實(shí)根。解實(shí)根為/

若/(/)=0,則%為所求根

否則若f(a)J(Xo)<。，則根在區(qū)間［。，須)］，取q=x0

若/S)/(%)<0,則根在區(qū)間島，勿，取4=Xo，b［=b

[a,b]n[?1，/?!]z>...n[ak,bk]Tt...

每一區(qū)間為前一區(qū)間的一半，有根區(qū)間［4,4］長(zhǎng)度%一見(jiàn)=-(b-a)

2

,一(4

§1.2預(yù)備知識(shí)和誤差

(1)誤差的來(lái)源

實(shí)際問(wèn)題"建立數(shù)學(xué)模型”研究計(jì)算方法》編程上機(jī)計(jì)算解結(jié)果。

模型誤差：在建立數(shù)學(xué)模型過(guò)程中,不可能將所有因素均考慮,必然要進(jìn)行必要的簡(jiǎn)化,這

就帶來(lái)了與實(shí)際問(wèn)題的誤差。

測(cè)量誤差：測(cè)量已知參數(shù)時(shí)，數(shù)據(jù)帶來(lái)的誤差。

截?cái)嗾`差：模型的準(zhǔn)確解與某種數(shù)值方法的準(zhǔn)確解之間的誤差稱為截?cái)嗾`差或方法誤差。

舍入誤差：計(jì)算機(jī)的字長(zhǎng)是有限的,每一步運(yùn)算均需四舍五入，由此產(chǎn)出的誤差稱舍入誤

差。如：n.1/3,……取小數(shù)點(diǎn)8位、16位。

［截?cái)嗾`差的實(shí)例］

21一+

己知e"=1+x+—X4--"3+?..+------X十

2!7i!

求e-的近似值，并估計(jì)誤差。

解：利用展開(kāi)式的前三項(xiàng)，取n=2,

6T?14-(-1)4-1(-1)2=0.5

由Qy如公式:

/(x)=f(x0)+/'(x0)(x-x(l)+

+k(i。-即a-"

8

"+l

=Ov?<1

5+1)!

\R\=Ie-1-O.S|^—<1.7*IO-1

213!截?cái)嗾`差為：0.17

［舍入誤差的實(shí)例］

1.492x1.066=1.590472,設(shè)在一臺(tái)虛構(gòu)的4位數(shù)字的計(jì)算機(jī)上計(jì)算

1.492x1.066?1.590,舍入誤差為0.000472。

數(shù)值計(jì)算方法主要討論截?cái)嗾`差和舍入誤差的影響，不討論模型誤差和測(cè)量誤差。

三、誤差的基本概念

(1)誤差與誤差限

誤差不可避免，設(shè)以工代表數(shù)K*的近似值，稱《二”一/是近似值大的絕對(duì)誤差。簡(jiǎn)稱誤

差。誤差是有量綱的，可正可負(fù)。

誤差通常是無(wú)法計(jì)算的，但可以估計(jì)出它的一個(gè)上界。即

卜一‘稱￡是近似值X的誤差限，或稱精度，即

**

X-8<x<x+8

O

(2)相對(duì)誤差與相對(duì)誤差限

e_x*—x

絕對(duì)誤差并不能完全反應(yīng)精度，稱?-X為近似值x的相對(duì)誤差，記作。相對(duì)

誤差是個(gè)相對(duì)數(shù),是無(wú)量綱的,也可正可負(fù)。

相對(duì)誤差的估計(jì)圖",「，稱￡，為相對(duì)誤差限，即

(3)有效數(shù)字

定義：如果近似值X的誤差限是3(某一數(shù)位的半個(gè)單位)，則稱X準(zhǔn)確到小數(shù)點(diǎn)后n

位,并從第一個(gè)非零的數(shù)字到這一位的所有數(shù)字均為有效數(shù)字。

如：n=3.1415926535,

3.14有三位有效數(shù)字,誤差限e=0.005;

3.1416有五位有效數(shù)字,誤差限為0.00005o

(4)有效數(shù)字與誤差限的關(guān)系：

x有n位有效數(shù)字，標(biāo)準(zhǔn)形式為.x=±KTx0.生生…%其中a(i=l,2,…)是0~9之間的

整數(shù)，且qW0,如果誤差|x-x|<^xl(F"JV/V〃，稱x為/的具有1位有效數(shù)值的

近似值.

(5)有效數(shù)字與相對(duì)誤差的關(guān)系：

9

標(biāo)準(zhǔn)形式為x=±UTxO.q/…耳，則:

M

a)若寸有〃位有效數(shù)字，J_xio'-

kI2q

1.?10止"

品甯WxlO1

若邑？!<一!一xio?

b)以12(4+1)，則x"有〃位有效數(shù)字

,n

證:lx-x*-----------x10l-nxx*|4―!—x10~x(a.+l)x10-'=-x10*”

112(4+1)2(q+l)'2

例，已知乃=3.14159265..,試問(wèn)其近似值內(nèi)=3.1,x2=3.14,x3=3.1415,A:3=3.1416

各有幾位有效數(shù)字？并給出它們的誤差限和相對(duì)誤差限。

e,=|^-^|?0.04<^10十分位以前都是有效數(shù)字，有兩位有效數(shù)字

1-2",

e\r-<—xlO=-xl0

2x36

?=歸一々核0.002<-xl02有三位有效數(shù)字

年一天|<^—XlO1-3=-xl0-2

2x36

3

|^--x3|?0.00009<^xl0-,有四位有效數(shù)字

<—!—xio1-4=-xio-3

，「

22x36

/=年一%|。0.00001<^xW4,有五位有效數(shù)字

^,叱小叱

例：為使二*的相對(duì)誤差小于0.001%,至少應(yīng)取幾位有效數(shù)字?

解:

￡「M」一XlO-1<0.001%

2al

〃>6—k)g6,即〃之6,取〃=6,則"*=3.14159

10

§1.3數(shù)值計(jì)算的若干原則

1,避免兩相近數(shù)相減

當(dāng)x較大時(shí)，計(jì)算工T-6，可先轉(zhuǎn)化為'-6=-^J—尸

VX+I4-VX

/(x)=G&x=2得導(dǎo)數(shù)值f⑵X,2+%二J2i,精確值尸Q)=0.353553

2%

人k八［組，”\V2+^-V2^A1.4491-1.3784n_?.n

令h=0.1得/(2)=-----------------------?------------------------?0.35350

2h0.2

人」AAAA,田V2+A-V2^h1.4142-1.4142八

令h=0.0001得f(2)*-----------------------a------------------------=0

2h0.0002

計(jì)算"c°s*,x=l,分子出現(xiàn)相近數(shù)相減，可轉(zhuǎn)換為

sinx

1—cosxsinxh、、a

—；----=--------,再計(jì)算

sinx1-cosx

2.避免絕對(duì)值太小的數(shù)做除數(shù)

分母接近零的數(shù)會(huì)產(chǎn)生溢出錯(cuò)誤,因而產(chǎn)生大的誤差,此時(shí)可以用數(shù)學(xué)公式化簡(jiǎn)后再做.

V=,___],_==ViooT+Viooo

Viooi-Viooo

3.要防止大數(shù)“吃掉”小數(shù)

計(jì)算機(jī)在進(jìn)行算術(shù)計(jì)算時(shí)，首先要把參加運(yùn)算的數(shù)對(duì)階，即把兩數(shù)都寫(xiě)成絕對(duì)值小于1,而

階碼相同的數(shù)。如：%=1。9+1必須改寫(xiě)成：x=0.1x1()1°+0.0000000001x1010如果

計(jì)算機(jī)只能表示8位小數(shù)，則算出xnO.lxlOio,大數(shù)吃掉了小數(shù)。這種情形是要盡量避

免的。

4.簡(jiǎn)化計(jì)算步驟，提高計(jì)算效率

簡(jiǎn)化計(jì)算步躲是提高程序執(zhí)行速度的關(guān)鍵，它不僅可以節(jié)省時(shí)間，還能減少舍入誤差。

例4：設(shè)A、B、C、D分別是10x20、20x50、50x1、1x100的矩陣，試按不同的算法求

矩陣乘積E=ABCD.

解：由矩陣乘法的結(jié)合律，可有如下算法

1.E=((AB)C)D.計(jì)算量N=11500flop

2.E=A(B(CD)).計(jì)算量N=125000flop

3.E=(A(BC))D.計(jì)算量N=2200flop

5.要使用數(shù)值穩(wěn)定的算法

我們已經(jīng)知道，所謂算法的穩(wěn)定性，是指誤差的傳播可以得到控制，在用計(jì)算機(jī)解決實(shí)際

問(wèn)題時(shí)，運(yùn)算次數(shù)成千上萬(wàn)。如果誤差的傳播得不到控制，那么誤差的累積會(huì)使問(wèn)題的解

答成為荒謬的，尤其是某些病態(tài)問(wèn)題(如病態(tài)方程組)，舍入誤差對(duì)其計(jì)算結(jié)果往往有非常

嚴(yán)重的影響。因此，在選擇計(jì)算方案時(shí)，要特別謹(jǐn)慎。

考察方程組

11

11

3~6

13

x解為X]=1,電=1,X=1

242n3

JX347

34560

四舍五入系數(shù)后，解為M=1.09,%=0-484，%3=149

盡管系數(shù)變動(dòng)不大，但求出得解卻變動(dòng)很大，這類問(wèn)題稱為病態(tài)的。

例：蝴蝶效應(yīng)（氣象學(xué)家洛倫茲，1963）

——南美洲亞馬孫河流域熱帶雨林中的一只蝴蝶翅膀一拍，偶爾扇動(dòng)幾下翅膀，可能在兩

周后引起美國(guó)德克薩斯引起一場(chǎng)龍卷風(fēng)？！

12

13

第二章插值法

一、教學(xué)目標(biāo)及基本要求

通過(guò)對(duì)本章的學(xué)習(xí)，使學(xué)生掌握插值法計(jì)算常見(jiàn)的數(shù)學(xué)問(wèn)題。

二、教學(xué)內(nèi)容及學(xué)時(shí)分配

本章主要介紹數(shù)值分析的插值法。具體內(nèi)容如下：

第3-4學(xué)時(shí)講授內(nèi)容：?jiǎn)栴}的提法、拉格朗日插值公式。第5-6學(xué)時(shí)講授內(nèi)容：插值

余項(xiàng)、牛頓插值公式。第7-8學(xué)時(shí)講授內(nèi)容：曲線擬合。

三、教學(xué)重點(diǎn)難點(diǎn)

1.教學(xué)重點(diǎn)：插值方法的由來(lái)、拉格朗日插值公式、牛頓插值公式、曲線擬合。

2.教學(xué)難點(diǎn)：拉格朗口插值公式、牛頓插值公式。

四、教學(xué)中應(yīng)注意的問(wèn)題

多媒體課堂教學(xué)為主。適當(dāng)提問(wèn)，加深學(xué)生對(duì)概念的理解。

第2講拉格朗日插值公式

眾所周知，反映自然規(guī)律的數(shù)量關(guān)系的函數(shù)有三種表示方法：

A.解析表達(dá)式

f(x)=x3-2x-5

(開(kāi)普勒(Kepler)方程)％=>一esiny.。

懸鏈線方程：y=4cos(x")。

B.圖象法

C.表格法

14

Xy

0.924-0.008513725

0.928-0.003822324

09320.000343434

0.9360.005532443

0.9400.012976643

1、插值法對(duì)于一組離散點(diǎn)（％J（X））,（，=0,1,2,...,〃），選定一個(gè)便于計(jì)算的簡(jiǎn)單

函數(shù)P（M，如多項(xiàng)式函數(shù)，要求尸㈤滿足「區(qū)）=/（茗），由此確定函數(shù)P（幻作

為*幻的近似函數(shù)，然后通過(guò)處理P（幻獲得關(guān)于《幻的結(jié)果。這就是插值方法。

2、曲線擬合選定近似函數(shù)P㈤時(shí)，不要求近似函數(shù)P（刈必須滿足

尸（七）=/（匕），而只要求在某種意義下（最小二乘法原理），使近似函數(shù)尸⑶在

這些點(diǎn)上的總偏差量最小，這類方法成為曲線擬合。

§1.1多項(xiàng)式插值問(wèn)題的一般提法

1插值法的概念：

假設(shè)函數(shù)尸f（x）是［46］上的實(shí)值函數(shù)，的用,…,為是5］上加1個(gè)互異的

點(diǎn)，f（x）在這些點(diǎn)上的取值分別為必，兒…,以

求一個(gè)確定的函數(shù)尸（才），使之滿足：

產(chǎn)（%）二%（/=0,1,2,-,n）（1）

稱沏為,“.,心為插值節(jié)點(diǎn)，關(guān)系式⑴稱為插值原則，函數(shù)PG）稱為函數(shù)y￥（x）

的插值函數(shù)，區(qū)間［為3稱為插值區(qū)間。

2泰勒插值：

人們熟悉的泰勒展開(kāi)方法其實(shí)就是一種插值方法，泰勒多項(xiàng)式：

23=/*0）+/'（元0）*-/）+-。0）2+.?.+―/）"（1）

'2I!T%）r,v.，％

與刈在點(diǎn)與鄰近會(huì)很好的逼近f（x）o

泰勒余項(xiàng)定理：

定理1假設(shè)《刈在含有點(diǎn)%的區(qū)間［a,b］內(nèi)有直到n+1階導(dǎo)數(shù)，則當(dāng)

例時(shí)，對(duì)于式（1）給出的匕⑴，成立

/（幻一X。嚴(yán)

（〃+1）!

15

其中J介于與與X之間，因而J￡[〃,/?]。

所謂泰勒插值指下述問(wèn)題：

問(wèn)題1求作n次多項(xiàng)式月⑴,使?jié)M足？，?)=帶),％=0,1,2,…刀，端為

一組已給數(shù)據(jù)。

易看出，上述插值問(wèn)題的解就是泰勒多項(xiàng)式(l)o

例1例題分析：

求作力幻=正在/=100的一次和二次泰勒多項(xiàng)式，利用它們計(jì)算斤的近似

值并估算誤差。

解：

l/23/2-5/2

fix)=4x,f'(x)=^x~ff"(x)=^-X~,/"W=|x

248

/xJ=10,/'(xo)=l/2O,/"(/)=-1/4000,/優(yōu))=3/8000000

yw=正在/=IOO的一次泰勒多項(xiàng)式是

6(X)=/(%)+,尸(/Xx-X(J=5+0.05X

7=115時(shí)Vil?=/(115)?^(x)=10.75

根據(jù)定理1可估計(jì)誤差

22

|/(x)-Pi(x)|="(x-A0)<，；(x-x0)<0.028125<0.05

誤差小于十分位的一半，故十分位及前面的數(shù)字為有效數(shù)字，所以結(jié)果有三

位有效數(shù)字。

修正R(x)可進(jìn)一步得到二次泰勒公式

鳥(niǎo)(幻=《。)+^^。一%)2

VH5=/(115)?^(x)=10.75-0.028125=10.721875

,-,|/"'(X0)|--Q

3

,(x)—P2(x)|=l2。_/)<]-(X-x0)<0.0006328125<0.005

誤差小于百分位的一半，故百分位及前面的數(shù)字為有效數(shù)字，所以結(jié)果有四

位有效數(shù)字。

泰勒插值是一種有效的插值方法，對(duì)函數(shù)要求嚴(yán)格(要足夠光滑，存在高階

導(dǎo)數(shù))，要計(jì)算函數(shù)的高階導(dǎo)數(shù)，而高階導(dǎo)數(shù)的計(jì)算對(duì)計(jì)算機(jī)來(lái)說(shuō)就很困難；

另外，計(jì)算過(guò)程不能形成機(jī)械重復(fù)的過(guò)程，不利于計(jì)算機(jī)程序?qū)崿F(xiàn)。

§1.2拉格朗日(Lagrange)插值

1多項(xiàng)式插值的存在惟一性：

多項(xiàng)式導(dǎo)數(shù)易于計(jì)算，函數(shù)表達(dá)式簡(jiǎn)單，計(jì)算機(jī)易于計(jì)算，故考慮用多項(xiàng)式

函數(shù)彳型插值函數(shù)來(lái)模擬實(shí)色函數(shù)。

從如下數(shù)據(jù)表著手,并假定七。?！抖?4

X：XoX\X2...尤〃

y-yoyiy?...y〃

16

求〃次多項(xiàng)式々（］）=〃0+&11+...+々〃］：使得：

P（x）=yi（2=0,1,2,???,n）。

根據(jù)插值條件，有：

P（M）=%+。用+…+4石=%

P（$）=%+4%+…+ax；=%

<n

P區(qū)）二旬+4升+…+=yn（i）

顯然，這是一個(gè)關(guān)于。。，弓-一〃〃的〃丹元線性方程組，其系數(shù)矩陣的行

列式為

1玉）…玉）

匕（/，2，…，5）=：）7

1士…<

/?1rxV（x,x,???,%?）=n（x；-x；）0

注意到插值節(jié)點(diǎn)必"=1，2,…，〃）兩兩相異，而"ft0MX"'

故方程組（1）有惟一解，4，???"〃，于是滿足插值條件的多項(xiàng)式存在且惟一。

定理由加1個(gè)不同插值節(jié)點(diǎn)％，*1，???，工〃可以惟一確定一個(gè)n次多項(xiàng)式

匕（元）=%+4工+???+滿足插值條件Pn（N）=yo

從理論上說(shuō)，由方程組（1）可以求出〃。，4,…〃〃的惟一解，從而確定?（回。但

從數(shù)值計(jì)算上看，當(dāng)〃較大時(shí)求解線性方程組的工作量較大且不便應(yīng)用。

解方程組（1）需計(jì)算n+1個(gè)n階行列式，每個(gè)n階行列式為n!項(xiàng)之和，每

項(xiàng)乂是n個(gè)元素的乘積，需n-1次乘法，所以求解需要（〃+1）〃!（〃-1）次乘法，

當(dāng)n較大時(shí)，計(jì)算量非常大。

為解決此問(wèn)題，現(xiàn)已提出了不少構(gòu)造2（幻的巧妙辦法。

2Lagrange插值的基函數(shù)構(gòu)造法

首先討論爐1時(shí)的情形。

已知*0,%，為，y,求乙（%）=%+“I］使得4（/）=%；4%）=X

顯然4（X）是過(guò)（％），%）和（％，M）兩點(diǎn)的一條直線。

由點(diǎn)斜式容易求得

17

L1(x)=y0+-—―(x-x0)

1x0-xJyx,-XJ/=o

V-------Y-------)V-------Y-------)

4G)AG)

其中，4(x),(，=0,l)具有如下特點(diǎn)：

7o(xo)=l;/o(x)=O

4(/)=。；4a)=i

稱其為線性插值基函數(shù)。。(“)可以通過(guò)函數(shù)4(%)，("二°」)組合得出，且組

合系數(shù)恰為所給數(shù)據(jù)y0,y.o

再討論聲2時(shí)的情形。

顯然4(%)是過(guò)(/，％)、(用，％)、(%，j2)三點(diǎn)的一條拋物線。

y

°Xo.V1.X2X

仿照線性插值基函數(shù)的構(gòu)造方法，令

/(幻二(xfXxr)

0(x0-x,)(x0-x2)

/(x)^U-xQ)(x-x2)

a-5)a-x2)

/式?=(…。)*7

(工2-%)(%一%)

其中，4G),(i二°,L2)具有如下特點(diǎn)：

小/)=l;/o(x,)=O;/o(x2)=0

</1(xo)=O;/l(x1)=l;/](x2)=0

/2(x0)=0"2(%)=0;/2(x2)=1

稱其為拋物重插值基函數(shù)(如下面所示)0

18

于是,

。一%）（了一馬）,

L(X)=

2（x0-x,）（x0-x2）0

*一%）（尢一9）

（石一工0）。-x2）

+（二?「）斗⑴%

（X,一演）（無(wú)，一%）r=0

最后討論一版情形。

求乙（而使得L（M）=%（7=0,1,2,-,/?）o

令〃詼多項(xiàng)式插值基函數(shù)為：

〃（）

43=—X-X4.

4.（x）,（i=0,19???,〃）具有如下特點(diǎn):

l,i=j

4（勺）=%.=<【。"打

于是，滿足插值條件的〃次多項(xiàng)式可以直接寫(xiě)為：

i=0j^i（X,—XJ?=0

j=01J

我們稱￡〃（x）為L(zhǎng)agrange多項(xiàng)式，4（“）其Lagrange插值基函數(shù)。

19

■給定%=>+1,/=0,1,2,3,4,5.下面哪個(gè)是&(x)的圖像?

3插值余項(xiàng)

如圖所示，其截?cái)嗾`差尺5)=f(x)-￡，(x),稱為L(zhǎng)agrange插值多項(xiàng)式的余

項(xiàng)。

20

定理假設(shè)F5)在［a,b］上有連續(xù)的直到小1階導(dǎo)數(shù)，且在不同插值節(jié)點(diǎn)

%,玉，???，%〃取值為/(%)=%,Ln(x)是經(jīng)過(guò)插值樣點(diǎn)(%,%),"=0,1,…㈤

的Lagrange插值多項(xiàng)式，若引進(jìn)記號(hào)：

q+1(X)=(X)(X_%…(X_當(dāng))=—蒼)

1=0

則當(dāng)勿時(shí)，有如下的誤差估計(jì)：

4。)-fM-W-9~~n。一七)

(〃+1)!1-0

=—儒多“⑴”)

證明：因?yàn)榇?若)=/(七)一4(%)=°?=0,1，….)

于是可假定凡(X)具有如下形式：

n

RnM=-x0)(x-X,)?--U-x?)=k(x)U(x-xr.)

1=0

將X看作(a,b)上的一個(gè)固定點(diǎn)，作輔助函數(shù)

9(f)=/(/)—Ln(t)—k(x)(Z-x0)(Z—X))???(/—xn)

=/(0-4(f)-Mx)加一七)

i=O

容易看出，。⑺有乂％不…，毛共加2個(gè)相異零點(diǎn)，且在［a,b］上存在加1階導(dǎo)數(shù)。

根據(jù)羅爾，“⑺在。⑺的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn)，故。'⑺在［a,b］上至少

有加1個(gè)零點(diǎn)。如此類推,“川)⑺在(&b)上至少有1個(gè)零點(diǎn)1使得

小〃+1)

產(chǎn)⑹=f向皤)_￡片?_攵⑶%而口n("%)|y

ati=o

=0

n

注意到4是〃次多項(xiàng)式，4"%)三°;口”刈的首項(xiàng)為f叫

)=5+i)!

故力(〃+~=。o由上述方程解得

（”+l）（g）

&（幻=

5+1）!

產(chǎn)）⑸〃

凡㈤=

于是

21

4例題

例1己知函數(shù)尸f(x)的觀察數(shù)據(jù)為

Xk-2045

yk51-31

試構(gòu)造F(x)的拉格朗日多項(xiàng)式〃(力，并計(jì)算人一1)。

解先構(gòu)造基函數(shù)

x(x-4)(x-5)__x(x-4)(x-5)

(-2-0)(-2-4)(-2-5)-84

(x+2)(x-4)(x-5)_(x+2)(x-4)(x-5)

(0-(-2))(0-4)(0-5)~40-

.、(x+2)x(”5)x(x+2)(x-5)

iwz=--------=-------

2(4+2)(4-0)(4-5)24

。+2?(升—2)。-4)_(x+2)x(x—4)

J(5+2)(5-0)(5-4)35-

所求三次多項(xiàng)式為

3

Z3(%)-JO

-5J("4X"5)(x+2)a-4)Q-5)

84+40

(_3X，(x+2)(x-9(x+2)x(x-4)

~24+35-

上1

-15421

-155,24

〃———+1——

4214217

第3講牛頓公式

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

1差商的概念：

稱％一不為函數(shù)f(x)的一階差商；

/[XpXj-Zlx^xJ

」一--

/[x0,Xpx2]=--

稱馬一%為函數(shù)f(x)的二階差商;

22

rrrrri_/[X]，…,―/[%,.??,七?/

JL人0,人]，…，人〃J—一

一般地，稱為函數(shù)F（x）的〃階

差商；

特別地，定義力%］二/（與）為函數(shù)/U）關(guān)于先的零階差商。

由此可知，高階差商總是由比它低一階的的兩個(gè)差商組合而成。

2差商性質(zhì)

（a）性質(zhì)1"階差商可以表示成加1個(gè)函數(shù)值為'''.?"的線性組合，

即

/K，???代］二互——V——、-------「——;

,=。（X,.-%。）（西一百）…（％"—％_|'）（七一苦+1）…（％—X,）

該性質(zhì)說(shuō)明：4階差商/［%，%，…，%］計(jì)算是由函數(shù)值代為），/'（幻，…人天）線

性組合而。

如：f[xQ,x[9x2]=/[xpx0,x2]=/[x2,xpx0].

九外,無(wú)|］二/（“）一/?！悖?f（'°）I/（"）

%一元0%一%%7。

/知豆,引=&1見(jiàn)二色聞

%7。

ZU；）-/Ui）_/U,）2/（小）

超一玉X,-A-_/（x）,/（x,）

-------------------0-------0------

七一?%七一%X一%

fgf（M）［

與一小

/（見(jiàn)）??/（W）

（$一x,）（x0-x2）（%一及）（％一與）（x2-%）（左-%）

（b）性質(zhì)2（對(duì)稱性）:差商與節(jié)點(diǎn)的順序無(wú)關(guān)。即

/區(qū),3］=小"（）］,

這一點(diǎn)可以從性質(zhì)1看出。

3利用差商表計(jì)算差商

利用差商的遞推定義,可以用遞推來(lái)計(jì)算差商。

差商表：

23

一階差商二階差商三階差商

,八陽(yáng)）

八%）

為/（巧）小”X」

/[XpX2]/[”0,“1，/]

工2f（x2）

/[x2,x3]/[x19x2,x3]

/（/）/[x0,xnx2,x3]

如要計(jì)算四階差商,應(yīng)再增加一個(gè)節(jié)點(diǎn),表中還要增加一行。

4差分的概念

定義設(shè)函數(shù)尸/U）在等距節(jié)點(diǎn)為=%+^a=°』，…，"）上的函數(shù)值『（為）=￡,

其中，力為常數(shù)稱作步長(zhǎng)。稱

▽工可/1

九一九

/力汨也2尸2，-2

分別為F（x）在％處以力為步長(zhǎng)的一階向前差分，一階向后差分和一階中心差分。

稱符號(hào)/、▽、6分別為向前差分算子，向后差分算子和中心差分算子。

f+-C--

在節(jié)點(diǎn)等距情況I,差商%用差分表示，設(shè)步長(zhǎng)力=匕+1-匕，有

Jyxi，演+i）--------------7

“川一天八

//、/（苞+1，巧+2）一/（如演+1）1/AA、1A2

f5,x/+1，z+2）=-------------------------------=T7T（一△”?）=R△M

xj+2-Xj2h2h

一般形式（數(shù)學(xué)歸納法可證）

f5,xM,?.，,+?）=M

§1.5牛頓插值公式

1.牛頓插值公式的構(gòu)造

24

Lagrange插值雖然易算，但若要增加一個(gè)節(jié)點(diǎn)時(shí)，全部基函數(shù)1人6都

需重新算過(guò)。本節(jié)介紹另外一種方法-牛頓插值法，并用它解決上面所述問(wèn)題。

由線性插值

N|（x）=y（）+^―^-（x-x0）,令。0==~—=+a1（x-x0）

二次插值能否寫(xiě)成

N2(x)=al)+ai(x-x^+a^x-x^x-x^

由條件N2ao)=%，(再)=y,N2(X2)=y2得

為一）‘。y-y。

推廣得

N“(x)=4+4(x-x0)+4(x—MX%-%)

+…+Q〃(X—拓)…(X-X〃T),

其中，〃。.…，〃〃為待定系數(shù)。如何求"o，4尸?.，4??

/卬引/⑴一小。）

所以/（工）=/（/）+/〔九，/］（%_%）（0）

〃X,Xo，xJ=

/[X,XO]=/[XO,X1]+/[X,XO,X1](X-X1)⑴

又

/n1=

x-x2

/(x,x0,x1]=/[x0,x1,x,]+/[x,x0,x1,x2](x-x2)⑵

一般地，,%]=/阮知不…''/一/[%，再，…，品

f[x,XQ,X]xn_J=f[xQ,玉xn]+f[x,xQ,X[，…，xn](x-xn)(n)

將式(n)代入式(n-1),...，式⑵代入式(1),式(1)代入式(0),

25

如此可得:

/(x)=/(x0)+/rx0,x1](x-x0)

+/[x(pX],](x—*0)(2-X[)+???

+/[x0,xI,-,xn](x-x0)(x-x1)-(x-xzi_1)

+/[^x0,x1,-,rj(x-x0)(x-x1)-(x-x?)

尤為注意的是：最后一項(xiàng)中，差商部分含有X,乃是余項(xiàng)部分，記作此(X)；而

前面小1項(xiàng)中,差商部分都不含有X,因而前面加1項(xiàng)是關(guān)于X的〃次多項(xiàng)式,

記作N”(x),這就是牛頓插值公式。

2算例

例1:當(dāng)n=l嘲，

f(x)=/(x0)+f[xQ,xJ(x-工0)+/[x,x0,x1](x-x0)(x-芭)

其中，’

^i(^)=/(x0)+/[x0,x1](x-x0)

=典+生*1。)

/一再

O

這就是牛頓一次插值多項(xiàng)式，也就是點(diǎn)斜式直線方程。

當(dāng)n=2時(shí)，

/(x)=/(x0)+/[x0,Xj](x-x0)+/[x0,x1,x2](x-x0)(x-x1)

+/[x,x0,x1,x2](x-x0)(x-x1