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

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

1

嚏要內(nèi)容

-算法和誤差

-非線性方程

■線性方程組

-特征值

■插值和擬合

■微分和積分

■微分方程

2

第一章算法與誤差

數(shù)值計(jì)算是求解數(shù)學(xué)問題的常用方法，隨著計(jì)算機(jī)技術(shù)

的飛速發(fā)展，數(shù)值計(jì)算方法在現(xiàn)代科學(xué)研究中的作用越來越

廣泛。數(shù)值計(jì)算的算法的研究越來越受到人們的重視。

1）數(shù)值計(jì)算是應(yīng)用數(shù)學(xué)一個(gè)重要分支，比如:微分方程，

現(xiàn)代物理.

2）新的數(shù)學(xué)，混沌理論（迭代法求非線性方程的根）.

與過去相比，現(xiàn)代數(shù)值計(jì)算方法有兩個(gè)顯著特點(diǎn)：

1）數(shù)值計(jì)算的方法和理論都結(jié)合數(shù)字計(jì)算機(jī)的特點(diǎn)來

研究。在進(jìn)行算法研究時(shí)，注意算法與計(jì)算速度，計(jì)算內(nèi)存

消耗的關(guān)系

2）在研究算法時(shí)，注重算法誤差分析，注意數(shù)值解的收

斂性和數(shù)值計(jì)算的穩(wěn)定性問題。

3

模型：人們?yōu)榱艘欢ǖ哪康?，對客觀事物的某一部分進(jìn)

行簡化、抽象和提煉出來的替代物，它集中反映了客觀

事物中人們需要研究的那部分特征。

數(shù)學(xué)模型：將模型的特征、內(nèi)存規(guī)律用數(shù)學(xué)的語言和符

號來描述的數(shù)學(xué)表述或數(shù)學(xué)結(jié)構(gòu)。例如：人口增長模型

求解問題的方法和步驟：

?形成問題一明確待研究問題的特征、背景、用途

?提出假設(shè)一抓住主要矛盾、忽略次要因素

?建立模型一量化關(guān)鍵因素、建立數(shù)學(xué)結(jié)構(gòu)和模型

?算法求解一選擇合適的算法對模型問題進(jìn)行求解

■算法分析一對算法的誤差和靈敏度、穩(wěn)定性進(jìn)行分析

?修正模型一對模型進(jìn)行檢驗(yàn)和修正

?算法應(yīng)用一應(yīng)用成果解決實(shí)際問題

4

1.1算法

一、算法的概念

當(dāng)我們用數(shù)值計(jì)算方法求解一個(gè)比較復(fù)雜的數(shù)學(xué)問題

時(shí)，常常要事先擬定一個(gè)計(jì)算方案，規(guī)劃一下計(jì)算的步驟。

所謂算法，就是指在求解數(shù)學(xué)問題時(shí)，對求解方案和計(jì)算

步驟的完整而明確的描述。

描述一個(gè)算法可以采用許多方法，最常用的一個(gè)方法

是程序流程圖。算法也可以用人的自然語言來描述。如果

用計(jì)算機(jī)能接受的語言來描述算法，就稱為程序設(shè)計(jì)。

5

二、算法的質(zhì)量標(biāo)準(zhǔn)

求解一個(gè)數(shù)學(xué)問題，可以采用不同的算法，比如：

線性方程組，可用克萊姆法則，高斯消元法等多種方法

求解。但是每一種方法的優(yōu)劣不同，評價(jià)一個(gè)算法的好

壞有以下幾個(gè)標(biāo)準(zhǔn)：

1）算法的計(jì)算量（時(shí)間復(fù)雜性）

例L用克萊姆法則求解一個(gè)n階線性方程組時(shí)，需要計(jì)

算（n+1）個(gè)n階行列式的值。需要做J川次乘法。設(shè)

n=20,若采用10億/秒的計(jì)算機(jī)，要花費(fèi)三十萬年的時(shí)間

進(jìn)行計(jì)算。若用高斯消元法來求解，采用一個(gè)普通的

