当前位置：文档之家 › 精品课件-计算方法(任传祥)-第1章

精品课件-计算方法(任传祥)-第1章

  • 格式：ppt
  • 大小：1.23 MB
  • 文档页数：58

下载文档原格式

  / 58

合集下载

计算方法第一章数值计算方法.ppt

计算方法第一章数值计算方法.ppt

x1
a22b1
a12b2 D
S4 输出计算的结果 x1, x2
x2
a11b2
a21b1 D
开始
输入
a11, a12 , a21, a22 ,b1,b2
D=a11a22-a12a21
Yes D=0
No
x1 (b1a22 b2a12 ) / D x2 (b2a11 b1a21) / D
输出无解信息
…
…
第一章计算方法与误差
本章内容
§1 引言 §2 误差的来源及分类 §3 误差的度量 §4 误差的传播 §5 减少运算误差的原则
小结
第一章计算方法与误差
要求掌握的内容
概念 包括有效数字、绝对误差、绝对误差限、 相对误差、相对误差限等
误差 截断误差、舍入误差的详细内容，误差种 类等
分析运算误差的方法和减少运算误差的若 干原则
常用的两种复杂性有：计算时间复杂性和空间复杂性。
二、算法的优劣
➢ 计算量小 例：用行列式解法求解线性方程组:
n阶方程组，要计算n + 1个n阶行列式的值，
总共需要做n! (n - 1) (n + 1) 次乘法运算。
n=20 需要运 算多少次？
n=100?
计算量大小是衡量算法优劣的一项重要标准。
在估计计算量时，我们将区分主次抓住计算过程中费时较多的 环节。比如，由于加减操作的机器时间比乘除少得多，对和式
例：求解二元一次联立方程组
aa1211xx11
a12 x2 a22 x2
b1 b2
用行列式解法：首先判别
D a11a22 a21a12
是否为零，存在两种可能：
（1）如果 D 0，则令计算机计算

第一章计算方法

第一章计算方法

令
D a11a22 a21a12
通过求解过程，可以总结出算法步骤如下：
S1 输入
a11, a12 , a21, a22 , b1, b2 S2 计算 D a11a22 a21a12
S3 如果
D0
则输出原方程无解或有无穷多组解的信息;
否则
D0
a22b1 a12b2 a11b2 a21b1 x1 x2 D D
(i) (ii)
高斯消 去法
48 17 2 7 只小兔 2
10只小鸡
x y 17 (II) (4 2) y 48 - 17 2
48 17 2 y 7 只小兔 42
例：求解二元一次联立方程组
a11 x1 a12 x 2 b1 a 21 x1 a 22 x 2 b2
sin( x ) sin x 2 cos x sin 2 2
2. 避免大数吃小数
例：用单精度计算 精确解为 的根。 x 2 (109 1) x 109 0
b b 2 4ac x 2a
x1 109 , x2 1
算法1：利用求根公式
例: 求
y x 1 x
的值。当x = 1000，y 的准确值为0.01580
（1）、直接相减
y 1001 1000 31 .64 31 .62 0.02
（2）、将该式改写为
y x 1 x 1 x 1 x
则
y = 0.01581
x 类似地 ln x ln y ln y
d 2s m 2 mg dt
其中 g 为重力加速度。
（1.1）
通过测量得到模型中参数的值 —— 观测误差

计算方法课件

计算方法课件

