数值计算方法-全套课件

——数值计算方法数值计算方法Numerical

Method数值计算方法1第一章

绪论数值计算方法4课程简介什么是数值计算方法？为什么学习数值计算方法？数值计算方法的主要内容数值计算中的误差误差的种类及其来源绝对误差与相对误差有效数字与误差舍入误差与截断误差误差的传播与估计算法的数值稳定性非计算机方法数值计算方法5解析方法简单问题实际价值有限图解法结果准确？三维及以下手工方法计算器速度慢，很容易出现低级错误数值计算方法6工程问题求解的三个阶段公式化简洁表示的基本定律解释深入分析受限于耗时的求解过程求解用详细、通常也是复杂的方法来求解问题计算机时代到来之前公式化深入分析问题与基本定律的关系解释易于计算使得能够进行整体思考和直观研究，可以对系统的灵敏性和特性进行研究求解易于使用的计算机方法计算机时代学习数值计算方法的意义数值计算方法7增强求解问题的技能在理解的基础上使用一些商品化软件解决一些软件所不能解决的问题学习使用计算机的一个有效载体加深对数学的理解数值计算方法的内容（一）数值计算方法8方程求根（Roots

of

Equation）f(x)

0xf(x)根数值计算方法的内容（二）数值计算方法9线性代数方程组（System

of

LinearAlgebraic

Equations）a11x1

a12

x2

c1a21x1

a22

x2

c2x1x2解数值计算方法的内容（三）数值计算方法10xx插值（Interpolation）和曲线拟合（CurveFitting）f(x) f(x)数值计算方法的内容（四）数值计算方法11数值微分（numerical

differentiation）和数值积分（numerical

integration）xf(x)baf

(x)dxI

ab面积数值计算方法的内容（五）数值计算方法12常微分方程（Ordinary

DifferentialEquation

）tydy

y

f(t,

y)dt

t求关于自变量t的函数yyi

1

yi

f(ti,yi

)

ttiti+1

t斜率=f(ti

,yi)课堂教学内容绪论

(1周)非线性方程求根

(1周)求解线性方程组的数值方法

(2周)插值和曲线拟合

(1周)数值微分和数值积分

(1周)常微分方程数值解

(1周)19数值计算方法教学安排理论13：15～15：40上机（助教负责）四次海洋大楼机房刷校园卡20数值计算方法考核方式平时成绩（70%）课堂（10%）

+上机（10%）上机作业提交时间 当天24:00每周作业（50%）提交时间：每次布置作业后一周内，注意截止时间提交到课程网站，程序+报告文档，一个压缩文件期末作业（30%）自选题目 截止提交时间

6月26日24:00利用数值方法解决问题专业领域、以往课程、社会生活解析解？数值解？分析212016/5/1数值计算方法考核方式必须遵守学术道德规范，鼓励相互之间进行讨论，但提交的作业必须独立完成。杜绝抄袭！23数值计算方法作业要求完整性程序+文档报告要求问题分析程序（算法、必要的注释）结果分析排版、格式（清晰、美观）22数值计算方法作业题例数值计算方法19在对汽车、机器人以及其他运动器械的控制时，

经常需要获得其移动距离的数据通过对于一连串采样点（

即时速度）

的插值，

得到速度关于时间的函数，

再对于速度进行积分，

即可得到对象所运动的距离总长度为5451.24米作业题例——西湖面积数值计算方法20作业题例——上海世博会参观人数过千万时间点数值计算方法21作业题例——手数值计算方法22作业题例——任意球数值计算方法23数学建模与工程问题求解数值计算方法24问题定义数学模型数值或图形结果实现理论数据问题求解工具：计算机、统计学、数值方法、图解法等社会应用：调度、最优化、通信等等数学模型（Mathematical

Model）数值计算方法25用数学语言来表达物理系统或过程本质特征的公式或方程。因变量=f(自变量，参数，强制函数)因变量（dependent

variable）：用来刻画系统行为或状态的特征量；自变量（independent

variable）：通常为维度，如时间和空间，系统的行为是用自变量来确定的；参数（parameter）：反映系统的性质或组成；强制函数（forcing

function）：外部对系统施加的影响。一个简单的数学模型——牛顿第二定律数值计算方法26F=ma

a=F/ma为因变量，表示了系统的行为；F为强制函数；m为表示系统性质的参数；在这种简单的情况下，没有自变量，没有涉及到加速度a在随时间或空间的变化。物理世界中数学模型的几个典型特点：用数学语言描述自然过程或系统；代表了一种理想情况，或是对现实的简化。即忽略了自然过程的不重要的细节，而集中于自然过程的本质特征；得到的是一个可以重现的结果，可以用来做预测。降落伞问题（Falling

ParachutistProblem）数值计算方法27确定降落伞的最后速度加速度表示为速度的变化率FUFDdv