586微機(jī)，在幾分鐘之內(nèi)就可得結(jié)果。

計(jì)算量的大小事衡量一個(gè)算法優(yōu)劣的重要標(biāo)準(zhǔn)。

6

例2：天竺國，梵塔

據(jù)說在東方的古國一印度土地上，有一座印度教的

神廟，這廟有一塊黃銅板，板上插著三根細(xì)細(xì)的、鑲上

寶石的細(xì)針，細(xì)針像菜葉般粗，而高就像成人由手腕到

肘關(guān)節(jié)的長。

當(dāng)印度教的主神梵天在創(chuàng)造地球這個(gè)世界時(shí)，就在其

中的一根針上從下到上放了半徑由大到小的六十四片圓

金片環(huán)，這就是有名的「梵塔」或稱「漢內(nèi)塔」

(TowersofHanoi)。

天神梵天要這廟的僧侶,把這些金片全部由一根針移

到另外一根指定的針上，一次只能移一片，不管在什么

情況下，金片環(huán)的大小次序不能變更，小金片環(huán)永遠(yuǎn)只

能放在大金片環(huán)上面。

只要有一天這六十四片的金環(huán)能從指定的針上完全轉(zhuǎn)

移到另外指定的針上，世界末日就來到。

經(jīng)過計(jì)算機(jī)的運(yùn)算，移動的次數(shù)需18,446,744,073,

709,551,615,一秒移動一次，大約需要5849億年。

7

2）算法的空間復(fù)雜性

當(dāng)使用計(jì)算機(jī)信解一個(gè)數(shù)學(xué)問題時(shí)，計(jì)算程序要占

用許多工作單元（內(nèi)存）。當(dāng)計(jì)算一個(gè)大型的數(shù)學(xué)問題

時(shí)，內(nèi)存的消耗量是很大的。因此，算法占用內(nèi)存數(shù)量

的多少，是衡量算法優(yōu)劣的另一個(gè)標(biāo)準(zhǔn)。

3）算法邏輯結(jié)構(gòu)的復(fù)雜性

設(shè)計(jì)算法時(shí)應(yīng)該考慮的另一個(gè)因素是邏輯結(jié)構(gòu)問題,

雖然計(jì)算機(jī)能自動執(zhí)行極其復(fù)雜的計(jì)算程序，但是計(jì)算

程序的每個(gè)細(xì)節(jié)都需要編程人員制定，因此算法的邏輯

結(jié)構(gòu)應(yīng)盡量簡單，才能使程序的編制、維修和使用比較

方便。

以上我們介紹了算法的一些基本概念。下面討論數(shù)

值計(jì)算中的另一個(gè)重要問題——誤差。

8

1?2誤差

在研究算法時(shí)，要進(jìn)行誤差分析，能估計(jì)誤差的算

法才是有實(shí)用價(jià)值的算法。

一、誤差的來源：

引起計(jì)算誤差的原因是多方面的。

1）模型誤差

當(dāng)解決一個(gè)工程實(shí)際問題時(shí)，常常需要用一定的數(shù)

學(xué)表達(dá)式來描述，即建立一個(gè)數(shù)學(xué)模型。建立數(shù)學(xué)模型

時(shí)，通常要根據(jù)實(shí)際需要做一些簡化，忽略一些次要因

素，是模型不致過分復(fù)雜，又能滿足精度要求。這樣建

立起來的數(shù)學(xué)模型是客觀現(xiàn)象的近似描述。這種近似必

然產(chǎn)生誤差。

9

2）方法誤差

在計(jì)算過程中，由數(shù)學(xué)方法產(chǎn)生的誤差，稱為方法

誤差。

例如，在計(jì)算指數(shù)函數(shù)的值時(shí)，常用到如下塞級數(shù)展開

式：

2n

XXX

e=1+x+----+…+-----+…

2!n!

這是一個(gè)無窮級數(shù)。計(jì)算時(shí)，只能取有限項(xiàng)。

2n

XX

Sn(vx)/—1+x++,?+—

