S vt0 V
据此有 Vt1 vt0 S ，两端同除以 V v ，有
S t * 由于 V v
V v S t1 t0 V v V v V v
为人龟追赶问题的精确解，
由此可见，精确解等于任给预报值同它的校正值的加权平均：
其中
v V v
t* (1 )t1 t0
数
值
分
析
——插值、拟合与数值微积分
：
1
• 引例
数值分析(计算方法)简介
a11 x1 a1n xn b1 a x a x b nn n n n1 1
考虑如下线性方程组
(1)
或者：
Ax b
其中 det(A) 0 , 由克莱姆法则可知 (1)有唯一的解，而且解为：
, a3 0.8610 ，其绝对误差限都是0.005， 例 设近似值 a1 1.38, a2 0.0312 求各个近似值各有几位有效数字？
解
4
3 李庆扬. 数值分析. 清华大学出版社，2001.
4 白峰杉. 数值计算引论. 高等教育出版社, 2004. 5 王能超. 计算方法. 北京: 高等教育出版社, 2005
8
数值分析的基本概念
内容:
• • • • • 算法设计技术 误差 数值计算中需要注意的一些问题 算法的稳定性 病态问题
9
算法设计技术
1 a x1 x0 2 x0
0出发，利用上式反复迭代，即可获得满足精度要求的开
1 a xk , k 0,1, 2, 2 xk
校正技术的基本思想：删繁就简，逐步求精 ！ 17
• 算法优化的松弛技术 再考察Zeno算法： 对于给定的预报值 t 0 ，校正值为 t1
数列求和问题：
S a0 a1
an
（1 ）
是最简单的计算模型。若记表示前n项的部分和，则有
b0 a0 bk bk 1 ak , k 1,2,
S bn
（2 ）
,n
（3 ）
则计算结果即为所求的和值：
可见，上述累加求和算法的设计思想是将多项求和（1）化归为两项求和 （2）的重复，最终加工成一项和式（3）（(1)的退化情形）,从而得出 和值。 这样，如果定义和式的项数为数列求和问题的规模，则所求和值为（1） 的退化情形。因之，只要令和式的规模逐次减1，最终当规模为1时即可 直接得出所求的和值，而这样设计出来的算法就是累加求和算法（2）。 13
S vt0 t1 V
V
Zeno悖论所描述的逼近过程正是这种迭代过程，当k→∞时，tk →t* （问题2: 证明该结论！）。大家知道，任何形式的重复都可看成是 “时间”的量度。Zeno在刻画人龟追赶问题中设置了两个“时钟”：一 个是日常的钟，另外Zeno又将迭代次数视为另一种时钟，不妨称之为 Zeno钟。Zeno公式（2）表明，当Zeno钟趋于∞时人才能追上龟，Zeno 正是据此断言人永远追不上龟。
S0 S , Sk Sk 1 v
V
k 1, 2,
——Zeno算法
可见，Zeno算法的设计思想是，将人龟追赶计算化归为简单的行 程计算的重复，它的设计方法是逐步压缩计算模型的规模，这种 “化大为小”的设计策略称为规模缩减技术，简称缩减技术。 算法的设计精髓：“简单”的重复生成复杂！
12
• 直接法的缩减技术

学习过程中应该注意以下几个方面： 认清算法的计算对象； 掌握基本的计算方法及其原理； 用C++语言编制程序，在计算机上对算法进行验证； 对于算法要勤思考多比较！
7
参考书目：
1 钟尔杰. 数值分析. 高等教育出版社，2004. 2 颜庆津. 数值分析. 修订版. 北京航空航天大学出版社, 2000.
x
x

注: 用绝对误差来刻画近似数的精确程度不能反映它在原数中所占的比例。
, a 0.001 例 x 0.0002 e x a 0.001 ，可是 a 与真值 x 相差一个数量级。
e xa e xa e 记 er ，称 er为近似值 a 的相对误差，也可以记为 r a a x x
2
a 成立，
2
设校正量 x是个小量，舍去上式中的高阶小量 x ， 令 x0 2 2 x0 x a ，从中定出 x ，继而可得校正值：
近似
问题3:编程实现!要 求：画出流程图， 初始值由键盘输入。 反复实施这种预报校正手续，即可导出开方公式 ：
xk 1
从某个初值 x0 方值 a 。
er 的一个上界 r
上例中 er