Fdt m如果净受力为正，物体加速运动；如果为负，物体减速运动；如果为0，物体速度不变。假定向下的力为正，FD

mg FU

cvc为比例系数，称为阻力系数（dragcoefficient(kg/s)）。参数c说明了下降物体的特征，如形状或表面的粗糙程度。降落伞问题（Falling

ParachutistProblem）数值计算方法28模型——微分方程（differential

equation）dv

mg

cv

g

cvdt m m若初始时处于静止状态（t=0时，v=0），可得gmcv(t)

1

e

(c

/

m)t

v(t)为因变量；t为自变量；c和m为参数；g为强制函数。问题：从静止热气球中弹出一个质量为68.1kg的降落伞，阻力系数等于12.5kg/sv(t)

9.8

68.1

1

e

(12.5

/

68.1)t

53.39

1

e

0.18355t

12.5降落伞问题（Falling

ParachutistProblem）数值计算方法29t(s)v(m/s)00.00216.40427.77635.64841.091044.871247.48

53.39246810121400504030201060t(s)解析解或精确解但许多模型不能精确地求解数值方法——对数学问题进行变换，使得它可以用算术运算来求解v(m/s)终速数值计算方法30降落伞问题（Falling

ParachutistProblem）数值方法：在时刻ti处导数的有限差商近似dv

v

v(ti

1)

v(ti

)dt

tti

1

tidtdv

lim

v

t

0

t

iv(t

) tcmi

1 ii

1 i

v(t )

v(t

)

g

t

t(s)v(m/s)00.00219.6432.00639.86844.821047.971249.96

/1053.39欧拉法024681012140102030405060t(s)v(m/s)数值解解析解终速用直线段来近似表示连续的曲线函数，因此两者之间存在一定差异。可以用更小的步长使误差减小——计算量与精度之间的权衡数值计算方法数值计算方法31数值计算方法是一门根据计算机特点，研究通过计算机求工程问题满足精度要求的近似解的学科。将所欲求解的数学模型（数学问题）简化成一系列算术运算和逻辑运算，以便在计算机上求出问题的数值解，并对算法的收敛性、稳定性和误差进行分析、计算。算法数值计算方法32基本运算和运算顺序的规定所组成的整个解题方案和步骤。一般可以通过框图（流程图）来较直观地描述算法的全貌。选择合适的算法是整个数值计算中非常重要的一个环节。算法的选择数值计算方法33例：计算多项式的值直接计算，再逐次相加，共需只要n次乘法和n次加法即可。（霍纳Horner1819年）P(x)

axn

a xn

1

ax

an n

1 1 0iiax(i

0,1,2,

,

n)1

2

(n

1)

n

n(n

1)2次乘法和n次加法。秦九韶（我国宋朝数学家）算法（1247年）P(x)

((

((an

x

an

1

)x

an

2

)x

a2

)x

a1

)x

a0算法数值计算方法34算法的优劣直接影响计算的速度和效率对于小型问题，计算速度和占用计算机内存的多寡似乎意义不大，但对复杂的大型问题却起着决定性作用。不合适的算法还会由于计算机计算的近似性和误差的传播、积累直接影响到计算结果的精度，甚至影响到计算的成败。——算法的数值稳定性第一章

绪论数值计算方法35课程简介什么是数值计算方法？为什么学习数值计算方法？数值计算方法的主要内容数值计算中的误差误差的种类及其来源绝对误差与相对误差有效数字与误差舍入误差与截断误差误差的传播与估计算法的数值稳定性误差的种类数值计算方法36舍入误差（round-off

error）由于计算机只能表示有限位数的量而引起的截断误差（truncation

error）由于数值方法可能运用近似方法表示准确数值运算或数量而引起的不与数值方法本身直接相关的误差粗差形式化或模型误差数据不确定性误差有效数字（significant

digit）数值计算方法37为了正式规定数值的可靠程度一个数的有效数字是指可以放心使用的那些数字有效数字对应于确定数字和一个估计数字的总位数数值方法得到的是近似解，所以必须建立准则来规定近似结果的可信度。建立准则的一种方法是基于有效数字实现的，例如：如果有4位有效数字是正确的，可能就认定得到的近似结果是可以接受的。计算机只能保留有限个有效数字。保留有效数字后被省略的部分称为舍入误差。如：

3.141592653589793238462643

准确度（accuracy）与精确度（precision）数值计算方法38准确度计算值或测量值与真值接近的程度精度或精确度各计算值或测量值相互之间的集中程度准确度（accuracy）与精确度（precision）——射击的例子数值计算方法39准确度增加精确度增加(a)

既不准确也不精确(b)

准确但不精确(c)

不准确但精确(d)

既准确也精确数值计算方法40误差的定义数值误差源于用近似方法表示准确的数学运算和准确的数量数值误差包括截断误差和舍入误差当用近似方法表示准确数学过程时会出现截断误差当用有限个有效数字表示准确的数时会引起舍入误差绝对误差真值=近似值+误差 误差=真值-近似值相对误差E