2!n!

用有限項(xiàng)逼近無窮級數(shù)，會產(chǎn)生一個(gè)誤差，這個(gè)誤差

是由數(shù)學(xué)方法產(chǎn)生的，所以是一種方法誤差。

10

3)舍入誤差

在計(jì)算過程中，當(dāng)我們表示一個(gè)數(shù)時(shí)，常常只能取有

限位。超出的尾數(shù)將會舍去，從而造成誤差，這種誤差稱

為舍入誤差。

舍入誤萋時(shí)我們數(shù)值計(jì)算中重點(diǎn)研究的對象，將貫穿

整個(gè)課程之中。

11

二、誤差的概念

1）誤差：

某個(gè)量的真值與近似值的差的絕對值，稱為近似值

的誤差，又稱絕對誤差，用e表示。?

e=x-八?x—真值，八一近似值，

2）誤差限

在許多情況下，我們不知道某個(gè)量的真實(shí)值是多少,

因此也不知道它的近似值的誤差。但是我們能估計(jì)出

誤差不會超過某個(gè)確定的數(shù)值。這個(gè)數(shù)值就稱為近似

值的誤差限。

我們能用誤差限定量的衡量一個(gè)近似值的誤差。

如果某近似值的誤差限是E,我們就說，在允許誤

差￡的條件下，近似值是準(zhǔn)確的。

12

3）有效數(shù)字

我們還可以用有效數(shù)字的概念來說明一個(gè)近似值的準(zhǔn)

確程度。

我們先介紹“四舍五入”的概念，四舍五入是數(shù)值計(jì)

算時(shí)，取近似值的一種方法。若被舍去部分的頭一位大

于等于5時(shí)，就在所取數(shù)的末位加1；小于5時(shí)，就舍去。

用四舍五入方法得到的近似值，稱為有效數(shù)字。

有效數(shù)字的末位到第一位非零數(shù)字的個(gè)數(shù)，稱為該有

效數(shù)字的位數(shù)。

有效數(shù)字可用來表示一個(gè)近似值的準(zhǔn)確程度，一個(gè)近

似值的有效位數(shù)越多，這個(gè)近似值就越逼近真值。

13

由上面的有效數(shù)字的定義，我們能給出另外一種等

價(jià)的定義。

若近似值的誤差小于某一位的半個(gè)單位，便稱近似

值準(zhǔn)確到這一位。從這一位到第一個(gè)非零數(shù)字的個(gè)數(shù)就

是近似值的有效位數(shù)。

上述定義常用在數(shù)值計(jì)算的過程中，用來控制迭代

的精度。

14

例：圓周率IT是一個(gè)無理數(shù)，

TT=3.14159265358979323...,考察下列近似值的有效位數(shù)。

±1J)/jV?X(J~?XIXWJ~?-1.IXfcZ

解：

1)￡是按四舍五入原則得到的，有三位有效數(shù)字。

e=兀一九、w.wwx5926"______

小于百分位上的半個(gè)單位。準(zhǔn)確到百分位。從這一位

到個(gè)位(第一位非零數(shù)字)有三位。有三位有效數(shù)字。

2)e=〃一九?----J073…05

小于萬分位上的半個(gè)單位。準(zhǔn)確到萬分位。從萬分位

到個(gè)位有五位。有五位有效數(shù)字。

15

3)2的萬分位不是按四舍五入規(guī)則得到的，因止玄

有四位有效數(shù)字，而不是五位有效數(shù)字。

c=71一九?

小于千分位上的半個(gè)單位，從千分位到個(gè)位有四

位。九精確到千分位。3.1416有五位有效數(shù)字，準(zhǔn)

確到萬分位。3.1415有四位有效數(shù)字，準(zhǔn)確到千分

位。這就后r的近似值采用3.1416而不采用3.1415

的原因。

16

三、算法與穩(wěn)定性

計(jì)算積分：

1