a
,称为近似值 a 的相对误界
xa 0.0002 0.001 0.8 ，易见近似程度并不高！ a 0.001
21
(2) 有效数字
定义 设 a是数 x 的近似值，如果 a 的绝对误差限是它的某一 位的半个单位，且从该位到 a 的第一位非零数字共有n 位，则 称 a 作为 x 的近似有 n 位有效数字。
a11 a1i 1 b1 Di xi , D det(A), Di det D a a bn ni 1 n1
2
a1i 1 a1n ani 1 ann
首先看一个简单的例子：
x1 x2 1 误差的分类
模型误差
按 来 源 分 类
观测误差 截断误差 数值分析进行误差分析的对象 舍入误差
20
• 误差和有效数字
(1) 误差
定义 设 是准确值， a是 的一个近似值，记 e x a，称 e为近似 值 a 的绝对误差，简称误差。 若已知 e 的一个上界为 ，即 e ，则称 为近似值 a 的绝对误差界， 简称误差界（越小表示近似程度越高）。
引例 古希腊哲学家Zeno在两千多年前提出过一个骇人听闻的命题： 一个人不管跑得多快，也追不上爬在他前面的一只乌龟。这就 是著名的Zeno悖论。 Zeno在论证这个命题时采取了如下形式的逻辑推理：设人与龟 同时同向起跑，如果龟不动，那么人经过某段时间便能追上它； 但实际上在这段时间内龟又爬了一段路程，从而人又得重新追 赶，如下图所示，这样每追赶一次所归结的是同样类型的追赶 问题，因而这种追赶过程“永远”不会终结。
10
tk-1 tk
V
v
Sk-1
V
v
Sk
图示: 人龟追赶过程
耐人寻味的是，尽管 Zeno悖论的论断极其荒谬，但从算法设计思想的角 度来看它却是极为精辟的。Zeno悖论将人龟追赶问题表达为一连串追赶 步的逐步逼近过程。设人与龟的速度分别为V与v，记Sk表示逼近过程的第 k 步人与龟的间距，另以 tk 表示相应的时间，相邻两步的时间差为 Δtk 。 Zeno悖论将人龟追赶问题分解为一追一赶两个过程： 追的过程：先令龟不动，计算人追上龟所费的时间
有些问题的“大事化小”过程似乎无法了结。Zeno悖论强调人“永远”赶 不上龟正是为了突出这层含义。这是一类无限逼近的过程，适于用所谓预 报校正技术来处理。 设人龟起初相距 S ，两者的速度分别为 V 和 v ， 则有方程
S 易得人追上龟所花的时间是 t* V v 设解t*有某个预报值t0，希望提供校正量△t，使校正值t1= t0+ △t 能 更好的满足所给方程（1），即使得
16
给定 a 0 ，求开方值 a 的问题就是要求解方程 （1） x2 a 0
利用校正技术，设计求解 a （ a 0 ）的算法。 设给定某个预报值 x0 ，希望借助于某种简单方法确定校正量 x ，使校正值 能够比较准确地满足方程（1），即使 x0 x
x1 x0 x
3
研究对象和主要内容
实际问题 数学模型 算法设计
应用数学
程序设计
计 算 数 学
上机求解
4
数值分析（数值计算方法），是一种研究如何求解数学
问题数值近似解的方法，是在计算机上使用的解数学问 题的方法，简称计算方法。包括直接方法和迭代方法!
直接解法 若计算过程没有舍入误差，经过有限次算术运算就能 求出问题精确解的数值方法。 迭代解法 若计算过程没有舍入误差，也不能经过有限次算术运 算求得问题的精确解，而只能是逐步逼近的数值方法。
数值分析（数值计算方法）的计算对象是线性代数，微积
分，常微分方程中的数学问题。内容包括：求解线性方程 组的数值解法、计算矩阵特征值和特征向量、非线性方程 和非线性方程组的迭代解法、插值与拟合、数值微积分和 常微分方程数值解等问题。
5
特点
面向计算机 收敛性 有可靠的理论分析 特点 稳定性
时间复杂度 有较好的计算复杂性 空间复杂度 有数值实验
x1 1 x2 2
（若是更高阶的方程组呢？）
若行列式用按行（列）展开的方法计算 ，
用克莱姆法则求解（1）需做乘除法的次数: (n 1)(n 1)n ! 当方程组阶数较高时，计算量很大，因此克莱姆法则通常仅有理论上的 价值，计算线性方程组的解还要考虑数值解法 = 算法 + 计算机。 人类的计算能力是计算工具和计算方法效率的乘积，提高计算方法的效 率与提高计算机硬件的效率同样重要。科学计算已用到科学技术和社会 生活的各个领域中，成为继实验和理论研究之后的第三种研究方法。
即在松弛过程中张扬 F1 的优势而抑制 F0 的劣势，这种设计策略称作外 推松弛技术，简称超松弛。 总之，超松弛的设计机理是优劣互补，化粗为精。松弛技术的关键在 于松弛因子的选取，而这往往是相当困难的。
在实际计算中常常可以获得目标值 F * 的两个相伴的近似值 F0 与 F1 ， 将它们加工成更高精度的结果的方法之一就是取两者的某种加权平均作 为改进值：
，
可以看到，这里任意一对迭代值经过上述手续松弛即可得到问题的 精确解。这种加工效果是奇妙的。