x

x*rx

E

100%绝对误差可正可负，一般E的准确值很难求出。可用真值的最优估计值代替真值，或者给出误差的一个上界

(x*)（误差限）。当x=0时，相对误差无意义，准确值x往往未知，故常用x*代替x，相对误差限为

(x*)/|

x*

|。误差计算——例1数值计算方法41问题：假设对一座桥梁和一个铆钉的长度进行了测量，测量的结果分别为9999cm和9cm。如果真值分别为10000cm和10cm，计算两种情况下的真误差和真相对误差解：(a)桥梁的真误差为铆钉的真误差为(b)桥梁的相对误差为铆钉的相对误差为Et

10000

9999

1cmEt

10

9

1cm10000r

1

100%

0.01%10r

1

100%

10%尽管两个绝对误差都是1cm，但测量铆钉的相对误差要大得多，因此，我们对桥梁的测量已经够准确了，但对铆钉的估计在某种程度上偏离了希望值。误差——例2数值计算方法42已知

=3.1415926

，若取近似数为

x*

3.14

，则E

x*

0.0015926

，E

0.002

(x*

)

为

x*

的误差限，相*rx*

(x*)对误差限为

(x)

0.0007通常在x有多位数字时，若取前有限位数的数字作为近似值，都采用四舍五入原则，他们的误差限都不超过近似数x*末位数的半个单位，即

3.14

1

10

2

3.1416

1

10

42 2有效数字与误差的关系数值计算方法43,其中每个ai（i=1，2，

，n）均为0，1，2，

，9中的一个数字，且a1≠0，如果则称x*近似x有n位有效数字。如果x*具有n位有效数字，则其相对误差限为定义：设x*是x的一个近似数，表示为x*

10k

0.a1a2

an2x

x*

1

10k

n近似数的有效数字越多，相对误差限就越小，反之亦然。*11r2a

(x)

10

(n

1)迭代方法的误差估计数值计算方法44当前迭代结果的误差：

当前近似值

前一近似值

100%当前近似值a

采用绝对值是否小于预先设定好的容限

s

a

s如果下面的准则成立，则一般可以保证至少n位有效数字是正确的：

(0.5

102

n

)%s数值计算方法迭代方法的误差估计——例45问题：指数函数可以用下式表示（麦克劳林级数展开）计算的值，每加入一个新项后计算真误差和近似百分比相对误差。真值为，直到近似误差小于2 3!xx2 x3xnn!e

1

x

e0.5e0.5

1.648721

s，

s

必须符合3位有效数字的要求。项数结果

t(%)

a(%)1139.321.59.0233.331.6251.447.6941.6458333330.1751.2751.6484375000.01720.15861.6486979170.001420.0158

(0.5

102

3)%

0.05%解：误差准则：

s第一章

绪论数值计算方法46课程简介什么是数值计算方法？为什么学习数值计算方法？数值计算方法的主要内容数值计算中的误差误差的种类及其来源绝对误差与相对误差有效数字与误差舍入误差与截断误差误差的传播与估计算法的数值稳定性舍入误差数值计算方法47数的计算机表示计算机中的算术运算数的计算机表示数值计算方法48浮点表示例：1/34=0.029411765

以十进制浮点形式存储，并且只准许4个十进制为可用。 0.0294

1000.2941

10-1可以多保存一个有效数字尾数 基数r

m

be指数b1

m

1尾数符号有符号指数尾数仅保存了有限的有效数字，因此，会引入舍入误差。归一化2015/5/10数的计算机表示数值计算方法49例：对于一个用7位的字存储信息的计算机，建立一个假定的浮点数集合。用数的第一位表示符号位，接着的3位表示指数的符号和大小，最后的3位存放尾数。最小可能的正数为0111100数的符号指数的符号指数的大小尾数的大小最小可能的正浮点数100.5

2

3

(0.0625)增大100111101

(1

2

1

0

2

2

1

2

3

)

2

3

(0.078125)100111110

(1

2

1

1

2

2

0

2

3

)

2

3

(0.093750)100111111

(1

2

1

1

2

2

1

2

3

)

2

3

(0.109375)相邻两数间隔为0.015625100110100

(1

2

1

0

2

2

0

2

3

)

2

2

(0.125000)100110101

(1

2

1

0

2

2

1

2

3

)

2

2

(0.156250)100110110

(1

2

1

1

2

2

0

2

3

)

2

2

(0.187500)100110111

(1

2

1

1

2

2

1

2

3

)

2

2

(0.218750)相邻两数2015/5/10间隔为0.03125100011111

(1

2

1

1

2

2

1

2

3

)

23

(7)最大的数21 20 2-1 2-2 2-3数的计算机表示数值计算方法50溢出 070在0值附近的一个“洞”处会下溢x-

xx+

x

x/2

x/2舍入x-

x

