计算方法第1章-诸论.doc

第一章 绪 论
§1.0 引 言
§1.1 数值算法概论
(1) 计算方法的研究内容、对象与特点
(2) 基本求解步骤
§1.2 预备知识、误差
(1) 误差的来源
(2) 误差分析、数值稳定性的分析和说明
(3) 误差的基本概念——绝对误差 相对误差 有效数字
(4) 数值算法

18

§1.0 引 言
¨ 现代科学的三个重要组成部分: 科学理论, 科学实验, 科学计算。
它们相辅相成，互相独立，可以互相补充又都不可缺少，作为三种科学研究手段之一的科学计算是一门工具性、方法性、边缘性的新学科，发展迅速，它的物质基础是计算机(包括其软硬件系统)，其理论基础主要是计算数学。
¨ 科学计算的核心内容是以现代化计算机以及数学软件为工具，以数学模型为基础进行模拟研究。
¨ 出现了形如:计算数学,计算物理学,计算力学,计算化学, 计算生物学,计算地质学,
计算经济学等许多新学科及其发展。并已形成一系列专门研究数学问题的数值解法的算法软件，如目前流行的数学软件主要有以下几种：
符号运算软件： Mathematica, Maple
矩阵处理软件： Matlab Matlab简介
统计处理软件： SAS, Spss, Origin
数学CAD软件： MathCAD
等功能强大的著名数学软件。

§1.1 数值算法概论
§1.1.1 计算方法的研究内容、对象与特点
内容：
(1) 数值代数: 求解线性方程组的解法（分直接方法和间接方法），求矩阵的特征值与特征向量。
(2) 数值逼近：插值和数值逼近，数值微分和数值积分。
(3) 方程求解：非线性方程、常微分方程、偏微分方程数值解法。
对象：
(1) 计算方法是一门与计算机应用密切结合的实用性很强的学科； 思维方法是归纳法，核心问题是“误差”或误差分析。
(2) 计算方法这门课程讨论连续变量问题又要讨论离散变量问题，关心的是数值结果。
(3) 计算方法这门课程已成为近代数学的一个重要分支。
特点：
(1) 面向计算机
将计算机上不能执行的运算化为在计算机上可执行的运算;
(2) 有可靠的理论分析（收敛性、稳定性、误差分析）。
因为可能采用了近似等价运算,故要进行误差分析,即数值的性态及数值方法的稳定性。
(3) 要有好的算法，并考虑计算复杂性（时间、空间）
针对所求解的数值问题研究在计算机上可执行的且有效的计算公式。
(4) 要有数值试验

§1.1.2 基本求解步骤
实际
问题
建立数学模型
构造数值 算法
编程上机
计算结果

说明：
(1) 数学模型是通过科学实验或者观察分析一系列数据后，用数学作为工具近似地描述客观事物的一种数学表达式。
在数学模型中，往往包含了若干参量如物体比重、阻力系数、热交换系数等，这些物理参数通常由实验仪器测得，根据仪器的精密程度，物理参数的确定也会产生一定的误差。
(2) 在建立了数学模型之后，并不能立刻用计算机直接求解，还必须寻找用计算机计算这些数学模型的数值方法，即将数学模型中的连续变量离散化，转化成一系列相应的算法步骤，编制出正确的计算程序，再上机计算得出满意的数值结果。
(3) 算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。
评价算法的两个主要标准：计算速度和计算精度，此外，还有计算存贮量等。 一个面向计算机,计算复杂性好,又有可靠理论分析的算法就是一个好算法.
计算复杂性是算法好坏的标志，它包括时间复杂性(指计算时间多少)和空间复杂性(指占用存储单元多少)。对很多数值问题使用不同算法，其计算复杂性将会大不一样，例如对20阶的线性方程组若用代数中的Cramer法则作为算法求解，其乘除法运算次数需要，若用每秒运算1亿次的计算机计算也要30万年，这是无法实现的，而用"计算方法"中介绍的Gauss消元法求解，其乘除法运算次数只需3 060次，这说明选择算法的重要性。当然有很多数值方法事先不可能知道其计算量，故对数值方法除理论分析外，还必须通过数值试验检验其计算复杂性。作为基本要求希望读者能适当做一些计算机上的数值试验，对加深算法的理解是极有好处的。
例1.1：计算多项式的值。
算法1
由计算出后再计算。
说明：需乘法6次，加法3次，存储单元7个。

算法2
计算。
说明：需乘法3次，加法3次，存储单元7个。
例1.2：计算n次多项式的值。
算法 采用：秦九韶算法(1247) (又称为Horner算法(1819))
计算。

说明：需乘法n次，加法n次，存储单元n+3个。
上述秦九韶算法的结构是递归的，它通过一次式的反复计算，逐步降低多项式的次数，直到归结为零次式为止。若以多项式的次数（或项数）定义为求值问题的规模，则秦九韶算法的特点是，在递归计算的过程中问题的规模逐次减1。