※ 特点：简单、直观，编程容易且收敛性总能得到保证。但收敛速度
较慢，且只能用于求实函数的实根，不能求偶数重根及复根。
§2.2
迭代法
思想：首先给出方程的根的一个粗糙的初始值，然后反复使用某一个 公式校正这个初始值，使之逐步精确化，直到满足预先给出的精度 要求为止。具体方法如下： （1） f ( x) 0 化为下列等价形式：
设其跟为 xk 1 , 即
f ( xk ) f ( xk )( xk 1 xk ) 0
则有
f ( xk ) xk 1 xk f ( xk )
(f ( xk ) 0)
牛顿迭代法的几何意义：
y
P （ 0 x0 ,f (x0 )）
P （ 1 x1,f ( x1 )）
y f ( x0 ) f ( x0 )( x x0 )
2.4
弦截法：
弦 截 法（割线法）
xk 1
几何意义：P23
f ( xk )( xk xk 1 ) xk , f ( xk ) f ( xk 1 )
(k 1,2, )
一般，弦截法的收敛速度（收敛的阶为1.618）比牛顿迭代法慢，但优点是无 需计算导数，每步只需计算一次函数值。
x g ( x)
（2） 构造迭代公式
x k 1 g ( x k ),
(k 0,1,2,)
在有根区间【a,b】上取一点 x 0 (初始近似根)作为方程的近似值，代 入上面公式右端，求得 x1 g ( x 0 ) ，在把 x 1 作为预测值，得到
x 2 g ( x1 ), 如此反复进行下去，得到一个近似根的序列
1. 要避免相近两数相减 2. 要防止“大数吃掉小数” 3. 避免用绝对值很小的数除数 4. 注意简化计算步骤，减少运算次数 5. 注意控制递推公式中误差的传播

计算方法讲义