E=fxnex{dxH=1,2,3…

Jo

解：用分部積分法

dx

nx—1i

=xe1dx

0

i

x-

=\—n[xedx

Jo

17

或En=\-nEn-1,(n=2,3,...)

1

這里瑪=一=0.3678794412

取6位有效數(shù)字，計(jì)算凡的前9個(gè)值

￡,I=0.367879EO.1-6E.=0.127120

凡=1-2瑪=0.264242號1-7EO=0.110160

E=1-3E、=0.207174號=

32.o1-80.118720

E,=1-4M=0.170904E1-9M=-0.068480

439QO

E5=1-5EA4=0.145480

雖然被積函數(shù)x'eXT在整個(gè)積分區(qū)間0,1)是正的，可是計(jì)算的結(jié)果

卻是負(fù)的。

18

什么原因引起這么大的誤差呢？計(jì)算機(jī)中唯一的舍入

誤差是在鳥

號的舍入誤差是4.412x101在計(jì)算石2時(shí)它乘了+2,在計(jì)

算后3時(shí)心中的誤差又乘了+3,以此類推，石9的誤差為：

-7

9!x4.412x10?0.1601

*

所以69=石9+6=-0-068480+0.1601=0.0916(取三位有效數(shù)字)

怎樣避免這種不穩(wěn)定的算法呢？改寫遞歸關(guān)系式如下：

1-E

,3,2)

En-1=--------(n=--

n

E=x〃e'dx

nJo

<Cx"dx

J0

〃+lI

X

<-------

n+\

o

1

<----

72+1

19

當(dāng)“f8,凡f0。如取石20的近似值為零，以它為起始值，

11

則起始誤差最大為——O此誤差在求?9時(shí)乘了一，因此嗎9的誤

2120

111111

差最大為——x—石9的誤差最大，為——X——X…一。七9

202110112021

時(shí)，起始誤差已減小至2.5x10

1-%。

石2。=°干9=---------=0.05

20

1-石191-嗎8

005

嗎8=——-=-￡17=---------=0.0527778

1918

1-Eg\-E

「

E16=---------=0.0557190E=---------=0.0590176

1716

1-嗎51-E

嗎4=——以=0.0627322=---------=0.0669477

14

20

1-F1-F

F=-^^=0.0717733r=——=0.0773522

乜1213""12

1-F1-p

斤=——=0.0838771F=——三為=0.0916123

"1011“910

由于算法的穩(wěn)定性，E2。中的起始誤差已經(jīng)完全被抑制了。

21

第二章非線性方程

2.1二分法

一、定理：

設(shè)非線性方程/(。)=0，xE[a,b]

若：

1)/(%)單調(diào)連續(xù)xe[a,b]

2)/((?)?/(b)V0則方程在[a,b]有一個(gè)根

二、基本思想：

將分為相等的2個(gè)小區(qū)間，計(jì)算小區(qū)間端點(diǎn)函數(shù)值，找出新

的有根區(qū)間。重復(fù)上述過程，直到找到滿足精度要求的根。

22

X

I(N

qq

+CM4-CM

J

IIII

CM

K

三、誤差估計(jì)：

設(shè)近似根的誤差限位￡

則：第一次二分的誤差

*1

1)x-%1W6,-a,=-b、一a、

--2

*1

2)x-X、＜b-a=--b,-a、

233y211

*1

〃)X-3<a-=-

2

24

1

令：bl-%<￡

b—a

1g-----------

解得：n>--------------

1g2

二分法在迭代前可以確定迭代次但二分法的求解效率不高

25

例題：求/(%)=1+4%2-10=0的根XG[1,2],￡二-X10-3

2

2-1

1gl----------

1-3

-X10

解：n>-=---1-0--.-9-7-----

1g2

取〃=11,得下表：

26

nMg

1121.5+

211.51.25-

31.251.51.375+

41.251.3751.3125-

51.31251.3751.34375-

61.343751.3751.359375-

71.3593751.3751.36718754-

81.3593751.36718751.36328125-

91.363281251.36718251.365234375+

101.363281251.3652343751.364257813-

111.3642578131.3652343751.364746094

x=l.364746094

