数值计算方法课件

数值计算方法

1

嚏要内容

-算法和误差

-非线性方程

■线性方程组

-特征值

■插值和拟合

■微分和积分

■微分方程

2

第一章算法与误差

数值计算是求解数学问题的常用方法，随着计算机技术

的飞速发展，数值计算方法在现代科学研究中的作用越来越

广泛。数值计算的算法的研究越来越受到人们的重视。

1）数值计算是应用数学一个重要分支，比如:微分方程，

现代物理.

2）新的数学，混沌理论（迭代法求非线性方程的根）.

与过去相比，现代数值计算方法有两个显著特点：

1）数值计算的方法和理论都结合数字计算机的特点来

研究。在进行算法研究时，注意算法与计算速度，计算内存

消耗的关系

2）在研究算法时，注重算法误差分析，注意数值解的收

敛性和数值计算的稳定性问题。

3

模型：人们为了一定的目的，对客观事物的某一部分进

行简化、抽象和提炼出来的替代物，它集中反映了客观

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

数学模型：将模型的特征、内存规律用数学的语言和符

号来描述的数学表述或数学结构。例如：人口增长模型

求解问题的方法和步骤：

•形成问题一明确待研究问题的特征、背景、用途

•提出假设一抓住主要矛盾、忽略次要因素

•建立模型一量化关键因素、建立数学结构和模型

•算法求解一选择合适的算法对模型问题进行求解

■算法分析一对算法的误差和灵敏度、稳定性进行分析

•修正模型一对模型进行检验和修正

•算法应用一应用成果解决实际问题

4

1.1算法

一、算法的概念

当我们用数值计算方法求解一个比较复杂的数学问题

时，常常要事先拟定一个计算方案，规划一下计算的步骤。

所谓算法，就是指在求解数学问题时，对求解方案和计算

步骤的完整而明确的描述。

描述一个算法可以采用许多方法，最常用的一个方法

是程序流程图。算法也可以用人的自然语言来描述。如果

用计算机能接受的语言来描述算法，就称为程序设计。

5

二、算法的质量标准

求解一个数学问题，可以采用不同的算法，比如：

线性方程组，可用克莱姆法则，高斯消元法等多种方法

求解。但是每一种方法的优劣不同，评价一个算法的好

坏有以下几个标准：

1）算法的计算量（时间复杂性）

例L用克莱姆法则求解一个n阶线性方程组时，需要计

算（n+1）个n阶行列式的值。需要做J川次乘法。设

n=20,若采用10亿/秒的计算机，要花费三十万年的时间

进行计算。若用高斯消元法来求解，采用一个普通的

586微机，在几分钟之内就可得结果。

计算量的大小事衡量一个算法优劣的重要标准。

6

例2：天竺国，梵塔

据说在东方的古国一印度土地上，有一座印度教的

神庙，这庙有一块黄铜板，板上插著三根细细的、镶上

宝石的细针，细针像菜叶般粗，而高就像成人由手腕到

肘关节的长。

当印度教的主神梵天在创造地球这个世界时，就在其

中的一根针上从下到上放了半径由大到小的六十四片圆

金片环，这就是有名的「梵塔」或称「汉内塔」

(TowersofHanoi)。

天神梵天要这庙的僧侣,把这些金片全部由一根针移

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

情况下，金片环的大小次序不能变更，小金片环永远只

能放在大金片环上面。

只要有一天这六十四片的金环能从指定的针上完全转

移到另外指定的针上，世界末日就来到。

经过计算机的运算，移动的次数需18,446,744,073,

709,551,615,一秒移动一次，大约需要5849亿年。

7

2）算法的空间复杂性

当使用计算机信解一个数学问题时，计算程序要占

用许多工作单元（内存）。当计算一个大型的数学问题

时，内存的消耗量是很大的。因此，算法占用内存数量

的多少，是衡量算法优劣的另一个标准。

3）算法逻辑结构的复杂性

设计算法时应该考虑的另一个因素是逻辑结构问题,

虽然计算机能自动执行极其复杂的计算程序，但是计算

程序的每个细节都需要编程人员制定，因此算法的逻辑

结构应尽量简单，才能使程序的编制、维修和使用比较

方便。

以上我们介绍了算法的一些基本概念。下面讨论数

值计算中的另一个重要问题——误差。

8

1・2误差

在研究算法时，要进行误差分析，能估计误差的算

法才是有实用价值的算法。

一、误差的来源：

引起计算误差的原因是多方面的。

1）模型误差

当解决一个工程实际问题时，常常需要用一定的数

学表达式来描述，即建立一个数学模型。建立数学模型

时，通常要根据实际需要做一些简化，忽略一些次要因

素，是模型不致过分复杂，又能满足精度要求。这样建

立起来的数学模型是客观现象的近似描述。这种近似必

然产生误差。

9

2）方法误差

在计算过程中，由数学方法产生的误差，称为方法

误差。

例如，在计算指数函数的值时，常用到如下塞级数展开

式：

2n

XXX

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

2!n!

这是一个无穷级数。计算时，只能取有限项。

2n

XX

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

2!n!

用有限项逼近无穷级数，会产生一个误差，这个误差

是由数学方法产生的，所以是一种方法误差。

10

3)舍入误差

在计算过程中，当我们表示一个数时，常常只能取有

限位。超出的尾数将会舍去，从而造成误差，这种误差称

为舍入误差。

舍入误萋时我们数值计算中重点研究的对象，将贯穿

整个课程之中。

11

二、误差的概念

1）误差：

某个量的真值与近似值的差的绝对值，称为近似值