x舍去2015/5/102015/5/10数值计算方法51数的计算机表示仅能表示有限范围内的数使用可接受范围以外的数会导致溢出。不能表示非常小的数，在0与第一个正数之间存在一个“洞”。在可接受数的范围内也只能表示有限个数无理数以及不与该集合中的数对应的有理数都不可能准确地表示——量化误差舍入（rounded

floating-point

representation）和舍去（choppedfloating-point

representation）有效数字足够多的情况下，总的舍入误差通常可以忽略不计。数之间的间隔随着数大小的增加而增大量化误差与数的大小成比例相对量化误差：舍去的情况 舍入的情况

为机器精度x

x

x

x 2

b1

t尾数有效数字个数数的计算机表示数值计算方法52机器精度：采用上例中的浮点系统，b=2，t=3，则

=21-3=0.25。对于舍去方法，量化误差小于0.25。最大相对误差2015/5/10误差幅度与量化误差的相关性有很多实际的应用：测试两个数是否相等在迭代过程中，当对一个量的收敛性或迭代过程是否中止，测试它们的差是否小于某个可接受的容限。用相对误差。可用机器精度作为停止或收敛准则。数的计算机表示数值计算方法532015/5/10测试机器精度的伪代码Epsilon=1DOif(epsilon+1<=1)

EXITepsilon=epsilon/2ENDDOepsilon=epsilon*2数的计算机表示数值计算方法542015/5/10多数计算机上的有效数字数目足够满足大多数工程计算的需要扩展精度双精度消除舍入误差的影响代价：更多的内存和计算时间计算机中的算术运算数值计算方法55通用算术运算（加、减、乘、除）——有效数字丢失当两个浮点数相加时，需要对较小的数的尾数进行调整，使两个数

0.0001

103=0.1000

100，之后的计算会把后面的3个0都作为有效数字当两个数非常接近时，会产生非常大的计算误差。乘法：指数相加，尾数相乘。两个n位尾数相乘得到2n位计算结果。0.1363

103

0.6423

10-1=0.08754549

102

0.8754

101除法：尾数相除，指数相减。然后对结果进行归一化和舍去处理。的指数相同0.1557.101例：0.1557

101+0.4381

10-10.004381.101将结果舍去处理后得0.1600

101 0.160081.101减法的执行过程类似，

0.0995

102=0.9950

1010.7642.1030.3641.102-0.7641.103-0.2686.1020.0001.1030.0955.1022015/5/10计算机中的算术运算数值计算方法562015/5/10大规模计算即使单个计算的舍入误差可能很小，但在大量计算过程中的累积效应可能非常严重。问题：对一个数求和100000次，对数1以单精度方式求和，对数0.00001分别以单精度和双精度方式求和。结果：对1进行单精度求和得到期望的结果，但对0.00001进行单精度求和的结果却具有较大的偏差，但当对0.00001进行双精度求和时，计算误差显著减小。根源：量化误差。因为整数1可以在计算机中准确地表示，所以对1可以精确地求和运算。0.00001不能在计算机中准确地表示，只能对其进行量化处理时，得到一个与真值略微不同的值，尽管这是一个非常微小的差异，对于小量计算可以忽略，但在重复进行大量计算后，这个误差会不断累积。在双精度情况下，量化误差要小得多，可以得到改善。在上述迭代操作中，所有误差具有相同的正负号。很多情况下，误差的符号

以随机模式不断交替的，经常相互抵销了，但有些情况下，这些误差没有被抵销掉，就会得到误差较大的结果。计算机中的算术运算数值计算方法57大数和小数相加例：一个小数0.0010和一个大数4000相加，使用一个假想的计算机，具有4位尾数和1位指数，对较小的数进行调整，使其指数与较大的数相匹配。将结果进行舍去处理得0.4000.104可以不执行这个加法！无穷级数求和：初始项通常大于后面的项反向求和：以升序而不是降序对级数求和当n趋于无穷时，无穷级数收敛于

4/90。采用单精度表示，编写一个程序计算n=10000时f(n)的值，分别按从i=1到10000和i=10000到1的顺序计算，对比误差并分析结果。0.4000.1040.0000001.1040.4000001.10412015/5/10i

1i4nf(n)

∑计算机中的算术运算数值计算方法58减性抵销——两个几乎相等的浮点数相减时所引起的舍入误差例：二次求根公式当时，分子可能非常小。可以用双精度或变换公式或先计算较大的根，再根据计算较小的根。

b

b2

4acx1,2

2ab2

4ac1,22x

2c b

b

4ac1

22015/5/10axx

c问题：当a=1，b=3000.001，c=3时，分别以单精度和双精度计算方程的根。（真实根为x1=-0.001，x2=-3000）计算机中的算术运算数值计算方法59拖尾效应（smearing）在求和过程中，如果某一项的值大于和值本身时，就会出现拖尾效应。在符号交替的级数中会出现这种现象。问题：指数函数以下面无穷级数的形式给出：分别计算x=10和x=-10时的函数值，研究其舍入误差。在不断地进行加减运算时，抵销了大量的有效数字。其他计算策略或扩展精度。内积使用扩展精度y