例1.3：计算在某点的值。
数学上有如下算法:
算法(1)
算法(2)

显然：算法（1）的计算量N=63次乘法；
由于算法（2）中，故计算量N=11次乘法。
算法（2）比算法（1）好。

§1.2 预备知识和误差
§1.2.1 误差的来源

实际问题è建立数学模型è研究计算方法è编程上机计算è解结果

a) 模型误差:
在建立数学模型过程中,不可能将所有因素均考虑,必然要进行必要的简化,这就带来了与实际问题的误差。
b) 测量误差: 测量已知参数时,数据带来的误差。
c) 截断误差: 在设计算法时,必然要近似处理,寻求一些简化。
d) 舍入误差: 计算机的字长是有限的,每一步运算均需四舍五入，由此产出的误差称舍入误差。如：π、1／3，……取小数点8位、16位。
[截断误差的实例]
例1.4：
当很小时，可用作为的近似值，其截断误差小于。

例1.5： 已知：
求的近似值，并估计误差。
分析：对函数用Taylor展开，用多项式

近似代替，则数值方法的截断误差为
。

解：利用展开式的前三项，取n=2，

截断误差为：

数值计算方法主要讨论截断误差和舍入误差的影响,不讨论模型误差和测量误差。

§1.2.2 误差分析的重要性以及数值稳定性
一个数值方法进行计算时，由于原始数据有误差，在计算中这些误差会传播，有时误差增长很快使计算结果误差很大，影响了结果不可靠.
定义　一个算法如果原始数据有扰动(即误差)，而计算过程舍入误差不增长，则称此算法是数值稳定的.否则，若误差增长则称算法不稳定.
例如：计算并分析误差

解：
由积分估值

由积分性质知
设计如下两种算法：
[算法1]：
取，按公式
（n=0，1，2……）
依次计算的近似值。
设。
假设计算过程中不产生新的舍入误差，则有
（n=0，1，2……）
误差扩散。
[算法2]：
从计算，应有
。
在运算过程中，舍入误差不增大,数值稳定。

n

0
0.182
0.182
0.182
1
0.088
0.090
0.088
2
0.058
0.050
0.058
3
0.0431
0.083
0.0431
4
0.0343
-0.165
0.0343
5
0.0284
1.025
0.0284
6
0.024
-4.958
0.024
7
0.021
24.933
0.021
8
0.019
-124.540
0.019

[关于数值稳定性的算法]
v 误差的传播与积累
例：蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！
v 以上是一个病态问题

例5: ,
解：用分部积分公式得递推式:
。
用四位有效数字计算: ,
, ,
, ,
, ,
,.
分析1：
可以估计出 故
,。
于是与精确值已经面目全非,一位有效数字也没有。
这是由于如果有误差,不计中间再产生的舍入误差,该误差随着计算过程分别乘以,到时已经变成了,误差扩大了4万倍。因而该算法不是稳定的。
分析2：
如果递推式改为,由
, ,
逐步计算直到。计算结果有四位有效数字,如果有误差,其传播到所引起的误差仅为。故该算法是稳定的。

三、误差的基本概念
(1) 误差与误差限
是精确值, 是它的一个近似值，称

是近似值的绝对误差。简称误差。
误差是有量纲的,可正可负。
误差是无法计算的,但可以估计出它的一个上界。即
,
称是近似值 的误差限,即 。

(2) 相对误差与相对误差限
称为近似值的相对误差,记作。
相对误差是个相对数,是无量纲的,也可正可负。
相对误差的估计,称为相对误差限,即
。
实际中, 是未知的,可用来代替。
当较小时,因两者的差为:
是的高阶无穷小，可忽略不计。

(3) 有效数字
定义: 如果近似值的误差限是 (某一数位的半个单位),
则称准确到小数点后位,并从第一个非零的数字到这一位的所有数字均为有效数字。
如：
3.14有三位有效数字,误差限ε=0.005;
3.1416有五位有效数字,误差限为0.00005。
如：＝
近似值准确到小数点后五位，有三位有效数字。

(4) 有效数字与误差限的关系：
有n位有效数字，标准形式为，
则有。
有效位数越多，（绝对）误差限越小。

e) 有效数字与相对误差限的关系：

定理1：
，若有位有效数字，
则其相对误差限为

反之，若的相对误差限为

则至少具有n位有效数字。

证：因 ，故当有n位有效数字时，
。
反之，由
因此，至少具有n位有效数字。 证毕
定理说明，有效位数越多相对误差限越小。
实例
例1 设= p=3.1415926…
近似值x=3.14＝0.314×101,即m=1，它的绝对误差是 －0.001 592 6…，
有
即l=3，故x=3.14有3位有效数字。x=3.14准确到小数点后第2位。
又近似值x=3.1416，它的绝对误差是0.0000074…，有

即m=1,l＝5，x=3.1416有5位有效数字。
而近似值x=3.1415，它的绝对误差是0.0000926…，有