的误差，又称绝对误差，用e表示。〜

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

2）误差限

在许多情况下，我们不知道某个量的真实值是多少,

因此也不知道它的近似值的误差。但是我们能估计出

误差不会超过某个确定的数值。这个数值就称为近似

值的误差限。

我们能用误差限定量的衡量一个近似值的误差。

如果某近似值的误差限是E,我们就说，在允许误

差£的条件下，近似值是准确的。

12

3）有效数字

我们还可以用有效数字的概念来说明一个近似值的准

确程度。

我们先介绍“四舍五入”的概念，四舍五入是数值计

算时，取近似值的一种方法。若被舍去部分的头一位大

于等于5时，就在所取数的末位加1；小于5时，就舍去。

用四舍五入方法得到的近似值，称为有效数字。

有效数字的末位到第一位非零数字的个数，称为该有

效数字的位数。

有效数字可用来表示一个近似值的准确程度，一个近

似值的有效位数越多，这个近似值就越逼近真值。

13

由上面的有效数字的定义，我们能给出另外一种等

价的定义。

若近似值的误差小于某一位的半个单位，便称近似

值准确到这一位。从这一位到第一个非零数字的个数就

是近似值的有效位数。

上述定义常用在数值计算的过程中，用来控制迭代

的精度。

14

例：圆周率IT是一个无理数，

TT=3.14159265358979323...,考察下列近似值的有效位数。

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

解：

1)£是按四舍五入原则得到的，有三位有效数字。

e=兀一九、w.wwx5926"______

小于百分位上的半个单位。准确到百分位。从这一位

到个位(第一位非零数字)有三位。有三位有效数字。

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

小于万分位上的半个单位。准确到万分位。从万分位

到个位有五位。有五位有效数字。

15

3)2的万分位不是按四舍五入规则得到的，因止玄

有四位有效数字，而不是五位有效数字。

c=71一九।

小于千分位上的半个单位，从千分位到个位有四

位。九精确到千分位。3.1416有五位有效数字，准

确到万分位。3.1415有四位有效数字，准确到千分

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

的原因。

16

三、算法与稳定性

计算积分：

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位有效数字，计算凡的前9个值

£,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

虽然被积函数x'eXT在整个积分区间0,1)是正的，可是计算的结果

却是负的。

18

什么原因引起这么大的误差呢？计算机中唯一的舍入

误差是在鸟

号的舍入误差是4.412x101在计算石2时它乘了+2,在计

算后3时心中的误差又乘了+3,以此类推，石9的误差为：

-7

9!x4.412x10«0.1601

*

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

怎样避免这种不稳定的算法呢？改写递归关系式如下：

1-E

,3,2)

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

n

E=x〃e'dx

nJo

<Cx"dx

J0

〃+lI

X

<-------

n+\

o

1

<----

72+1

19

当“f8,凡f0。如取石20的近似值为零，以它为起始值，

11

则起始误差最大为——O此误差在求?9时乘了一，因此吗9的误

2120

111111

差最大为——x—石9的误差最大，为——X——X…一。七9

202110112021

时，起始误差已减小至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

由于算法的稳定性，E2。中的起始误差已经完全被抑制了。

21

第二章非线性方程

2.1二分法

一、定理：

设非线性方程/(。)=0，xE[a,b]

若：

1)/(%)单调连续xe[a,b]

2)/((?)•/(b)V0则方程在[a,b]有一个根

二、基本思想：

将分为相等的2个小区间，计算小区间端点函数值，找出新

的有根区间。重复上述过程，直到找到满足精度要求的根。

22

X

I(N

qq

+CM4-CM

J

IIII

CM

K

三、误差估计：

设近似根的误差限位£

则：第一次二分的误差

*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迭代法

一、基本思路：

设方程/(x)=0(1)

其等价形式为x=①(x)(2)

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

式中：工。为初值，0（乙）为迭代函数。

如果：limX,=x

ktg

X*为方程的根，则称迭代格式收敛

28

X

二、定理：

设。（％）为连续函数，Xe\^a,b迭代格式（3）收敛的充要条件是

»

（p（x）<1xea,b

若x*是方程的根，则

X=（p（x）

证：〈''(4)称为方程的不动点。

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牛顿法

一、基本思想

设/"）=0

将方程展开

12

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

2!

略去高阶项

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

整理

/（%。）

X2%0--------

/'（%）

37

ecc

个几何意义

收敛快,

切线法

>

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…

特点：

1）需要两个初始值，X。和X,

2）精度比牛顿法稍低

3）不用求函数的微分

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

解方程组：

设尸（X）=0

式中

[力（"1-"，j

尸（x）=:（

I

[/"（*1-"））

将方程展开，略去高阶项

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戈产婿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消元法

•高斯消元法与因子表法在算法上的不同点是，规格化和消元的顺序不同

°高斯消元法：对增广矩阵进行规格化和消元

°因子表法：先对系数矩阵进行规格化和消元，然后再对右端项进行规格化和消元。

•因子表法的优点是：

当系数矩阵不变，右端项变化时，可反复利用因子表对右端项进行规格化和消元，

可大大减少运算时间。

53

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

列主元法是常用的消元法，在保证一定精度的基础上比全主元法耗费的机时少。

设3阶线性方程组的增广矩阵为：

「巴1,12a\3

11

A=1a-「I

121Q2-2a23a2-4

Ial

L31a32a3、3、a34」

设：a”>=1,2,3否则交换行

a,1，i

（1）规格化第一行，使当的系数为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为右端项

54

（2）消元，使第二行，三行七的系数为0

(1)(1)⑴-

a11a12a13a14

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

a2122