27

2.2迭代法

一、基本思路：

設(shè)方程/(x)=0(1)

其等價(jià)形式為x=①(x)(2)

其迭代格式為乙+i=。(匕)，k=0,1,2...(3)

式中：工。為初值，0（乙）為迭代函數(shù)。

如果：limX,=x

ktg

X*為方程的根，則稱迭代格式收斂

28

X

二、定理：

設(shè)。（％）為連續(xù)函數(shù)，Xe\^a,b迭代格式（3）收斂的充要條件是

?

（p（x）<1xea,b

若x*是方程的根，則

X=（p（x）

證：〈''(4)稱為方程的不動點(diǎn)。

l/g二9（t）

相減：x-=（P（X\夕(x*)(5)

K\\/t/

_。（A）

-----(乙-X

XkX

由中值定理

*k*

x*=。'（4）X,一X€X,X

29

1)

若<1,

k

令MmaxXX

夕?)4W9

*

則Xx<MXkX

k+x

**

<k+1

或?+iXM“。x

取極限：

左一》8

得

limx,k+1,fx

kTg

30

2)

若(P(4)>1,

令m=min(p(J)

**

則x,,-x>mx,-x

k+1k

*、

或x,,-x>mA+lx-x*

k+10n

取極限：

__…Too

ktg

得lim,foo

kT8k4-1

31

例題：求方程/(%)=%'+4x-10=0,xe[1,2],xQ=1.5,￡=10

解：

八32

1)X=X-x-4ylx-+10

110

3221。

2)x=A1——4x(x=10—4xfx=--4x)

VX

3)x=-A/10—x323213

(4x=10-x-?x=-(10-x))

24

尸

,,10

4)%=J--------(x-(4+x)=10fx=-------)

V4+x4+1

33

n(1)(2)(3)(4)

11.51.51.51.5

2-0.8750.81651.286953771.34839973

36.7322.99691.402540801.36737637

4-469.7(—8.65)31.345458381.36495700

51.03xlO81.375170251.36526475

61.360094191.36522559

71.367846971.365223058

81.363887001.36522994

91.365916731.36523002

*9一%8=°,002X=8x108

x9-8

x=l.36523002

34

1)0(%)=x—1—4X一+10

<p(x)=1—3x~—8x-17.5

x—1.5

、

10

4=-7.832

2

X7

=0.6556

35

10

4)9(x)=

4+x

-0.1226

36

2.3牛頓法

一、基本思想

設(shè)/"）=0

將方程展開

12

/（%）+廣（%。）（％7。）+—廣'（%）（%7。）+

2!

略去高階項(xiàng)

小。）+廣（%）（%-、0）=0

整理

/（%。）

X2%0--------

/'（%）

37

ecc

個(gè)幾何意義

收斂快,

切線法

>

X

39

40

例題：

求方程/(%)=<+4x-10=0的根，xe[l,2],x0=1.5,f=1x10

解：

9

f'(x)=3"+8x

迭代格式

x3+4x2-10

nn八1???

xn+1=xn------------7-----------------,n=0,1,

3xn+n8x

3

n01一9

1.51.3733333136526201.3652300

k-i-x」0.12666670.00807130.000032

x=l.3652300

41

2.4割線法

牛頓法（切線法）

將微分改為差分，得割線法

f(x〃)

-工…）

n=1,2,3…

特點(diǎn)：

1）需要兩個(gè)初始值，X。和X,

2）精度比牛頓法稍低

3）不用求函數(shù)的微分

42

令幾何意義

X

43

例題：

求方程/(x)=+4x2-10=0的根，

xe[1,2],x()=1.5,=1.6,￡=1x10

解：

迭代格式

X3+4X2-10

x=x----------------------------------------(x-x.),n=1,2,3,

n+1n3232w-173

x+4x-(x,+4x,)

nn'〃一1M-17

37

X1+47-10

2=1---3------.----2-----.---3------.----2--.(vx,1-xn0))

/+4/-(x0+4x0)

1.6,3+4x1.62-10