即m=1,l＝4，x=3.1415有4位有效数字。
这就是说某数有s位数，若末位数字是四舍五入得到的，那么该数有s位有效数字；
例2 指出下列各数具有几位有效数字，及其绝对误差限和相对误差限：
2.000 4 －0.002 00 9 000 9 000.00
解 因为x1=2.000 4＝0.200 04×101, 它的绝对误差限0.000 05=0.5×10 1―5，即m=1,l=5,故x=2.000 4有5位有效数字. a1=2，相对误差限
x2=－0.002 00，绝对误差限0.000 005，因为m=－2，l=3，x2=－0.002 00有3位有效数字. a1=2，相对误差限er==0.002 5
x3=9 000，绝对误差限为0.5×100，因为m=4, l=4, x3=9 000有4位有效数字，a=9，相对误差限er＝＝0.000 056
x4=9 000.00，绝对误差限0.005，因为m=4，l=6，x4=9 000.00有6位有效数字，相对误差限为er=er＝＝0.000 000 56
由x3与x4可以看到小数点之后的0，不是可有可无的，它是有实际意义的。
例3 ln2=0.69314718…，精确到10－3的近似值是多少？
解 精确到10－3＝0.001，即绝对误差限是e＝0.0005, 故至少要保留小数点后三位才可以。ln2=0.693

§1.2.4 数值算法
例:求解微分方程:

将其变成数值问题，即将其“离散化”

“离散化”是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一。

[计算方法的主要任务]
1. 将计算机上不能执行的运算化为在计算机上可执行的运算；
2. 针对所求解的数值问题，研究在计算机上可执行的且有效的计算公式；
3. 因为可能采用了近似等价运算,故要进行误差分析,即数值问题的性态及数值 方法的稳定性。

Matlab简介：

MATLAB的含义是矩阵实验室,是Matrix Laboratory的缩写。它的前身是LINPACK（解线性方程）和EISPACK（解特征值问题）的FORTRAN子程序库。由于它把矩阵当成一个对象，因此编写程序更加直观、方便。1984年正式推出,最新版本为V7.0 Release14.MATLAB具有非常强大和直观的计算功能，并且由于其有非常好的扩展性能，现在已成为世界上应用最广泛的工程计算软件之一。
(1) 强大的数值运算功能
在MATLAB环境中，有超过500种数学、统计、科学及工程方面的函数可使用，函数的命名表示自然，使得问题和解答像数学公式一般简单明了，让用户可全力发挥在解题方面，而非浪费在电脑操作上。
(2) 数据分析和可视化功能、文字处理功能
MATLAB可以绘制二、三维图形，与Mathematic和Maple相比，它还能处理光照模型，制作出高品质的图形。功能十分强大。MATLAB Notebook为用户提供了强大的文字处理功能，并允许WORD访问MATLAB的数值计算和可视化结果，制作科学性或工程性图文并茂的文章.
(3) 高级、简单、高效的程序环境
做为一种解释型的程序语言，MATLAB允许使用者在短时间内写完程序,所花的时间约为用 FORTRAN或 C 的几分之一，而且不需要编译 (compile) 及连接(link) 即能执行，同时包含了更多及更容易使用的内建功能。
(4) 开放及可延伸的架构
MATLAB允许使用者接触它的大多数的数学源代码，检查运算法，更改现有函数，甚至加入自己的函数使 MATLAB成为使用者所需要的环境。
(5) 丰富的工具箱
MATLAB的工具箱融合了套装前软体的优点，与一个灵活的开放但容易操作之环境，这些工具箱提供了使用者在特别应用领域所需的许多函数。现有工具箱有：符号运算（利用Maple V的计算核心执行）、图像处理、统计分析、信号处理、通信、线性矩阵不等式、偏微分方程、高阶谱分析、财政金融、神经网络、模拟分析、控制系统、实时控制、小波分析、最优化、模糊逻辑、μ分析及合成等30多种。

第一章小结 绪 论

误差在数值计算中是不可避免的，误差的传播和积累直接影响到计算结果的精度。在研究算法的同时，必须注重误差分析，使建立起来的算法科学有效。绝大多数情况下不存在绝对的严格和精确，在考虑数值算法时要能将误差限制在许可的范围之内，这种算法就是数值稳定的。
本章介绍了计算方法和误差理论的基本概念，并且对误差的产生与防止进行了分析；同时介绍了绝对误差(限)、相对误差(限)、有效数字的概念和三者的联系及计算的方法；最后介绍了误差在近似值运算中的传播、估算方法和数值稳定性的概念以及减少运算误差的原则。
按照误差产生的来源可分为模型误差、观测误差、截断误差和舍入误差等。
误差的表示法有绝对误差和相对误差两种。
在表示一个近似数时，要用到有效数字的概念，这在数值计算中非常有用，有效数字是由绝对误差决定的。
通常用函数的泰勒展开对误差进行估计。