ex2 3!x2 x3y

1

x

n2015/5/10

xiyi

x1y1

x2y2

xn

yni

1指数函数运行结果数值计算方法602015/5/10x=10x=-10itermsumitermsum011011110111-10-925061250413166.6667227.66667183-166.6667-125.66667184416.6667644.3333744416.66672915833.33341477.6667485-833.3334-542.333374

270.091836922026.417968841280.032798922026.451171942290.0113122026.462890643-1.6552107e-0101.1033645569114e-04300.0037722026.4667969443.7618422e-0111.1033649207093e-04310.001216122026.4687545-8.3596498e-0121.1033648479497e-04Exact

value22026.465794806718Exact

value0.000045399929762截断误差与泰勒级数数值计算方法61截断误差是由于用近似过程代替准确过程而产生的误差。利用泰勒级数了解截断误差dv

v

v(ti

1)

v(ti

)dt

tti

1

ti近似真导数值2015/5/10泰勒定理数值计算方法62在包含a和x的区间上，如果一个函数f及其直至n+1阶导数都是连续的，那么该函数在x处的值可以表示为：n

(x

a)

Rnf

(a)2!f(x)

f(a)

f(a)(x

a)

f(n)

(a)n!2(x

a)

f (t)dtn!n

1x

x

t

nRn

a泰勒定理表明：任何光滑的函数都可以用多项式来逼近积分形式的余项n

1Rn

x

a

f

n

1

(

)

n

1

!应用中值定理，可以得到余项的拉格朗日形式：a和x之间的一个点2015/5/10泰勒级数数值计算方法630阶近似(zero-order

approximation)一阶近似(first-order

approximation)完整的泰勒展开f(xi

1)

f(xi

)f(xi

1)

f(xi)

f

(xi)(xi

1

xi

)ii

f

2!)

f

(x )

f(x)

f