=1.6--------------------------------------------------(1.6-1.5)

3737v7

1.6+4x1.6-(1.5+4x1.5-)

=1.378888

44

n01234

U1.51.61.3788881.3657821.365234

0.2211120.01311060.000548316

x=1365234

解方程組：

設(shè)尸（X）=0

式中

[力（"1-"，j

尸（x）=:（

I

[/"（*1-"））

將方程展開，略去高階項(xiàng)

F（x°）+J（x°）Ax°=6“

式中

（a/,...a，、

I%0%J

J=□:.雅克比矩陣

df“'

J〃...

<%也"

46

得迭代格式

17/(A)\A(A)(*)\

JIxIAx=—rIxI

I(*+l)(*),人(")

X=X+

式中：

或：

”1)J)+A—

47

例題:

f%,+2x.-3=0

求方程)12的根，

)c22

[2x]+x2-5=0

解：（1）

k=0,1,

(M(*)

J"x+Ax

k=0,1,…

-4)-2/+3

-F(xW

2(*)

□⑹上")+5

48

r（o）-i--i

1x.?r|i1.5

k=0||=

"力k。」

/（o）\「121

《）」62J

-F（x（0））=r-（）,5"

'7[-0.5

線性方程組

「[「-0.5]

620）

_JLA^2J-L-°-5-

解得

尸；。[_「01

[△月。）」-L-0-25_

迭代精度判別

（0）

max=0.25>￡

i=2

49

▼Q⑼1「△%⑼】

二+

(')(0)X」

LX2_LX2J

「1.5]-o-

+

1.0-0.25

15r

0.75

k戈產(chǎn)婿max譚）

01.51.0

11.50.750.25

21.4880950.7559520.011905

31.4880340.7559830.5X104

「王]「1.4880341

%[o.755983

50

收斂精度

?線性收斂

1

°二分法，收斂精度3—（%-X,）

2

°迭代法，收斂精度oc（P也）（x-x,）

?乘方收斂

。牛頓法，收斂精度3（乙-一）2

°割線法，收斂精度8（%“一匕一）38

51

第三章線性方程組

?消元法

°高斯消元法（列主元法）

°因子表法

?矩陣分解法

°三角分解法（LU分解法）

°平方根法

0喬累斯基法

?迭代法

0一般迭代法

°塞德爾迭代法

52

3.1消元法

?高斯消元法與因子表法在算法上的不同點(diǎn)是，規(guī)格化和消元的順序不同

°高斯消元法：對增廣矩陣進(jìn)行規(guī)格化和消元

°因子表法：先對系數(shù)矩陣進(jìn)行規(guī)格化和消元，然后再對右端項(xiàng)進(jìn)行規(guī)格化和消元。

?因子表法的優(yōu)點(diǎn)是：

當(dāng)系數(shù)矩陣不變，右端項(xiàng)變化時(shí)，可反復(fù)利用因子表對右端項(xiàng)進(jìn)行規(guī)格化和消元，

可大大減少運(yùn)算時(shí)間。

53

?算法1:高斯消元法（列主元）

列主元法是常用的消元法，在保證一定精度的基礎(chǔ)上比全主元法耗費(fèi)的機(jī)時(shí)少。

設(shè)3階線性方程組的增廣矩陣為：

「巴1,12a\3

11

A=1a-「I

121Q2-2a23a2-4

Ial

L31a32a3、3、a34」

設(shè)：a”>=1,2,3否則交換行

a,1，i

（1）規(guī)格化第一行，使當(dāng)?shù)南禂?shù)為1

(1)(1)(1)1

1，I3

1如巴2丐4

1

1I

a2-22a2c3ra2r4I

、,

a3..1Q3233a34

a%3

(1)\2(1)(I)"14

、、=a,,—

a12，Q1,3、=14

a、、a.,a.,

式中：a]1為右端項(xiàng)

54

（2）消元，使第二行，三行七的系數(shù)為0

(1)(1)⑴-

a11a12a13a14

a(1)a(1)a(1)

a2122