计算方法讲义
4
1、计算效率——可计算性（计算复杂性——空间、时间） 例：解线性方程组 Ax = b 的 Grammar 方法： xi =
Ai A
，其中 A 是方程
组系数矩阵 A 对应的行列式，而 Ai 则是以右端向量 b 替代 A 的第 i 列所得矩阵 对应的行列式。由线性代数知识可知，若 A = (α ij ) ，则
5
~ ⎛ − 6.22 ⎞ 的解则变成： X = ⎜ 38.25 ⎟ ； ⎜ − 33.65 ⎟ ⎠ ⎝
扰动后的数据 ~ x ⇒ 计算结果 f ( ~ x) ， 若对问题 f 存在常数 m，满足关系式： f ( x) − f ( ~ x) x−~ x ≤m f ( x) x
x) f(x) - f(~ f(x) m = sup x−~ x x
A =
∑ (−1) J (i ,i
1 2
in )
α 1i1 α 2i2
α nin ，
i n }所需的置换次数。可见每
其中 J (i1 , ,
, n }变换到{ i1 , i 2 ,
计算一个行列式，需要 (n − 1) ⋅ n ! 个浮点运算；因此，按 Grammar 方法解方程组 约需 N = (n 2 − 1) ⋅ n ! 个浮点运算。当 n = 20 时
所计算的问题当原始数据发生小扰动时，问题的解一般也发生扰动。问题的 性态——问题的解对原始数据发生变化的敏感性。
⎧小扰动 — —问题是良态的 原始数据小扰动 ⇒ 问题解 ⎨ ⎩大变化 — —问题是病态的
例：线性方程组：
1 1 11 ⎧ ⎪ x1 + 2 x 2 + 3 x3 = 6 ⎛ 1⎞ ⎪ ⎜ ⎟ 1 1 13 ⎪1 的解是： X = ⎜1⎟ ⎨ x1 + x 2 + x3 = 3 4 12 ⎪2 ⎜ 1⎟ 1 1 1 ⎝ ⎠ ⎪ x + x + x = 47 1 2 3 ⎪ 4 5 60 ⎩3 若将方程组的系数改写成具有 2 位有效数字的小数：

计算方法第一章 讲义

计算方法第一章 讲义

L m U 。由于机器数的字长与阶码有限，因此，计算机中的数是有限的。事实上，计算
机中共有 2
t
U L 1 1 个机器数。把计算机中的全体机器数组成的集合记为 F 或
L 1
F(2,t,L,U),称为计算机机器系。显然，机器系数 F 是一个有限的、离散的、分布不均匀的集 合。不难验证，F 中任意非零数 x 满足 2
计算方法讲义 .1.
谢 进
数理系信息与计算科学教研室 2016 年 9 月
1
第1章
§1.1 计算方法及其相关概念
1.科学计算
绪论
随着人们的生产活动和计算需要， 数学中逐渐发展了一种新的分支一一计算数学。 随着 计算工具的应用，特别是计算机的出现和发展，计算数学（Computational Mathematics）逐 渐发展成为现代意义下的计算科学，或称科学计算(Scientific Computing)，成为了传统的理 论研究和科学实验之后的第三大科学科学方法。 现在， 科学计算在科学研究与工程实际中作 用越来越重要， 甚至用科学计算来取代部分实验和理论研究。 如通过科学让计算机模拟核爆 炸。 这种由科学实验向科学计算的转变， 也促使一些边缘学科的相继出现， 例如， 计算物理、 计算力学、计算化学、计算生物学以及计算经济学等等都应运而生。有些理论证明往往也是 通过科学计算去解决，例如，四色问题，吴文俊院士开创的机器证明等。也就是说，科学计 算可以全部或部分地代替理论证明。
m=-2
0.125 0.15625 0.171875 0.1875 0.203125 0.21875 0.234375
m=-1
0.25 0.3125 0.34375 0.375 0.40625 0.4375 0.46875

计算方法第一章 绪论

计算方法第一章 绪论

知称道，实为Er际近(x)计似算值时x的通相常对取误差，由于精确值 一般x不*
x* x
Er (x)
作为近似值x的相对误差。
x
若能求出一个正数 ，使r 得
E，r (x则) 称r 为近似r
值x的相对误差限。它是无量纲的数，通常用百分
比表示。
2021/6/26
整理课件
15
例：甲用米尺测量10M长的物体，所产生的绝对 误差为2cm，乙用同一米尺测量1M长的物体，所产 生的绝对误差为1cm，他们谁的测量精度好？
用计算机解决科学计算问题的一般过程，可以概括为：
实际问题→数学模型→计算方法→ 程序设计→上机计算→结果分析
整理课件
由实际问题应用有关科学知识和数学理论建立
数学模型这一过程，通常作为应用数学的任务。 而根据数学模型提出求解的计算方法直到编出程 序上机算出结果，进而对计算结果进行分析，这 一过程则是计算数学的任务，也是数值计算方法 的研究对象。
第二，有可靠的理论分析，能任意逼近并达到精度要 求，对近似算法要保证方法的收敛性和数值稳定性，还要对 误差进行分析，这些都建立在相应数学理论基础上。
第三，要有好的计算复杂性（即时间复杂性和空间复杂 性）；时间复杂性好是指节省时间，空间复杂性好是指节省 存储量，这也是建立算法要研究的问题，它关系到算法能否 在计算机上实现。
x x * 0.04 0.05 1 101 2
x 又 （0.3289） 1,故02该不等式又可写为
x x * 1 10 23 2
x 故 有3位有效数字，分别是 3,2，8。 x x 由于 中的数字9不是有效数字,故 不是有效数。
思考： 3.1415有几位有效数字？
2021/6/26

计算方法 课件第一章


舍入误差
计算机实现计算时，机器的有限字长所造成
1.2.2 误差与有效数字
x 定义1 设 x 是某量的准确值，* 是 x 的一个 近似值，则称 e* = x* − x为近似值的误差或绝 对误差。 * 的绝对值的上界，即满足 x* − x ≤ ε * 的 ε *， e 称为近似值 x* 的误差限。 误差与精确值的比值称为相对误差。即 * er = ( x* − x) / x ，如果 ( x* − x) / x ≤ ε r*，则 ε r 称 为相对误差限。 实际使用中以 er* = ( x* − x) / x*为相对误差。
*
ε r (s ) ≈
ε (s )
*
s
*
27 = * * ≈ = 0.31% ld 8800
ε (s )
*
1.3 误差定性分析与避免误差危害
前面讨论的误差限的方法是最坏情况 对于千万次的运算可用概率统计的方法 20世纪60年代后提出
向后误差分析法 区间分析法
目前尚无有效方法对误差做出定量分析 本节讨论：
数值分析
Numerical Analysis
主讲教师： 主讲教师： 郭策安
Instructor: GUO CEAN E-mail: guocean@
教材
(Text Book)
TUP & Springer Press
李庆扬、王能超、 李庆扬、王能超、易大义 编
数值分析
参考书目 (Reference)
In = e (x e
I0 = e
−1
−1
n x 1 0
− n ∫ x n −1e x dx) = 1 − nI n −1 (n = 1, 2,L)0来自1∫1
0

计算方法优质获奖课件


f [x0, x1, x2 ]( x x0 )( x x1)
2 1 (x 1) 1 (x 1)(x 1)
2
6
这种差商形式旳插值公式称为牛顿插值公式。
Newton插值
轻易证明牛顿插值多项式满足插值条件。
由插值多项式旳唯一性，得 Ln (x) Nn (x)
牛顿插值多项式旳误差估计
Rn (x) f [x0 , x1,
, xn , x]n (x)
f (n1) ( )
(n 1)!
n
(
x)
Newton插值(续)
❖ (3)曲线拟正当，即选择合适旳曲线直接拟合洛伦 兹曲线，常用旳曲线有二次曲线、指数曲线和幂函数 曲线。
❖ 利用第一种措施不能得到洛伦兹曲线旳体现 式，只能用来计算基尼系数，但因为在计算分块 面积时用直线近似地替代曲线，所估计旳基尼系 数要不大于实际值，尤其在数据点较少时，误差 较大。第二种措施因为计算收入分配旳概率密度 旳复杂性,极难提出合适旳概率函数。至于第三种 措施，即直接用曲线方程去拟合洛伦兹曲线，应 该不失为一种很好旳措施，但目前主要旳问题在 于既有常用旳曲线并不合用，曲线含义不明确， 或拟合误差较大。
称
f [ x0 , x1 , xn ]
f [ x0 , x1 ,, xn1 ] f [ x1 , x2 , xn ] x0 xn
为f (x)在点
处旳n阶差商。
差商表
x
f(x) 一阶差商 二阶差商 三阶差商
X0 f(x0) X1 f(x1) f(x0,x1) X2 f(x2) f(x1,x2) f(x0,x1,x2) x3 f(x3) f(x2,x3) f(x1,x2,x3) f(x0,x1,x2,x3)
例题分析（续1）

计算方法-第1章


13
一．自然语言法
1. 输入数据a, b, c 2.如果a=0, 转3，否则转4
c 3.如果 b 0，则 x1 ，转7；否则，无解停机 b 2 ， b 4 ac 4. 设 D SD SQRT (| D |)
0 ,x ( b iSD ) / 2 a , 如果 D 1 x ( b iSD ) / 2 a ，转7 2 否则 ， 5. 如果b>0不成立， S 1 b SD ，转7 x S 1 / 2 a , x 2 c / S 1 1 2 S 2 / 2 a , x 2 c / S 2 2 b SD 6. S ，x 1 2 7. 输出x1和x2
x1， x2，……， x100 取为
数值方法
0.1, 0.2, 0.3, ……,10=a
2-1
★ 计算公式不一定都是数值方法。如求
类似地， 求根公式
2 b b 4 ac x 1 ,2 2 a
3 。
不能在计算机 上直接运行
◆ 研究数值方法的任务有三条：
1）将计算机不能直接计算的运算化成计算机上可执行的 运算；利用等价或近似等价的方法转化； 7
1） 数学的发展极大地促进了计算机科学的发展：
★ Leibniz发现二进制编码； ★ Von Neumann提出现代计算机建构理论； ★ Bohm和Jacopini为结构化程序设计奠定了基础。
2）计算机科学为数学提供先进手段，并对数学 发展产生了重大影响。
★ 为利用数学解决实际问题提供了工具； ★ 解决了一些数学难题，并提出了新的研究课题；
x 2 ( b iS D ) / 2 a
输 出 x1, x 2
15
▲ 结构化框图法：N-S图示法

第1章 计算方法


定义1 设 x 为准确值， x * 为 x 的一个近似值，称
e* x * x
为近似值的绝对误差， 简称误差. 通常准确值 若 则
x 是未知的，因此误差 e * 也是未知的.
e* x*x *
*
叫做近似值x*的误差限， 它总是正数.
13
对于一般情形
x * x * ，即
* ( xk xk )

k 1
f x k
* ek ,
26
*
于是误差限
( A *)

n
k 1
f x k
* ( x k );
*
（2.3）
而
A*
的相对误差限为
* r

r ( A *)
( A *)
2
相对误差限
r ( s *) ( s *)
s*

( s *)
l*d *

27 8800
0 . 31 %.
29
1.3
误差定性分析与避免误差危害
30
1.3
一、
定义3
误差定性分析与避免误差危害
算法的数值稳定性
一个算法如果输入数据有误差，而在计算过
程中舍入误差不增长，则称此算法是数值稳定的，否则称 此算法为不稳定的.
A*


n
k 1
f x k

*
( xk )
*
.
（2.4）
A*
27
例2 为
已测得某场地长 ， 已知
l
的值为
l * 110 m ，宽 d
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
则-18.75的浮点数表示如图1.5所示。
图1.5 例1－2用图
第1章 绪 论 1.3 数值计算的误差
1.3.1 误差的来源 基于计算方法应用计算机求解实际问题的过程，不可避免
会引入误差，根据误差的来源不同，误差通常分为以下四种类 型：
(1)模型误差。 用数学方法解决一个具体的实际问题， 首先要建立数学模型，这就要对实际问题进行抽象、简化或假 设，因此建立的数学模型与实际客观问题之间就存在着一定的 差距，即误差，这种误差称做模型误差。
第1章 绪 论
计算机解决实际问题的过程包括实际问题、数学模型、计 算方法、方法的程序设计、计算机求解等步骤。其中实际问题 包括各个领域的许多问题，而这些实际问题的计算机求解，目 前虽有一些计算软件可以直接使用，如Matlab、Mathematica 等，但需要了解算法设计的原理，以便更好地应用；同时，随 着实际问题越来越复杂，规模越来越庞大，现成的数值方法软 件难以满足实际需要，如天气预报、计算化学、Web搜索、结 构设计等，这也要求学习计算方法，以便寻求新的解决问题的 方法。
第1章 绪 论
例如，计算sinx的值时，应用其泰勒展开式有
sin x x x3 x5 x7 3! 5! 7!
如果取该式的前两项计算sinx的值，即 sin x x x3 , 3!
则 x5 x7 为计算sinx的截断误差。 5! 7!
第1章 绪 论
(4)舍入误差。由于计算机的字长有限，参加运算的数据 在计算机中只能表示为数据真实值的近似值，由此产生了误差， 而且用计算机进行实际计算时每一步都可能产生该类误差，这 种误差称为舍入误差。
第1章 绪 论
数学是研究数量、结构、变化以及空间模型等概念的一门 学科。随着社会的发展和科学的进步，数学开始被应用于力学 领域，后来被应用于越来越广的范围，覆盖了物理、工程、化 学、天文、地理、生物、医学，甚至经济、语言等领域，这促 进了包括可应用的数学及数学的应用两个部分的应用数学的产 生和迅速发展，使其成为数学的一个分支。应用数学研究如何 将数学知识应用到其他的范畴，它包含许多分支，其中数值计 算方法是其重要的分支之一。
通常，用一位二进制数Pf表示阶码的符号位。当Pf=0时， 表示阶码为正；当Pf=1时，表示阶码为负。
同样，用一位二进制数Sf表示尾数的符号位。当Sf=0时， 表示尾数为正；当Sf=1时，表示尾数为负。
第1章 绪 论 例1－2 用浮点数表示-18.75，并假定尾数用8位二进制
表示，阶码用4位二进制表示，均含符号位。 解 因为(-18.75)10=(-10010.11)2=(-0.1001011)×2+101
例如，设计算机的字长为最多能够处理10位十进制数，则 1÷3=0.3333333333，而其真实值应为1÷3=0.33333333333…， 由此产生的误差就是舍入误差。
e* x x* 第1章 绪 论
1.3.2 绝对误差 定义1.1 设x为准确值，x*为x的一个近似值，称x－x*
为近似值x*的绝对误差，简称误差，记做e*，即
第1章 绪 论 第1章 绪 论
1.1 引言 1.2 计算机中数的表示 1.3 数值计算的误差 1.4 函数求值的误差 1.5 数值计算中要注意的若干原则
第1章 绪 论
1.1 引 言
数学是研究数量、结构、变化以及空间模型等概念的一门 学科。随着社会的发展和科学的进步，数学开始被应用于力学 领域，后来被应用于越来越广的范围，覆盖了物理、工程、化 学、天文、地理、生物、医学，甚至经济、 语言等领域，这促进了包括可应用的数学及数学的应用两个部 分的应用数学的产生和迅速发展，使其成为数学的一个分支。 应用数学研究如何将数学知识应用到其他的范畴，它包含许多 分支，其中数值计算方法是其重要的分支之一。
相比定点表示，浮点表示在位数有限的前提下可以扩 大数的表示范围，同时又可保持数的有效精度。
浮点数在机器中的一般表示形式如图1.4所示。
图1.4 浮பைடு நூலகம்数的表示形式
第1章 绪 论
其中P表示阶码，而阶符表示阶码的符号；S表示尾数，尾符表 示尾数的符号。也就是说，计算机中一个浮点数由阶码和尾数 组成，而阶码和尾数都有自己的符号。
第1章 绪 论 (2)观测误差。 在数学模型中通常包含一些需要通过观
测得到的物理量，如温度、长度、电压等，这些量的观测值与 其实际值之间的误差，称做观测误差。
(3)截断误差。当数学模型不能得到精确解时，通常用数 值方法求它的近似解，则所求得的近似解与准确解之间的误差 称为截断误差，也称为方法误差。
定点纯小数是把小数点固定在数的符号位之后、最高数值 位之前，小数点位置隐含，本身不占位，其格式如图1.1所示。
图1.1 定点纯小数的格式
第1章 绪 论 定点纯整数是把小数点固定在数值的最低位之后，最
高位为符号位，小数点位置隐含，本身不占位，其格式如图 1.2所示。
图1.2 定点纯整数的格式
第1章 绪 论
例1－1 如图1.3所示的两个8位二进制数,求对应的 十进制数。
解 图1.3(a)所示为定点纯整数表示方法，故可得N1=+84， N2=-84。
图1.3(b)所示为定点纯小数表示方法,故可得N1=+0.65625， N2=-0.65625。
第1章 绪 论 图1.3 例1－1用图
第1章 绪 论 1.2.2 浮点表示
本书从工程实际问题出发，研究以下数学问题:非线性方 程的求解、线性方程组的求解、函数的插值与逼近、数值积分 与微分、微分方程的数值求解、矩阵的特征值与特征向量的计 算。
第1章 绪 论 1.2 计算机中数的表示
在数值计算中无处不涉及小数的运算，了解小数在计算机 中的表示和运算是学习数值计算方法的基础。计算机中的数都
dn 2n dn12n1 d121 d0 20
而对于小于1的正数，其形式为
d1 21 d2 22 d3 23
其中，di表示二进制数字，取值为0或1。
第1章 绪 论 1.2.1 定点表示
定点表示就是小数点的位置在数中固定不变。计算机中有 两种定点数最常用:一种是定点纯小数，另一种是定点纯整数。