(x

)(x

xf

(n)2 n(xi

1

xi

1 i i i

1)

(xi

1

xi

)

Rnn!f

n

1

(

)n

1Rn

n

1

!

xi

1

xi

存在一个值可以给出准确的误差表示定义步长h

xi

1

xinhn

Rf

(n)n!f

2f(xi

1)

f(xi)

f

(xi)h

2!

h

f

n

1

(

)2015/5/10n

1Rn

n

1

!

h泰勒级数展开的余项数值计算方法642015/5/10泰勒级数的多项式逼近数值计算方法65

2015/5/10例：当

xi

0,

h

1时，用零阶到四阶泰勒级数展开预测函数f

(x)

0.1x4

0.15x3

0.5x2

0.25x

1.2在xi

1

1处的函数值：解：

f

(0)

1.2n=0，

f

(xi

1

)

1.2Et

0.2

1.2

1.0

n=1，

f

(0)

0.25f

(xi

1

)

1.2

0.25hf(1)

0.95Et

0.2

0.95

0.75n=2，

f

(0)

1.0i

1f

(x )

1.2

0.25h

0.5h2f(1)

0.45tE

0.2

0.45

0.25泰勒级数的多项式逼近数值计算方法66四阶级数的泰勒级数展开将得到一个准确的估计结果：f

(x)

1.2

0.25h

0.5h2

0.15h3

0.1h452015/5/10f(5)(

)5!R4

h

0通常，n阶多项式的n阶泰勒级数展开得到的结果是准确的。对于其他连续可微函数，如指数函数和正弦函数，有限级数项是不可能得到准确结果的。每增加一项将使近似结果得到一定的改进，但改进程度不显著。多数情况下，泰勒级数展开的实际值只需要包含少数几项就可以得到非常接近真值的近似结果，对于实际应用来说足够了。泰勒级数展开的逼近误差数值计算方法67利用余项估计需要多少项及步长才能得到足够接近真值的近似值？

nhf

n

1

(

)n

1R

n

1!n2015/5/10R

O(hn

1

)误差与步长的n+1次方成比例。如果误差的量级为

O(h)，那么步长减半就会使误差也减半。如果误差的量级为

O(h2

)，那么步长减半就会使误差变为原来的四分之一。一般地，假定截断误差随泰勒级数项数的增加而减小。在许多情况下，如果h足够小，一阶、二阶以及其他低阶项通常不成比例地占估计值的绝大部分。因此，只需要少数项就可以获得一个足够精确的估计值。2015/5/10数值计算方法68泰勒级数展开的逼近误差例：利用泰勒级数展开，基于f(x)=cos(x)在

xi

/4

处的函数值和导数值，用n=0~6共7项来逼近

xi

1

/3

的值。解：

h

/

3

/

4

/12阶数nf(n)

x

f

/

3

百分比相对误差0cosx0.707106781-41.41-sinx0.512986659-4.42-cosx0.4977544910.4493sinx0.4998691472.62

10-24cosx0.500007551-1.51

10-35-sinx0.500000304-6.08

10-56-cosx0.4999999882.44

10-6f

/3

0.5增加更多的项，误差的改进可以忽略不计。利用泰勒级数估计截断误差数值计算方法69降落伞问题：将v(t)展开成泰勒级数截去一阶导数项以后的各项可得：ni

i

1 i(t

t)2

Ri2!v(t

)v(ti

1

)

v(ti

)

v

(ti

)(ti

1

t

)

v(ti

1

)

v(ti

)

v

(ti

)(ti

1

ti

)

R1v

(t)

v(ti

1 )

v(ti )

R1 i t

t t

ti

1 i i

1 i一阶逼近 截断误差f

n

1

(

)n

1Rn

n

1

!

ht

i

1 ii

1 iR1t

t2!

v

(

)

t

O

t

t

2015/5/10i

1 ii

1 iR1t

t导数的近似误差与步长成比例。如果将步长减半，则导数值的误差也减半。0.5122.502468101214161.5xf(x)m=4m=3m=2m=1非线性与步长对泰勒级数逼近的影响数值计算方法70

一阶泰勒级数展开：问题：

f

(x)

xm

,

m

1,

2,

3,4

x

[1,

2]ii

1 if

(x )

f(x)

mxm

1h22015/5/10341

i

2!

i

3!

i

4!f(3)(x

)f(4)(x

)R

f

(x

)h

h

h

随着函数非线性程度的增大，一阶泰勒级数逼近的误差增大。随着步长的减小，一阶泰勒级数逼近的误差减小。第一章

绪论数值计算方法712015/5/10课程简介什么是数值计算方法？为什么学习数值计算方法？数值计算方法的主要内容数值计算中的误差误差的种类及其来源绝对误差与相对误差有效数字与误差舍入误差与截断误差误差的传播与估计算法的数值稳定性误差传播——单变量函数数值计算方法72假设一个函数f(x)，设

x

是x的近似值，估计x和

x

的差异对函数值的影响，即

f

x

f

x

f

x

如果f(x)连续可微，用泰勒级数计算逼近

f

x

的

f

x

2舍去二阶及二阶以上的项，并重新整理：f

x

f

x

f

x

x

x

f

x

x

x

2

f

x

f

x

f

x

x

x

或函数值的误差估计函数的导数自变量的误差估计值

f

(x

)

f

(x

) x

x

2015/5/10一阶误差传播的图形描述数值计算方法73xf(x)xx

真误差估计误差

x

x

x

2015/5/10单变量函数的误差传播数值计算方法74解：问题：给定一个值

x

2.5 ，其误差为

x

0.01

，估计由此导致的函数值

f

(x)

x3

的误差。

f

x

f

x

x

x

3(2.5)2

(0.01)

0.1875由于2015/5/10f(2.5)

15.625可以预测：

f

(2.5)

15.625

0.1875误差传播——多变量函数数值计算方法75一个具有两个变量u和v的函数，泰勒级数可以写为舍去二阶和高阶项多变量函数22iiui

1 i

1 i ii

1i

1f

(u ,

v )

f(u,v)

f

(u

u)

f

(v

v

)

u

v

2

f

2

f 2

1

2

f

2!

(ui

1

ui

)

2

u

v(ui

1

ui)(vi

1

vi)

v2(vi

1

vi)

f(u

,v

)

f

u

f

v

u

v12015/5/102121 2 nnn

x

x

x

f(x

,x

,

,x

)

f

x

f

x

f

x

一般数学运算的误差传播关系数值计算方法76运算估计误差加法

(u

v

)

u

v

减法

(u

v

)

u

v

乘法

(u

v

)u

v

v

u

除法

u

v

u

v

v

u

v

22015/5/10误差传播——例数值计算方法77初始误差可稳定传播或不稳定传播例：用无限精度算法结合下列3个方案可递归生成序列中的各项值。

1/

3n

n

002015/5/100 10 13(2)3 333 3nnnn

1n

1n

2n

1n

2(1) r

1,r

1

rp

1,

p

1

,

p

4

p(3) q

1,

q

1

,

q

10

q,

n

1,

2,

1

p ,

n

2,

3,

q ,

n

2,

3,

误差传播——例数值计算方法78(2)差分方程的通解是pn

A(1/3)

Bn验证如下：3 32015/5/103 33 33 3n n3nn

1 n

2n

1An

21

p4

p

4

A

B

1

B

4

3

A

4

1

B

A1

B

3 3

pn设A=1且B=0，可得到期望的序列。误差传播——例数值计算方法79(3)差分方程的通解是pn

A(1/3)

B3n n验证如下：3 3 32015/5/1033 3n n3nAn

1n

2n

1 n

2n

1n

2

10

p

10

Ap

B3

B3

10

9

A

10

1

3n

2

B

A

1

B

3n

pn设A=1且B=0，可得到期望的序列。误差传播——例数值计算方法80

试研究每个算法的误差传播情况。例：用下列方法求出序列

xn

13n

的近似值。02015/5/103333n0 1 nn

1n

1n

20 1 n n

1 n

2(1) r

0.99996,r

1

r(2) p

1,

p

0.33332,

p

4

p(3) q

1,

q

0.33332,

q

10

q,

n

1,

2,

1

p ,

n

2,

3,

q ,

n

2,

3,

r0初始误差为0.00004，p1,

q1

初始误差为0.00001333，误差传播——例数值计算方法81nxnrnxn

–rn(10-4)pnxn

–pn(10-4)qnxn

–qn01.00000000000.99996000000.4000001.00000000000.0000001.00000000000.000000000010.33333333330.33332000000.1333330.33332000000.1333330.33332000000.000013333320.11111111110.11110666670.0444440.11109333330.1777780.11106666670.000044444430.03703703700.03703555560.0148150.03701777780.1925930.03690222220.000134814840.01234567900.01234518520.0049380.01232592590.1975310.01194074070.000404938350.00411522630.00411506170.0016460.00409530860.1991770.00290024690.001214979460.00137174210.00137168720.0005490.00135176950.199726-0.00227325100.003644993170.00045724740.00045722910.0001830.00043725650.199909-0.01047775030.010934997780.00015241580.00015240970.0000610.00013241880.199970-0.03265258340.032804999290.00005080530.00005080320.0000200.00003080630.199990-0.09836419450.0984149997100.00001693510.00001693440.000007-0.00000306460.199997-0.29522806480.29524499992015/5/10012345678910012x10-5x-r123456789100012x10-5x-p12345678910000.20.4x-q误差传播——例数值计算方法82误差是稳定的，且按指数级递减误差是稳定的，但误差占支配地位误差是不稳定的，按指数级增长2015/5/10第一章

绪论数值计算方法832015/5/10课程简介什么是数值计算方法？为什么学习数值计算方法？数值计算方法的主要内容数值计算中的误差误差的种类及其来源绝对误差与相对误差有效数字与误差舍入误差与截断误差误差的传播与估计算法的数值稳定性稳定性与条件数数值计算方法84f

x

f

x

f

x

x

xxPf

x

K

xf

x

f

x

f

x

f

x

x x

xKP

1病态问题y=f(x)2015/5/10xx

yy

x

x(1

)y

y(1

)稳定性与条件数数值计算方法85一个算法如果原始数据有误差，而计算过程舍入误差不增长，则称此算法是数值稳定的，否则，若误差增长，则称算法是不稳定的（numerically

unstable）。（输入值的不确定性通过数值方法在总体上是放大的）条件数（condition

number）定义为相对误差之比：f(x)与x的相对误差分别为条件数为条件数体现了x的不确定性被f(x)放大程度。如果条件数等于1，表示函数的相对误差等于x的相对误差，如果条件数大于1，表示相对误差被放大了，而条件数小于1，表示相对误差减小了。条件数非常大(大于等于10)的函数称为病态（ill-conditioned）函数。f(x)

f(x

)

f

x

x

x

f

(x

) f

(x

)x

x

x

x

f

x

f

(x

)2015/5/10问题条件数与算法条件数数值计算方法86例：问题条件数f

(x)

x2

1

xx

100

f

(x)

0.5

10

2xf

(x)

1x2

1f

x

f

x

f

x

1

0.1

103

0算法A：4位有效数字x

0.1

103

f

(x

)

(0.1000

0.00001)

105

x

x

1101

t

110

3x 2 2KP

1

KA

2000算法条件数，改善方法：提高精度，重写算法算法B：f

(x)

1 x2

1

x

0.5

10

210.1

103

0.1

103f(x

)

0

KA

0

12015/5/10(当x>>1时)总的数值误差数值计算方法872015/5/10截断误差和舍入误差之和通常，最小化舍入误差的方法是增加计算机的有效数字个数缩短步长使截断误差减小但缩短步长可能导致减性抵销或增加计算量，使舍入误差增大大多数计算机可以表示足够多的有效数字，因此舍入误差不会占主导地位避免误差危害的原则数值计算方法882015/5/10选择数值稳定的计算方法，避开不稳定的算式。注意简化计算步骤及公式，设法减少运算次数；选用运算次数少的算式，尤其是乘方幂次要低，以减少舍入误差，同时可节约计算机的机时。合理安排计算顺序，防止大数“淹没”小数。多个数相加时，最好从绝对值最小的数到绝对值最大的数依次相加；多个数相乘时，最好从有效位数最多的数到有效位数最少的数依次相乘。避免两相近数相减。避免用绝对值很小的数作为除数。第一部分

总结（一）数值计算方法892015/5/10数学问题的类型数值方法的特点稳定性准确性与精确性收敛速度第一部分

重要关系数值计算方法902015/5/10误差真误差真百分比相对误差近似百分比相对误差停止准则泰勒级数泰勒级数展开余项误差传播Matlab基础数值计算方法912015/5/10Arithmetic

Operations

（算术符号）Built-in

Functions（内建函数）Assignment

Statements（赋值语句）DefiningFunction（函数定义）Matrices（矩阵）Matrix

Operations（矩阵运算）Array

Operations（数组运算）Graphics（图形）Loops

and

Conditionals（循环和条件）Programs（程序）插值和拟合数值计算方法1举例数值计算方法2t(s)v(t)(m/s)0010227.0415362.7820517.3522.5602.9730901.672016/6/12已知火箭在几个不同时刻的速度如下表所示，求t=16时的速度？插值和拟合数值计算方法3(a)

用直线段连接这些点数据点分布接近线性或彼此距离很近(b)

用曲线描述了数据所具有的局部变化趋势(c)

体现了数据总体的趋势最小二乘回归线性插值非线性插值2016/6/12插值和拟合——概述数值计算方法4x0x1x2x3x4x问题：有的函数虽有表达式，但较复杂，也可用简单的函数g(x)来逼近它某些变量之间的函数关系y=f(x)存在，但没有f(x)的解析式，y=f(x)以函数表格或曲线形式给出要求：根据函数表推算该函数在某些点上的函数值。解决与该函数有关的一些问题，如分析函数的性态，研究y=f(x)的变化规律，求导数、积分、零点与极值点等。g(x)

f(x)xx0x1…xnf(x)y0y1…yn2016/6/12插值和拟合——概述数值计算方法52016/6/12数学函数的逼近问题高精度快速计算建立实验数据的数学模型只要求适度的精度插值拟合不要求过所有的点（可以消除误差影响）尽可能表现数据的趋势，靠近这些点用某个简单函数在满足一定条件下在某个范围内近似代替另一个较为复杂或者解析表达式未给出的函数，以便于简化对后者的各种计算或揭示后者的某些性质。本章内容数值计算方法62016/6/12插值插值问题Lagrange插值多项式Newton插值多项式分段低次插值样条插值拟合最小二乘方法插值问题数值计算方法7插值函数y=f(x)

在区间[a,b]上连续，

x0,x1,…,xn是[a,b]上的n+1个互异的点，且在这些点处函数值yi=f(xi)已知

为给定的某一函数类（性质优良、便于计算）g(xi)

=yi (i=0,1,…,n)插值节点插值区间插值条件插值函数类插值函数基本问题是否存在唯一如何构造误差估计插值函数类代数多项式有理函数三角函数ninia

xg(x)

i

0

1n,m

m 0mPn

x

x

0 1 n p

px

p

xnQ

x

q

qx

q

xm多项式插值被插函数2016/6/12有理函数：选取有理函数（多项式的商）作为插值函数。i

ina

xi

0P(x)

mnQm

x

x q0

q1x

qmx

P

x

p

px

p

xn0 1 nn,m有理插值可使区间内插值误差分布较为均匀，特别适用于某些被插函数具有无穷大间断点的附近，这种情况下若用多项式逼近效果很差。三角函数：选取正弦和余弦等三角函数作为插值函数。=> 选择不同的函数类作为插值函数逼近f(x)，其效果是不同的，因此需要根据实际问题选择合适的插值函数。插值问题插值函数类代数多项式：选取多项式Pn(x)作为插值函数，Pn(x)称为插值多项式。n插值函数存在唯一定理数值计算方法9特点：与插值节点有关与原函数f(x)无关基函数个数与点个数相同g(x)

a0

0

(x)

an

n

(x)g(xi

)

f

(xi

)

a0

0

(xi

)

an

n

(xi

)

f(x0

)

0(x0

)

0(xn)

n(xn)

an

f(xn

)

n(x0)

a0

a0

an

有唯一解0 n2016/6/12n n

(x

)

(x

)

0

(x0

)

n(x0

)

0

设则则

定理：为n＋1个节点，n+1维空间，则插值函数存在唯一，当且仅当

nixi

0

span{

0

,

1

,

n

}

0(x0

)

0(xn

)插值函数存在唯一定理数值计算方法102016/6/12

n(x0

)

0

n(xn

)插值多项式存在唯一性数值计算方法11若插值节点互异，则存在唯一的多项式Pn(x)使f(xi)=Pn(xi) i=0,1,…,nn

P

(x)

span{1,

x,

x2

,

xn

}02016/6/1200i jn n n1 xx2 xnx2xnx2xnn i

1i

1 j

0V

(x

x

)

1 x1 1

1

1 x

n+1阶范德蒙(Vandermonde)行列式本章内容数值计算方法122016/6/12插值插值问题Lagrange插值多项式Newton插值多项式分段低次插